pgr_dijkstraNear - Propuesto

pgr_dijkstraNear — Utilizando el algoritmo dijkstra, encuentra la ruta que conduce al vértice más cercano.

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

  • Versión 3.3.0

    • Promovido a función propuesta

  • Versión 3.2.0

    • Nueva función experimental

Descripción

Dado un grafo, un vértice inicial y un conjunto de vértices finales, esta función encuentra la ruta más corta desde el vértice inicial hasta el vértice final más cercano.

Características

  • Utiliza el algoritmo Dijkstra.

  • Funciona para grafos dirigidos y no dirigidos.

  • Cuando hay más de una ruta al mismo vértice con el mismo coste:

    • El algoritmo devolverá solo una ruta

  • Opcionalmente permite encontrar más de una ruta.

    • Cuando se va a devolver más de una ruta:

      • Los resultados se ordenan en orden creciente de:

        • costo agregado

        • Dentro del mismo valor de los costes agregados:

          • los resultados se ordenan por (fuente, destino)

  • Tiempo de ejecución: Dijkstra tiempo de ejecución: \(drt = O((|E| + |V|)log|V|)\)

    • Uno a Muchos; \(drt\)

    • Muchos a Uno: \(drt\)

    • Muchos a Muchos: \(drt * |Starting vids|\)

    • Combinaciones: \(drt * |Starting vids|\)

Firmas

Resumen

pgr_dijkstraNear(SQL de aristas, salida, destinos, [opciones A])
pgr_dijkstraNear(SQL de aristas, salidas, destino, [opciones A])
pgr_dijkstraNear(SQL de aristas, salidas, destinos, [opciones B])
pgr_dijkstraNear(SQL de aristas, SQL de combinaciones, [opciones B])
options A: [directed, cap]
options B: [directed, cap, global]
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Uno a Muchos

pgr_dijkstraNear(SQL de aristas, salida, destinos, [opciones])
options: [directed, cap]
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo:

Saliendo en coche desde el vértice \(6\) encontrar la estación de metro más cercana.

  • Usando un grafo dirigido para el ruteo de automóviles.

  • Las estaciones de metro se encuentran en los siguientes vértices \(\{ 1, 10, 11\}\)

  • Los valores predeterminados utilizados:

    • directed => true

    • cap => 1

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

El resultado muestra que la estación en el vértice \(11\) es la más cercana.

Muchos a Uno

pgr_dijkstraNear(SQL de aristas, salidas, destino, [opciones])
options: [directed, cap]
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo:

Saliendo en coche desde una estación de metro encontrar las dos estaciones más cercanas al vértice \(2\)

  • Usando un grafo dirigido para el ruteo de automóviles.

  • Las estaciones de metro se encuentran en los siguientes vértices \(\{ 1, 10, 11\}\)

  • En la línea 4: utilizando el parámetro posicional: directed configurado en true

  • En la línea 5: usando el parámetro con nombre cap => 2

 1SELECT * FROM pgr_dijkstraNear(
 2  'SELECT id, source, target, cost, reverse_cost FROM edges',
 3  ARRAY[10, 11, 1], 6,
 4  true,
 5  cap => 2);
 6 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
 7-----+----------+-----------+---------+------+------+------+----------
 8   1 |        1 |        10 |       6 |   10 |    2 |    1 |        0
 9   2 |        2 |        10 |       6 |    6 |   -1 |    0 |        1
10   3 |        1 |        11 |       6 |   11 |    8 |    1 |        0
11   4 |        2 |        11 |       6 |    7 |    4 |    1 |        1
12   5 |        3 |        11 |       6 |    6 |   -1 |    0 |        2
13(5 rows)
14

El resultado muestra que la estación en el vértice \(10\) es la más cercana y la siguiente mejor es \(11\).

Muchos a Muchos

pgr_dijkstraNear(SQL de aristas, salidas, destinos, [opciones])
options: [directed, cap, global]
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo:

Encuentra la mejor conexión peatonal entre dos líneas de autobuses

  • Usando un grafo no dirigido para el ruteo de peatones

  • Las estaciones de la primera línea de metro están en \(\{15, 16\}\)

  • Las estaciones de la segunda línea de metro están en \(\{1, 10, 11\}\)

  • En la línea 4: utilizando el parámetro con nombre: directed => false

  • Los valores predeterminados utilizados:

    • cap => 1

    • global => true

 1SELECT * FROM pgr_dijkstraNear(
 2  'SELECT id, source, target, cost, reverse_cost FROM edges',
 3  ARRAY[15, 16], ARRAY[10, 11, 1],
 4  directed => false);
 5 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
 6-----+----------+-----------+---------+------+------+------+----------
 7   1 |        1 |        15 |      10 |   15 |    3 |    1 |        0
 8   2 |        2 |        15 |      10 |   10 |   -1 |    0 |        1
 9(2 rows)
10

Para un peatón la mejor conexión es subir/bajar en el vértice \(15\) de la primera línea de metro y en el vértice \(10\) de la segunda línea de metro.

Solo se devuelve una ruta porque global es true y cap es 1

Combinaciones

pgr_dijkstraNear(SQL de aristas, SQL de combinaciones, [opciones])
options: [directed, cap, global]
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo:

