pgr_withPointsKSP - Proposed - pgRouting Manual (3.7)
pgr_withPointsKSP - Proposed
pgr_withPointsKSP
- Yen’s algorithm for K shortest paths using Dijkstra.
Warning
Proposed functions for next mayor release.
-
They are not officially in the current release.
-
They will likely officially be part of the next mayor release:
-
The functions make use of ANY-INTEGER and ANY-NUMERICAL
-
Name might not change. (But still can)
-
Signature might not change. (But still can)
-
Functionality might not change. (But still can)
-
pgTap tests have being done. But might need more.
-
Documentation might need refinement.
-
Availability
Version 3.6.0
-
Standarizing output columns to
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) -
pgr_withPointsKSP(One to One)-
Signature change:
driving_sideparameter changed from named optional to unnamed compulsory driving side . -
Added
start_vidandend_vidresult columns.
-
-
New overload functions
-
pgr_withPointsKSP(One to Many) -
pgr_withPointsKSP(Many to One) -
pgr_withPointsKSP(Many to Many) -
pgr_withPointsKSP(Combinations)
-
-
Deprecated signature
-
pgr_withpointsksp(text,text,bigint,bigint,integer,boolean,boolean,char,boolean)
-
Version 2.2.0
-
New proposed function
Description
Modifies the graph to include the points defined in the Points SQL and using Yen algorithm, finds the \(K\) shortest paths.
Signatures
[directed,
heap_paths,
details]
(seq,
path_id,
path_seq,
node,
edge,
cost,
agg_cost)
One to One
[directed,
heap_paths,
details]
(seq,
path_id,
path_seq,
start_vid,
end_vid,
node,
edge,
cost,
agg_cost)
- Example :
-
Get 2 paths from Point \(1\) to point \(2\) on a directed graph with left side driving.
-
For a directed graph.
-
No details are given about distance of other points of the query.
-
No heap paths are returned.
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
-1, -2, 2, 'l');
seq path_id path_seq start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 -1 -2 -1 1 0.6 0
2 1 2 -1 -2 6 4 1 0.6
3 1 3 -1 -2 7 8 1 1.6
4 1 4 -1 -2 11 11 1 2.6
5 1 5 -1 -2 12 13 1 3.6
6 1 6 -1 -2 17 15 0.6 4.6
7 1 7 -1 -2 -2 -1 0 5.2
8 2 1 -1 -2 -1 1 0.6 0
9 2 2 -1 -2 6 4 1 0.6
10 2 3 -1 -2 7 8 1 1.6
11 2 4 -1 -2 11 9 1 2.6
12 2 5 -1 -2 16 15 1.6 3.6
13 2 6 -1 -2 -2 -1 0 5.2
(13 rows)
One to Many
[directed,
heap_paths,
details]
(seq,
path_id,
path_seq,
node,
edge,
cost,
agg_cost)
- Example :
-
Get 2 paths from point \(1\) to point \(3\) and vertex \(7\) on an undirected graph
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
-1, ARRAY[-3, 7], 2, 'B',
directed => false);
seq path_id path_seq start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 -1 -3 -1 1 0.6 0
2 1 2 -1 -3 6 4 1 0.6
3 1 3 -1 -3 7 10 1 1.6
4 1 4 -1 -3 8 12 0.6 2.6
5 1 5 -1 -3 -3 -1 0 3.2
6 2 1 -1 -3 -1 1 0.6 0
7 2 2 -1 -3 6 4 1 0.6
8 2 3 -1 -3 7 8 1 1.6
9 2 4 -1 -3 11 11 1 2.6
10 2 5 -1 -3 12 12 0.4 3.6
11 2 6 -1 -3 -3 -1 0 4
12 3 1 -1 7 -1 1 0.6 0
13 3 2 -1 7 6 4 1 0.6
14 3 3 -1 7 7 -1 0 1.6
15 4 1 -1 7 -1 1 0.6 0
16 4 2 -1 7 6 2 1 0.6
17 4 3 -1 7 10 5 1 1.6
18 4 4 -1 7 11 8 1 2.6
19 4 5 -1 7 7 -1 0 3.6
(19 rows)
Many to One
[directed,
heap_paths,
details]
(seq,
path_id,
path_seq,
node,
edge,
cost,
agg_cost)
- Example :
-
Get a path from point \(1\) and vertex \(6\) to point \(3\) on a directed graph with right side driving and details set to True
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
ARRAY[-1, 6], -3, 1, 'r', details=> true);
seq path_id path_seq start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 -1 -3 -1 1 0.4 0
2 1 2 -1 -3 5 1 1 0.4
3 1 3 -1 -3 6 4 0.7 1.4
4 1 4 -1 -3 -6 4 0.3 2.1
5 1 5 -1 -3 7 10 1 2.4
6 1 6 -1 -3 8 12 0.6 3.4
7 1 7 -1 -3 -3 -1 0 4
8 2 1 6 -3 6 4 0.7 0
9 2 2 6 -3 -6 4 0.3 0.7
10 2 3 6 -3 7 10 1 1
11 2 4 6 -3 8 12 0.6 2
12 2 5 6 -3 -3 -1 0 2.6
(12 rows)
Many to Many
[directed,
heap_paths,
details]
(seq,
path_id,
path_seq,
start_vid,
end_vid,
node,
edge,
cost,
agg_cost)
- Example :
-
Get a path from point \(1\) and vertex \(6\) to point \(3\) and vertex \(1\) on a directed graph with left side driving and heap_paths set to True
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
ARRAY[-1, 6], ARRAY[-3, 1], 1, 'l', heap_paths => true);
seq path_id path_seq start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 -1 -3 -1 1 0.6 0
2 1 2 -1 -3 6 4 1 0.6
3 1 3 -1 -3 7 10 1 1.6
4 1 4 -1 -3 8 12 0.6 2.6
5 1 5 -1 -3 -3 -1 0 3.2
6 2 1 -1 1 -1 1 0.6 0
7 2 2 -1 1 6 4 1 0.6
8 2 3 -1 1 7 7 1 1.6
9 2 4 -1 1 3 6 1 2.6
10 2 5 -1 1 1 -1 0 3.6
11 3 1 6 -3 6 4 1 0
12 3 2 6 -3 7 10 1 1
13 3 3 6 -3 8 12 0.6 2
14 3 4 6 -3 -3 -1 0 2.6
15 4 1 6 1 6 4 1 0
16 4 2 6 1 7 7 1 1
17 4 3 6 1 3 6 1 2
18 4 4 6 1 1 -1 0 3
(18 rows)
Combinations
[directed,
heap_paths,
details]
(seq,
path_id,
path_seq,
node,
edge,
cost,
agg_cost)
- Example :
-
Using a combinations table on an directed graph
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
'SELECT * FROM (VALUES (-1, 10), (6, -3)) AS combinations(source, target)',
2, 'r', details => true);
seq path_id path_seq start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 -1 10 -1 1 0.4 0
2 1 2 -1 10 5 1 1 0.4
3 1 3 -1 10 6 4 0.7 1.4
4 1 4 -1 10 -6 4 0.3 2.1
5 1 5 -1 10 7 8 1 2.4
6 1 6 -1 10 11 9 1 3.4
7 1 7 -1 10 16 16 1 4.4
8 1 8 -1 10 15 3 1 5.4
9 1 9 -1 10 10 -1 0 6.4
10 2 1 -1 10 -1 1 0.4 0
11 2 2 -1 10 5 1 1 0.4
12 2 3 -1 10 6 4 0.7 1.4
13 2 4 -1 10 -6 4 0.3 2.1
14 2 5 -1 10 7 8 1 2.4
15 2 6 -1 10 11 11 1 3.4
16 2 7 -1 10 12 13 1 4.4
17 2 8 -1 10 17 15 1 5.4
18 2 9 -1 10 16 16 1 6.4
19 2 10 -1 10 15 3 1 7.4
20 2 11 -1 10 10 -1 0 8.4
21 3 1 6 -3 6 4 0.7 0
22 3 2 6 -3 -6 4 0.3 0.7
23 3 3 6 -3 7 10 1 1
24 3 4 6 -3 8 12 0.6 2
25 3 5 6 -3 -3 -1 0 2.6
(25 rows)
Parameters
|
Column |
Type |
Description |
|---|---|---|
|
|
Edges SQL query as described. |
|
|
|
Points SQL query as described. |
|
|
start vid |
ANY-INTEGER |
Identifier of the departure vertex.
|
|
end vid |
ANY-INTEGER |
Identifier of the destination vertex.
|
|
K |
ANY-INTEGER |
Number of required paths |
|
driving_side |
CHAR |
Value in [
|
Where:
- ANY-INTEGER :
-
SMALLINT,INTEGER,BIGINT
Optional parameters
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
|
|
|
|
KSP Optional parameters
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
|
|
|
|
withPointsKSP optional parameters
|
Parameter |
Type |
Default |
Description |
|---|---|---|---|
|
|
|
|
|
Inner Queries
Edges SQL
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
|
ANY-NUMERICAL |
Weight of the edge (
|
|
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Where:
- ANY-INTEGER :
-
SMALLINT,INTEGER,BIGINT - ANY-NUMERICAL :
-
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
Points SQL
|
Parameter |
Type |
Default |
Description |
|---|---|---|---|
|
|
ANY-INTEGER |
value |
Identifier of the point.
|
|
|
ANY-INTEGER |
Identifier of the "closest" edge to the point. |
|
|
|
ANY-NUMERICAL |
Value in <0,1> that indicates the relative postition from the first end point of the edge. |
|
|
|
|
|
Value in [
|
Where:
- ANY-INTEGER :
-
SMALLINT,INTEGER,BIGINT - ANY-NUMERICAL :
-
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
Combinations SQL
|
Parameter |
Type |
Description |
|---|---|---|
|
|
ANY-INTEGER |
Identifier of the departure vertex. |
|
|
ANY-INTEGER |
Identifier of the arrival vertex. |
Where:
- ANY-INTEGER :
-
SMALLINT,INTEGER,BIGINT
Result columns
Returns set of
(seq,
path_id,
path_seq,
start_vid,
end_vid,
node,
edge,
cost,
agg_cost)
|
Column |
Type |
Description |
|---|---|---|
|
|
|
Sequential value starting from 1 . |
|
|
|
Path identifier.
|
|
|
|
Relative position in the path. Has value 1 for the beginning of a path. |
|
|
|
Identifier of the node in the path from
|
|
|
|
Identifier of the edge used to go from
|
|
|
|
Cost to traverse from
|
|
|
|
Aggregate cost from
start vid
to
|
Additional Examples
Use pgr_findCloseEdges in the Points SQL .
Get \(2\) paths using left side driving topology, from vertex \(1\) to the closest location on the graph of point (2.9, 1.8) .
SELECT * FROM pgr_withPointsKSP(
$e$ SELECT * FROM edges $e$,
$p$ SELECT edge_id, round(fraction::numeric, 2) AS fraction, side
FROM pgr_findCloseEdges(
$$SELECT id, geom FROM edges$$,
(SELECT ST_POINT(2.9, 1.8)),
0.5, cap => 2)
$p$,
1, -1, 2,'r');
seq path_id path_seq start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 1 -1 1 6 1 0
2 1 2 1 -1 3 7 1 1
3 1 3 1 -1 7 8 1 2
4 1 4 1 -1 11 9 1 3
5 1 5 1 -1 16 16 1 4
6 1 6 1 -1 15 3 1 5
7 1 7 1 -1 10 5 0.8 6
8 1 8 1 -1 -1 -1 0 6.8
9 2 1 1 -1 1 6 1 0
10 2 2 1 -1 3 7 1 1
11 2 3 1 -1 7 10 1 2
12 2 4 1 -1 8 12 1 3
13 2 5 1 -1 12 13 1 4
14 2 6 1 -1 17 15 1 5
15 2 7 1 -1 16 16 1 6
16 2 8 1 -1 15 3 1 7
17 2 9 1 -1 10 5 0.8 8
18 2 10 1 -1 -1 -1 0 8.8
(18 rows)
-
Point \(-1\) corresponds to the closest edge from point (2.9, 1.8) .
Left driving side
Get \(2\) paths using left side driving topology, from point \(1\) to point \(3\) with details.
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
-1, -3, 2, 'l', details => true);
seq path_id path_seq start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 -1 -3 -1 1 0.6 0
2 1 2 -1 -3 6 4 0.7 0.6
3 1 3 -1 -3 -6 4 0.3 1.3
4 1 4 -1 -3 7 10 1 1.6
5 1 5 -1 -3 8 12 0.6 2.6
6 1 6 -1 -3 -3 -1 0 3.2
(6 rows)
Right driving side
Get \(2\) paths using right side driving topology from, point \(1\) to point \(2\) with heap paths and details.
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
-1, -2, 2, 'r',
heap_paths => true, details => true);
seq path_id path_seq start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 -1 -2 -1 1 0.4 0
2 1 2 -1 -2 5 1 1 0.4
3 1 3 -1 -2 6 4 0.7 1.4
4 1 4 -1 -2 -6 4 0.3 2.1
5 1 5 -1 -2 7 8 1 2.4
6 1 6 -1 -2 11 9 1 3.4
7 1 7 -1 -2 16 15 0.4 4.4
8 1 8 -1 -2 -2 -1 0 4.8
9 2 1 -1 -2 -1 1 0.4 0
10 2 2 -1 -2 5 1 1 0.4
11 2 3 -1 -2 6 4 0.7 1.4
12 2 4 -1 -2 -6 4 0.3 2.1
13 2 5 -1 -2 7 8 1 2.4
14 2 6 -1 -2 11 11 1 3.4
15 2 7 -1 -2 12 13 1 4.4
16 2 8 -1 -2 17 15 1 5.4
17 2 9 -1 -2 16 15 0.4 6.4
18 2 10 -1 -2 -2 -1 0 6.8
19 3 1 -1 -2 -1 1 0.4 0
20 3 2 -1 -2 5 1 1 0.4
21 3 3 -1 -2 6 4 0.7 1.4
22 3 4 -1 -2 -6 4 0.3 2.1
23 3 5 -1 -2 7 10 1 2.4
24 3 6 -1 -2 8 12 0.6 3.4
25 3 7 -1 -2 -3 12 0.4 4
26 3 8 -1 -2 12 13 1 4.4
27 3 9 -1 -2 17 15 1 5.4
28 3 10 -1 -2 16 15 0.4 6.4
29 3 11 -1 -2 -2 -1 0 6.8
(29 rows)
The queries use the Sample Data network.
See Also
Indices and tables