pgr_trsp - Proposed¶
pgr_trsp - routing vertices with restrictions.
Boost Graph Inside¶
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.4.0
New proposed signatures:
pgr_trsp(One to One)pgr_trsp(One to Many)pgr_trsp(Many to One)pgr_trsp(Many to Many)pgr_trsp(Combinations)
Deprecated signatures:
pgr_trsp(text,integer,integer,boolean,boolean,text)pgr_trsp(text,integer,float,integer,float,boolean,boolean,text)pgr_trspViaVertices(text,anyarray,boolean,boolean,text)pgr_trspviaedges(text,integer[],double precision[],boolean,boolean,text)
Version 2.1.0
New prototypes:
pgr_trspViaVerticespgr_trspViaEdges
Version 2.0.0
Official function
Description¶
Turn restricted shortest path (TRSP) is an algorithm that receives turn restrictions in form of a query like those found in real world navigable road networks.
The main characteristics are:
It does no guarantee the shortest path as it might contain restriction paths.
The general algorithm is as follows:
Execute a Dijkstra.
If the solution passes thru a restriction then.
Execute the TRSP algorithm with restrictions.
Signatures¶
Proposed
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)One to One¶
pgr_trsp(Edges SQL, Restrictions SQL, start vid, end vid, [directed])
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- Example:
From vertex \(6\) to vertex \(10\) on an undirected graph.
SELECT * FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
6, 10,
false);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 10 | 6 | 2 | 1 | 0
2 | 2 | 6 | 10 | 10 | -1 | 0 | 1
(2 rows)
One to Many¶
pgr_trsp(Edges SQL, Restrictions SQL, start vid, end vids, [directed])
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- Example:
From vertex \(6\) to vertices \(\{10, 1\}\) on an undirected graph.
SELECT * FROM pgr_trsp(
$$SELECT id, source, target, cost FROM edges$$,
$$SELECT * FROM restrictions$$,
6, ARRAY[10, 1],
false);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 1 | 6 | 4 | 1 | 0
2 | 2 | 6 | 1 | 7 | 10 | 1 | 1
3 | 3 | 6 | 1 | 8 | 12 | 1 | 2
4 | 4 | 6 | 1 | 12 | 11 | 1 | 3
5 | 5 | 6 | 1 | 11 | 8 | 1 | 4
6 | 6 | 6 | 1 | 7 | 7 | 1 | 5
7 | 7 | 6 | 1 | 3 | 6 | 1 | 6
8 | 8 | 6 | 1 | 1 | -1 | 0 | 7
9 | 1 | 6 | 10 | 6 | 4 | 1 | 0
10 | 2 | 6 | 10 | 7 | 8 | 1 | 1
11 | 3 | 6 | 10 | 11 | 5 | 1 | 2
12 | 4 | 6 | 10 | 10 | -1 | 0 | 3
(12 rows)
Many to One¶
pgr_trsp(Edges SQL, Restrictions SQL, start vids, end vid, [directed])
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- Example:
From vertices \(\{6, 1\}\) to vertex \(8\) on a directed graph.
SELECT * FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[6, 1], 8);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 8 | 1 | 6 | 1 | 0
2 | 2 | 1 | 8 | 3 | 7 | 1 | 1
3 | 3 | 1 | 8 | 7 | 10 | 101 | 2
4 | 4 | 1 | 8 | 8 | -1 | 0 | 103
5 | 1 | 6 | 8 | 6 | 4 | 1 | 0
6 | 2 | 6 | 8 | 7 | 10 | 1 | 1
7 | 3 | 6 | 8 | 8 | -1 | 0 | 2
(7 rows)
Many to Many¶
pgr_trsp(Edges SQL, Restrictions SQL, start vids, end vids,
[directed])
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- Example:
From vertices \(\{6, 1\}\) to vertices \(\{10, 8\}\) on an undirected graph.
SELECT * FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[6, 1], ARRAY[10, 8],
false);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 8 | 1 | 6 | 1 | 0
2 | 2 | 1 | 8 | 3 | 7 | 1 | 1
3 | 3 | 1 | 8 | 7 | 4 | 1 | 2
4 | 4 | 1 | 8 | 6 | 2 | 1 | 3
5 | 5 | 1 | 8 | 10 | 5 | 1 | 4
6 | 6 | 1 | 8 | 11 | 11 | 1 | 5
7 | 7 | 1 | 8 | 12 | 12 | 1 | 6
8 | 8 | 1 | 8 | 8 | -1 | 0 | 7
9 | 1 | 1 | 10 | 1 | 6 | 1 | 0
10 | 2 | 1 | 10 | 3 | 7 | 1 | 1
11 | 3 | 1 | 10 | 7 | 4 | 1 | 2
12 | 4 | 1 | 10 | 6 | 2 | 1 | 3
13 | 5 | 1 | 10 | 10 | -1 | 0 | 4
14 | 1 | 6 | 8 | 6 | 4 | 1 | 0
15 | 2 | 6 | 8 | 7 | 10 | 1 | 1
16 | 3 | 6 | 8 | 8 | -1 | 0 | 2
17 | 1 | 6 | 10 | 6 | 2 | 1 | 0
18 | 2 | 6 | 10 | 10 | -1 | 0 | 1
(18 rows)
Combinations¶
pgr_trsp(Edges SQL, Restrictions SQL, Combinations SQL, [directed])
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- Example:
Using a combinations table on an undirected graph.
SELECT * FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
$$SELECT * FROM (VALUES (6, 10), (6, 1), (6, 8), (1, 8)) AS combinations (source, target)$$);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 8 | 1 | 6 | 1 | 0
2 | 2 | 1 | 8 | 3 | 7 | 1 | 1
3 | 3 | 1 | 8 | 7 | 10 | 101 | 2
4 | 4 | 1 | 8 | 8 | -1 | 0 | 103
5 | 1 | 6 | 1 | 6 | 4 | 1 | 0
6 | 2 | 6 | 1 | 7 | 10 | 1 | 1
7 | 3 | 6 | 1 | 8 | 12 | 1 | 2
8 | 4 | 6 | 1 | 12 | 13 | 1 | 3
9 | 5 | 6 | 1 | 17 | 15 | 1 | 4
10 | 6 | 6 | 1 | 16 | 9 | 1 | 5
11 | 7 | 6 | 1 | 11 | 8 | 1 | 6
12 | 8 | 6 | 1 | 7 | 7 | 1 | 7
13 | 9 | 6 | 1 | 3 | 6 | 1 | 8
14 | 10 | 6 | 1 | 1 | -1 | 0 | 9
15 | 1 | 6 | 8 | 6 | 4 | 1 | 0
16 | 2 | 6 | 8 | 7 | 10 | 1 | 1
17 | 3 | 6 | 8 | 8 | -1 | 0 | 2
18 | 1 | 6 | 10 | 6 | 4 | 1 | 0
19 | 2 | 6 | 10 | 7 | 10 | 1 | 1
20 | 3 | 6 | 10 | 8 | 12 | 1 | 2
21 | 4 | 6 | 10 | 12 | 13 | 1 | 3
22 | 5 | 6 | 10 | 17 | 15 | 1 | 4
23 | 6 | 6 | 10 | 16 | 16 | 1 | 5
24 | 7 | 6 | 10 | 15 | 3 | 1 | 6
25 | 8 | 6 | 10 | 10 | -1 | 0 | 7
(25 rows)
Parameters¶
Column |
Type |
Description |
|---|---|---|
|
SQL query as described. |
|
|
SQL query as described. |
|
|
Combinations SQL as described below |
|
start vid |
ANY-INTEGER |
Identifier of the departure vertex. |
start vids |
|
Array of identifiers of destination vertices. |
end vid |
ANY-INTEGER |
Identifier of the departure vertex. |
end vids |
|
Array of identifiers of destination vertices. |
Where:
- ANY-INTEGER:
SMALLINT,INTEGER,BIGINT
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
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 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 |
See Also¶
Indices and tables