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¶
[directed, heap_paths, stop_on_first, strict]
(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 |
---|---|---|
|
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 |
---|---|---|---|
|
|
|
|
KSP Optional parameters¶
Column |
Type |
Default |
Description |
---|---|---|---|
|
|
|
|
Special optional parameters¶
Column |
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
Restrictions SQL¶
Column |
Type |
Description |
---|---|---|
|
|
Sequence of edge identifiers that form a path that is not allowed to be
taken.
- Empty arrays or |
|
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 |
---|---|---|
|
|
Sequential value starting from 1. |
|
|
Path identifier.
|
|
|
Relative position in the path. Has value 1 for the beginning of a path. |
|
|
Identifier of the starting vertex. |
|
|
Identifier of the ending vertex. |
|
|
Identifier of the node in the path from |
|
|
Identifier of the edge used to go from |
|
|
Cost to traverse from |
|
|
Aggregate cost from |
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)
See Also¶
Indices and tables