pgr_trsp_withPoints  Proposed¶
pgr_trsp_withPoints
Routing Vertex/Point 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_withPoints
(One to One)pgr_trsp_withPoints
(One to Many)pgr_trsp_withPoints
(Many to One)pgr_trsp_withPoints
(Many to Many)pgr_trsp_withPoints
(Combinations)
Description¶
Modify the graph to include points defined by points_sql. Using Dijkstra algorithm, find the shortest path(s)
Characteristics:
Vertices of the graph are:
positive when it belongs to the Edges SQL
negative when it belongs to the Points SQL
Driving side can not be
b
Values are returned when there is a path.
When the starting vertex and ending vertex are the same, there is no path.
The agg_cost the non included values (v, v) is 0
When the starting vertex and ending vertex are the different and there is no path:
The agg_cost the non included values (u, v) is ∞
For optimization purposes, any duplicated value in the start_vids or end_vids are ignored.
The returned values are ordered:  start_vid ascending  end_vid ascending
Running time: \(O(start\_vids\times(V \log V + E))\)
Signatures¶
Summary
[directed, driving_side, details]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
One to One¶
[directed, driving_side, details]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
 Example:
From point \(1\) to vertex \(10\) with details on a left driving side configuration on a directed graph with details.
SELECT * FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT id, path, cost FROM restrictions$$,
$$SELECT pid, edge_id, fraction, side FROM pointsOfInterest$$,
1, 10,
details => true);
seq  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
+++++++
1  1  1  10  1  1  0.4  0
2  2  1  10  5  1  1  0.4
3  3  1  10  6  4  0.7  1.4
4  4  1  10  6  4  0.3  2.1
5  5  1  10  7  8  1  2.4
6  6  1  10  11  9  1  3.4
7  7  1  10  16  15  0.4  4.4
8  8  1  10  2  15  0.6  4.8
9  9  1  10  17  15  1  5.4
10  10  1  10  16  16  1  6.4
11  11  1  10  15  3  1  7.4
12  12  1  10  10  1  0  8.4
(12 rows)
One to Many¶
[directed, driving_side, details]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
 Example:
From point \(1\) to point \(3\) and vertex \(7\).
SELECT * FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT id, path, cost FROM restrictions$$,
$$SELECT pid, edge_id, fraction, side FROM pointsOfInterest$$,
1, ARRAY[3, 7]);
seq  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
+++++++
1  1  1  3  1  1  1.4  0
2  2  1  3  6  4  1  1.4
3  3  1  3  7  10  1  2.4
4  4  1  3  8  12  0.6  3.4
5  5  1  3  3  1  0  4
6  1  1  7  1  1  1.4  0
7  2  1  7  6  4  1  1.4
8  3  1  7  7  1  0  2.4
(8 rows)
Many to One¶
[directed, driving_side, details]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
 Example:
From point \(1\) and vertex \(6\) to point \(3\).
SELECT * FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT id, path, cost FROM restrictions$$,
$$SELECT pid, edge_id, fraction, side FROM pointsOfInterest$$,
ARRAY[1, 6], 3);
seq  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
+++++++
1  1  1  3  1  1  1.4  0
2  2  1  3  6  4  1  1.4
3  3  1  3  7  10  1  2.4
4  4  1  3  8  12  0.6  3.4
5  5  1  3  3  1  0  4
6  1  6  3  6  4  1  0
7  2  6  3  7  10  1  1
8  3  6  3  8  12  0.6  2
9  4  6  3  3  1  0  2.6
(9 rows)
Many to Many¶
[directed, driving_side, details]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
 Example:
From point \(1\) and vertex \(6\) to point \(3\) and vertex \(1\).
SELECT * FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT id, path, cost FROM restrictions$$,
$$SELECT pid, edge_id, fraction, side FROM pointsOfInterest$$,
ARRAY[1, 6], ARRAY[3, 1]);
seq  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
+++++++
1  1  1  3  1  1  1.4  0
2  2  1  3  6  4  1  1.4
3  3  1  3  7  10  1  2.4
4  4  1  3  8  12  0.6  3.4
5  5  1  3  3  1  0  4
6  1  1  1  1  1  1.4  0
7  2  1  1  6  4  1  1.4
8  3  1  1  7  8  1  2.4
9  4  1  1  11  9  1  3.4
10  5  1  1  16  15  2  4.4
11  6  1  1  16  9  1  6.4
12  7  1  1  11  8  1  7.4
13  8  1  1  7  7  1  8.4
14  9  1  1  3  6  1  9.4
15  10  1  1  1  1  0  10.4
16  1  6  3  6  4  1  0
17  2  6  3  7  10  1  1
18  3  6  3  8  12  0.6  2
19  4  6  3  3  1  0  2.6
20  1  6  1  6  4  1  0
21  2  6  1  7  10  1  1
22  3  6  1  8  12  1  2
23  4  6  1  12  13  1  3
24  5  6  1  17  15  1  4
25  6  6  1  16  9  1  5
26  7  6  1  11  8  1  6
27  8  6  1  7  7  1  7
28  9  6  1  3  6  1  8
29  10  6  1  1  1  0  9
(29 rows)
Combinations¶
[directed, driving_side, details]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
 Example:
