pgr_dijkstraVia - Proposed

Name

pgr_dijkstraVia — Using dijkstra algorithm, it finds the route that goes through a list of vertices.

_images/boost-inside.jpeg

Boost Graph Inside

Availability: 2.2.0

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 for dijkstra like functions

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  

Weight of the edge (source, target)

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

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
  • When true Graph is considered Directed
  • When false the graph is considered as Undirected.
strict BOOLEAN false
  • When false ignores missing paths returning all paths found
  • When true if a path is missing stops and returns EMPTY SET
U_turn_on_edge BOOLEAN true
  • When true departing from a visited vertex will not try to avoid using the edge used to reach it. In other words, U turn using the edge with same id is allowed.
  • When false when a departing from a visited vertex tries to avoid using the edge used to reach it. In other words, U turn using the edge with same id is used when no other path is found.

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)

ROLLBACK;
ROLLBACK