pgr_withPointsKSP - Proposed - pgRouting Manual (3.0)
pgr_withPointsKSP - Proposed
pgr_withPointsKSP
- Find the K shortest paths using Yen’s algorithm.
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
-
Support
Description
Modifies the graph to include the points defined in the
points_sql
and
using Yen algorithm, finds the
\(K\)
shortest paths.
Signatures
Summary
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)
Using defaults
pgr_withPointsKSP(edges_sql, points_sql, start_pid, end_pid, K)
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)
- Example :
-
From point \(1\) to point \(2\) in \(2\) cycles
-
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 edge_table 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 2 4 1 0.6
3 1 3 5 8 1 1.6
4 1 4 6 9 1 2.6
5 1 5 9 15 0.4 3.6
6 1 6 -2 -1 0 4
7 2 1 -1 1 0.6 0
8 2 2 2 4 1 0.6
9 2 3 5 8 1 1.6
10 2 4 6 11 1 2.6
11 2 5 11 13 1 3.6
12 2 6 12 15 0.6 4.6
13 2 7 -2 -1 0 5.2
(13 rows)
Complete Signature
Finds the \(K\) shortest paths depending on the optional parameters setup.
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 :
-
From point \(1\) to vertex \(6\) in \(2\) cycles with details.
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
-1, 6, 2, details := true);
seq path_id path_seq node edge cost agg_cost
-----+---------+----------+------+------+------+----------
1 1 1 -1 1 0.6 0
2 1 2 2 4 0.7 0.6
3 1 3 -6 4 0.3 1.3
4 1 4 5 8 1 1.6
5 1 5 6 -1 0 2.6
6 2 1 -1 1 0.6 0
7 2 2 2 4 0.7 0.6
8 2 3 -6 4 0.3 1.3
9 2 4 5 10 1 1.6
10 2 5 10 12 0.6 2.6
11 2 6 -3 12 0.4 3.2
12 2 7 11 13 1 3.6
13 2 8 12 15 0.6 4.6
14 2 9 -2 15 0.4 5.2
15 2 10 9 9 1 5.6
16 2 11 6 -1 0 6.6
(16 rows)
Parameters
|
Parameter |
Type |
Description |
|---|---|---|
|
edges_sql |
|
Edges SQL query as described above. |
|
points_sql |
|
Points SQL query as described above. |
|
start_pid |
|
Starting point id. |
|
end_pid |
|
Ending point id. |
|
K |
|
Number of shortest paths. |
|
directed |
|
(optional). When
|
|
heap_paths |
|
(optional). When
|
|
driving_side |
|
|
|
details |
|
(optional). When
|
Inner query
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
id |
|
Identifier of the edge. |
|
|
source |
|
Identifier of the first end point vertex of the edge. |
|
|
target |
|
Identifier of the second end point vertex of the edge. |
|
|
cost |
|
Weight of the edge (source, target)
|
|
|
reverse_cost |
|
-1 |
Weight of the edge (target, source) ,
|
Where:
- ANY-INTEGER :
-
SMALLINT, INTEGER, BIGINT
- ANY-NUMERICAL :
-
SMALLINT, INTEGER, BIGINT, REAL, FLOAT
Description of the Points SQL query
- points_sql :
-
an SQL query, which should return a set of rows with the following columns:
|
Column |
Type |
Description |
|---|---|---|
|
pid |
|
(optional) Identifier of the point.
|
|
edge_id |
|
Identifier of the "closest" edge to the point. |
|
fraction |
|
Value in <0,1> that indicates the relative postition from the first end point of the edge. |
|
side |
|
(optional) Value in [‘b’, ‘r’, ‘l’, NULL] indicating if the point is:
|
Where:
- ANY-INTEGER :
-
smallint, int, bigint
- ANY-NUMERICAL :
-
smallint, int, bigint, real, float
Result Columns
|
Column |
Type |
Description |
|---|---|---|
|
seq |
|
Row sequence. |
|
path_seq |
|
Relative position in the path of node and edge. Has value 1 for the beginning of a path. |
|
path_id |
|
Path identifier. The ordering of the paths: For two paths i, j if i < j then agg_cost(i) <= agg_cost(j). |
|
node |
|
Identifier of the node in the path. Negative values are the identifiers of a point. |
|
edge |
|
|
|
cost |
|
|
|
agg_cost |
|
|
Additional Examples
- Example :
-
Left side driving topology from point \(1\) to point \(2\) in \(2\) cycles, with details
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edge_table 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 2 4 0.7 0.6
3 1 3 -6 4 0.3 1.3
4 1 4 5 8 1 1.6
5 1 5 6 9 1 2.6
6 1 6 9 15 1 3.6
7 1 7 12 15 0.6 4.6
8 1 8 -2 -1 0 5.2
9 2 1 -1 1 0.6 0
10 2 2 2 4 0.7 0.6
11 2 3 -6 4 0.3 1.3
12 2 4 5 8 1 1.6
13 2 5 6 11 1 2.6
14 2 6 11 13 1 3.6
15 2 7 12 15 0.6 4.6
16 2 8 -2 -1 0 5.2
(16 rows)
- Example :
-
Right side driving topology from point \(1\) to point \(2\) in \(2\) cycles, with heap paths and details
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edge_table 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 1 1 1 0.4
3 1 3 2 4 0.7 1.4
4 1 4 -6 4 0.3 2.1
5 1 5 5 8 1 2.4
6 1 6 6 9 1 3.4
7 1 7 9 15 0.4 4.4
8 1 8 -2 -1 0 4.8
9 2 1 -1 1 0.4 0
10 2 2 1 1 1 0.4
11 2 3 2 4 0.7 1.4
12 2 4 -6 4 0.3 2.1
13 2 5 5 8 1 2.4
14 2 6 6 11 1 3.4
15 2 7 11 13 1 4.4
16 2 8 12 15 1 5.4
17 2 9 9 15 0.4 6.4
18 2 10 -2 -1 0 6.8
19 3 1 -1 1 0.4 0
20 3 2 1 1 1 0.4
21 3 3 2 4 0.7 1.4
22 3 4 -6 4 0.3 2.1
23 3 5 5 10 1 2.4
24 3 6 10 12 0.6 3.4
25 3 7 -3 12 0.4 4
26 3 8 11 13 1 4.4
27 3 9 12 15 1 5.4
28 3 10 9 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