Hi Kishore,<br><br>I read your report and saw the APSP_Johnson implementation. The prototype is:<br><pre><div style="background-color: transparent;" class="line" id="LC60"><span class="k">CREATE</span> <span class="k">OR</span> <span class="k">REPLACE</span> <span class="k">FUNCTION</span> <span class="n">apsp_johnson</span><span class="p">(</span><span class="k">sql</span> <span class="nb">text</span><span class="p">)</span></div>
<div style="background-color: transparent;" class="line" id="LC61"> <span class="k">RETURNS</span> <span class="k">SETOF</span> <span class="n">apsp_edge</span></div><div style="background-color: transparent;" class="line" id="LC62">
<span class="k">AS</span> <span class="s1">'$libdir/librouting'</span></div><div style="background-color: transparent;" class="line" id="LC63"> <span class="k">LANGUAGE</span> <span class="s1">'C'</span> <span class="k">IMMUTABLE</span> <span class="k">STRICT</span><span class="p">;</span></div>
</pre><br>I guess this serves the same function as the apsp algorithm we already have[1]. <br><br>I think for your application, you need APSP for all vertices in the database table. So, if you use: <br><pre><span class="k">SELECT</span> <span class="o">*</span> <span class="k">from</span> <span class="n">all_pairs_shortest_path</span><br>
<span class="p">(</span><span class="s1">'SELECT gid as id,source::integer,target::integer,length::double precision as cost </span><br><span class="s1"> from ways where source in (select distinct(source) from ways)'</span><span class="p">::</span><span class="nb">TEXT</span><br>
<span class="p">,</span><span class="k">false</span><span class="p">,</span><span class="k">false</span><span class="p">);</span><br><br></pre>
<br>it will solve your query. Please correct me if I am wrong, or any additional information is needed.<br><br>Also, Daniel, Steve - <br><br>Should we change my apsp implementation so that it gives option to use either johnsons boost implementation or warshall boost implementation? That would provide more options? <br>
<pre><span class="k"></span>[1] <a href="https://github.com/pgRouting/pgrouting/wiki/APSP">https://github.com/pgRouting/pgrouting/wiki/APSP</a><br></pre><div class="gmail_quote">On Wed, Aug 10, 2011 at 6:10 PM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">Hi Kishore,<br>
<br>
Very nice diagram! This really helps me understand more of what you have been doing in this project and how the scheduled routing works.<br>
<br>
Thanks,<br>
-Steve<div><div></div><div class="h5"><br>
<br>
On 8/10/2011 8:27 AM, Kishore Kumar wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Hi,<br>
Prepared this diagram(attached) depicting the file structure and flow<br>
of control of scheduled routing algorithm. Currently the code works<br>
for GTFS Trips with fixed timetable(Eg:Train). To make it multi-modal,<br>
it has to support GTFS Trips with only frequency information(Eg:Bus)<br>
and private transit(Eg:Walk, Cycle). The existing scheduled routing<br>
can be extended a little by also including trips which have frequency<br>
information only. And, for walking to be private transit options,<br>
since the speed of transit is going to be a constant, the straight<br>
line distance from X to goal divided by constant velocity will give<br>
the shortest time heuristic. Hence, I'll possibly finish it in a day<br>
or two.<br>
<br>
Once that is finished, I'll start writing documentation, tests and<br>
demo implementations at <a href="http://busroutemaps.in/" target="_blank">http://busroutemaps.in/</a> and of course, Code<br>
cleanup and optimisations.<br>
<br>
Thanks,<br>
J Kishore kumar.<br>
<br>
On Sat, Jul 9, 2011 at 8:47 PM, Kishore Kumar<<a href="mailto:justjkk@gmail.com" target="_blank">justjkk@gmail.com</a>> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Hi,<br>
<br>
I commited the code[1] that implements the scheduled route using<br>
modified boost astar search and Implicit graph. And, I have an issue<br>
now:<br>
1. The modified astar and breadth first search boost header files are<br>
copied from Boost Version 1.46.1. I intent to test it on earlier boost<br>
libraries. But, what is the best approach to handle this scenario?<br>
Should we notify boost developers about having a non-const version to<br>
support Implicit Graphs?<br>
<br>
Thanks,<br>
J Kishore kumar.<br>
<br>
[1] - <a href="https://github.com/pgRouting/pgrouting/commit/3aa2b4e951c584fa3ae03235f7b2e06379cbb229" target="_blank">https://github.com/pgRouting/<u></u>pgrouting/commit/<u></u>3aa2b4e951c584fa3ae03235f7b2e0<u></u>6379cbb229</a><br>
<br>
On Tue, Jun 28, 2011 at 3:36 AM, Stephen Woodbridge<br>
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Hi Kishore,<br>
<br>
I not sure I can improve on this algorithm as I'm do not think I have<br>
followed all the details and issues in implementing it. But I do have two<br>
thoughts:<br>
<br>
1. if you are not on the boost-users mailing list [1] them you should<br>
subscribe to that list and ask questions about how to best tackle some of<br>
the boost problems you are facing. In the Subject: add the tag "[BGL]" to<br>
indicate this is a Boost Graph Library question and the developers are very<br>
helpful and responsive to question.<br>
<br>
2. often I find that it is useful to transform my problem into another<br>
problem that has a simpler or known solution. It seems like you should be<br>
able to do this with your problem. If I understand it correct (and I confess<br>
I might not), It seems that your frequency problem could be transformed into<br>
a straight scheduling problem if your transfer is just a waiting time at a<br>
transfer point. One simple way to represent these transfer times is to add<br>
an additional edge that has the cost of the transfer associated to it.<br>
<br>
So if we think about the route like, I start at a bus station at some time<br>
X, and there is some transfer cost representing the wait time W window. so<br>
I'm now on the the bus route at X+W+edge cost, and I continue accumulating<br>
wait times and edge costs as I trasfer between lines and travel the network<br>
to my destination. If this works, then this is just a straight time<br>
dependent solution but the trick is to analyze the data and create a network<br>
suitable for this type of solution.<br>
<br>
[1] <a href="http://lists.boost.org/mailman/listinfo.cgi/boost-users" target="_blank">http://lists.boost.org/<u></u>mailman/listinfo.cgi/boost-<u></u>users</a><br>
<br>
-Steve<br>
<br>
<br>
On 6/27/2011 5:40 PM, Kishore Kumar wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br>
Hi,<br>
<br>
After reading on Contraction Hierarchies[1] and APSP algorithms, I<br>
came up with a plan to find the scheduled route. Here goes the plan:<br>
<br>
* Pre-compute Shortest Time Graph for Directly reachable pair of stops<br>
by going through every trip in a loop.<br>
* Find Shortest Time Graph from every stop to every other<br>
stop(Transitive closure) using APSP.<br>
* Use Boost astar_search_no_init[2] function passing an Implicit<br>
Graph[3] G with following definitions:<br>
Vertex : (Stop, Time)<br>
Edge : Trip<br>
Edge weight : Travel Time + Waiting Time<br>
Heuristic : Shortest Time from Trip destination to Target<br>
* As Every Vertex is expanded, new Vertices and Edges are generated<br>
for trips in the next 1 hour(or whatever is the Upper limit for<br>
Waiting time).<br>
<br>
I didn't find any examples using astar_search_no_init function. [4]<br>
solves 8-puzzle problem using Implicit Graph for astar_search<br>
function, but it uses astar_search function with a hacked BFS code.<br>
So, it is going to be a challenge to code this out using BGL.<br>
<br>
Please advise on ways to improve the algorithm.<br>
<br>
Thanks,<br>
J Kishore kumar.<br>
<br>
[1] - <a href="http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf" target="_blank">http://algo2.iti.kit.edu/<u></u>documents/routeplanning/<u></u>geisberger_dipl.pdf</a><br>
[2] -<br>
<a href="http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/astar_search.html" target="_blank">http://www.boost.org/doc/libs/<u></u>1_40_0/libs/graph/doc/astar_<u></u>search.html</a><br>
[3] - <a href="http://en.wikipedia.org/wiki/Implicit_graph" target="_blank">http://en.wikipedia.org/wiki/<u></u>Implicit_graph</a><br>
[4] - <a href="http://www.cs.rpi.edu/%7Ebeevek/research/astar_bgl04.pdf" target="_blank">http://www.cs.rpi.edu/~beevek/<u></u>research/astar_bgl04.pdf</a><br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</blockquote>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
<br>
</blockquote>
<br>
<br>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</blockquote></blockquote>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>