pgr_trspVia
¶
pgr_trspVia
Route that goes through a list of vertices with restrictions.
Availability
Version 4.0.0
Function promoted to official.
Version 3.4.0
New proposed function.
Description¶
Given a list of vertices and a graph, this function is equivalent to finding the
shortest path between
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_edge
flag 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
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
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
Executes the pgr_trsp 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 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_edge
flag 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
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 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¶
Indices and tables