pgr_withPoints - Proposed - pgRouting Manual (3.0)
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 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 2.2.0
-
New proposed function
-
Support
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
pgr_withPoints(edges_sql, points_sql, from_vid, to_vid [, directed] [, driving_side] [, details])
pgr_withPoints(edges_sql, points_sql, from_vid, to_vids [, directed] [, driving_side] [, details])
pgr_withPoints(edges_sql, points_sql, from_vids, to_vid [, directed] [, driving_side] [, details])
pgr_withPoints(edges_sql, points_sql, from_vids, to_vids [, directed] [, driving_side] [, details])
RETURNS SET OF (seq, path_seq, [start_vid,] [end_vid,] node, edge, cost, agg_cost)
Using defaults
pgr_withPoints(edges_sql, points_sql, from_vid, to_vid)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
- Example :
-
From point \(1\) to point \(3\)
-
For a directed graph.
-
The driving side is set as b both. So arriving/departing to/from the point(s) can be in any direction.
-
No details are given about distance of other points of points_sql query.
-
SELECT * FROM pgr_withPoints(
'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
-1, -3);
seq path_seq node edge cost agg_cost
-----+----------+------+------+------+----------
1 1 -1 1 0.6 0
2 2 2 4 1 0.6
3 3 5 10 1 1.6
4 4 10 12 0.6 2.6
5 5 -3 -1 0 3.2
(5 rows)
One to One
pgr_withPoints(edges_sql, points_sql, from_vid, to_vid [, directed] [, driving_side] [, details])
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
- Example :
-
From point \(1\) to vertex \(3\) with details of passing points
SELECT * FROM pgr_withPoints(
'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
-1, 3,
details := true);
seq path_seq node edge cost agg_cost
-----+----------+------+------+------+----------
1 1 -1 1 0.6 0
2 2 2 4 0.7 0.6
3 3 -6 4 0.3 1.3
4 4 5 8 1 1.6
5 5 6 9 1 2.6
6 6 9 16 1 3.6
7 7 4 3 1 4.6
8 8 3 -1 0 5.6
(8 rows)
One to Many
pgr_withPoints(edges_sql, points_sql, from_vid, to_vids [, directed] [, driving_side] [, details])
RETURNS SET OF (seq, path_seq, end_vid, node, edge, cost, agg_cost)
- Example :
-
From point \(1\) to point \(3\) and vertex \(5\)
SELECT * FROM pgr_withPoints(
'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
-1, ARRAY[-3,5]);
seq path_seq end_pid node edge cost agg_cost
-----+----------+---------+------+------+------+----------
1 1 -3 -1 1 0.6 0
2 2 -3 2 4 1 0.6
3 3 -3 5 10 1 1.6
4 4 -3 10 12 0.6 2.6
5 5 -3 -3 -1 0 3.2
6 1 5 -1 1 0.6 0
7 2 5 2 4 1 0.6
8 3 5 5 -1 0 1.6
(8 rows)
Many to One
pgr_withPoints(edges_sql, points_sql, from_vids, to_vid [, directed] [, driving_side] [, details])
RETURNS SET OF (seq, path_seq, start_vid, node, edge, cost, agg_cost)
- Example :
-
From point \(1\) and vertex \(2\) to point \(3\)
SELECT * FROM pgr_withPoints(
'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
ARRAY[-1,2], -3);
seq path_seq start_pid node edge cost agg_cost
-----+----------+-----------+------+------+------+----------
1 1 -1 -1 1 0.6 0
2 2 -1 2 4 1 0.6
3 3 -1 5 10 1 1.6
4 4 -1 10 12 0.6 2.6
5 5 -1 -3 -1 0 3.2
6 1 2 2 4 1 0
7 2 2 5 10 1 1
8 3 2 10 12 0.6 2
9 4 2 -3 -1 0 2.6
(9 rows)
Many to Many
pgr_withPoints(edges_sql, points_sql, from_vids, to_vids [, directed] [, driving_side] [, details])
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Example :
-
From point \(1\) and vertex \(2\) to point \(3\) and vertex \(7\)
SELECT * FROM pgr_withPoints(
'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
ARRAY[-1,2], ARRAY[-3,7]);
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 2 4 1 0.6
3 3 -1 -3 5 10 1 1.6
4 4 -1 -3 10 12 0.6 2.6
5 5 -1 -3 -3 -1 0 3.2
6 1 -1 7 -1 1 0.6 0
7 2 -1 7 2 4 1 0.6
8 3 -1 7 5 7 1 1.6
9 4 -1 7 8 6 1 2.6
10 5 -1 7 7 -1 0 3.6
11 1 2 -3 2 4 1 0
12 2 2 -3 5 10 1 1
13 3 2 -3 10 12 0.6 2
14 4 2 -3 -3 -1 0 2.6
15 1 2 7 2 4 1 0
16 2 2 7 5 7 1 1
17 3 2 7 8 6 1 2
18 4 2 7 7 -1 0 3
(18 rows)
Parameters
|
Parameter |
Type |
Description |
|---|---|---|
|
edges_sql |
|
Edges SQL query as described above. |
|
points_sql |
|
Points SQL query as described above. |
|
start_vid |
|
Starting vertex identifier. When negative: is a point’s pid. |
|
end_vid |
|
Ending vertex identifier. When negative: is a point’s pid. |
|
start_vids |
|
Array of identifiers of starting vertices. When negative: is a point’s pid. |
|
end_vids |
|
Array of identifiers of ending vertices. When negative: is a point’s pid. |
|
directed |
|
(optional). When
|
|
driving_side |
|
|
|
details |
|
(optional). When
|
Inner query
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
id |
|
Identifier of the edge. |
|
|
source |
|
Identifier of the first end point vertex of the edge. |
|
|
target |
|
Identifier of the second end point vertex of the edge. |
|
|
cost |
|
Weight of the edge (source, target)
|
|
|
reverse_cost |
|
-1 |
Weight of the edge (target, source) ,
|
Where:
- ANY-INTEGER :
-
SMALLINT, INTEGER, BIGINT
- ANY-NUMERICAL :
-
SMALLINT, INTEGER, BIGINT, REAL, FLOAT
Description of the Points SQL query
- points_sql :
-
an SQL query, which should return a set of rows with the following columns:
|
Column |
Type |
Description |
|---|---|---|
|
pid |
|
(optional) Identifier of the point.
|
|
edge_id |
|
Identifier of the "closest" edge to the point. |
|
fraction |
|
Value in <0,1> that indicates the relative postition from the first end point of the edge. |
|
side |
|
(optional) Value in [‘b’, ‘r’, ‘l’, NULL] indicating if the point is:
|
Where:
- ANY-INTEGER :
-
smallint, int, bigint
- ANY-NUMERICAL :
-
smallint, int, bigint, real, float
Result Columns
|
Column |
Type |
Description |
|---|---|---|
|
seq |
|
Row sequence. |
|
path_seq |
|
Path sequence that indicates the relative position on the path. |
|
start_vid |
|
Identifier of the starting vertex. When negative: is a point’s pid. |
|
end_vid |
|
Identifier of the ending vertex. When negative: is a point’s pid. |
|
node |
|
|
|
edge |
|
|
|
cost |
|
|
|
agg_cost |
|
|
Additional Examples
- Example :
-
Which path (if any) passes in front of point \(6\) or vertex \(6\) with right side driving topology.
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 edge_table ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
ARRAY[1,-1], ARRAY[-2,-3,-6,3,6],
driving_side := 'r',
details := true)
WHERE node IN (-6,6);
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 6
(-1 => 3) at 4th step: passes in front of Point 6
(-1 => 3) at 6th step: passes in front of Vertex 6
(-1 => 6) at 4th step: passes in front of Point 6
(-1 => 6) at 6th step: visits Vertex 6
(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 6
(1 => 3) at 3th step: passes in front of Point 6
(1 => 3) at 5th step: passes in front of Vertex 6
(1 => 6) at 3th step: passes in front of Point 6
(1 => 6) at 5th step: visits Vertex 6
(16 rows)
- Example :
-
Which path (if any) passes in front of point \(6\) or vertex \(6\) with left side driving topology.
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 edge_table ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
ARRAY[1,-1], ARRAY[-2,-3,-6,3,6],
driving_side := 'l',
details := true)
WHERE node IN (-6,6);
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 6
(-1 => 3) at 3th step: passes in front of Point 6
(-1 => 3) at 5th step: passes in front of Vertex 6
(-1 => 6) at 3th step: passes in front of Point 6
(-1 => 6) at 5th step: visits Vertex 6
(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 6
(1 => 3) at 4th step: passes in front of Point 6
(1 => 3) at 6th step: passes in front of Vertex 6
(1 => 6) at 4th step: passes in front of Point 6
(1 => 6) at 6th step: visits Vertex 6
(16 rows)
- Example :
-
From point \(1\) and vertex \(2\) to point \(3\) to vertex \(7\) on an undirected graph, with details.
SELECT * FROM pgr_withPoints(
'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
ARRAY[-1,2], ARRAY[-3,7],
directed := false,
details := true);
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 2 4 0.7 0.6
3 3 -1 -3 -6 4 0.3 1.3
4 4 -1 -3 5 10 1 1.6
5 5 -1 -3 10 12 0.6 2.6
6 6 -1 -3 -3 -1 0 3.2
7 1 -1 7 -1 1 0.6 0
8 2 -1 7 2 4 0.7 0.6
9 3 -1 7 -6 4 0.3 1.3
10 4 -1 7 5 7 1 1.6
11 5 -1 7 8 6 0.7 2.6
12 6 -1 7 -4 6 0.3 3.3
13 7 -1 7 7 -1 0 3.6
14 1 2 -3 2 4 0.7 0
15 2 2 -3 -6 4 0.3 0.7
16 3 2 -3 5 10 1 1
17 4 2 -3 10 12 0.6 2
18 5 2 -3 -3 -1 0 2.6
19 1 2 7 2 4 0.7 0
20 2 2 7 -6 4 0.3 0.7
21 3 2 7 5 7 1 1
22 4 2 7 8 6 0.7 2
23 5 2 7 -4 6 0.3 2.7
24 6 2 7 7 -1 0 3
(24 rows)
The queries use the Sample Data network
See Also
Indices and tables