pgr_withPoints
 Proposed¶
pgr_withPoints
 Returns the shortest path in a graph with additional
temporary vertices.
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.2.0
New proposed function:
pgr_withPoints(Combinations)
Version 2.2.0
New proposed function
Description¶
Modify the graph to include points defined by points_sql. Using Dijkstra algorithm, find the shortest path(s)
The main characteristics are:
Process is done only on edges with positive costs.
Vertices of the graph are:
positive when it belongs to the edges_sql
negative when it belongs to the points_sql
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_pid], [end_pid], node, edge, cost, agg_cost)
One to One¶
(seq, path_seq, node, edge, cost, agg_cost)
 Example:
From point \(1\) to vertex \(10\) with details
SELECT * FROM pgr_withPoints(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
1, 10,
details => true);
seq  path_seq  node  edge  cost  agg_cost
+++++
1  1  1  1  0.6  0
2  2  6  4  0.7  0.6
3  3  6  4  0.3  1.3
4  4  7  8  1  1.6
5  5  11  9  1  2.6
6  6  16  16  1  3.6
7  7  15  3  1  4.6
8  8  10  1  0  5.6
(8 rows)
One to Many¶
(seq, path_seq, end_pid, node, edge, cost, agg_cost)
 Example:
From point \(1\) to point \(3\) and vertex \(7\) on an undirected graph
SELECT * FROM pgr_withPoints(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
1, ARRAY[3, 7],
directed => false);
seq  path_seq  end_pid  node  edge  cost  agg_cost
++++++
1  1  3  1  1  0.6  0
2  2  3  6  4  1  0.6
3  3  3  7  10  1  1.6
4  4  3  8  12  0.6  2.6
5  5  3  3  1  0  3.2
6  1  7  1  1  0.6  0
7  2  7  6  4  1  0.6
8  3  7  7  1  0  1.6
(8 rows)
Many to One¶
(seq, path_seq, start_pid, node, edge, cost, agg_cost)
 Example:
From point \(1\) and vertex \(6\) to point \(3\)
SELECT * FROM pgr_withPoints(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
ARRAY[1, 6], 3);
seq  path_seq  start_pid  node  edge  cost  agg_cost
++++++
1  1  1  1  1  0.6  0
2  2  1  6  4  1  0.6
3  3  1  7  10  1  1.6
4  4  1  8  12  0.6  2.6
5  5  1  3  1  0  3.2
6  1  6  6  4  1  0
7  2  6  7  10  1  1
8  3  6  8  12  0.6  2
9  4  6  3  1  0  2.6
(9 rows)
Many to Many¶
(seq, path_seq, start_pid, end_pid, node, edge, cost, agg_cost)
 Example:
From point \(1\) and vertex \(6\) to point \(3\) and vertex \(1\)
SELECT * FROM pgr_withPoints(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
ARRAY[1, 6], ARRAY[3, 1]);
seq  path_seq  start_pid  end_pid  node  edge  cost  agg_cost
+++++++
1  1  1  3  1  1  0.6  0
2  2  1  3  6  4  1  0.6
3  3  1  3  7  10  1  1.6
4  4  1  3  8  12  0.6  2.6
5  5  1  3  3  1  0  3.2
6  1  1  1  1  1  0.6  0
7  2  1  1  6  4  1  0.6
8  3  1  1  7  7  1  1.6
9  4  1  1  3  6  1  2.6
10  5  1  1  1  1  0  3.6
11  1  6  3  6  4  1  0
12  2  6  3  7  10  1  1
13  3  6  3  8  12  0.6  2
14  4  6  3  3  1  0  2.6
15  1  6  1  6  4  1  0
16  2  6  1  7  7  1  1
17  3  6  1  3  6  1  2
18  4  6  1  1  1  0  3
(18 rows)
Combinations¶
(seq, path_seq, start_pid, end_pid, node, edge, cost, agg_cost)
 Example:
Two combinations
From point \(1\) to vertex \(10\), and from vertex \(6\) to point \(3\) with right side driving.
SELECT * FROM pgr_withPoints(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
'SELECT * FROM (VALUES (1, 10), (6, 3)) AS combinations(source, target)',
driving_side => 'r', details => true);
seq  path_seq  start_pid  end_pid  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  16  1  4.4
8  8  1  10  15  3  1  5.4
9  9  1  10  10  1  0  6.4
10  1  6  3  6  4  0.7  0
11  2  6  3  6  4  0.3  0.7
12  3  6  3  7  10  1  1
13  4  6  3  8  12  0.6  2
14  5  6  3  3  1  0  2.6
(14 rows)
Parameters¶
Column 
Type 
Description 


Edges SQL as described below 


Points SQL as described below 


Combinations SQL as described below 

start vid 

Identifier of the starting vertex of the path. Negative value is for point’s identifier. 
start vids 

Array of identifiers of starting vertices. Negative values are for point’s identifiers. 
end vid 

Identifier of the ending vertex of the path. Negative value is for point’s identifier. 
end vids 

Array of identifiers of ending vertices. Negative values are for point’s identifiers. 
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
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_seq [, start_pid] [, end_pid], node, edge, cost,
agg_cost)
Column 
Type 
Description 



Sequential value starting from 1. 


Relative position in the path.



Identifier of a starting vertex/point of the path.