From point \(1\) to vertex \(10\) and from vertex \(6\) to point \(3\) with right side driving configuration.
SELECT * FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT id, path, cost FROM restrictions$$,
$$SELECT pid, edge_id, fraction, side FROM pointsOfInterest$$,
$$SELECT * FROM (VALUES (1, 10), (6, 3)) AS t(source, target)$$,
driving_side => 'r',
details => true);
seq  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
+++++++
1  1  1  10  1  1  0.4  0
2  2  1  10  5  1  1  0.4
3  3  1  10  6  4  0.7  1.4
4  4  1  10  6  4  0.3  2.1
5  5  1  10  7  8  1  2.4
6  6  1  10  11  9  1  3.4
7  7  1  10  16  15  0.4  4.4
8  8  1  10  2  15  0.6  4.8
9  9  1  10  17  15  1  5.4
10  10  1  10  16  16  1  6.4
11  11  1  10  15  3  1  7.4
12  12  1  10  10  1  0  8.4
13  1  6  3  6  4  0.7  0
14  2  6  3  6  4  0.3  0.7
15  3  6  3  7  10  1  1
16  4  6  3  8  12  0.6  2
17  5  6  3  3  1  0  2.6
(17 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 





With points optional parameters¶
Parameter 
Type 
Default 
Description 




Value in [





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
Points SQL¶
Parameter 
Type 
Default 
Description 


ANYINTEGER 
value 
Identifier of the point.


ANYINTEGER 
Identifier of the “closest” edge to the point. 


ANYNUMERICAL 
Value in <0,1> that indicates the relative postition from the first end point of the edge. 




Value in [

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 
Additional Examples¶
Use pgr_findCloseEdges
for points on the fly¶
Using pgr_findCloseEdges:
Find the routes from vertex \(1\) to the two closest locations on the graph of point (2.9, 1.8).
SELECT * FROM pgr_trsp_withPoints(
$e$ SELECT * FROM edges $e$,
$r$ SELECT id, path, cost FROM restrictions $r$,
$p$ SELECT edge_id, round(fraction::numeric, 2) AS fraction, side
FROM pgr_findCloseEdges(
$$SELECT id, geom FROM edges$$,
(SELECT ST_POINT(2.9, 1.8)),
0.5, cap => 2)
$p$,
1, ARRAY[1, 2],
driving_side => 'r');
seq  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
+++++++
1  1  1  2  1  6  1  0
2  2  1  2  3  7  1  1
3  3  1  2  7  8  0.9  2
4  4  1  2  2  1  0  2.9
5  1  1  1  1  6  1  0
6  2  1  1  3  7  1  1
7  3  1  1  7  8  2  2
8  4  1  1  7  10  1  4
9  5  1  1  8  12  1  5
10  6  1  1  12  13  1  6
11  7  1  1  17  15  1  7
12  8  1  1  16  16  1  8
13  9  1  1  15  3  1  9
14  10  1  1  10  5  0.8  10
15  11  1  1  1  1  0  10.8
(15 rows)
Point \(1\) corresponds to the closest edge from point (2.9, 1.8).
Point \(2\) corresponds to the next close edge from point (2.9, 1.8).
Pass in front or visits.¶
Which path (if any) passes in front of point \(6\) or vertex \(11\) with right side driving topology.
SELECT ('('  start_vid  ' => '  end_vid ') at '  path_seq  'th step:')::TEXT AS path_at,
CASE WHEN edge = 1 THEN ' visits'
ELSE ' passes in front of'
END as status,
CASE WHEN node < 0 THEN 'Point'
ELSE 'Vertex'
END as is_a,
abs(node) as id
FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT id, path, cost FROM restrictions$$,
$$SELECT pid, edge_id, fraction, side FROM pointsOfInterest$$,
ARRAY[5, 1], ARRAY[6, 3, 6, 10, 11],
driving_side => 'r',
details => true)
WHERE node IN (6, 11);
path_at  status  is_a  id
+++
(1 => 6) at 4th step:  visits  Point  6
(1 => 3) at 4th step:  passes in front of  Point  6
(1 => 10) at 4th step:  passes in front of  Point  6
(1 => 10) at 6th step:  passes in front of  Vertex  11
(1 => 11) at 4th step:  passes in front of  Point  6
(1 => 11) at 6th step:  visits  Vertex  11
(5 => 6) at 3th step:  visits  Point  6
(5 => 3) at 3th step:  passes in front of  Point  6
(5 => 10) at 3th step:  passes in front of  Point  6
(5 => 11) at 3th step:  passes in front of  Point  6
(5 => 11) at 5th step:  visits  Vertex  11
(11 rows)
Show details on undirected graph.¶
From point \(1\) and vertex \(6\) to point \(3\) to vertex \(1\) on an undirected graph, with details.
SELECT * FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT id, path, cost FROM restrictions$$,
$$SELECT pid, edge_id, fraction, side FROM pointsOfInterest$$,
ARRAY[1, 6], ARRAY[3, 1],
directed => false,
details => true);
seq  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
+++++++
1  1  1  3  1  1  0.6  0
2  2  1  3  6  4  0.7  0.6
3  3  1  3  6  4  0.3  1.3
4  4  1  3  7  10  1  1.6
5  5  1  3  8  12  0.6  2.6
6  6  1  3  3  1  0  3.2
7  1  1  1  1  1  0.6  0
8  2  1  1  6  4  0.7  0.6
9  3  1  1  6  4  0.3  1.3
10  4  1  1  7  7  1  1.6
11  5  1  1  3  6  0.7  2.6
12  6  1  1  4  6  0.3  3.3
13  7  1  1  1  1  0  3.6
14  1  6  3  6  4  0.7  0
15  2  6  3  6  4  0.3  0.7
16  3  6  3  7  10  1  1
17  4  6  3  8  12  0.6  2
18  5  6  3  3  1  0  2.6
19  1  6  1  6  4  0.7  0
20  2  6  1  6  4  0.3  0.7
21  3  6  1  7  7  1  1
22  4  6  1  3  6  0.7  2
23  5  6  1  4  6  0.3  2.7
24  6  6  1  1  1  0  3
(24 rows)
See Also¶
Indices and tables