pgr_dijkstraVia - Proposed

pgr_dijkstraVia — Route that goes through a list of vertices.

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.

Boost Graph Inside

Availability

• Version 2.2.0

  • New proposed function

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)\).

Route:

is a sequence of paths.

Path:

is a section of the route.

Signatures

One Via

pgr_dijkstraVia(Edges SQL, via vertices, [options])

options: [directed, strict, U_turn_on_edge]

Returns set of (seq, path_id, 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 \(\{5, 1, 8\}\) in that order on an directed graph.

SELECT * FROM pgr_dijkstraVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  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 |    7 |    1 |        2 |              2
   4 |       1 |        4 |         5 |       1 |    3 |    6 |    1 |        3 |              3
   5 |       1 |        5 |         5 |       1 |    1 |   -1 |    0 |        4 |              4
   6 |       2 |        1 |         1 |       8 |    1 |    6 |    1 |        0 |              4
   7 |       2 |        2 |         1 |       8 |    3 |    7 |    1 |        1 |              5
   8 |       2 |        3 |         1 |       8 |    7 |   10 |    1 |        2 |              6
   9 |       2 |        4 |         1 |       8 |    8 |   -2 |    0 |        3 |              7
(9 rows)

Parameters

Parameter	Type	Default	Description
Edges SQL	TEXT		SQL query as described.
via vertices	ARRAY [ ANY-INTEGER ]		Array of ordered vertices identifiers that are going to be visited.

Where:

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

Optional parameters

Column	Type	Default	Description
directed	BOOLEAN	true	When true the graph is considered Directed When false the graph is considered as Undirected.

Via optional parameters

Parameter	Type	Default	Description
strict	BOOLEAN	false	When true if a path is missing stops and returns EMPTY SET When false ignores missing paths returning all paths found
U_turn_on_edge	BOOLEAN	true	When true departing from a visited vertex will not try to avoid

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 (target, source) When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result columns

Column	Type	Description
seq	INTEGER	Sequential value starting from 1.
path_id	INTEGER	Identifier of a path. Has value 1 for the first path.
path_seq	INTEGER	Relative position in the path. Has value 1 for the beginning of a 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 path sequence.
agg_cost	FLOAT	Aggregate cost from start_vid to node.
route_agg_cost	FLOAT	Total cost from start_vid of seq = 1 to end_vid of the current seq.

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_dijkstraVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  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 |    1 |        2 |              6
  10 |       3 |        4 |         1 |       8 |    8 |   -1 |    0 |        3 |              7
  11 |       4 |        1 |         8 |      15 |    8 |   12 |    1 |        0 |              7
  12 |       4 |        2 |         8 |      15 |   12 |   13 |    1 |        1 |              8
  13 |       4 |        3 |         8 |      15 |   17 |   15 |    1 |        2 |              9
  14 |       4 |        4 |         8 |      15 |   16 |   16 |    1 |        3 |             10
  15 |       4 |        5 |         8 |      15 |   15 |   -2 |    0 |        4 |             11
(15 rows)

Aggregate cost of the third path.

SELECT agg_cost FROM pgr_dijkstraVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  ARRAY[5, 7, 1, 8, 15])
WHERE path_id = 3 AND edge <0;
 agg_cost
----------
        3
(1 row)

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 edges order by id',
  ARRAY[5, 7, 1, 8, 15])
WHERE path_id = 3 AND edge < 0;
 route_agg_cost
----------------
              7
(1 row)

Nodes visited in the route.

SELECT row_number() over () as node_seq, node
FROM  pgr_dijkstraVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  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_dijkstraVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  ARRAY[5, 7, 1, 8, 15])
WHERE edge < 0;
 path_id | route_agg_cost
---------+----------------
       1 |              2
       2 |              4
       3 |              7
       4 |             11
(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_dijkstraVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  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 |              7 |    8 |        3 | visits
  12 |              8 |   12 |        1 | passes in front
  13 |              9 |   17 |        2 | passes in front
  14 |             10 |   16 |        3 | passes in front
  15 |             11 |   15 |        4 | passes in front
(12 rows)

See Also

• Via - Category.

• Dijkstra - Family of functions.

• Sample Data network.

• https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Indices and tables

• Index

• Search Page