pgr_trsp - Proposed¶
pgr_trsp - routing vertices with restrictions.
Disponibilidad
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)
Signature
pgr_trsp(text,integer,integer,boolean,boolean,text)is deprecatedSignature
pgr_trsp(text,integer,float,integer,float,boolean,boolean,text)is deprecatedSignature
pgr_trspViaVertices(text,anyarray,boolean,boolean,text)is deprecatedSignature
pgr_trspviaedges(text,integer[],double precision[],boolean,boolean,text)is deprecated
Versión 2.1.0
Nuevo Via prototypes
pgr_trspViaVerticespgr_trspViaEdges
Versión 2.0.0
Función oficial
Contents
Descripción¶
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:
Automatic detection of
reverse_costcolumnAccepts ANY-INTEGER and ANY-NUMERICAL on input columns
All variations give as result the same columns
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¶
Summary
Proposed
Advertencia
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.
pgr_trsp(Edges SQL, Restrictions SQL, start vid, end vid [, directed]) -- Proposed on v3.4 pgr_trsp(Edges SQL, Restrictions SQL, start vid, end vids [, directed]) -- Proposed on v3.4 pgr_trsp(Edges SQL, Restrictions SQL, start vids, end vid [, directed]) -- Proposed on v3.4 pgr_trsp(Edges SQL, Restrictions SQL, start vids, end vids [, directed]) -- Proposed on v3.4 pgr_trsp(Edges SQL, Restrictions SQL, Combinations SQL, [, directed]) -- Proposed on v3.4 RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) OR EMPTY SET
One to One¶
pgr_trsp(Edges SQL, Restrictions SQL, start vid, end vid [, directed]) -- Proposed on v3.4 RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) OR EMPTY SET
- Ejemplo
From vertex \(2\) to vertex \(3\) on an undirected graph
SELECT * FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edge_table$$,
$$SELECT path, cost FROM restrictions$$,
2, 3,
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 2 | 3 | 2 | 2 | 1 | 0
2 | 2 | 2 | 3 | 3 | -1 | 0 | 1
(2 rows)
One to Many¶
pgr_trsp(Edges SQL, Restrictions SQL, start vid, end vids [, directed]) -- Proposed on v3.4 RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) OR EMPTY SET
- Ejemplo
From vertex \(2\) to vertices \(\{3, 7\}\) on an undirected graph
SELECT * FROM pgr_trsp(
$$SELECT id, source, target, cost FROM edge_table$$,
$$SELECT * FROM restrictions$$,
2, ARRAY[3,7],
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 2 | 3 | 2 | 4 | 1 | 0
2 | 2 | 2 | 3 | 5 | 8 | 1 | 1
3 | 3 | 2 | 3 | 6 | 5 | 1 | 2
4 | 4 | 2 | 3 | 3 | -1 | 0 | 3
5 | 1 | 2 | 7 | 2 | 4 | 1 | 0
6 | 2 | 2 | 7 | 5 | 10 | 1 | 1
7 | 3 | 2 | 7 | 10 | 12 | 1 | 2
8 | 4 | 2 | 7 | 11 | 11 | 1 | 3
9 | 5 | 2 | 7 | 6 | 8 | 1 | 4
10 | 6 | 2 | 7 | 5 | 7 | 1 | 5
11 | 7 | 2 | 7 | 8 | 6 | 1 | 6
12 | 8 | 2 | 7 | 7 | -1 | 0 | 7
(12 rows)
Many to One¶
pgr_trsp(Edges SQL, Restrictions SQL, start vids, end vid [, directed]) -- Proposed on v3.4 RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) OR EMPTY SET
- Ejemplo
From vertices \(\{2, 7\}\) to vertex \(10\) on a directed graph
SELECT * FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edge_table$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[2,7], 10
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 2 | 10 | 2 | 4 | 1 | 0
2 | 2 | 2 | 10 | 5 | 10 | 1 | 1
3 | 3 | 2 | 10 | 10 | -1 | 0 | 2
4 | 1 | 7 | 10 | 7 | 6 | 1 | 0
5 | 2 | 7 | 10 | 8 | 7 | 1 | 1
6 | 3 | 7 | 10 | 5 | 10 | 101 | 2
7 | 4 | 7 | 10 | 10 | -1 | 0 | 103
(7 rows)
Many to Many¶
pgr_trsp(Edges SQL, Restrictions SQL, start vids, end vids [, directed]) -- Proposed on v3.4 RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) OR EMPTY SET
- Ejemplo
From vertices \(\{2, 7\}\) to vertices \(\{3, 10\}\) on an undirected graph
SELECT * FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edge_table$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[2,7], ARRAY[3,10],
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 2 | 3 | 2 | 2 | 1 | 0
2 | 2 | 2 | 3 | 3 | -1 | 0 | 1
3 | 1 | 2 | 10 | 2 | 4 | 1 | 0
4 | 2 | 2 | 10 | 5 | 10 | 1 | 1
5 | 3 | 2 | 10 | 10 | -1 | 0 | 2
6 | 1 | 7 | 3 | 7 | 6 | 1 | 0
7 | 2 | 7 | 3 | 8 | 7 | 1 | 1
8 | 3 | 7 | 3 | 5 | 4 | 1 | 2
9 | 4 | 7 | 3 | 2 | 2 | 1 | 3
10 | 5 | 7 | 3 | 3 | -1 | 0 | 4
11 | 1 | 7 | 10 | 7 | 6 | 1 | 0
12 | 2 | 7 | 10 | 8 | 7 | 1 | 1
13 | 3 | 7 | 10 | 5 | 8 | 1 | 2
14 | 4 | 7 | 10 | 6 | 5 | 1 | 3
15 | 5 | 7 | 10 | 3 | 2 | 1 | 4
16 | 6 | 7 | 10 | 2 | 4 | 1 | 5
17 | 7 | 7 | 10 | 5 | 10 | 1 | 6
18 | 8 | 7 | 10 | 10 | -1 | 0 | 7
(18 rows)
Combinations¶
pgr_trsp(Edges SQL, Restrictions SQL, Combinations SQL, [, directed]) -- Proposed on v3.4 RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) OR EMPTY SET
- Ejemplo
Using a combinations table on an undirected graph
SELECT * FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edge_table$$,
$$SELECT path, cost FROM restrictions$$,
$$SELECT * FROM (VALUES (2, 3), (2, 7), (2, 10), (7, 10)) AS combinations (source, target)$$
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 2 | 3 | 2 | 4 | 1 | 0
2 | 2 | 2 | 3 | 5 | 10 | 1 | 1
3 | 3 | 2 | 3 | 10 | 12 | 1 | 2
4 | 4 | 2 | 3 | 11 | 13 | 1 | 3
5 | 5 | 2 | 3 | 12 | 15 | 1 | 4
6 | 6 | 2 | 3 | 9 | 16 | 1 | 5
7 | 7 | 2 | 3 | 4 | 3 | 1 | 6
8 | 8 | 2 | 3 | 3 | -1 | 0 | 7
9 | 1 | 2 | 7 | 2 | 4 | 1 | 0
10 | 2 | 2 | 7 | 5 | 10 | 1 | 1
11 | 3 | 2 | 7 | 10 | 12 | 1 | 2
12 | 4 | 2 | 7 | 11 | 13 | 1 | 3
13 | 5 | 2 | 7 | 12 | 15 | 1 | 4
14 | 6 | 2 | 7 | 9 | 9 | 1 | 5
15 | 7 | 2 | 7 | 6 | 8 | 1 | 6
16 | 8 | 2 | 7 | 5 | 7 | 1 | 7
17 | 9 | 2 | 7 | 8 | 6 | 1 | 8
18 | 10 | 2 | 7 | 7 | -1 | 0 | 9
19 | 1 | 2 | 10 | 2 | 4 | 1 | 0
20 | 2 | 2 | 10 | 5 | 10 | 1 | 1
21 | 3 | 2 | 10 | 10 | -1 | 0 | 2
22 | 1 | 7 | 10 | 7 | 6 | 1 | 0
23 | 2 | 7 | 10 | 8 | 7 | 1 | 1
24 | 3 | 7 | 10 | 5 | 10 | 101 | 2
25 | 4 | 7 | 10 | 10 | -1 | 0 | 103
(25 rows)
Parameters¶
Parameter |
Type |
Default |
Descripción |
|---|---|---|---|
|
Edges SQL as described below |
||
|
Restrictions SQL as described below |
||
|
Combinations SQL as described below |
||
start vid |
|
Identifier of the starting vertex of the path. |
|
start vids |
|
Array of identifiers of starting vertices. |
|
end vid |
|
Identifier of the ending vertex of the path. |
|
end vids |
|
Array of identifiers of ending vertices. |
|
|
|
|
|
Inner queries¶
Edges SQL¶
Column |
Type |
Default |
Descripción |
|---|---|---|---|
|
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 |
Descripción |
|---|---|---|
|
|
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 |
Descripción |
|---|---|---|
|
ANY-INTEGER |
Identifier of the departure vertex. |
|
ANY-INTEGER |
Identifier of the arrival vertex. |
Where:
- ANY-INTEGER
SMALLINT,INTEGER,BIGINT
Return Columns¶
Set of (seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost,
agg_cost)
Column |
Type |
Descripción |
|---|---|---|
|
|
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. Returned when multiple starting vetrices are in the query. |
|
|
Identifier of the ending vertex. Returned when multiple ending vertices are in the query. |
|
|
Identifier of the node in the path from |
|
|
Identifier of the edge used to go from |
|
|
Cost to traverse from |
|
|
Aggregate cost from |
Ver también¶
Índices y tablas