pgr_dijkstraNearCost - Propuesto

pgr_dijkstraNearCost — Usando 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.

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_dijkstraNearCost(SQL de aristas, salida, destinos, [opciones A])

pgr_dijkstraNearCost(SQL de aristas, salidas, destino, [opciones A])

pgr_dijkstraNearCost(SQL de aristas, salidas, destinos, [opciones B])

pgr_dijkstraNearCost(SQL de aristas, SQL de combinaciones, [opciones B])

options A: [directed, cap]

options B: [directed, cap, global]

Regresa conjunto de (start_vid, end_vid, agg_cost)

OR EMPTY SET

Uno a Muchos

pgr_dijkstraNearCost(SQL de aristas, salida, destinos, [opciones])

options: [directed, cap]

Regresa conjunto de (start_vid, end_vid, 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

SELECT * FROM pgr_dijkstraNearCost(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  6, ARRAY[10, 11, 1]);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |      11 |        2
(1 row)

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

Muchos a Uno

pgr_dijkstraNearCost(SQL de aristas, salidas, destinos*, [**opciones])

options: [directed, cap]

Regresa conjunto de (start_vid, end_vid, 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 \(6\)

• 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

SELECT * FROM pgr_dijkstraNearCost(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  ARRAY[10, 11, 1], 6,
  true,
  cap => 2) ORDER BY agg_cost;
 start_vid | end_vid | agg_cost
-----------+---------+----------
        10 |       6 |        1
        11 |       6 |        2
(2 rows)

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_dijkstraNearCost(SQL de aristas, salidas, destinos, [opciones])

options: [directed, cap, global]

Regresa conjunto de (start_vid, end_vid, 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

SELECT * FROM pgr_dijkstraNearCost(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  ARRAY[15, 16], ARRAY[10, 11, 1],
  directed => false);
 start_vid | end_vid | agg_cost
-----------+---------+----------
        15 |      10 |        1
(1 row)

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_dijkstraNearCost(SQL de aristas, SQL de combinaciones, [opciones])

options: [directed, cap, global]

Regresa conjunto de (start_vid, end_vid, 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 establecen 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

SELECT * FROM pgr_dijkstraNearCost(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  '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',
  global => false);
 start_vid | end_vid | agg_cost
-----------+---------+----------
        11 |      16 |        1
        15 |      10 |        1
        16 |      11 |        1
        10 |      16 |        2
         1 |      16 |        4
(5 rows)

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 \((11 \rightarrow 16)\) con un costo de \(1\) (line: 1)

• 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)}\)

  • Ambos son igualmente buenos ya que tienen el mismo costo. (lines: 12 and 13)

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

Conjunto de (start_vid, end_vid, agg_cost)

Columna	Tipo	Descripción
start_vid	BIGINT	Identificador del vértice de salida.
end_vid	BIGINT	Identificador del vértice destino.
agg_cost	FLOAT	Costo afregado desde start_vid hasta end_vid.

Ver también

• Dijkstra - Familia de funciones

• pgr_dijkstraNear - Propuesto

• Datos Muestra .

• boost: https://www.boost.org/libs/graph/doc/table_of_contents.html

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

Índices y tablas

• Índice

• Página de Búsqueda