`pgr_dijkstraVia` - Propuesto¶

pgr_dijkstraVia - Ruta que recorre una lista de vértices.

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 ENTEROS y FLOTANTES
- Probablemente el nombre no cambie. (Pero todavía puede)
- Es posible que la firma no cambie. (Pero todavía puede)
- Probablemente 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 — 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 el camino más corto entre \(vértice_i\) y \(vértice_{i+1}\) para todo \(i < tamaño\_de(vía\;vértices)\).

Ruta:: es una secuencia de trayectorias.
Ruta:: es una sección de la ruta.

Firmas¶

Una Vía¶

pgr_dijkstraVia(SQL de aristas, vértices, [opciones])

opcionales: [directed, strict, U_turn_on_edge]

Regresa el conjunto de (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost, route_agg_cost)

O CONJUNTO VACÍO

Ejemplo:: Encontrar la ruta que visita los vértices \({5, 1, 8\}\) en ese orden en un grafo dirigido.

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)

Parámetros¶

Parámetro	Tipo	x Defecto	Descripción
SQL de aristas	`TEXT`		Consulta SQL como se describe.
vértices	`ARRAY` [ENTEROS ]		Arreglo ordenado de identificadores de vértices que serán visitados.

Donde:

ENTEROS:: SMALLINT, INTEGER, BIGINT

Parámetros opcionales¶

Columna	Tipo	x Defecto	Descripción
`directed`	`BOOLEAN`	`true`	Cuando `true` el gráfo se considera Dirigido Cuando `false` el gráfo se considera No Dirigido.

Parámetros opcionales Vía¶

Parámetro	Tipo	x Defecto	Descripción
`strict`	`BOOLEAN`	`false`	Cuando `true` si un camino le faltan paradas y regresa EMPTY SET Cuando `false`, ignora las rutas faltantes y devuelve todas las rutas encontradas
`U_turn_on_edge`	`BOOLEAN`	`true`	Cuando `true` saliendo desde un vértice visitado no intentara esquivarlo

Consultas Internas¶

SQL aristas¶

Columna	Tipo	x Defecto	Descripción
`id`	ENTEROS		Identificador de la arista.
`source`	ENTEROS		Identificador del primer vértice de la arista.
`target`	ENTEROS		Identificador del segundo vértice de la arista.
`cost`	FLOTANTES		Peso de la arista (`source`, `target`)
`reverse_cost`	FLOTANTES	-1	Peso de la arista (`target`, `source`) Cuando negativo: la arista (`target`, `source`) no existe, por lo tanto no es parte del grafo.

Donde:

ENTEROS:: SMALLINT, INTEGER, BIGINT
FLOTANTES:: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de resultados¶

Columna	Tipo	Descripción
`seq`	`INTEGER`	Valor secuencial a partir de 1.
`path_id`	`INTEGER`	Identificador del camino. Tiene valor 1 para el primer camino.
`path_seq`	`INTEGER`	Posición relativa en la ruta. Tiene el valor 1 para el inicio de una 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 la arsita utilizada para ir del `node` al siguiente nodo de la secuencia de ruta. -1 para el último nodo de la ruta. -2 para el último nodo de la ruta.
`cost`	`FLOAT`	Costo para atravesar desde `node` usando `edge` hasta el siguiente nodo en la secuencia de la ruta.
`agg_cost`	`FLOAT`	Costo agregado desde `start_vid` hasta `node`.
`route_agg_cost`	`FLOAT`	Costo total desde `start_vid` en `seq = 1` hasta `end_vid` del `seq` actual.

Ejemplos Adicionales¶

Todos estos ejemplos son sobre la ruta que visita los vértices \(\{5, 7, 1, 8, 15\}\) en ese orden, en un grafo dirigido.

La consulta principal ¶

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 |         5 |       7 |    5 |    1 |    1 |        0 |              0
|       1 |        2 |         5 |       7 |    6 |    4 |    1 |        1 |              1
|       1 |        3 |         5 |       7 |    7 |   -1 |    0 |        2 |              2
|       2 |        1 |         7 |       1 |    7 |    7 |    1 |        0 |              2
|       2 |        2 |         7 |       1 |    3 |    6 |    1 |        1 |              3
|       2 |        3 |         7 |       1 |    1 |   -1 |    0 |        2 |              4
|       3 |        1 |         1 |       8 |    1 |    6 |    1 |        0 |              4
|       3 |        2 |         1 |       8 |    3 |    7 |    1 |        1 |              5
|       3 |        3 |         1 |       8 |    7 |   10 |    1 |        2 |              6
|       3 |        4 |         1 |       8 |    8 |   -1 |    0 |        3 |              7
|       4 |        1 |         8 |      15 |    8 |   12 |    1 |        0 |              7
|       4 |        2 |         8 |      15 |   12 |   13 |    1 |        1 |              8
|       4 |        3 |         8 |      15 |   17 |   15 |    1 |        2 |              9
|       4 |        4 |         8 |      15 |   16 |   16 |    1 |        3 |             10
|       4 |        5 |         8 |      15 |   15 |   -2 |    0 |        4 |             11
(15 rows)

Costo agregado de la tercera ruta.¶

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)

Costo agregado al final de la tercera ruta.¶

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)

Nodos visitados en la ruta.¶

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)

Costo agregado de la ruta al llegar a los vértices visitados.¶

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)

Estado de «pasa enfrente» o «visita» los nodos.¶

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)

Ver también¶

Índices y tablas

pgr_dijkstraVia - Propuesto¶

Descripción¶

Firmas¶

Una Vía¶

Parámetros¶

Parámetros opcionales¶

Parámetros opcionales Vía¶

Consultas Internas¶

SQL aristas¶

Columnas de resultados¶

Ejemplos Adicionales¶

La consulta principal¶

Costo agregado de la tercera ruta.¶

Costo agregado al final de la tercera ruta.¶

Nodos visitados en la ruta.¶

Costo agregado de la ruta al llegar a los vértices visitados.¶

Estado de «pasa enfrente» o «visita» los nodos.¶

Ver también¶

`pgr_dijkstraVia` - Propuesto¶

La consulta principal ¶