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 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¶
pgr_withPointsKSP(Edges SQL, Points SQL start_pid, end_pid, K [, directed] [, heap_paths] [, driving_side] [, details]) RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)
Example: | Get 2 paths from Point \(1\) to point \(2\) on a directed graph. |
---|
- For a directed graph.
- The driving side is set as b both. So arriving/departing to/from the point(s) can be in any direction.
- 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);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | -1 | 1 | 0.6 | 0
2 | 1 | 2 | 6 | 4 | 1 | 0.6
3 | 1 | 3 | 7 | 8 | 1 | 1.6
4 | 1 | 4 | 11 | 9 | 1 | 2.6
5 | 1 | 5 | 16 | 15 | 0.4 | 3.6
6 | 1 | 6 | -2 | -1 | 0 | 4
7 | 2 | 1 | -1 | 1 | 0.6 | 0
8 | 2 | 2 | 6 | 4 | 1 | 0.6
9 | 2 | 3 | 7 | 8 | 1 | 1.6
10 | 2 | 4 | 11 | 11 | 1 | 2.6
11 | 2 | 5 | 12 | 13 | 1 | 3.6
12 | 2 | 6 | 17 | 15 | 0.6 | 4.6
13 | 2 | 7 | -2 | -1 | 0 | 5.2
(13 rows)
Parameters¶
Column | Type | Description |
---|---|---|
Edges SQL | TEXT |
Edges SQL query as described. |
Points SQL | TEXT |
Points SQL query as described. |
start vid | ANY-INTEGER | Identifier of the departure vertex. |
end vid | ANY-INTEGER | Identifier of the departure vertex. |
K | ANY-INTEGER | Number of required paths |
Where:
ANY-INTEGER: | SMALLINT , INTEGER , BIGINT |
---|
Optional parameters¶
Column | Type | Default | Description |
---|---|---|---|
directed |
BOOLEAN |
true |
|
KSP Optional parameters¶
Column | Type | Default | Description |
---|---|---|---|
heap_paths |
BOOLEAN |
false |
|
With points optional parameters¶
Parameter | Type | Default | Description |
---|---|---|---|
driving_side |
CHAR |
b |
Value in [
|
details |
BOOLEAN |
false |
|
Inner Queries¶
Edges SQL¶
Column | Type | Default | Description |
---|---|---|---|
id |
ANY-INTEGER | Identifier of the edge. | |
source |
ANY-INTEGER | Identifier of the first end point vertex of the edge. | |
target |
ANY-INTEGER | Identifier of the second end point vertex of the edge. | |
cost |
ANY-NUMERICAL | Weight of the edge (source , target ) |
|
reverse_cost |
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 |
---|---|---|---|
pid |
ANY-INTEGER | value | Identifier of the point.
|
edge_id |
ANY-INTEGER | Identifier of the “closest” edge to the point. | |
fraction |
ANY-NUMERICAL | Value in <0,1> that indicates the relative postition from the first end point of the edge. | |
side |
CHAR |
b |
Value in [
|
Where:
ANY-INTEGER: | SMALLINT , INTEGER , BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT , INTEGER , BIGINT , REAL , FLOAT |
Result Columns¶
Returns set of (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost,
agg_cost)
Column | Type | Description |
---|---|---|
seq |
INTEGER |
Sequential value starting from 1. |
path_id |
INTEGER |
Path identifier.
|
path_seq |
INTEGER |
Relative position in the path. Has value 1 for the beginning of a path. |
node |
BIGINT |
Identifier of the node in the path from start vid to end vid |
edge |
BIGINT |
Identifier of the edge used to go from node to the next node in the
path sequence. -1 for the last node of the path. |
cost |
FLOAT |
Cost to traverse from
|
agg_cost |
FLOAT |
Aggregate cost from start vid to node . |
Additional Examples¶
Left driving side¶
Get \(2\) paths using left side driving topology, from point \(1\) to point \(2\) 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, -2, 2,
driving_side := 'l', details := true);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | -1 | 1 | 0.6 | 0
2 | 1 | 2 | 6 | 4 | 0.7 | 0.6
3 | 1 | 3 | -6 | 4 | 0.3 | 1.3
4 | 1 | 4 | 7 | 8 | 1 | 1.6
5 | 1 | 5 | 11 | 11 | 1 | 2.6
6 | 1 | 6 | 12 | 13 | 1 | 3.6
7 | 1 | 7 | 17 | 15 | 0.6 | 4.6
8 | 1 | 8 | -2 | -1 | 0 | 5.2
9 | 2 | 1 | -1 | 1 | 0.6 | 0
10 | 2 | 2 | 6 | 4 | 0.7 | 0.6
11 | 2 | 3 | -6 | 4 | 0.3 | 1.3
12 | 2 | 4 | 7 | 8 | 1 | 1.6
13 | 2 | 5 | 11 | 9 | 1 | 2.6
14 | 2 | 6 | 16 | 15 | 1 | 3.6
15 | 2 | 7 | 17 | 15 | 0.6 | 4.6
16 | 2 | 8 | -2 | -1 | 0 | 5.2
(16 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,
heap_paths := true, driving_side := 'r', details := true);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | -1 | 1 | 0.4 | 0
2 | 1 | 2 | 5 | 1 | 1 | 0.4
3 | 1 | 3 | 6 | 4 | 0.7 | 1.4
4 | 1 | 4 | -6 | 4 | 0.3 | 2.1
5 | 1 | 5 | 7 | 8 | 1 | 2.4
6 | 1 | 6 | 11 | 9 | 1 | 3.4
7 | 1 | 7 | 16 | 15 | 0.4 | 4.4
8 | 1 | 8 | -2 | -1 | 0 | 4.8
9 | 2 | 1 | -1 | 1 | 0.4 | 0
10 | 2 | 2 | 5 | 1 | 1 | 0.4
11 | 2 | 3 | 6 | 4 | 0.7 | 1.4
12 | 2 | 4 | -6 | 4 | 0.3 | 2.1
13 | 2 | 5 | 7 | 8 | 1 | 2.4
14 | 2 | 6 | 11 | 11 | 1 | 3.4
15 | 2 | 7 | 12 | 13 | 1 | 4.4
16 | 2 | 8 | 17 | 15 | 1 | 5.4
17 | 2 | 9 | 16 | 15 | 0.4 | 6.4
18 | 2 | 10 | -2 | -1 | 0 | 6.8
19 | 3 | 1 | -1 | 1 | 0.4 | 0
20 | 3 | 2 | 5 | 1 | 1 | 0.4
21 | 3 | 3 | 6 | 4 | 0.7 | 1.4
22 | 3 | 4 | -6 | 4 | 0.3 | 2.1
23 | 3 | 5 | 7 | 10 | 1 | 2.4
24 | 3 | 6 | 8 | 12 | 0.6 | 3.4
25 | 3 | 7 | -3 | 12 | 0.4 | 4
26 | 3 | 8 | 12 | 13 | 1 | 4.4
27 | 3 | 9 | 17 | 15 | 1 | 5.4
28 | 3 | 10 | 16 | 15 | 0.4 | 6.4
29 | 3 | 11 | -2 | -1 | 0 | 6.8
(29 rows)
The queries use the Sample Data network.
See Also¶
Indices and tables