sanak
February 7, 2015, 8:23am
1
Hi list,
I am facing an issue about K-Shortest Path round-trip pattern.
When I specified same source and target ids, then pgr_ksp results are
invalid like this.
sampledata=# SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost
FROM pgr_ksp(
'SELECT id, source, target, cost FROM edge_table',
1, 1, 4, false
);
seq | route | node | edge | cost
-----+-------+------+-------------+-----------------------
0 | 0 | 1 | -2147483648 | 1.79769313486232e+308
1 | 0 | 1 | -1 | 0
(2 rows)
I think that the results should be as follows,
because in my understanding, K-Shortest Path should support round-trip pattern.
seq | route | node | edge | cost
-----+-------+------+-------------+-----------------------
0 | 0 | 1 | 1 | 1
1 | 0 | 2 | 1 | 1
2 | 0 | 1 | -1 | 0
3 | 1 | 1 | 1 | 1
: | : | : | : | :
But is my understanding wrong ?
(Shouldn't K-Shortest Path support round-trip case ?)
If my understanding is wrong, does someone know
how to support round-trip case ?
About above pgr_ksp issue, I created the ticket to here.
[pgr_ksp returns invalid one route when source and target are same #287 ]
opened 07:44AM - 07 Feb 15 UTC
closed 01:44AM - 17 Jul 15 UTC
Fixed on Develop
I used the following sample data.
http://docs.pgrouting.org/2.0/en/doc/src/devel… oper/sampledata.html
<pre>
sampledata=# SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost
FROM pgr_ksp(
'SELECT id, source, target, cost FROM edge_table',
1, 1, 4, false
);
seq | route | node | edge | cost
-----+-------+------+-------------+-----------------------
0 | 0 | 1 | -2147483648 | 1.79769313486232e+308
1 | 0 | 1 | -1 | 0
(2 rows)
</pre>
I think that the results should be as follows,
because in my understanding, K-Shortest Path should support round-trip pattern.
<pre>
seq | route | node | edge | cost
-----+-------+------+-------------+-----------------------
0 | 0 | 1 | 1 | 1
1 | 0 | 2 | 1 | 1
2 | 0 | 1 | -1 | 0
3 | 1 | 1 | 1 | 1
: | : | : | : | :
</pre>
Regards,
--
Ko Nagase (長瀬 興)
Georepublic Japan
mail: nagase@georepublic.co.jp
web: http://georepublic.co.jp
Nagase-san,
I answered this in the user list.
Basically there is not roundtrip support for any shortest path algorithm. Shorthest path is point to point and the shortest path from a point to itself is defined as zero.
-Steve
On 2/7/2015 3:23 AM, Ko Nagase wrote:
Hi list,
I am facing an issue about K-Shortest Path round-trip pattern.
When I specified same source and target ids, then pgr_ksp results are
invalid like this.
sampledata=# SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost
FROM pgr_ksp(
'SELECT id, source, target, cost FROM edge_table',
1, 1, 4, false
);
seq | route | node | edge | cost
-----+-------+------+-------------+-----------------------
0 | 0 | 1 | -2147483648 | 1.79769313486232e+308
1 | 0 | 1 | -1 | 0
(2 rows)
I think that the results should be as follows,
because in my understanding, K-Shortest Path should support round-trip pattern.
seq | route | node | edge | cost
-----+-------+------+-------------+-----------------------
0 | 0 | 1 | 1 | 1
1 | 0 | 2 | 1 | 1
2 | 0 | 1 | -1 | 0
3 | 1 | 1 | 1 | 1
: | : | : | : | :
But is my understanding wrong ?
(Shouldn't K-Shortest Path support round-trip case ?)
If my understanding is wrong, does someone know
how to support round-trip case ?
About above pgr_ksp issue, I created the ticket to here.
[pgr_ksp returns invalid one route when source and target are same #287 ]
https://github.com/pgRouting/pgrouting/issues/287
Regards,
sanak
February 7, 2015, 3:33pm
3
Hi Stephen,
Thanks for your answer.
2015-02-08 0:09 GMT+09:00 Stephen Woodbridge <woodbri@swoodbridge.com>:
Basically there is not roundtrip support for any shortest path algorithm.
Shorthest path is point to point and the shortest path from a point to
itself is defined as zero.
Okay.
Thanks for clarification.
Regards,
On 2/7/2015 3:23 AM, Ko Nagase wrote:
Hi list,
I am facing an issue about K-Shortest Path round-trip pattern.
When I specified same source and target ids, then pgr_ksp results are
invalid like this.
sampledata=# SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost
FROM pgr_ksp(
'SELECT id, source, target, cost FROM edge_table',
1, 1, 4, false
);
seq | route | node | edge | cost
-----+-------+------+-------------+-----------------------
0 | 0 | 1 | -2147483648 | 1.79769313486232e+308
1 | 0 | 1 | -1 | 0
(2 rows)
I think that the results should be as follows,
because in my understanding, K-Shortest Path should support round-trip
pattern.
seq | route | node | edge | cost
-----+-------+------+-------------+-----------------------
0 | 0 | 1 | 1 | 1
1 | 0 | 2 | 1 | 1
2 | 0 | 1 | -1 | 0
3 | 1 | 1 | 1 | 1
: | : | : | : | :
But is my understanding wrong ?
(Shouldn't K-Shortest Path support round-trip case ?)
If my understanding is wrong, does someone know
how to support round-trip case ?
About above pgr_ksp issue, I created the ticket to here.
[pgr_ksp returns invalid one route when source and target are same #287 ]
pgr_ksp returns invalid one route when source and target are same · Issue #287 · pgRouting/pgrouting · GitHub
Regards,
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
pgrouting-dev Info Page
--
Ko Nagase (長瀬 興)
Georepublic Japan
mail: nagase@georepublic.co.jp
web: http://georepublic.co.jp