[pgrouting-users] pgr_apspjohnson algorithm

Sun Jan 5 10:27:43 PST 2014

Hi Helder,

As far as I remember the 2 APSP functions were implemented:

- pgr_apspwarshall: by Jay Mahadeokar to get familiar with pgRouting before
his GSoC term started
- pgr_apspjohnson: by Kishore Kumar during his GSoC project, where he
needed it for multi-modal routing

Daniel

On Mon, Jan 6, 2014 at 3:18 AM, Helder Alves <helderalvespt at gmail.com>wrote:

> Hi Steve,
>
> I think I get it!
> As soon I settle the reasoning in my head I'll contribute for the
> project... :-)
>
> --
> Helder Alves
>
>
> On Sun, Jan 5, 2014 at 1:18 PM, Stephen Woodbridge <
> woodbri at swoodbridge.com> wrote:
>
>> On 1/4/2014 11:28 PM, Helder Alves wrote:
>>
>>> Hi Steve,
>>>
>>> I'm following those experiments you are working on... :-)
>>>
>>> Regarding APSP I think currently it's not clear on what circumstances
>>> these functions can be used. I found some explicit reference on
>>> develop-vrp or gsoc-vrp branch and after that I realized no one seems to
>>> be using those algorithms, apart from the fact that Johnson's
>>> implementation seems to not handle at all negative costs which I think
>>> that may defeat it theoretical purpose (but this is not the reason of
>>> this e-mail as I'm still studying that subject).
>>>
>>
>> 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.
>>
>> 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.
>>
>>
>>  Maybe this help to understand my doubts...
>>>
>>
>> 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.
>>
>> Best regards,
>>   -Steve
>>
>>  Thanks!
>>>
>>> ----
>>> Helder Alves
>>>
>>> On Jan 5, 2014 2:54 AM, "Stephen Woodbridge" <woodbri at swoodbridge.com
>>> <mailto:woodbri at swoodbridge.com>> wrote:
>>>
>>>     On 1/4/2014 8:58 PM, Helder Alves wrote:
>>>
>>>         Hi List,
>>>
>>>         I've search the Internet for an example of a practical appliance
>>> of
>>>         pgr_apspjohnson function using OSM data.
>>>
>>>         If this algorithm is supposed to feed VRP using a VRP distance
>>>         table,
>>>         from the found documentation I suppose it must generate the
>>>         equivalent
>>>         to TSP distance matrix but in a record format pair by pair of
>>>         all the
>>>         vertices instead of the multi-dimensional array used by pgr_TSP,
>>>         please
>>>         correct me if I'm wrong.
>>>
>>>         Problem is, what data is supposed to feed pgr_apspjohnson?
>>>         source/target/cost ways (table) data for the vids I want to
>>>         order using
>>>         pgr_pointtovids function, for example? If not, I would like
>>>         someone to
>>>         elaborate a bit on this...
>>>
>>>         What about pgr_apspwarshall? Is it the same or not?
>>>
>>>         Thanks in advance for your help!
>>>
>>>
>>>     Helder,
>>>
>>>     I'm not sure that either of these are very useful as they in theory
>>>     generate ALL pairs for all nodes in the graph and VRP and TSP want a
>>>     matrix of some defined locations in the graph and not ALL locations
>>>     in the graph.
>>>
>>>     I had the same problem and my solution to this was to create
>>>
>>>     https://github.com/woodbri/__osrm-tools
>>>
>>>     <https://github.com/woodbri/osrm-tools>
>>>
>>>     which provides some postgresql wrapper functions that call to a
>>>     local instance of OSRM and creates the distances or tables needed to
>>>     feed into VRP or TSP. This is much faster than pgrouting path
>>>     generation, but does not allow for all the flexibility of pgRouting.
>>>     Also you have the added headache of setting up ORSM.
>>>
>>>     The other option that I created was to create a function
>>>     pgr_vidsToDMatrix()
>>>
>>>     This creates and array vetrex ids into a distance matrix.
>>>
>>>     https://github.com/pgRouting/__pgrouting/tree/develop/src/__
>>> common/doc/convenience
>>>     <https://github.com/pgRouting/pgrouting/tree/develop/src/
>>> common/doc/convenience>
>>>
>>>     -Steve
>>>     _________________________________________________
>>>     Pgrouting-users mailing list
>>>     Pgrouting-users at lists.osgeo.__org
>>>     <mailto:Pgrouting-users at lists.osgeo.org>
>>>     http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
>>>     <http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> Pgrouting-users mailing list
>>> Pgrouting-users at lists.osgeo.org
>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>>
>>>
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>

-- 
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
Web: http://georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20140106/d636e387/attachment.html>