pgr_dijkstraVia - Propuesto

pgr_dijkstraVia — Utilizando el algoritmo dijkstra, encuentra la ruta que pasa por una lista de vértices.

Advertencia

Funciones propuestas para el próximo lanzamineto.

• 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 de pgTap. Pero tal vez necesite más.

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

Adentro: Boost Graph

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

Resumen

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

Uso de valores predeterminados

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

Ejemplo

Encuentre la ruta que visita los vértices \(\{ 1, 3, 9\}\) en ese orden

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)

Firma completa

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

Ejemplo

Encuentre la ruta que visita los vértices \(\{ 1, 3, 9\}\) en ese orden en un grafo no direccionado, evitando los giros en U cuando sea posible

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 |    3 |    1 |        0 |              2
   5 |       2 |        2 |         3 |       9 |    4 |   16 |    1 |        1 |              3
   6 |       2 |        3 |         3 |       9 |    9 |   -2 |    0 |        2 |              4
(6 rows)

Parámetros

Parámetro	Tipo	Valores predeterminados	Descripción
edges_sql	TEXT		Consulta SQL como se describió anteriormente.
via_vertices	ARRAY[ANY-INTEGER]		Arreglo de identificadores de vértices ordenados que serán visitados.
dirigido	BOOLEAN	true	Cuando true el gráfo se considera Dirigido Cuando false el gráfico se considera como No Dirigido
strict	BOOLEAN	false	En caso de false, ignora las rutas faltantes y devuelve todas las rutas encontradas en caso de true si falta una ruta de acceso se detiene y devuelve EMPTY SET
U_turn_on_edge	BOOLEAN	true	En caso de true saliendo de un vértice visitado no intentará evitar el uso de la arista utilizada para alcanzarlo. En otras palabras, se permite el giro U utilizando la arista con el mismo “id”. En caso de false cuando una salida de un vértice visitado intenta evitar el uso de la arista utilizada para alcanzarlo. En otras palabras, se utiliza el giro U utilizando el borde con el mismo id cuando no se encuentra ninguna otra ruta.

Consulta interna

Columna	Tipo	Valores predeterminados	Descripción
id	ANY-INTEGER		Identificador de la arista.
origen	ANY-INTEGER		Identificador del primer punto final en el vértice de la arista.
objetivo	ANY-INTEGER		Identificador del segundo punto final en el vértice de la arista.
cost	ANY-NUMERICAL		Peso de la arista (source, target) Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.
reverse_cost	ANY-NUMERICAL	-1	Peso de la arista (target, source), En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Devoluciones

Devuelve un conjunto de (start_vid, end_vid, agg_cost)

Columna	Tipo	Descripción
seq	BIGINT	Valor secuencial a partir de 1.
path_pid	BIGINT	Identificador de la ruta.
path_seq	BIGINT	Valor secuencial a partir de 1 para la ruta.
start_vid	BIGINT	Identificador del vértice inicial de la ruta.
end_vid	BIGINT	Identificador del vértice final de la ruta.
node	BIGINT	Identificador del nodo en la ruta de start_vid a end_vid.
edge	BIGINT	Identificador de arista utilizado para pasar del nodo al siguiente nodo de la secuencia de la ruta. -1 para el último nodo de la trayectoria. -2 para el último nodo de la ruta.
cost	FLOAT	Coste para recorrer desde node usando edge hacia el siguiente nodo de la secuencia de ruta.
agg_cost	FLOAT	Coste total desde start_vid hacia end_vid de la ruta.
route_agg_cost	FLOAT	Coste total desde start_vid de path_pid = 1 hacia end_vid del actual path_pid .

Ejemplos Adicionales

Ejemplo 1

Encuentre la ruta que visita los vértices \(\{1, 5, 3, 9, 4\}\) en ese orden

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)

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, 3, 9, 4]
)
WHERE path_id = 3 AND edge <0;
 agg_cost
----------
        2
(1 row)

Ejemplo 3

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

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)

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, 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)

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

Ejemplo 6

Muestre la secuencia de la ruta, el costo agregado y el estado de los «pases al frente» o del nodo \(9\) , «visitss»

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

Ver también

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

• Red Datos Muestra .

Índices y tablas

• Índice

• Página de Búsqueda