pgr_dijkstraViaVertex

[cvvergara]

This issue is to discuss the signature and functionality for

pgr_dijkstraViaVertex

The function is based on pgr_dijkstra(edges_sql, start_vid, end_vid, directed)

[cvvergara]

problem definition:

Find the route that visits the vertices via1, via2, via3, .... viaN in graph G(V,E):

• in that order
• the path between viaI and viaI+1 is the shortest path.
• starting from subscript 1 as arrays and row numbering start with 1 in postgreSQL.

The shortest path from viaI to viaI+1 can be found using:

SELECT * from pgr_dijkstra(edges_sql, ARRAY[viaI], ARRAY[viaI + 1])

I am using the ARRAY notation of the pgr_dijkstra as it provides more columns in the result:

seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost

In this case start_vid = ARRAY[viaI] in all rows
and also end_vid = ARRAY[viaI + 1] in all rows

So this sequence of queries are performed we get
SELECT * FROM pgr_dijkstra(edges_sql, ARRAY[via1], ARRAY[via2])
SELECT * FROM pgr_dijkstra(edges_sql, ARRAY[via2], ARRAY[via3])
SELECT * FROM pgr_dijkstra(edges_sql, ARRAY[via3], ARRAY[via4])
…
SELECT * FROM pgr_dijkstra(edges_sql, ARRAY[vian-1], ARRAY[viaN])

we can “see” the individual paths that will conform the route.

So, for example:
from the sample_data of the documentation, using a directed graph:
we want to find the route that visits the vertices 1 5 3 9 4 in that order

select * from pgr_dijkstra(
    'select id, source, target, cost, reverse_cost from edge_table', 
    ARRAY[1], ARRAY[5]);
select * from pgr_dijkstra(
    'select id, source, target, cost, reverse_cost from edge_table', 
    ARRAY[5], ARRAY[3]);
select * from pgr_dijkstra(
    'select id, source, target, cost, reverse_cost from edge_table', 
    ARRAY[3], ARRAY[9]);
select * from pgr_dijkstra(
    'select id, source, target, cost, reverse_cost from edge_table', 
    ARRAY[9], ARRAY[4]);

Execution sows:

doc_data=# select * from pgr_dijkstra(
doc_data(#     'select id, source, target, cost, reverse_cost from edge_table', 
doc_data(#     ARRAY[1], ARRAY[5]);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost 
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         1 |       5 |    1 |    1 |    1 |        0
   2 |        2 |         1 |       5 |    2 |    4 |    1 |        1
   3 |        3 |         1 |       5 |    5 |   -1 |    0 |        2
(3 rows)

doc_data=# select * from pgr_dijkstra(
doc_data(#     'select id, source, target, cost, reverse_cost from edge_table', 
doc_data(#     ARRAY[5], ARRAY[3]);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost 
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         5 |       3 |    5 |    8 |    1 |        0
   2 |        2 |         5 |       3 |    6 |    9 |    1 |        1
   3 |        3 |         5 |       3 |    9 |   16 |    1 |        2
   4 |        4 |         5 |       3 |    4 |    3 |    1 |        3
   5 |        5 |         5 |       3 |    3 |   -1 |    0 |        4
(5 rows)

doc_data=# select * from pgr_dijkstra(
doc_data(#     'select id, source, target, cost, reverse_cost from edge_table', 
doc_data(#     ARRAY[3], ARRAY[9]);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost 
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         3 |       9 |    3 |    5 |    1 |        0
   2 |        2 |         3 |       9 |    6 |    9 |    1 |        1
   3 |        3 |         3 |       9 |    9 |   -1 |    0 |        2
(3 rows)

doc_data=# select * from pgr_dijkstra(
doc_data(#     'select id, source, target, cost, reverse_cost from edge_table', 
doc_data(#     ARRAY[9], ARRAY[4]);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost 
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         9 |       4 |    9 |   16 |    1 |        0
   2 |        2 |         9 |       4 |    4 |   -1 |    0 |        1
(2 rows)

[cvvergara]

Manualy from the above results:

• making a big table
• adding a path_id : gives an ordering to the individual paths.
• adding a route_agg_cost : gives the route's aggregate cost
• fixing the seq number : would be the routes's sequence
• note: I am not deleting any row of the original results
• for clarity I am leaving a line between paths

 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 |   -1 |    0 |        1 |  9

[cvvergara]

Suppose that select * pgr_dijkstraViaVertices(<params>) returns the values posted in the previous comment.

1. what's the aggregate cost of the third path?

SELECT agg_cost FROM  pgr_dijkstraViaVertices(<params>) 
  WHERE path_id = 3 AND edge = -1

2. what's the aggregate cost of the route at the end of the third path?

SELECT route_agg_cost FROM  pgr_dijkstraViaVertices(<params>)
   WHERE path_id = 3 AND edge = -1

3. how are the nodes visited in the route?

SELECT row_number() over () as node_seq, node 
  FROM  pgr_dijkstraViaVertices(<params>) 
  WHERE edge <> -1 ORDER BY seq;

4. what are the aggregate cots of the route when the visited vertices are reached?

SELECT path_id, route_agg_cost FROM  pgr_dijkstraViaVertices(<params>) 
  WHERE edge = -1

5. show the route's seq and aggregate cost and a status of if passes in front or visits node 9

SELECT seq, route_agg_cost, 
  CASE WHEN edge = -1 THEN "visits"
           ELSE "passes in front"
  END as status
 FROM  pgr_dijkstraViaVertices(<params>) 
 WHERE node = 9 AND agg_cost<>0

[woodbri]

I have started a wiki page describing some ideas related to latlon, vertex, edge, heading in the definition and use in pgrouting.
https://github.com/pgRouting/pgrouting/wiki/Defining-Vias-with-%28Loc-or-Vertex-or-Edge%29-and-Heading

[cvvergara]

@woodbri
as you see, this is based on pgr_dijkstra as is defined:
Is defined here: http://docs.pgrouting.org/2.1/src/dijkstra/doc/index.html#pgr-dijkstra
the usage is here: http://docs.pgrouting.org/2.1/src/dijkstra/doc/dijkstra_v3.html#pgr-dijkstra-v3
So the that wiki doesn't apply here, it can apply to this non existing pgr_withHeading in #425
I placed the link in that issue.

[TheRealDashu]

I need that functionality. I was pretty happy that i found someone working on it. But i cant seem to build the 2.2dev branch. error: ISO C does not support ‘__int128’ type

[cvvergara]

pgr_dijkstraVia is being added as a proposed function in V2.2
Documentation of pgr_dijkstraVia can be found at
http://docs.pgrouting.org/dev/src/dijkstra/doc/pgr_dijkstraVia.html

Closing this issue