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

Soporte

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¶

Índices y tablas