pgr_dijkstraVia - Proposed¶
Name¶
pgr_dijkstraVia — Using dijkstra algorithm, it finds the route that goes through a list of vertices.
Boost Graph Inside
Synopsis¶
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(vertex_via)\).
The paths represents the sections of the route.
Note
This is a proposed function
Signatrue Summary¶
pgr_dijkstraVia(edges_sql, via_vertices)
pgr_dijkstraVia(edges_sql, via_vertices, directed, strict, U_turn_on_edge)
RETURNS SET OF (seq, path_pid, path_seq, start_vid, end_vid,
node, edge, cost, agg_cost, route_agg_cost) or EMPTY SET
Signatures¶
Minimal Signature¶
pgr_dijkstraVia(edges_sql, via_vertices)
RETURNS SET OF (seq, path_pid, path_seq, start_vid, end_vid,
node, edge, cost, agg_cost, route_agg_cost) or EMPTY SET
| Example: | Find the route that visits the vertices 1 3 9 in that order |
|---|
SELECT * FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
ARRAY[1, 3, 9]
);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 1 | 3 | 1 | 1 | 1 | 0 | 0
2 | 1 | 2 | 1 | 3 | 2 | 4 | 1 | 1 | 1
3 | 1 | 3 | 1 | 3 | 5 | 8 | 1 | 2 | 2
4 | 1 | 4 | 1 | 3 | 6 | 9 | 1 | 3 | 3
5 | 1 | 5 | 1 | 3 | 9 | 16 | 1 | 4 | 4
6 | 1 | 6 | 1 | 3 | 4 | 3 | 1 | 5 | 5
7 | 1 | 7 | 1 | 3 | 3 | -1 | 0 | 6 | 6
8 | 2 | 1 | 3 | 9 | 3 | 5 | 1 | 0 | 6
9 | 2 | 2 | 3 | 9 | 6 | 9 | 1 | 1 | 7
10 | 2 | 3 | 3 | 9 | 9 | -2 | 0 | 2 | 8
(10 rows)
Complete Signature¶
pgr_dijkstraVia(edges_sql, via_vertices, directed, strict, U_turn_on_edge)
RETURNS SET OF (seq, path_pid, path_seq, start_vid, end_vid,
node, edge, cost, agg_cost, route_agg_cost) or EMPTY SET
| Example: | Find the route that visits the vertices 1 3 9 in that order on an undirected graph, avoiding U-turns when possible |
|---|
SELECT * FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
ARRAY[1, 3, 9], false, strict:=true, 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 | 1 | 3 | 1 | 1 | 1 | 0 | 0
2 | 1 | 2 | 1 | 3 | 2 | 2 | 1 | 1 | 1
3 | 1 | 3 | 1 | 3 | 3 | -1 | 0 | 2 | 2
4 | 2 | 1 | 3 | 9 | 3 | 5 | 1 | 0 | 2
5 | 2 | 2 | 3 | 9 | 6 | 9 | 1 | 1 | 3
6 | 2 | 3 | 3 | 9 | 9 | -2 | 0 | 2 | 4
(6 rows)
Description of the Signature¶
Description of the edges_sql query¶
| edges_sql: | an SQL query, which should return a set of rows with the following columns: |
|---|
| 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 |
|
|
| reverse_cost | ANY-NUMERICAL | -1 |
|
Where:
| ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
|---|---|
| ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT |
Description of the parameters of the signatures¶
| Parameter | Type | Default | Description |
|---|---|---|---|
| edges_sql | TEXT | SQL query as described above. | |
| via_vertices | ARRAY[ANY-INTEGER] | Array of ordered vertices identifiers that are going to be visited. | |
| directed | BOOLEAN | true |
|
| strict | BOOLEAN | false |
|
| U_turn_on_edge | BOOLEAN | true |
|
Description of the parameters of the signatures¶
| Parameter | Type | Description |
|---|---|---|
| edges_sql | TEXT | SQL query as described above. |
| via_vertices | ARRAY[ANY-INTEGER] | Array of vertices identifiers |
| directed | BOOLEAN | (optional) Default is true (is directed). When set to false the graph is considered as Undirected |
| strict | BOOLEAN | (optional) ignores if a subsection of the route is missing and returns everything it found Default is true (is directed). When set to false the graph is considered as Undirected |
| U_turn_on_edge | BOOLEAN | (optional) Default is true (is directed). When set to false the graph is considered as Undirected |
Description of the return values¶
Returns set of (start_vid, end_vid, agg_cost)
| Column | Type | Description |
|---|---|---|
| seq | BIGINT | Sequential value starting from 1. |
| path_pid | BIGINT | Identifier of the path. |
| path_seq | BIGINT | Sequential value starting from 1 for the path. |
| start_vid | BIGINT | Identifier of the starting vertex of the path. |
| end_vid | BIGINT | Identifier of the ending vertex of the path. |
| node | BIGINT | Identifier of the node in the path from start_vid to end_vid. |
| edge | BIGINT | Identifier of the edge used to go from node to the next node in the path sequence. -1 for the last node of the path. -2 for the last node of the route. |
| cost | FLOAT | Cost to traverse from node using edge to the next node in the route sequence. |
| agg_cost | FLOAT | Total cost from start_vid to end_vid of the path. |
| route_agg_cost | FLOAT | Total cost from start_vid of path_pid = 1 to end_vid of the current path_pid . |
Examples¶
| Example 1: | Find the route that visits the vertices 1 5 3 9 4 in that order |
|---|
SELECT * FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
ARRAY[1, 5, 3, 9, 4]
);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 1 | 5 | 1 | 1 | 1 | 0 | 0
2 | 1 | 2 | 1 | 5 | 2 | 4 | 1 | 1 | 1
3 | 1 | 3 | 1 | 5 | 5 | -1 | 0 | 2 | 2
4 | 2 | 1 | 5 | 3 | 5 | 8 | 1 | 0 | 2
5 | 2 | 2 | 5 | 3 | 6 | 9 | 1 | 1 | 3
6 | 2 | 3 | 5 | 3 | 9 | 16 | 1 | 2 | 4
7 | 2 | 4 | 5 | 3 | 4 | 3 | 1 | 3 | 5
8 | 2 | 5 | 5 | 3 | 3 | -1 | 0 | 4 | 6
9 | 3 | 1 | 3 | 9 | 3 | 5 | 1 | 0 | 6
10 | 3 | 2 | 3 | 9 | 6 | 9 | 1 | 1 | 7
11 | 3 | 3 | 3 | 9 | 9 | -1 | 0 | 2 | 8
12 | 4 | 1 | 9 | 4 | 9 | 16 | 1 | 0 | 8
13 | 4 | 2 | 9 | 4 | 4 | -2 | 0 | 1 | 9
(13 rows)
| Example 2: | What’s the aggregate cost of the third path? |
|---|
SELECT agg_cost FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
ARRAY[1, 5, 3, 9, 4]
)
WHERE path_id = 3 AND edge <0;
agg_cost
----------
2
(1 row)
| Example 3: | What’s the route’s aggregate cost of the route at the end of the third path? |
|---|
SELECT route_agg_cost FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
ARRAY[1, 5, 3, 9, 4]
)
WHERE path_id = 3 AND edge < 0;
route_agg_cost
----------------
8
(1 row)
| Example 4: | How are the nodes visited in the route? |
|---|
SELECT row_number() over () as node_seq, node
FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
ARRAY[1, 5, 3, 9, 4]
)
WHERE edge <> -1 ORDER BY seq;
node_seq | node
----------+------
1 | 1
2 | 2
3 | 5
4 | 6
5 | 9
6 | 4
7 | 3
8 | 6
9 | 9
10 | 4
(10 rows)
| Example 5: | What are the aggregate costs of the route when the visited vertices are reached? |
|---|
SELECT path_id, route_agg_cost FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
ARRAY[1, 5, 3, 9, 4]
)
WHERE edge < 0;
path_id | route_agg_cost
---------+----------------
1 | 2
2 | 6
3 | 8
4 | 9
(4 rows)
| Example 6: | show the route’s seq and aggregate cost and a status of “passes in front” or “visits” node 9 |
|---|
SELECT seq, route_agg_cost, node, agg_cost ,
CASE WHEN edge = -1 THEN 'visits'
ELSE 'passes in front'
END as status
FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
ARRAY[1, 5, 3, 9, 4])
WHERE node = 9 and (agg_cost <> 0 or seq = 1);
seq | route_agg_cost | node | agg_cost | status
-----+----------------+------+----------+-----------------
6 | 4 | 9 | 2 | passes in front
11 | 8 | 9 | 2 | visits
(2 rows)
See Also¶
Indices and tables