Encuentra la mejor conexión de coche entre todas las estaciones de dos líneas de metro

  • Usando un grafo dirigido para el ruteo de automóviles.

  • Las estaciones de la primera línea de metro están en \(\{1, 10, 11\}\)

  • Las estaciones de la segunda línea de metro están en \(\{15, 16\}\)

El contenido de las combinaciones:

SELECT unnest(ARRAY[10, 11, 1]) as source, target
FROM (SELECT unnest(ARRAY[15, 16]) AS target) a
  UNION
SELECT unnest(ARRAY[15, 16]), target
FROM (SELECT unnest(ARRAY[10, 11, 1]) AS target) b ORDER BY source, target;
 source | target
--------+--------
      1 |     15
      1 |     16
     10 |     15
     10 |     16
     11 |     15
     11 |     16
     15 |      1
     15 |     10
     15 |     11
     16 |      1
     16 |     10
     16 |     11
(12 rows)

La consulta:

  • líneas 3~4 establece los vértices de inicio de la primera línea de metro y los vértices finales de la segunda línea de metro

  • la línea 6~7 establecen los vértices de inicio de la primera línea de metro y los vértices finales de la primera línea de metro

  • En la línea 8: usando el parámetro con nombre global => false

  • Los valores predeterminados utilizados:

    • directed => true

    • cap => 1

 1SELECT * FROM pgr_dijkstraNear(
 2  'SELECT id, source, target, cost, reverse_cost FROM edges',
 3  'SELECT unnest(ARRAY[10, 11, 1]) as source, target
 4  FROM (SELECT unnest(ARRAY[15, 16]) AS target) a
 5  UNION
 6  SELECT unnest(ARRAY[15, 16]), target
 7  FROM (SELECT unnest(ARRAY[10, 11, 1]) AS target) b',
 8  global => false);
 9 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
10-----+----------+-----------+---------+------+------+------+----------
11   1 |        1 |        11 |      16 |   11 |    9 |    1 |        0
12   2 |        2 |        11 |      16 |   16 |   -1 |    0 |        1
13   3 |        1 |        15 |      10 |   15 |    3 |    1 |        0
14   4 |        2 |        15 |      10 |   10 |   -1 |    0 |        1
15   5 |        1 |        16 |      11 |   16 |    9 |    1 |        0
16   6 |        2 |        16 |      11 |   11 |   -1 |    0 |        1
17   7 |        1 |        10 |      16 |   10 |    5 |    1 |        0
18   8 |        2 |        10 |      16 |   11 |    9 |    1 |        1
19   9 |        3 |        10 |      16 |   16 |   -1 |    0 |        2
20  10 |        1 |         1 |      16 |    1 |    6 |    1 |        0
21  11 |        2 |         1 |      16 |    3 |    7 |    1 |        1
22  12 |        3 |         1 |      16 |    7 |    8 |    1 |        2
23  13 |        4 |         1 |      16 |   11 |    9 |    1 |        3
24  14 |        5 |         1 |      16 |   16 |   -1 |    0 |        4
25(14 rows)
26

A partir de los resultados:

  • haciendo una conexión desde la primera línea de metro \(\{1, 10, 11\}\) a la segunda \(\{15, 16\}\):

    • Las mejores conecciones de todas las estaciones desde la primera línea son: \({(1 \rightarrow 16) (10 \rightarrow 16) (11 \rightarrow 16)}\)

    • La mejor es:math:(11 rightarrow 16) con un costo de \(1\) (líneas: 11 y 12)

  • haciendo una conexión desde la segunda línea de metro \(\{15, 16\}\) a la primera \(\{1, 10, 11\}\):

    • Las mejores conecciones de todas las estaciones desde la segunda línea son: \({(15 \rightarrow 10) (16 \rightarrow 11)}\)

    • Ambas son igualmente buenas, como también tienen el mismo costo. (lines: 13 and 14 and lines: 15 and 16)

Parámetros

Columna

Tipo

Descripción

SQL de aristas

TEXT

SQL de aristas como se describe a continuación

SQL de combinaciones

TEXT

SQL de combinaciones como se describe a abajo

salida

BIGINT

Identificador del vértice inicial de la ruta.

salidas

ARRAY[BIGINT]

Arreglo de identificadores de vértices iniciales.

destino

BIGINT

Identificador del vértice final de la ruta.

destinos

ARRAY[BIGINT]

Arreglo de identificadores de vértices finales.

Parámetros opcionales de Dijkstra

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 de Cercanía

Parámetro

Tipo

x Defecto

Descripción

cap

BIGINT

1

Encuentra como máximo el número cap de los caminos más cortos y más cercanos

global

BOOLEAN

true

  • Cuando true: solo se devolverán los resultados del límite cap

  • Cuando false: cap límite por Start vid será devuelto

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

SQL Combinaciones

Parámetro

Tipo

Descripción

source

ENTEROS

Identificador del vértice de salida.

target

ENTEROS

Identificador del vértice de llegada.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

Columnas de Resultados

Regresa (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

Columna

Tipo

Descripción

seq

INTEGER

Valor secuencial a partir de 1.

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 actual.

end_vid

BIGINT

Identificador del vértice final de la ruta actual.

node

BIGINT

Identificador del nodo en la ruta de start_vid a end_vid.

edge

BIGINT

Identificador de la arista utilizado para ir del node al siguiente nodo de la secuencia de ruta. -1 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.

Ver también

Índices y tablas