pgr_trspVia - Proposed¶
pgr_trspVia Route that goes through a list of vertices with restrictions.
Boost Graph Inside¶
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.4.0
New proposed function:
pgr_trspVia(One Via)
Description¶
Given a list of vertices and a graph, this function is equivalent to finding the shortest path between \(vertex_i\) and \(vertex_{i+1}\) for all \(i < size\_of(via\;vertices)\) trying not to use restricted paths.
The paths represents the sections of the route.
The general algorithm is as follows:
Execute a pgr_dijkstraVia - Proposed.
For the set of sub paths of the solution that pass through a restriction then
Execute the TRSP algorithm with restrictions for the paths.
NOTE when this is done,
U_turn_on_edgeflag is ignored.
Signatures¶
One Via¶
[directed, strict, U_turn_on_edge](seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost, route_agg_cost)- Example:
Find the route that visits the vertices \(\{5, 1, 8\}\) in that order on an directed graph.
SELECT * FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 1, 8]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 5 | 1 | 5 | 1 | 1 | 0 | 0
2 | 1 | 2 | 5 | 1 | 6 | 4 | 1 | 1 | 1
3 | 1 | 3 | 5 | 1 | 7 | 10 | 1 | 2 | 2
4 | 1 | 4 | 5 | 1 | 8 | 12 | 1 | 3 | 3
5 | 1 | 5 | 5 | 1 | 12 | 13 | 1 | 4 | 4
6 | 1 | 6 | 5 | 1 | 17 | 15 | 1 | 5 | 5
7 | 1 | 7 | 5 | 1 | 16 | 9 | 1 | 6 | 6
8 | 1 | 8 | 5 | 1 | 11 | 8 | 1 | 7 | 7
9 | 1 | 9 | 5 | 1 | 7 | 7 | 1 | 8 | 8
10 | 1 | 10 | 5 | 1 | 3 | 6 | 1 | 9 | 9
11 | 1 | 11 | 5 | 1 | 1 | -1 | 0 | 10 | 10
12 | 2 | 1 | 1 | 8 | 1 | 6 | 1 | 0 | 10
13 | 2 | 2 | 1 | 8 | 3 | 7 | 1 | 1 | 11
14 | 2 | 3 | 1 | 8 | 7 | 10 | 101 | 2 | 12
15 | 2 | 4 | 1 | 8 | 8 | -2 | 0 | 103 | 113
(15 rows)
Parameters¶
Parameter |
Type |
Description |
|---|---|---|
|
Edges SQL query as described. |
|
|
Restrictions SQL query as described. |
|
via vertices |
|
Array of ordered vertices identifiers that are going to be visited. |
Where:
- ANY-INTEGER:
SMALLINT, INTEGER, BIGINT
Optional parameters¶
Column |
Type |
Default |
Description |
|---|---|---|---|
|
|
|
|
Via optional parameters¶
Parameter |
Type |
Default |
Description |
|---|---|---|---|
|
|
|
|
|
|
|
|
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
Restrictions SQL¶
Column |
Type |
Description |
|---|---|---|
|
|
Sequence of edge identifiers that form a path that is not allowed to be
taken.
- Empty arrays or |
|
ANY-NUMERICAL |
Cost of taking the forbidden path. |
Where:
- ANY-INTEGER:
SMALLINT,INTEGER,BIGINT- ANY-NUMERICAL:
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
Result columns¶
Column |
Type |
Description |
|---|---|---|
|
|
Sequential value starting from 1. |
|
|
Identifier of a path. Has value 1 for the first path. |
|
|
Relative position in the path. Has value 1 for the beginning of a path. |
|
|
Identifier of the starting vertex of the path. |
|
|
Identifier of the ending vertex 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 |
|
|
Total cost from |
Additional Examples¶
All this examples are about the route that visits the vertices \(\{5, 7, 1, 8, 15\}\) in that order on a directed graph.
The main query¶
SELECT * FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 5 | 7 | 5 | 1 | 1 | 0 | 0
2 | 1 | 2 | 5 | 7 | 6 | 4 | 1 | 1 | 1
3 | 1 | 3 | 5 | 7 | 7 | -1 | 0 | 2 | 2
4 | 2 | 1 | 7 | 1 | 7 | 7 | 1 | 0 | 2
5 | 2 | 2 | 7 | 1 | 3 | 6 | 1 | 1 | 3
6 | 2 | 3 | 7 | 1 | 1 | -1 | 0 | 2 | 4
7 | 3 | 1 | 1 | 8 | 1 | 6 | 1 | 0 | 4
8 | 3 | 2 | 1 | 8 | 3 | 7 | 1 | 1 | 5
9 | 3 | 3 | 1 | 8 | 7 | 10 | 101 | 2 | 6
10 | 3 | 4 | 1 | 8 | 8 | -1 | 0 | 103 | 107
11 | 4 | 1 | 8 | 15 | 8 | 12 | 1 | 0 | 107
12 | 4 | 2 | 8 | 15 | 12 | 13 | 1 | 1 | 108
13 | 4 | 3 | 8 | 15 | 17 | 15 | 1 | 2 | 109
14 | 4 | 4 | 8 | 15 | 16 | 16 | 1 | 3 | 110
15 | 4 | 5 | 8 | 15 | 15 | -2 | 0 | 4 | 111
(15 rows)
Aggregate cost of the third path.¶
SELECT agg_cost FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15])
WHERE path_id = 3 AND edge < 0;
agg_cost
----------
103
(1 row)
Route’s aggregate cost of the route at the end of the third path.¶
SELECT route_agg_cost FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15])
WHERE path_id = 3 AND edge < 0;
route_agg_cost
----------------
107
(1 row)
Nodes visited in the route.¶
SELECT row_number() over () as node_seq, node
FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15])
WHERE edge <> -1 ORDER BY seq;
node_seq | node
----------+------
1 | 5
2 | 6
3 | 7
4 | 3
5 | 1
6 | 3
7 | 7
8 | 8
9 | 12
10 | 17
11 | 16
12 | 15
(12 rows)
The aggregate costs of the route when the visited vertices are reached.¶
SELECT path_id, route_agg_cost FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15])
WHERE edge < 0;
path_id | route_agg_cost
---------+----------------
1 | 2
2 | 4
3 | 107
4 | 111
(4 rows)
Status of “passes in front” or “visits” of the nodes.¶
SELECT seq, route_agg_cost, node, agg_cost ,
CASE WHEN edge = -1 THEN $$visits$$
ELSE $$passes in front$$
END as status
FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15])
WHERE agg_cost <> 0 or seq = 1;
seq | route_agg_cost | node | agg_cost | status
-----+----------------+------+----------+-----------------
1 | 0 | 5 | 0 | passes in front
2 | 1 | 6 | 1 | passes in front
3 | 2 | 7 | 2 | visits
5 | 3 | 3 | 1 | passes in front
6 | 4 | 1 | 2 | visits
8 | 5 | 3 | 1 | passes in front
9 | 6 | 7 | 2 | passes in front
10 | 107 | 8 | 103 | visits
12 | 108 | 12 | 1 | passes in front
13 | 109 | 17 | 2 | passes in front
14 | 110 | 16 | 3 | passes in front
15 | 111 | 15 | 4 | passes in front
(12 rows)
Simulation of how algorithm works.¶
The algorithm performs a pgr_dijkstraVia - Proposed
SELECT * FROM pgr_dijkstraVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
ARRAY[6, 3, 6]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 6 | 3 | 6 | 4 | 1 | 0 | 0
2 | 1 | 2 | 6 | 3 | 7 | 7 | 1 | 1 | 1
3 | 1 | 3 | 6 | 3 | 3 | -1 | 0 | 2 | 2
4 | 2 | 1 | 3 | 6 | 3 | 7 | 1 | 0 | 2
5 | 2 | 2 | 3 | 6 | 7 | 4 | 1 | 1 | 3
6 | 2 | 3 | 3 | 6 | 6 | -2 | 0 | 2 | 4
(6 rows)
Detects which of the sub paths pass through a restriction in this case is for
the path_id = 5 from 6 to 3 because the path \(15 \rightarrow 1\)
is restricted.
Executes the pgr_trsp - Proposed algorithm for the conflicting paths.
SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
6, 3);
path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 3 | 6 | 4 | 1 | 0
1 | 2 | 6 | 3 | 7 | 10 | 1 | 1
1 | 3 | 6 | 3 | 8 | 12 | 1 | 2
1 | 4 | 6 | 3 | 12 | 13 | 1 | 3
1 | 5 | 6 | 3 | 17 | 15 | 1 | 4
1 | 6 | 6 | 3 | 16 | 9 | 1 | 5
1 | 7 | 6 | 3 | 11 | 8 | 1 | 6
1 | 8 | 6 | 3 | 7 | 7 | 1 | 7
1 | 9 | 6 | 3 | 3 | -1 | 0 | 8
(9 rows)
From the pgr_dijkstraVia - Proposed result it removes the conflicting paths and builds the solution with the results of the pgr_trsp - Proposed algorithm:
WITH
solutions AS (
SELECT path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_dijkstraVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
ARRAY[6, 3, 6]) WHERE path_id != 1
UNION
SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
6, 3)),
with_seq AS (
SELECT row_number() over(ORDER BY path_id, path_seq) AS seq, *
FROM solutions),
aggregation AS (SELECT seq, SUM(cost) OVER(ORDER BY seq) AS route_agg_cost FROM with_seq)
SELECT with_seq.*, COALESCE(route_agg_cost, 0) AS route_agg_cost
FROM with_seq LEFT JOIN aggregation ON (with_seq.seq = aggregation.seq + 1);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 6 | 3 | 6 | 4 | 1 | 0 | 0
2 | 1 | 2 | 6 | 3 | 7 | 10 | 1 | 1 | 1
3 | 1 | 3 | 6 | 3 | 8 | 12 | 1 | 2 | 2
4 | 1 | 4 | 6 | 3 | 12 | 13 | 1 | 3 | 3
5 | 1 | 5 | 6 | 3 | 17 | 15 | 1 | 4 | 4
6 | 1 | 6 | 6 | 3 | 16 | 9 | 1 | 5 | 5
7 | 1 | 7 | 6 | 3 | 11 | 8 | 1 | 6 | 6
8 | 1 | 8 | 6 | 3 | 7 | 7 | 1 | 7 | 7
9 | 1 | 9 | 6 | 3 | 3 | -1 | 0 | 8 | 8
10 | 2 | 1 | 3 | 6 | 3 | 7 | 1 | 0 | 8
11 | 2 | 2 | 3 | 6 | 7 | 4 | 1 | 1 | 9
12 | 2 | 3 | 3 | 6 | 6 | -2 | 0 | 2 | 10
(12 rows)
Getting the same result as pgr_trspVia:
SELECT * FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[6, 3, 6]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 6 | 3 | 6 | 4 | 1 | 0 | 0
2 | 1 | 2 | 6 | 3 | 7 | 10 | 1 | 1 | 1
3 | 1 | 3 | 6 | 3 | 8 | 12 | 1 | 2 | 2
4 | 1 | 4 | 6 | 3 | 12 | 13 | 1 | 3 | 3
5 | 1 | 5 | 6 | 3 | 17 | 15 | 1 | 4 | 4
6 | 1 | 6 | 6 | 3 | 16 | 9 | 1 | 5 | 5
7 | 1 | 7 | 6 | 3 | 11 | 8 | 1 | 6 | 6
8 | 1 | 8 | 6 | 3 | 7 | 7 | 1 | 7 | 7
9 | 1 | 9 | 6 | 3 | 3 | -1 | 0 | 8 | 8
10 | 2 | 1 | 3 | 6 | 3 | 7 | 1 | 0 | 8
11 | 2 | 2 | 3 | 6 | 7 | 4 | 1 | 1 | 9
12 | 2 | 3 | 3 | 6 | 6 | -2 | 0 | 2 | 10
(12 rows)
- Example 8:
Sometimes
U_turn_on_edgeflag is ignored when is set tofalse.
The first step, doing a pgr_dijkstraVia - Proposed does consider not making a U turn on the same edge. But the path \(16 \rightarrow 13\) (Rows 4 and 5) is restricted and the result is using it.
SELECT * FROM pgr_dijkstraVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
ARRAY[6, 7, 6], U_turn_on_edge => false);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 6 | 7 | 6 | 4 | 1 | 0 | 0
2 | 1 | 2 | 6 | 7 | 7 | -1 | 0 | 1 | 1
3 | 2 | 1 | 7 | 6 | 7 | 8 | 1 | 0 | 1
4 | 2 | 2 | 7 | 6 | 11 | 9 | 1 | 1 | 2
5 | 2 | 3 | 7 | 6 | 16 | 16 | 1 | 2 | 3
6 | 2 | 4 | 7 | 6 | 15 | 3 | 1 | 3 | 4
7 | 2 | 5 | 7 | 6 | 10 | 2 | 1 | 4 | 5
8 | 2 | 6 | 7 | 6 | 6 | -2 | 0 | 5 | 6
(8 rows)
When executing the pgr_trsp - Proposed algorithm for the conflicting path, there is
no U_turn_on_edge flag.
SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
7, 6);
path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 7 | 6 | 7 | 4 | 1 | 0
1 | 2 | 7 | 6 | 6 | -1 | 0 | 1
(2 rows)
Therefore the result ignores the U_turn_on_edge flag when set to false.
SELECT * FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[6, 7, 6], U_turn_on_edge => false);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 6 | 7 | 6 | 4 | 1 | 0 | 0
2 | 1 | 2 | 6 | 7 | 7 | -1 | 0 | 1 | 1
3 | 2 | 1 | 7 | 6 | 7 | 4 | 1 | 0 | 1
4 | 2 | 2 | 7 | 6 | 6 | -2 | 0 | 1 | 2
(4 rows)
See Also¶
Sample Data network.
Indices and tables