Hi Stephen,<br><br>Thanks for the quick input. Some queries in-line.Greeting Jay,<br><br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br>
It looks like Johnsons algorithm might be a little faster on sparse graphs, but I'm not sure if you can extract the path between the pairs if you need that and I think that would be a valuable component to the algorithm, so the Warshall Algorithm might be better if we support that extraction capability.<br>
<br>
I'm not sure how these algorithms work from the point of view that you have to extract ALL pairs from the graph, or whether you can just extract selected pairs at a reduced cost. The use case for this would be that you have 20 locations that you are interested in and you want the APSP between those 20 locations and not the whole graph.<br>
<br></blockquote><div><br>Notations that I have used:<br>m - edges.<br>n - vertices.<br>v - vertices in subset.<br><br>
Our postgres map data constitutes a planar graph right? If so, then the
number of edges m = O(n). In that case,
the dijextra Shortest path algorithm will take O(m + n log n) that is
O(n logn) time. <br>
<br>
Now, if we want to find APSP between small subset of vertices v, we can call dijextra v^2 times to get total complexity O(v^2* n log n). We will have a good bound until (v^2 log n) < n^2. I guess this will also return the paths between vertices.<br>
<br>When (v^2 log n) > n^2 we can use Warshall algo. Extracting paths will be complicated task.<br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
I think some thought needs to go into:<br>
<br>
1. what are the results? just a V^2 table of costs?<br>
<br>
2. can we extract the paths? In pgRouting, this has some additional implications beyond is it physically possible to extract paths from the algorithm.<br>
a. typically queries do not store results, they only return sets<br>
b. extracting paths, implies computing assembling a graph, computing the results and holding the results for additional queries against them to extract paths.<br>
c. while this is potentially possible using temp tables, we do not currently do that<br>
<br></blockquote><div><br>I did not properly understand point b above.<br><br>I am not sure if the
boost implementation of Warshall returns a path matrix,
<a href="http://www.boost.org/doc/libs/1_45_0/libs/graph/doc/floyd_warshall_shortest.html">http://www.boost.org/doc/libs/1_45_0/libs/graph/doc/floyd_warshall_shortest.html</a>
says that it will just return the distance matrix.<br>
<br>
In theory, we can simultaneously create a n^2 path matrix along with the distance matrix and use that to extract paths. Pseudo code is present here: <a href="http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm">http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm</a>. So, if we want to build the path matrix, we need to code Warshall from scratch, using maybe boost data structures. <br>
<br>If we have vertex ids of whole graph, the path matrix is sufficient to extract all paths (extracting one path will take O(n) time), and I think there is no need for additional queries to database. <br><br>Please correct me if I am missing something. <br>
<br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Anyway, these are some things to start a discussion and provoke some thoughts. I do not want to grow the scope of this project to the point that it is problematic, so we should focus on what can be done and plan for future additions if they are needed.<br>
<br>
I look forward to working with you. Thank you for your interest in pgRouting.<br>
<br>
Best regards,<br>
-Steve W<br>_______________________________________________<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/mailman/listinfo/pgrouting-dev</a><br>
</blockquote></div><br><br clear="all"><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>