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.

  • No están oficialmente en la versión actual.

  • Es probable que oficialmente formen parte de la próxima versión:

    • 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 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 gráfico, 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 gráficos dirigidos y no dirigidos.

  • Cuando hay más de un trazado 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(Edges SQL, Start vid,  End vids  [, directed] [, cap])
pgr_dijkstraNearCost(Edges SQL, Start vids, End vid   [, directed] [, cap])
pgr_dijkstraNearCost(Edges SQL, Start vids, End vids  [, directed] [, cap], [global])
pgr_dijkstraNearCost(Edges SQL, Combinations SQL  [, directed] [, cap], [global])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Uno a Muchos

pgr_dijkstraNearCost(Edges SQL, Start vid,  End vids [, directed] [, cap])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Ejemplo

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

  • Usando un gráfico dirigido para el enrutamiento de automóviles.

  • Las estaciones de metro se encuentran en los siguientes vértices \(\{ 3, 6, 7\}\)

  • Los valores predeterminados utilizados:

    • directed => true

    • cap => 1

1SELECT * FROM pgr_dijkstraNearCost(
2    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
3    2, ARRAY[3, 6, 7]
4);
5 start_vid | end_vid | agg_cost
6-----------+---------+----------
7         2 |       6 |        2
8(1 row)
9

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

Muchos a Uno

pgr_dijkstraNearCost(Edges SQL, Start vids, End vid  [, directed] [, cap])
RETURNS SET OF (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 \(2\)

  • Usando un gráfico dirigido para el enrutamiento de automóviles.

  • Las estaciones de metro se encuentran en los siguientes vértices \(\{ 3, 6, 7\}\)

  • 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_dijkstraNearCost(
 2    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
 3    ARRAY[3, 6, 7], 2,
 4    true,
 5    cap => 2
 6);
 7 start_vid | end_vid | agg_cost
 8-----------+---------+----------
 9         3 |       2 |        1
10         6 |       2 |        2
11(2 rows)
12

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

Muchos a Muchos

pgr_dijkstraNearCost(Edges SQL, Start vids, End vids [, directed] [, cap], [global])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Ejemplo

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

  • Usando un gráfico no dirigido para el enrutamiento de peatones

  • Las primeras paradas de la línea de metro están en \(\{3, 6, 7\}\)

  • Las segundas estaciones de la línea de metro están en \(\{4, 9\}\)

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

  • Los valores predeterminados utilizados:

    • cap => 1

    • global => true

 1SELECT * FROM pgr_dijkstraNearCost(
 2    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
 3    ARRAY[4, 9], ARRAY[3, 6, 7],
 4    directed => false
 5);
 6 start_vid | end_vid | agg_cost
 7-----------+---------+----------
 8         4 |       3 |        1
 9(1 row)
10

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

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

Combinaciones

pgr_dijkstraNearCost(Edges SQL, Combinations SQL  [, directed] [, cap], [global])
RETURNS SET OF (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 gráfico dirigido para el enrutamiento de automóviles.

  • Las primeras paradas de la línea de metro están en \(\{3, 6, 7\}\)

  • Las segundas estaciones de la línea de metro están en \(\{4, 9\}\)

  • línea 3 establece los vértices de inicio para ser de la primera línea de metro y los vértices finales para ser de la segunda línea de metro

  • la línea 5 establece los vértices de inicio que sean de la primera línea de metro y los vértices finales de la primera línea de metro

  • En la línea 6: el uso del parámetro con nombre es “global “> false”

  • Los valores predeterminados utilizados:

    • directed => true

    • cap => 1

 1SELECT * FROM pgr_dijkstraNearCost(
 2    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
 3    'SELECT unnest(ARRAY[3, 6, 7]) as source, target FROM (SELECT unnest(ARRAY[4, 9]) AS target) a
 4    UNION
 5    SELECT unnest(ARRAY[4, 9]), target FROM (SELECT unnest(ARRAY[3, 6, 7]) AS target) b',
 6    global => false
 7);
 8 start_vid | end_vid | agg_cost
 9-----------+---------+----------
10         4 |       3 |        1
11         6 |       9 |        1
12         9 |       6 |        1
13         3 |       9 |        2
14         7 |       9 |        4
15(5 rows)
16

A partir de los resultados:

  • haciendo una conexión desde la primera línea de metro a la segunda:

    • \({(3 -> 9) (6 -> 9) (7 -> 9)}\) y lo mejor es \((6 -> 9)\) con un costo de \(1\) (line: 11)

  • haciendo una conexión desde la segunda línea de metro a la primera:

    • \({(4 -> 3) (9 -> 6)} \) y`12`)

Parámetros

Parámetro

Tipo

Valores predeterminados

Descripción

Edges SQL

TEXT

Edges query como se describe a continuación

Combinaciones SQL

TEXT

Consulta de combinaciones como se describe a continuación

Start vid

BIGINT

Identificador del vértice inicial de la ruta.

Start vids

ARRAY[BIGINT]

Arreglo de identificadores de vértices iniciales.

End vid

BIGINT

Identificador del vértice final de la ruta.

End vids

ARRAY[BIGINT]

Arreglo de identificadores de vértices finales.

dirigido

BOOLEAN

true

  • En caso de true, el grafo se considera Dirigido

  • Cuando false el gráfo se considera No Dirigido

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

Consulta interna

Consulta de aristas

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

Consulta de combinaciones

Columna

Tipo

Valores predeterminados

Descripción

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.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

Columnas de Devoluciones

Devuelve SET OF (start_vid, end_vid, agg_cost)

Columna

Tipo

Descripción

start_vid

BIGINT

Identificador del vértice inicial.

end_vid

BIGINT

Identificador del vértice final.

agg_cost

FLOAT

Coste agregado de start_vid a end_vid.

Ver también

Índices y tablas