<div dir="ltr">Hi Helder,<div><br></div><div>As far as I remember the 2 APSP functions were implemented:</div><div> </div><div>- pgr_apspwarshall: by Jay Mahadeokar to get familiar with pgRouting before his GSoC term started</div>
<div>- pgr_apspjohnson: by Kishore Kumar during his GSoC project, where he needed it for multi-modal routing</div><div><br></div><div>Daniel</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Mon, Jan 6, 2014 at 3:18 AM, Helder Alves <span dir="ltr"><<a href="mailto:helderalvespt@gmail.com" target="_blank">helderalvespt@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi Steve,<div><br></div><div>I think I get it!</div><div>As soon I settle the reasoning in my head I'll contribute for the project... :-)</div>
<div class="gmail_extra"><br clear="all"><div><div dir="ltr">
<div>--</div><div>Helder Alves </div></div></div><div><div class="h5">
<br><br><div class="gmail_quote">On Sun, Jan 5, 2014 at 1:18 PM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div>On 1/4/2014 11:28 PM, Helder Alves wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi Steve,<br>
<br>
I'm following those experiments you are working on... :-)<br>
<br>
Regarding APSP I think currently it's not clear on what circumstances<br>
these functions can be used. I found some explicit reference on<br>
develop-vrp or gsoc-vrp branch and after that I realized no one seems to<br>
be using those algorithms, apart from the fact that Johnson's<br>
implementation seems to not handle at all negative costs which I think<br>
that may defeat it theoretical purpose (but this is not the reason of<br>
this e-mail as I'm still studying that subject).<br>
</blockquote>
<br></div>
The two APSP algorithms were random additions from two of our GSoC students. I'm not sure what they are useful for, I'll need to go back to my graph theory and look that up again. I think that they have value where you construct a specific graph of important nodes and edges around a specific problem set and then you can solve that specific class of problems. I do not think it is useful to load a huge street network and solve it with APSP.<br>
<br>
Graph theory supports an abstract model for solving a lot more problems than vehicle routing. While MOST of our user base is focused on vehicle routing not everyone is so some of the tools we offer are more to support general graph solutions than just vehicle routing solutions.<div>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Maybe this help to understand my doubts...<br>
</blockquote>
<br></div>
Understood. We are always looking and hoping to get support from the community. My skills are more generally focused on C development and process management rather than on the specifics of implementing any given graph solution. So pull requests are welcome. These could be for code, tests, and/or docs. I also enjoy a good discussion (like this) with our users. It is hard to know what is important to add to the product with such a discussion around limits and short comings and concerns that users have.<br>
<br>
Best regards,<br>
-Steve<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>
Thanks!<br>
<br>
----<br>
Helder Alves<br>
<br>
On Jan 5, 2014 2:54 AM, "Stephen Woodbridge" <<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a><br></div><div><div>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>> wrote:<br>
<br>
On 1/4/2014 8:58 PM, Helder Alves wrote:<br>
<br>
Hi List,<br>
<br>
I've search the Internet for an example of a practical appliance of<br>
pgr_apspjohnson function using OSM data.<br>
<br>
If this algorithm is supposed to feed VRP using a VRP distance<br>
table,<br>
from the found documentation I suppose it must generate the<br>
equivalent<br>
to TSP distance matrix but in a record format pair by pair of<br>
all the<br>
vertices instead of the multi-dimensional array used by pgr_TSP,<br>
please<br>
correct me if I'm wrong.<br>
<br>
Problem is, what data is supposed to feed pgr_apspjohnson?<br>
source/target/cost ways (table) data for the vids I want to<br>
order using<br>
pgr_pointtovids function, for example? If not, I would like<br>
someone to<br>
elaborate a bit on this...<br>
<br>
What about pgr_apspwarshall? Is it the same or not?<br>
<br>
Thanks in advance for your help!<br>
<br>
<br>
Helder,<br>
<br>
I'm not sure that either of these are very useful as they in theory<br>
generate ALL pairs for all nodes in the graph and VRP and TSP want a<br>
matrix of some defined locations in the graph and not ALL locations<br>
in the graph.<br>
<br>
I had the same problem and my solution to this was to create<br>
<br></div></div>
<a href="https://github.com/woodbri/__osrm-tools" target="_blank">https://github.com/woodbri/__<u></u>osrm-tools</a><div><br>
<<a href="https://github.com/woodbri/osrm-tools" target="_blank">https://github.com/woodbri/<u></u>osrm-tools</a>><br>
<br>
which provides some postgresql wrapper functions that call to a<br>
local instance of OSRM and creates the distances or tables needed to<br>
feed into VRP or TSP. This is much faster than pgrouting path<br>
generation, but does not allow for all the flexibility of pgRouting.<br>
Also you have the added headache of setting up ORSM.<br>
<br>
The other option that I created was to create a function<br>
pgr_vidsToDMatrix()<br>
<br>
This creates and array vetrex ids into a distance matrix.<br>
<br></div>
<a href="https://github.com/pgRouting/__pgrouting/tree/develop/src/__common/doc/convenience" target="_blank">https://github.com/pgRouting/_<u></u>_pgrouting/tree/develop/src/__<u></u>common/doc/convenience</a><br>
<<a href="https://github.com/pgRouting/pgrouting/tree/develop/src/common/doc/convenience" target="_blank">https://github.com/pgRouting/<u></u>pgrouting/tree/develop/src/<u></u>common/doc/convenience</a>><br>
<br>
-Steve<br>
______________________________<u></u>___________________<br>
Pgrouting-users mailing list<br>
Pgrouting-users@lists.osgeo.__<u></u>org<br>
<mailto:<a href="mailto:Pgrouting-users@lists.osgeo.org" target="_blank">Pgrouting-users@lists.<u></u>osgeo.org</a>><br>
<a href="http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users" target="_blank">http://lists.osgeo.org/__<u></u>mailman/listinfo/pgrouting-__<u></u>users</a><br>
<<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-<u></u>users</a>><div><br>
<br>
<br>
<br>
______________________________<u></u>_________________<br>
Pgrouting-users mailing list<br>
<a href="mailto:Pgrouting-users@lists.osgeo.org" target="_blank">Pgrouting-users@lists.osgeo.<u></u>org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-<u></u>users</a><br>
<br>
</div></blockquote><div><div>
<br>
______________________________<u></u>_________________<br>
Pgrouting-users mailing list<br>
<a href="mailto:Pgrouting-users@lists.osgeo.org" target="_blank">Pgrouting-users@lists.osgeo.<u></u>org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-<u></u>users</a><br>
</div></div></blockquote></div><br></div></div></div></div>
<br>_______________________________________________<br>
Pgrouting-users mailing list<br>
<a href="mailto:Pgrouting-users@lists.osgeo.org">Pgrouting-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-users</a><br></blockquote></div><br><br clear="all"><div><br></div>-- <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>
</div>