[pgrouting-dev] K-Dijkstra code

[Stephen Woodbridge]

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:

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