<br><br><div class="gmail_quote">On Thu, Dec 2, 2010 at 10:54 AM, Daniel Kastl <span dir="ltr"><<a href="mailto:daniel@georepublic.de">daniel@georepublic.de</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;">
Let me make some proposal how the APSP function could look like.<div>(I mostly copy from Dijkstra: <a href="http://www.pgrouting.org/docs/1.x/dijkstra.html" target="_blank">http://www.pgrouting.org/docs/1.x/dijkstra.html</a>)</div>
<div>
<br></div><div><span style="font-family: 'Lucida Grande','Lucida Sans Unicode',Geneva,Verdana,sans-serif; font-size: 14px; line-height: 21px;"><pre style="overflow: auto; font-family: Consolas,'Deja Vu Sans Mono','Bitstream Vera Sans Mono',monospace; font-size: 0.8em; letter-spacing: 0.015em; line-height: 13px; padding: 0.5em; border: 1px solid rgb(204, 204, 204); background-color: rgb(248, 248, 248);">
<span style="color: rgb(0, 112, 32); font-weight: bold;">CREATE</span> <span style="color: rgb(0, 112, 32); font-weight: bold;">OR</span> <span style="color: rgb(0, 112, 32); font-weight: bold;">REPLACE</span> <span style="color: rgb(0, 112, 32); font-weight: bold;">FUNCTION</span> <span>apsp</span><span>(</span>
<span><b>sql</b></span> <span style="color: rgb(0, 112, 32);">text</span><span>,</span>
<b>n_<span><b>ids</b></span></b> <span style="color: rgb(0, 112, 32);">text</span>,
<b>m_ids</b> text,<br> <span>directed</span> <span style="color: rgb(0, 112, 32);">boolean</span><span>,</span>
<span>has_reverse_cost</span> <span style="color: rgb(0, 112, 32);">boolean</span><span>)</span>
<span style="color: rgb(0, 112, 32); font-weight: bold;">RETURNS</span> <span style="color: rgb(0, 112, 32); font-weight: bold;">SETOF</span> <span><???></span></pre></span><div>
With <b>sql</b> as ...</div><div><span style="font-family: 'Lucida Grande','Lucida Sans Unicode',Geneva,Verdana,sans-serif; font-size: 14px; line-height: 21px;"><pre style="overflow: auto; font-family: Consolas,'Deja Vu Sans Mono','Bitstream Vera Sans Mono',monospace; font-size: 0.8em; letter-spacing: 0.015em; line-height: 13px; padding: 0.5em; border: 1px solid rgb(204, 204, 204); background-color: rgb(248, 248, 248);">
<span style="color: rgb(0, 112, 32); font-weight: bold;">SELECT</span> <span>id</span><span>,</span> <span style="color: rgb(0, 112, 32); font-weight: bold;">source</span><span>,</span> <span>target</span><span>,</span> <span>cost</span> <span style="color: rgb(0, 112, 32); font-weight: bold;">FROM</span> <span>edge_table</span></pre>
</span></div><div>... like for Dijkstra, and <b>n_ids/m_ids</b> as ...</div><div><span style="font-family: 'Lucida Grande','Lucida Sans Unicode',Geneva,Verdana,sans-serif; font-size: 14px; line-height: 21px;"><pre style="overflow: auto; font-family: Consolas,'Deja Vu Sans Mono','Bitstream Vera Sans Mono',monospace; font-size: 0.8em; letter-spacing: 0.015em; line-height: 13px; padding: 0.5em; border: 1px solid rgb(204, 204, 204); background-color: rgb(248, 248, 248);">
<span style="color: rgb(0, 112, 32); font-weight: bold;">SELECT</span> <span>id</span> <span style="color: rgb(0, 112, 32); font-weight: bold;">FROM</span> <span>edge_table</span></pre>
</span></div><div>to select the relevant points for the n-m distance matrix.</div><div><br></div><div>With a select (instead of a list of ID's you can also select relevant points by attribute, update timestamp or whatever.</div>
<div><br></div><div><div>I can also think of an APSP that calculates all distances from 1 point to n points only. That's why I added n_ids/m_ids.</div>
<div>In that case you could update an existing distance matrix (that you stored in some table for example) if only one or a few points changed.</div></div><div><br></div></div></blockquote><div><br>Hey.. The dijextras algo should be able to provide solution for single source shortest paths to all other points (1 to n points). The boost doc here: <a href="http://www.cs.brown.edu/~jwicks/boost/libs/graph/doc/dijkstra_shortest_paths.html">http://www.cs.brown.edu/~jwicks/boost/libs/graph/doc/dijkstra_shortest_paths.html</a> states that: "If you provide a
distance property map through the <tt>distance_map()</tt> parameter
then the shortest distance from the source vertex to every other
vertex in the graph will be recorded in the distance map. Also you can
record the shortest paths tree in a predecessor map: for each vertex
<i>u in V</i>, <i>p[u]</i> will be the predecessor of <i>u</i> in
the shortest paths tree "<br><br>So, I think there is no need for doing APSP / Warshall O(n^3) time for this purpose, Dijextra will do that in O(m+nlog n). I am not fully aware of the pgRouting dijextra implementation, does it provide above functionality?<br>
<br><br><b>One more thing:</b> Can we have a wiki page or something like that where we can put up our ideas, and we can keep on modifying the draft as the ideas are refined? I guess there are too many ideas in this thread and I am finding some difficulty to keep track of all of them all.. Just a suggestion :)<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;"><div><div class="gmail_quote"><div><div class="h5"><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div class="gmail_quote"><br><div>I think the library should ensure that when you make a query it reads the network data available at that time. If the query for processing a huge distance matrix takes one hour for example, but makes steadily new requests to the database, it could happen that some attributes change over time.</div>
<div>Whether this is problematic for an application or not depends on the application. In most cases it probably isn't, that's true. But pgRouting isn't limited to road networks, so who knows what kind of applications will make use of it.</div>
<div>
<div><br></div><div> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
* It might be slower to later run single shortest path queries again<br>
independently<br>
</blockquote>
<br>
It would be interesting to enhance our single shortest path to be able to extract multiple single shortest paths based on a single graph build. So input might be something like<br></blockquote><div><br></div></div><div>This would be the same as k-Shortest Path, right?</div>
<div><a href="http://www.pgrouting.org/rfc/rfc-04.html" target="_blank">http://www.pgrouting.org/rfc/rfc-04.html</a></div><div><a href="http://www.pgrouting.org/rfc/rfc-04.html" target="_blank"></a> </div>
<div><br></div><div>Daniel </div><div><br></div><div><br></div><div><br></div></div>-- <br><span style="font-family: arial,sans-serif; font-size: 13px; border-collapse: collapse;"><div>Georepublic UG & Georepublic Japan<br>
eMail: <a href="mailto:daniel.kastl@georepublic.de" style="color: rgb(66, 99, 171);" target="_blank">daniel.kastl@georepublic.de</a><br></div>
Web: <a href="http://georepublic.de/" style="color: rgb(66, 99, 171);" target="_blank">http://georepublic.de</a></span><br>
</blockquote></div></div></div><div><div></div><div class="h5"><br><br clear="all"><br>-- <br><span style="font-family: arial,sans-serif; font-size: 13px; border-collapse: collapse;">Georepublic UG & Georepublic Japan<br>
eMail: <a href="mailto:daniel.kastl@georepublic.de" style="color: rgb(66, 99, 171);" target="_blank">daniel.kastl@georepublic.de</a><br>
Web: <a href="http://georepublic.de/" style="color: rgb(66, 99, 171);" target="_blank">http://georepublic.de</a></span><br>
</div></div></div>
<br>_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org">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>
<br></blockquote></div><br><br clear="all"><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>