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">http://www.pgrouting.org/docs/1.x/dijkstra.html</a>)</div><meta http-equiv="content-type" content="text/html; charset=utf-8"><div>
<br></div><div><meta http-equiv="content-type" content="text/html; charset=utf-8"><span class="Apple-style-span" style="font-family: 'Lucida Grande', 'Lucida Sans Unicode', Geneva, Verdana, sans-serif; font-size: 14px; line-height: 21px; "><pre style="overflow-x: auto; overflow-y: 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-top: 0.5em; padding-right: 0.5em; padding-bottom: 0.5em; padding-left: 0.5em; border-top-width: 1px; border-right-width: 1px; border-bottom-width: 1px; border-left-width: 1px; border-top-style: solid; border-right-style: solid; border-bottom-style: solid; border-left-style: solid; border-top-color: rgb(204, 204, 204); border-right-color: rgb(204, 204, 204); border-bottom-color: rgb(204, 204, 204); border-left-color: rgb(204, 204, 204); background-color: rgb(248, 248, 248); ">
<span class="k" style="color: rgb(0, 112, 32); font-weight: bold; ">CREATE</span> <span class="k" style="color: rgb(0, 112, 32); font-weight: bold; ">OR</span> <span class="k" style="color: rgb(0, 112, 32); font-weight: bold; ">REPLACE</span> <span class="k" style="color: rgb(0, 112, 32); font-weight: bold; ">FUNCTION</span> <span class="n">apsp</span><span class="p">(</span>
<span class="k"><b>sql</b></span> <span class="nb" style="color: rgb(0, 112, 32); ">text</span><span class="p">,</span>
<b>n_<span class="n"><b>ids</b></span></b> <span class="Apple-style-span" style="color: rgb(0, 112, 32); ">text</span>,
<b>m_ids</b> text,<br> <span class="n">directed</span> <span class="nb" style="color: rgb(0, 112, 32); ">boolean</span><span class="p">,</span>
<span class="n">has_reverse_cost</span> <span class="nb" style="color: rgb(0, 112, 32); ">boolean</span><span class="p">)</span>
<span class="k" style="color: rgb(0, 112, 32); font-weight: bold; ">RETURNS</span> <span class="k" style="color: rgb(0, 112, 32); font-weight: bold; ">SETOF</span> <span class="n"><???></span></pre></span><div>
With <b>sql</b> as ...</div><div><meta http-equiv="content-type" content="text/html; charset=utf-8"><span class="Apple-style-span" style="font-family: 'Lucida Grande', 'Lucida Sans Unicode', Geneva, Verdana, sans-serif; font-size: 14px; line-height: 21px; "><pre style="overflow-x: auto; overflow-y: 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-top: 0.5em; padding-right: 0.5em; padding-bottom: 0.5em; padding-left: 0.5em; border-top-width: 1px; border-right-width: 1px; border-bottom-width: 1px; border-left-width: 1px; border-top-style: solid; border-right-style: solid; border-bottom-style: solid; border-left-style: solid; border-top-color: rgb(204, 204, 204); border-right-color: rgb(204, 204, 204); border-bottom-color: rgb(204, 204, 204); border-left-color: rgb(204, 204, 204); background-color: rgb(248, 248, 248); ">
<span class="k" style="color: rgb(0, 112, 32); font-weight: bold; ">SELECT</span> <span class="n">id</span><span class="p">,</span> <span class="k" style="color: rgb(0, 112, 32); font-weight: bold; ">source</span><span class="p">,</span> <span class="n">target</span><span class="p">,</span> <span class="n">cost</span> <span class="k" style="color: rgb(0, 112, 32); font-weight: bold; ">FROM</span> <span class="n">edge_table</span></pre>
</span></div><div><meta http-equiv="content-type" content="text/html; charset=utf-8">... like for Dijkstra, and <b>n_ids/m_ids</b> as ...</div><div><meta http-equiv="content-type" content="text/html; charset=utf-8"><span class="Apple-style-span" style="font-family: 'Lucida Grande', 'Lucida Sans Unicode', Geneva, Verdana, sans-serif; font-size: 14px; line-height: 21px; "><pre style="overflow-x: auto; overflow-y: 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-top: 0.5em; padding-right: 0.5em; padding-bottom: 0.5em; padding-left: 0.5em; border-top-width: 1px; border-right-width: 1px; border-bottom-width: 1px; border-left-width: 1px; border-top-style: solid; border-right-style: solid; border-bottom-style: solid; border-left-style: solid; border-top-color: rgb(204, 204, 204); border-right-color: rgb(204, 204, 204); border-bottom-color: rgb(204, 204, 204); border-left-color: rgb(204, 204, 204); background-color: rgb(248, 248, 248); ">
<span class="k" style="color: rgb(0, 112, 32); font-weight: bold; ">SELECT</span> <span class="n">id</span> <span class="k" style="color: rgb(0, 112, 32); font-weight: bold; ">FROM</span> <span class="n">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><meta http-equiv="content-type" content="text/html; charset=utf-8"><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>One big question is what to return as a result.</div>
<div>And another question is if it will be possible to chose between Dijkstra, A-Star or Shooting*.</div><div><br></div><div>Daniel</div><div><br></div><br><div class="gmail_quote">2010/12/2 Daniel Kastl <span dir="ltr"><<a href="mailto:daniel@georepublic.de">daniel@georepublic.de</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="gmail_quote"><div class="im"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
I think there will be both cases. DARP/TSP might only need the matrix at<br>
first. But when you got your optimized tour result you had to run again<br>
the shortest path search to retrieve a path, which causes two problems:<br>
<br>
* The network (conditions) might have changed if you run those path<br>
queries later.<br>
</blockquote>
<br></div>
I guess this assumes the you are getting live feed data for traffic or something like that. What are you think here? Also be aware that the algorithms can select any of equal distance alternatives and the later if you single shortest path it might pick a different path, which may or may not be problematic.<br>
<br></blockquote><div><br></div></div><div>I actually don't assume live feed data but the fact that pgRouting keeps the network in a database and it's possible to change attributes for example, that are part of your cost parameter, at any time. Or maybe road links become unavailable during a long APSP query.</div>
<div><br></div><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 class="im">
<div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;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 class="im">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><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>