pgr_turnRestrictedPath - Experimental¶
pgr_turnRestrictedPath
Using Yen’s algorithm Vertex -Vertex routing with
restrictions
Warning
Possible server crash
- These functions might create a server crash
Warning
Experimental functions
- They are not officially of the current release.
- They likely will not be officially be part of the next release:
- The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
- Name might change.
- Signature might change.
- Functionality might change.
- pgTap tests might be missing.
- Might need c/c++ coding.
- May lack documentation.
- Documentation if any might need to be rewritten.
- Documentation examples might need to be automatically generated.
- Might need a lot of feedback from the comunity.
- Might depend on a proposed function of pgRouting
- Might depend on a deprecated function of pgRouting
Availability
- Version 3.0.0
- New Experimental function
Description¶
Using Yen’s algorithm to obtain K shortest paths and analyze the paths to select the paths that do not use the restrictions
Signatures¶
pgr_turnRestrictedPath(Edges SQL, Restrictions SQL, Start vid, End vid, K cycles, [, directed] [,heap_paths] [, stop_on_first] [,strict]) RETURNS SETOF (seq, path_id, path_seq, node, edge, cost, agg_cost)
Example: | From vertex \(3\) to vertex \(8\) on a directed graph |
---|
SELECT * FROM pgr_turnRestrictedPath(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM new_restrictions$$,
3, 8, 3);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 3 | 7 | 1 | Infinity
2 | 1 | 2 | 7 | 10 | 1 | 1
3 | 1 | 3 | 8 | -1 | 0 | 2
(3 rows)
Parameters¶
Column | Type | Description |
---|---|---|
Edges SQL | TEXT |
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 |
|
Special optional parameters¶
Column | Type | Default | Description |
---|---|---|---|
stop_on_first |
BOOLEAN |
true |
|
strict |
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 |
Restrictions SQL¶
Column | Type | Description |
---|---|---|
path |
ARRAY[ ANY-INTEGER ] |
Sequence of edge identifiers that form a path that is not allowed to be
taken.
- Empty arrays or NULL arrays are ignored.
- Arrays that have a NULL element will raise an exception. |
Cost |
ANY-NUMERICAL | Cost of taking the forbidden path. |
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. |
start_vid |
BIGINT |
Identifier of the starting vertex. |
end_vid |
BIGINT |
Identifier of the ending vertex. |
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 node using edge to the next node in the
path sequence. |
agg_cost |
FLOAT |
Aggregate cost from start_vid to node . |
Additional Examples¶
Example: | From vertex \(3\) to \(8\) with strict flag on. |
---|
No results because the only path available follows a restriction.
SELECT * FROM pgr_turnRestrictedPath(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM new_restrictions$$,
3, 8, 3,
strict => true);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
(0 rows)
Example: | From vertex \(3\) to vertex \(8\) on an undirected graph |
---|
SELECT * FROM pgr_turnRestrictedPath(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM new_restrictions$$,
3, 8, 3,
directed => false);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 3 | 7 | 1 | 0
2 | 1 | 2 | 7 | 4 | 1 | 1
3 | 1 | 3 | 6 | 2 | 1 | 2
4 | 1 | 4 | 10 | 5 | 1 | 3
5 | 1 | 5 | 11 | 11 | 1 | 4
6 | 1 | 6 | 12 | 12 | 1 | 5
7 | 1 | 7 | 8 | -1 | 0 | 6
(7 rows)
Example: | From vertex \(3\) to vertex \(8\) with more alternatives |
---|
SELECT * FROM pgr_turnRestrictedPath(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM new_restrictions$$,
3, 8, 3,
directed => false,
heap_paths => true,
stop_on_first => false);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 3 | 7 | 1 | 0
2 | 1 | 2 | 7 | 4 | 1 | 1
3 | 1 | 3 | 6 | 2 | 1 | 2
4 | 1 | 4 | 10 | 5 | 1 | 3
5 | 1 | 5 | 11 | 11 | 1 | 4
6 | 1 | 6 | 12 | 12 | 1 | 5
7 | 1 | 7 | 8 | -1 | 0 | 6
8 | 2 | 1 | 3 | 7 | 1 | 0
9 | 2 | 2 | 7 | 8 | 1 | 1
10 | 2 | 3 | 11 | 9 | 1 | 2
11 | 2 | 4 | 16 | 15 | 1 | 3
12 | 2 | 5 | 17 | 13 | 1 | 4
13 | 2 | 6 | 12 | 12 | 1 | 5
14 | 2 | 7 | 8 | -1 | 0 | 6
(14 rows)