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.
Availability
- Version 3.2.0
- New proposed function:
- pgr_withPointsCost(Combinations)
- New proposed function:
- 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
pgr_withPointsCost(Edges SQL, 'Points SQL', start vid, end vid [, directed] [, driving_side]) pgr_withPointsCost(Edges SQL, 'Points SQL', start vid, end vids [, directed] [, driving_side]) pgr_withPointsCost(Edges SQL, 'Points SQL', start vids, end vid [, directed] [, driving_side]) pgr_withPointsCost(Edges SQL, 'Points SQL', start vids, end vids [, directed] [, driving_side]) pgr_withPointsCost(Edges SQL, 'Points SQL', Combinations SQL [, directed] [, driving_side]) RETURNS (start_vid, end_vid, agg_cost)
Note
There is no details flag, unlike the other members of the withPoints family of functions.
One to One¶
pgr_withPointsCost(Edges SQL, start vid, end vid [, directed] [, driving_side]) RETURNS (start_vid, end_vid, 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¶
pgr_withPointsCost(Edges SQL, 'Points SQL', start vid, end vids [, directed] [, driving_side]) RETURNS (start_vid, end_vid, 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¶
pgr_withPointsCost(Edges SQL, 'Points SQL', start vids, end vid [, directed] [, driving_side]) RETURNS (start_vid, end_vid, 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¶
pgr_withPointsCost(Edges SQL, 'Points SQL', start vids, end vids [, directed] [, driving_side]) RETURNS (start_vid, end_vid, 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¶
pgr_withPointsCost(Edges SQL, 'Points SQL', Combinations SQL [, directed] [, driving_side]) RETURNS (seq, path_seq, start_vid, end_vid, 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_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 | TEXT |
Edges SQL as described below |
Points SQL | TEXT |
Points SQL as described below |
Combinations SQL | TEXT |
Combinations SQL as described below |
start vid | BIGINT |
Identifier of the starting vertex of the path. Negative value is for point’s identifier. |
start vids | ARRAY[BIGINT] |
Array of identifiers of starting vertices. Negative values are for point’s identifiers. |
end vid | BIGINT |
Identifier of the ending vertex of the path. Negative value is for point’s identifier. |
end vids | ARRAY[BIGINT] |
Array of identifiers of ending vertices. Negative values are for point’s identifiers. |
Optional parameters¶
Column | Type | Default | Description |
---|---|---|---|
directed |
BOOLEAN |
true |
|
With points optional parameters¶
Parameter | Type | Default | Description |
---|---|---|---|
driving_side |
CHAR |
b |
Value in [
|
Inner Queries¶
Edges SQL¶
Column | Type | Default | Description |
---|---|---|---|
id |
ANY-INTEGER | Identifier of the edge. | |
source |
ANY-INTEGER | Identifier of the first end point vertex of the edge. | |
target |
ANY-INTEGER | Identifier of the second end point vertex of the edge. | |
cost |
ANY-NUMERICAL | Weight of the edge (source , target ) |
|
reverse_cost |
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 |
---|---|---|---|
pid |
ANY-INTEGER | value | Identifier of the point.
|
edge_id |
ANY-INTEGER | Identifier of the “closest” edge to the point. | |
fraction |
ANY-NUMERICAL | Value in <0,1> that indicates the relative postition from the first end point of the edge. | |
side |
CHAR |
b |
Value in [
|
Where:
ANY-INTEGER: | SMALLINT , INTEGER , BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT , INTEGER , BIGINT , REAL , FLOAT |
Combinations SQL¶
Parameter | Type | Description |
---|---|---|
source |
ANY-INTEGER | Identifier of the departure vertex. |
target |
ANY-INTEGER | Identifier of the arrival vertex. |
Where:
ANY-INTEGER: | SMALLINT , INTEGER , BIGINT |
---|
Result Columns¶
Column | Type | Description |
---|---|---|
start_pid |
BIGINT |
Identifier of the starting vertex or point.
|
end_pid |
BIGINT |
Identifier of the ending vertex or point.
|
agg_cost |
FLOAT |
Aggregate cost from start_vid to end_vid . |
Additional Examples¶
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.