pgr_withPointsCost - Proposed - pgRouting Manual (3.4)
![Logo](images/pgrouting.png)
pgr_withPointsCost
- Proposed
pgr_withPointsCost
- Calculates the shortest path and returns only the
aggregate cost of the shortest path(s) found, for the combination of points
given.
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.
-
![images/boost-inside.jpeg](images/boost-inside.jpeg)
Availability
-
Version 3.2.0
-
New proposed function:
-
pgr_withPointsCost(Combinations)
-
-
-
Version 2.2.0
-
New proposed function
-
Description
Modify the graph to include points defined by points_sql. Using Dijkstra algorithm, return only the aggregate cost of the shortest path(s) found.
- The main characteristics are:
-
-
It does not return a path.
-
Returns the sum of the costs of the shortest path for pair combination of vertices in the modified graph.
-
Vertices of the graph are:
-
positive when it belongs to the edges_sql
-
negative when it belongs to the points_sql
-
-
Process is done only on edges with positive costs.
-
Values are returned when there is a path.
-
The returned values are in the form of a set of (start_vid, end_vid, agg_cost) .
-
When the starting vertex and ending vertex are the same, there is no path.
-
The agg_cost in 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 in the non included values (u, v) is \(\infty\)
-
-
-
If the values returned are stored in a table, the unique index would be the pair: (start_vid, end_vid) .
-
For undirected graphs, the results are symmetric .
-
The agg_cost of (u, v) is the same as for (v, u) .
-
-
For optimization purposes, any duplicated value in the start_vids or end_vids is ignored.
-
The returned values are ordered:
-
start_vid ascending
-
end_vid ascending
-
-
Running time: \(O( start\_vids * (V \log V + E))\)
-
Signatures
Summary
[directed,
driving_side]
(start_pid,
end_pid,
agg_cost)
Note
There is no details flag, unlike the other members of the withPoints family of functions.
One to One
[directed,
driving_side]
(start_pid,
end_pid,
agg_cost)
- Example :
-
From point \(1\) to vertex \(10\) with defaults
SELECT * FROM pgr_withPointsCost(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
-1, 10);
start_pid end_pid agg_cost
-----------+---------+----------
-1 10 5.6
(1 row)
One to Many
[directed,
driving_side]
(start_pid,
end_pid,
agg_cost)
- Example :
-
From point \(1\) to point \(3\) and vertex \(7\) on an undirected graph
SELECT * FROM pgr_withPointsCost(
'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);
start_pid end_pid agg_cost
-----------+---------+----------
-1 -3 3.2
-1 7 1.6
(2 rows)
Many to One
[directed,
driving_side]
(start_pid,
end_pid,
agg_cost)
- Example :
-
From point \(1\) and vertex \(6\) to point \(3\)
SELECT * FROM pgr_withPointsCost(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
ARRAY[-1, 6], -3);
start_pid end_pid agg_cost
-----------+---------+----------
-1 -3 3.2
6 -3 2.6
(2 rows)
Many to Many
[directed,
driving_side]
(start_pid,
end_pid,
agg_cost)
- Example :
-
From point \(15\) and vertex \(6\) to point \(3\) and vertex \(1\)
SELECT * FROM pgr_withPointsCost(
'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]);
start_pid end_pid agg_cost
-----------+---------+----------
-1 -3 3.2
-1 1 3.6
6 -3 2.6
6 1 3
(4 rows)
Combinations
[directed,
driving_side]
(start_pid,
end_pid,
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_withPointsCost(
'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');
start_pid end_pid agg_cost
-----------+---------+----------
-1 10 6.4
6 -3 2.6
(2 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 |
---|---|---|---|
|
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
Points SQL
Parameter |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
value |
Identifier of the point.
|
|
ANY-INTEGER |
Identifier of the "closest" edge to the point. |
|
|
ANY-NUMERICAL |
Value in <0,1> that indicates the relative postition from the first end point of the edge. |
|
|
|
|
Value in [
|
Where:
- ANY-INTEGER :
-
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL :
-
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Combinations SQL
Parameter |
Type |
Description |
---|---|---|
|
ANY-INTEGER |
Identifier of the departure vertex. |
|
ANY-INTEGER |
Identifier of the arrival vertex. |
Where:
- ANY-INTEGER :
-
SMALLINT
,INTEGER
,BIGINT
Result Columns
Column |
Type |
Description |
---|---|---|
|
|
Identifier of the starting vertex or point.
|
|
|
Identifier of the ending vertex or point.
|
|
|
Aggregate cost from
|
Additional Examples
Use pgr_findCloseEdges in the Points SQL .
Find the cost of the routes from vertex \(1\) to the two closest locations on the graph of point (2.9, 1.8) .
SELECT * FROM pgr_withPointsCost(
$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]);
start_pid end_pid agg_cost
-----------+---------+----------
1 -2 2.9
1 -1 6.8
(2 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) .
-
Being close to the graph does not mean have a shorter route.
Right side driving topology
Traveling from point \(1\) and vertex \(5\) to points \(\{2, 3, 6\}\) and vertices \(\{10, 11\}\)
SELECT * FROM pgr_withPointsCost(
'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');
start_pid end_pid agg_cost
-----------+---------+----------
-1 -6 2.1
-1 -3 4
-1 -2 4.8
-1 10 6.4
-1 11 3.4
5 -6 1.7
5 -3 3.6
5 -2 4.4
5 10 6
5 11 3
(10 rows)
Left side driving topology
Traveling from point \(1\) and vertex \(5\) to points \(\{2, 3, 6\}\) and vertices \(\{10, 11\}\)
SELECT * FROM pgr_withPointsCost(
'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');
start_pid end_pid agg_cost
-----------+---------+----------
-1 -6 1.3
-1 -3 3.2
-1 -2 5.2
-1 10 5.6
-1 11 2.6
5 -6 1.7
5 -3 3.6
5 -2 5.6
5 10 6
5 11 3
(10 rows)
Does not matter driving side driving topology
Traveling from point \(1\) and vertex \(5\) to points \(\{2, 3, 6\}\) and vertices \(\{10, 11\}\)
SELECT * FROM pgr_withPointsCost(
'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]);
start_pid end_pid agg_cost
-----------+---------+----------
-1 -6 1.3
-1 -3 3.2
-1 -2 4
-1 10 5.6
-1 11 2.6
5 -6 1.7
5 -3 3.6
5 -2 4.4
5 10 6
5 11 3
(10 rows)
The queries use the Sample Data network.
See Also
Indices and tables