[pgrouting-users] pgr_apspjohnson algorithm

[Helder Alves]

Hi Steve,

I'm already beyond that stage but thanks anyway! ;-)

Steve/Daniel,

Regarding my assumptions regarding pgr_apspjohnson, they seem to be wrong.
Can you please elaborate a little bit on exactly which data must be fed
into pgr_apspjohnson?

>From the pgRouting examples I read, it seems to return the equivalent to
the distance matrix used by pgr_TSP however I don't understand exactly
which part of a routable table must be queried in a viable way for an
algorithm to be able to infer which nodes have to be routed. Can you help
me with this one?

Thanks!

--
Helder Alves


On Sun, Jan 5, 2014 at 7:52 PM, Stephen Woodbridge
<woodbri at swoodbridge.com>wrote:

> On 1/5/2014 2:16 PM, Helder Alves wrote:
>
>> Hi Daniel,
>>
>> Regarding pgr_apspjohnson, I came to the conclusion that SQL query
>> passed into pgr_apspjohnson must already return a shortest path distance
>> matrix including all the stop points we want to optimize. Am I getting
>> it right?
>>
>> What I'm about to try now is to unnest the distance matrix generated for
>> pgr_TSP to feed pgr_apspjohnson...
>>
>
> You might be able to use something like this to convert the distance
> matrix into a table:
>
> with dm as (
>   select '{{1,2,3,4,5},
>            {6,7,8,9,10},
>            {11,12,13,14,15},
>            {16,17,18,19,20},
>            {21,22,23,24,25}}'::int[] as dm
> )
> select i, j, dm.dm[j][i]
>   from generate_series(1, 5) i,
>        generate_series(1, 5) j,
>        dm;
>
> -Steve
>
>  Problem was that from all my previous reading I thought that at some
>> point APSP Johnson would itself generate the routing graphs, what seems
>> not to be the case, if my understanding from the source code is right...
>> Meaning APSP Johnson only takes care of the total route minimum cost
>> (permutations) avoiding the problem of TSP with negative costs.
>>
>> Please let me know if I made foolish assumptions! :-)
>>
>> --
>> Helder Alves
>>
>>
>>
>>
>>
>> _______________________________________________
>> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20140105/00d40b78/attachment.html>