pgr_dijkstraVia - Proposed

pgr_dijkstraVia — Route that goes through a list of vertices.

Advertencia

Funciones propuestas para la próxima versión mayor.

  • No están oficialmente en la versión actual.

  • Es probable que oficialmente formen parte del próximo lanzamiento:

    • Las funciones hacen uso de ANY-INTEGER y ANY-NUMERICAL

    • Es posible que el nombre no cambie. (Pero todavía puede)

    • Es posible que la firma no cambie. (Pero todavía puede)

    • Es posible que la funcionalidad no cambie. (Pero todavía puede)

    • Se han hecho pruebas con pgTap. Pero tal vez se necesiten más.

    • Es posible que la documentación necesite un refinamiento.

_images/boost-inside.jpeg

Boost Graph Inside

Disponibilidad

  • Version 2.2.0

    • Nueva función propuesta

Descripción

Dada una lista de vértices y un grafo, esta función equivale a encontrar la ruta más corta entre \(vertex_i\) y \(vertex_{i+1}\) para todos \(i < size\_of(vertex_via)\).

Las trayectorias representan los tramos de la ruta.

Firmas

One Via

pgr_dijkstraVia(Edges SQL, via vertices
           [, directed] [, strict] [, U_turn_on_edge]) - Proposed on v2.2
RETURNS SET OF (seq, path_pid, path_seq, start_vid, end_vid,
                node, edge, cost, agg_cost, route_agg_cost)
OR EMPTY SET
Ejemplo

Find the route that visits the vertices \(\{ 1, 7, 10\}\) in that order on an directed graph.

SELECT * FROM pgr_dijkstraVia(
  'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
  ARRAY[1, 7, 10]);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         1 |       7 |    1 |    1 |    1 |        0 |              0
   2 |       1 |        2 |         1 |       7 |    2 |    4 |    1 |        1 |              1
   3 |       1 |        3 |         1 |       7 |    5 |    7 |    1 |        2 |              2
   4 |       1 |        4 |         1 |       7 |    8 |    6 |    1 |        3 |              3
   5 |       1 |        5 |         1 |       7 |    7 |   -1 |    0 |        4 |              4
   6 |       2 |        1 |         7 |      10 |    7 |    6 |    1 |        0 |              4
   7 |       2 |        2 |         7 |      10 |    8 |    7 |    1 |        1 |              5
   8 |       2 |        3 |         7 |      10 |    5 |   10 |    1 |        2 |              6
   9 |       2 |        4 |         7 |      10 |   10 |   -2 |    0 |        3 |              7
(9 rows)

Parámetros

Parámetro

Tipo

x Defecto

Descripción

Edges SQL

TEXT

SQL query as described.

via vertices

ARRAY[ ANY-INTEGER ]

Arreglo ordenados de identificadores de vértices que serán visitados.

Optional parameters

Columna

Tipo

default

Descripción

directed

BOOLEAN

true

  • When true the graph is considered Directed

  • When false the graph is considered as Undirected.

Via optional parameters

Parámetro

Tipo

x Defecto

Descripción

strict

BOOLEAN

false

  • When true if a path is missing stops and returns EMPTY SET

  • En caso de false, ignora las rutas faltantes y devuelve todas las rutas encontradas

U_turn_on_edge

BOOLEAN

true

  • When true departing from a visited vertex will not try to avoid

Consulta interna

Edges SQL

Columna

Tipo

x Defecto

Descripción

id

ANY-INTEGER

Identificador de la arista.

source

ANY-INTEGER

Identificador del primer vértice extremo de la arista.

target

ANY-INTEGER

Identificador del segundo vértice extremo de la arista.

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.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Devoluciones

Columna

Tipo

Descripción

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

Identificador del vértice inicial de la ruta.

end_vid

BIGINT

Identificador del vértice final de la ruta.

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.

Ejemplos Adicionales

Ejemplo 1

Find the route that visits the vertices \(\{1, 5, 7, 10, 4\}\) in that order

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

Ejemplo 2

¿Cuál es el costo total de la tercera ruta?

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

Ejemplo 3

¿Cuál es el costo agregado de la ruta al final de la tercera ruta?

SELECT route_agg_cost FROM pgr_dijkstraVia(
  'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
  ARRAY[1, 5, 7, 10, 4])
WHERE path_id = 3 AND edge < 0;
 route_agg_cost
----------------
              7
(1 row)

Ejemplo 4

¿Cómo se visitan los nodos en la ruta?

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, 7, 10, 4])
WHERE edge <> -1 ORDER BY seq;
 node_seq | node
----------+------
        1 |    1
        2 |    2
        3 |    5
        4 |    8
        5 |    7
        6 |    8
        7 |    5
        8 |   10
        9 |   11
       10 |   12
       11 |    9
       12 |    4
(12 rows)

Ejemplo 5

¿Cuáles son los costos agregados de la ruta cuando se llega a los vértices visitados?

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, 7, 10, 4])
WHERE edge < 0;
 path_id | route_agg_cost
---------+----------------
       1 |              2
       2 |              4
       3 |              7
       4 |             11
(4 rows)

Ejemplo 6

Show the route’s seq and aggregate cost and a status of «passes in front» or «visits»

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, 7, 10, 4])
WHERE agg_cost  <> 0 or seq = 1;
 seq | route_agg_cost | node | agg_cost |     status
-----+----------------+------+----------+-----------------
   1 |              0 |    1 |        0 | passes in front
   2 |              1 |    2 |        1 | passes in front
   3 |              2 |    5 |        2 | visits
   5 |              3 |    8 |        1 | passes in front
   6 |              4 |    7 |        2 | visits
   8 |              5 |    8 |        1 | passes in front
   9 |              6 |    5 |        2 | passes in front
  10 |              7 |   10 |        3 | visits
  12 |              8 |   11 |        1 | passes in front
  13 |              9 |   12 |        2 | passes in front
  14 |             10 |    9 |        3 | passes in front
  15 |             11 |    4 |        4 | passes in front
(12 rows)

Ver también

Índices y tablas