[pgrouting-dev] K-Dijkstra code
Stephen Woodbridge
woodbri at swoodbridge.com
Fri May 24 08:05:23 PDT 2013
On 5/22/2013 4:40 PM, Stephen Woodbridge wrote:
> OK, I have figured out a test case but I get some really strange results:
>
> Here is a test case:
>
> create database mytest
> psql mytest -c "create extension postgis"
> psql mytest -c "create extension pgrouting"
>
> # load some data to work with
> psql mytest -f src/driving_distance/test/drivingdistance-any-00.test
>
> # run the dist query
> psql mytest -c "select * from kdijkstra_dist_sp('select * from ddnoded2
> ', 585, ARRAY[1,26,1274, 1250], false, false)"
>
>> vertex_id_source | edge_id_source | vertex_id_target | edge_id_target
>> | cost
>> ------------------+----------------+------------------+----------------+------
>>
>> 585 | 62 | 1 | 1
>> | 23
>> 585 | 12 | 26 | 75
>> | 24
>> 585 | 12 | 1274 | 25
>> | 26
>> 585 | 12 | 1250 | 25
>> | 24
>> (4 rows)
>
> So this could be pgr_kdijkstraCost()
>
> seq - seq
> id1 - vertex_id_source
> id2 - vertex_id_target
> cost - cost
>
>
> # run the ways query
> psql mytest -c "select * from kdijkstra_ways_sp('select * from ddnoded2
> ', 585, ARRAY[1,26,1274, 1250], false, false)"
>
>> vertex_id_source | edge_id_source | vertex_id_target | edge_id_target
>> | cost | the_way
>> ------------------+----------------+------------------+----------------+------+--------------------------------------------------------------------------------------------------------
>>
>> 585 | 62 | 1 | 1
>> | 23 | 62, 62, 62, 62, 8, 61, 7, 60, 60, 5, 59, 59, 3, 3, 3, 3, 3,
>> 3, 3, 52, 2, 51, 1
>> 585 | 12 | 26 | 75
>> | 24 | 12, 63, 11, 11, 65, 10, 10, 10, 10, 10, 70, 70, 70, 70, 70,
>> 5, 5, 72, 72, 72, 2, 2, 2, 75
>> 585 | 12 | 1274 | 25
>> | 26 | 12, 12, 12, 12, 12, 12, 12, 12, 12, 71, 13, 72, 72, 72, 72,
>> 72, 72, 72, 72, 72, 72, 23, 23, 74, 74, 25
>> 585 | 12 | 1250 | 25
>> | 24 | 12, 12, 12, 12, 12, 12, 12, 12, 12, 53, 53, 53, 53, 53, 53,
>> 53, 53, 20, 52, 52, 52, 52, 52, 25
>> (4 rows)
>
> And this could be pgr_kdijkstra() returning pgr_costResult:
OK, that was a typo, but I think it makes more sense to change this
regardless to something like:
pgr_kdijkstraPath() returning pgr_costResult:
seq - seq
id1 - vertex_id_target (ie: which route)
id2 - edge_id in the route
cost - edge_id cost
The rationale for this instead of returning the pgr_geomResult is that
only the wrapper functions return geoms and they do that be joining the
edge table using the edge_id.
So the first function pgr_kdijkstraCost() returns the total path length
which could be used to populate a distance matrix, and the second
function pgr_kdijkstraPath() returns the ordered list of edge_ids that
can be used to join to the edge table to create pgr_geomResult if
needed. Also in the *Path() function we are returning edge ids and the
cost for that edge. This should hopefully be the reverse_cost if we
traversed it in the reverse direction.
I'm still not clear why we are getting edges showing up multiple time in
the results. And the cost reported by pgr_kdijkstraCost() does sum the
multiple instances of the edge because in this graph all edges have a
cost=1.0 and cost in the sample queries is equal to the number of edges
reported.
So this is another boost related problem. I could really use a little
help from someone with C++ and boost experience.
-Steve
> seq - seq
> id1 - vertex_id_target (ie: which route)
> id2 - edge_id in the route
> geom - the_geom for edge_id
>
> So the query output above would end up looking like(ignoring dup edges)
> and returning pgr_geomResult:
>
> seq, id1, id2, geom
> 0, 1, 62, ...
> 1, 1, 8, ...
> 3, 1, 61, ...
> 4, 1, 7, ...
> 5, 1, 60, ...
> 6, 1, 5, ...
> 6, 1, 59, ...
> 7, 1, 3, ...
> 8, 1, 52, ...
> 9, 1, 2, ...
> 10, 1, 51, ...
> 11, 1, 1, ...
> 12, 26, 12, ...
> 13, 26, 63, ...
> 14, 26, 11, ...
> etc
>
>
> What concerns me on the above query is why we are getting multiple edge
> ids for the same edge in the current code.
>
> The vertex_id_source is useless because it will always be the same for a
> given query. I'm not sure how useful edge_id_source is in either query.
> vertex_id_target is useful because it tells you which target route you
> are dealing with. I don't see edge_id_target as being useful, and you
> get that as the last edge id in the 2nd query.
>
> Thoughts?
>
> -Steve
>
> On 5/22/2013 11:46 AM, Stephen Woodbridge wrote:
>> Daniel,
>>
>> If you can make a working example for the existing code that would
>> help me.
>>
>> Thanks,
>> -Steve
>>
>> On 5/22/2013 11:01 AM, Stephen Woodbridge wrote:
>>> Pushed under branch name kdijkstra-merge
>>>
>>> -Steve
>>>
>>> On 5/22/2013 10:32 AM, Daniel Kastl wrote:
>>>>
>>>>
>>>>
>>>> On Wed, May 22, 2013 at 4:48 AM, Stephen Woodbridge
>>>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>>>>
>>>> Daniel,
>>>>
>>>> I have merged the KDijkstra fork into a private branch, but it is
>>>> using some strange result types. Also there are two functions, one
>>>> returns a cost and the other returns the geoms but they both take
>>>> the same args and have different names.
>>>>
>>>> So I'm going to need to spend some time with this and see if I can
>>>> make is cleanly fit the model we have for the other functions.
>>>>
>>>>
>>>> Hi Steve,
>>>>
>>>> If you push this branch to Github, then I can also try out. ;-)
>>>>
>>>> Daniel
>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Georepublic UG & Georepublic Japan
>>>> eMail: daniel.kastl at georepublic.de <mailto:daniel.kastl at georepublic.de>
>>>> Web: http://georepublic.de <http://georepublic.de/>
>>>>
>>>>
>>>> _______________________________________________
>>>> pgrouting-dev mailing list
>>>> pgrouting-dev at lists.osgeo.org
>>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>>>
>>>
>>> _______________________________________________
>>> pgrouting-dev mailing list
>>> pgrouting-dev at lists.osgeo.org
>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
More information about the pgrouting-dev
mailing list