Identifier of an ending vertex/point of the path.



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 in the Points SQL.¶
Find the routes from vertex \(1\) to the two closest locations on the graph of point (2.9, 1.8).
SELECT * FROM pgr_withPoints(
$e$ SELECT * FROM edges $e$,
$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]);
seq  path_seq  end_pid  node  edge  cost  agg_cost
++++++
1  1  2  1  6  1  0
2  2  2  3  7  1  1
3  3  2  7  8  0.9  2
4  4  2  2  1  0  2.9
5  1  1  1  6  1  0
6  2  1  3  7  1  1
7  3  1  7  8  1  2
8  4  1  11  9  1  3
9  5  1  16  16  1  4
10  6  1  15  3  1  5
11  7  1  10  5  0.8  6
12  8  1  1  1  0  6.8
(12 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).
Usage variations¶
All the examples are about traveling from point \(1\) and vertex \(5\) to points \(\{2, 3, 6\}\) and vertices \(\{10, 11\}\)
SELECT *
FROM pgr_withPoints(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
ARRAY[5, 1], ARRAY[2, 3, 6, 10, 11],
driving_side => 'r', details => true);
seq  path_seq  start_pid  end_pid  node  edge  cost  agg_cost
+++++++
1  1  1  6  1  1  0.4  0
2  2  1  6  5  1  1  0.4
3  3  1  6  6  4  0.7  1.4
4  4  1  6  6  1  0  2.1
5  1  1  3  1  1  0.4  0
6  2  1  3  5  1  1  0.4
7  3  1  3  6  4  0.7  1.4
8  4  1  3  6  4  0.3  2.1
9  5  1  3  7  10  1  2.4
10  6  1  3  8  12  0.6  3.4
11  7  1  3  3  1  0  4
12  1  1  2  1  1  0.4  0
13  2  1  2  5  1  1  0.4
14  3  1  2  6  4  0.7  1.4
15  4  1  2  6  4  0.3  2.1
16  5  1  2  7  8  1  2.4
17  6  1  2  11  9  1  3.4
18  7  1  2  16  15  0.4  4.4
19  8  1  2  2  1  0  4.8
20  1  1  10  1  1  0.4  0
21  2  1  10  5  1  1  0.4
22  3  1  10  6  4  0.7  1.4
23  4  1  10  6  4  0.3  2.1
24  5  1  10  7  8  1  2.4
25  6  1  10  11  9  1  3.4
26  7  1  10  16  16  1  4.4
27  8  1  10  15  3  1  5.4
28  9  1  10  10  1  0  6.4
29  1  1  11  1  1  0.4  0
30  2  1  11  5  1  1  0.4
31  3  1  11  6  4  0.7  1.4
32  4  1  11  6  4  0.3  2.1
33  5  1  11  7  8  1  2.4
34  6  1  11  11  1  0  3.4
35  1  5  6  5  1  1  0
36  2  5  6  6  4  0.7  1
37  3  5  6  6  1  0  1.7
38  1  5  3  5  1  1  0
39  2  5  3  6  4  0.7  1
40  3  5  3  6  4  0.3  1.7
41  4  5  3  7  10  1  2
42  5  5  3  8  12  0.6  3
43  6  5  3  3  1  0  3.6
44  1  5  2  5  1  1  0
45  2  5  2  6  4  0.7  1
46  3  5  2  6  4  0.3  1.7
47  4  5  2  7  8  1  2
48  5  5  2  11  9  1  3
49  6  5  2  16  15  0.4  4
50  7  5  2  2  1  0  4.4
51  1  5  10  5  1  1  0
52  2  5  10  6  4  0.7  1
53  3  5  10  6  4  0.3  1.7
54  4  5  10  7  8  1  2
55  5  5  10  11  9  1  3
56  6  5  10  16  16  1  4
57  7  5  10  15  3  1  5
58  8  5  10  10  1  0  6
59  1  5  11  5  1  1  0
60  2  5  11  6  4  0.7  1
61  3  5  11  6  4  0.3  1.7
62  4  5  11  7  8  1  2
63  5  5  11  11  1  0  3
(63 rows)
Passes in front or visits with right side driving.¶
For point \(6\) and vertex \(11\).
SELECT (start_pid  ' > '  end_pid ' 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_withPoints(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
ARRAY[5, 1], ARRAY[2, 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 > 2 at 4th step  passes in front of  Point  6
1 > 2 at 6th step  passes in front of  Vertex  11
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 > 2 at 3th step  passes in front of  Point  6
5 > 2 at 5th step  passes in front of  Vertex  11
5 > 10 at 3th step  passes in front of  Point  6
5 > 10 at 5th step  passes in front of  Vertex  11
5 > 11 at 3th step  passes in front of  Point  6
5 > 11 at 5th step  visits  Vertex  11
(16 rows)
Passes in front or visits with left side driving.¶
For point \(6\) and vertex \(11\).
SELECT (start_pid  ' => '  end_pid ' 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_withPoints(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
ARRAY[5, 1], ARRAY[2, 3, 6, 10, 11],
driving_side => 'l', details => true)
WHERE node IN (6, 11);
path_at  status  is_a  id
+++
1 => 6 at 3th step  visits  Point  6
1 => 3 at 3th step  passes in front of  Point  6
1 => 2 at 3th step  passes in front of  Point  6
1 => 2 at 5th step  passes in front of  Vertex  11
1 => 10 at 3th step  passes in front of  Point  6
1 => 10 at 5th step  passes in front of  Vertex  11
1 => 11 at 3th step  passes in front of  Point  6
1 => 11 at 5th step  visits  Vertex  11
5 => 6 at 4th step  visits  Point  6
5 => 3 at 4th step  passes in front of  Point  6
5 => 2 at 4th step  passes in front of  Point  6
5 => 2 at 6th step  passes in front of  Vertex  11
5 => 10 at 4th step  passes in front of  Point  6
5 => 10 at 6th step  passes in front of  Vertex  11
5 => 11 at 4th step  passes in front of  Point  6
5 => 11 at 6th step  visits  Vertex  11
(16 rows)
See Also¶
Indices and tables