pgr_trsp  Proposed¶
pgr_trsp
 routing vertices with restrictions.
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 ANYINTEGER and ANYNUMERICAL
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_trspViaVertices
pgr_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 
ANYINTEGER 
Identifier of the departure vertex. 
start vids 

Array of identifiers of destination vertices. 
end vid 
ANYINTEGER 
Identifier of the departure vertex. 
end vids 

Array of identifiers of destination vertices. 
Where:
 ANYINTEGER:
SMALLINT
,INTEGER
,BIGINT
Optional parameters¶
Column 
Type 
Default 
Description 





Inner Queries¶
Edges SQL¶
Column 
Type 
Default 
Description 


ANYINTEGER 
Identifier of the edge. 


ANYINTEGER 
Identifier of the first end point vertex of the edge. 


ANYINTEGER 
Identifier of the second end point vertex of the edge. 


ANYNUMERICAL 
Weight of the edge ( 


ANYNUMERICAL 
1 
Weight of the edge (

Where:
 ANYINTEGER:
SMALLINT
,INTEGER
,BIGINT
 ANYNUMERICAL:
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 

ANYNUMERICAL 
Cost of taking the forbidden path. 
Where:
 ANYINTEGER:
SMALLINT
,INTEGER
,BIGINT
 ANYNUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Combinations SQL¶
Parameter 
Type 
Description 


ANYINTEGER 
Identifier of the departure vertex. 

ANYINTEGER 
Identifier of the arrival vertex. 
Where:
 ANYINTEGER:
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