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.
-Steve
On Wed, May 22, 2013 at 4:48 AM, Stephen Woodbridge <woodbri@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@georepublic.de
Web: http://georepublic.de
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@swoodbridge.com <mailto:woodbri@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@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de/>_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
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@swoodbridge.com <mailto:woodbri@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@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de/>_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
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,
-SteveOn 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@swoodbridge.com <mailto:woodbri@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@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de/>_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
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_idSo 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, ...
etcWhat 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,
-SteveOn 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@swoodbridge.com <mailto:woodbri@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@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de/>_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev