pgr_dijkstraNear - Experimental

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

Advertencia

Posible bloqueo del servidor

  • Estas funciones pueden crear un bloqueo del servidor

Advertencia

Funciones experimentales

  • No son oficialmente de la versión actual.

  • Es probable que oficialmente no formen parte de la siguiente versión:

    • Las funciones no podrían hacer uso de ANY-INTEGER ni ANY-NUMERICAL

    • El nombre puede cambiar.

    • La firma o declaración de funciones podría cambiar.

    • La funcionalidad puede cambiar.

    • Las pruebas de pgTap pueden estar ausentes.

    • Posiblemente necesite codificación c/c++.

    • Puede haber carencia de documentación.

    • Hay documentación que, en dado caso, podría ser necesario reescribir.

    • Ejemplos de documentación que puede ser necesario generar automáticamente.

    • Puede ser necesaria más retroalimentación por parte de la comunidad.

    • Puede depender de una función propuesta de pgRouting.

    • Podría depender de una función obsoleta de pgRouting

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • 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(Edges SQL, Start vid,  End vids  [, directed] [, cap])
pgr_dijkstraNear(Edges SQL, Start vids, End vid   [, directed] [, cap])
pgr_dijkstraNear(Edges SQL, Start vids, End vids  [, directed] [, cap], [global])
pgr_dijkstraNear(Edges SQL, Combinations SQL  [, 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(Edges SQL, Start vid,  End vids [, 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 \(2\) encontrar la estación de metro más cercana.

  • Usando un grafo 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_dijkstraNear(
 2    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
 3    2, ARRAY[3, 6, 7]
 4);
 5 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
 6-----+----------+-----------+---------+------+------+------+----------
 7   1 |        1 |         2 |       6 |    2 |    4 |    1 |        0
 8   2 |        2 |         2 |       6 |    5 |    8 |    1 |        1
 9   3 |        3 |         2 |       6 |    6 |   -1 |    0 |        2
10(3 rows)
11

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

Muchos a Uno

pgr_dijkstraNear(Edges SQL, Start vids, End vid  [, 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 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_dijkstraNear(
 2    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
 3    ARRAY[3, 6, 7], 2,
 4    true,
 5    cap => 2
 6);
 7 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
 8-----+----------+-----------+---------+------+------+------+----------
 9   1 |        1 |         3 |       2 |    3 |    2 |    1 |        0
10   2 |        2 |         3 |       2 |    2 |   -1 |    0 |        1
11   3 |        1 |         6 |       2 |    6 |    8 |    1 |        0
12   4 |        2 |         6 |       2 |    5 |    4 |    1 |        1
13   5 |        3 |         6 |       2 |    2 |   -1 |    0 |        2
14(5 rows)
15

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_dijkstraNear(Edges SQL, Start vids, End vids [, 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 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_dijkstraNear(
 2    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
 3    ARRAY[4, 9], ARRAY[3, 6, 7],
 4    directed => false
 5);
 6 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
 7-----+----------+-----------+---------+------+------+------+----------
 8   1 |        1 |         4 |       3 |    4 |    3 |    1 |        0
 9   2 |        2 |         4 |       3 |    3 |   -1 |    0 |        1
10(2 rows)
11

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_dijkstraNear(Edges SQL, Combinations SQL  [, 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 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: 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 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 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
 9-----+----------+-----------+---------+------+------+------+----------
10   1 |        1 |         4 |       3 |    4 |    3 |    1 |        0
11   2 |        2 |         4 |       3 |    3 |   -1 |    0 |        1
12   3 |        1 |         6 |       9 |    6 |    9 |    1 |        0
13   4 |        2 |         6 |       9 |    9 |   -1 |    0 |        1
14   5 |        1 |         9 |       6 |    9 |    9 |    1 |        0
15   6 |        2 |         9 |       6 |    6 |   -1 |    0 |        1
16   7 |        1 |         3 |       9 |    3 |    5 |    1 |        0
17   8 |        2 |         3 |       9 |    6 |    9 |    1 |        1
18   9 |        3 |         3 |       9 |    9 |   -1 |    0 |        2
19  10 |        1 |         7 |       9 |    7 |    6 |    1 |        0
20  11 |        2 |         7 |       9 |    8 |    7 |    1 |        1
21  12 |        3 |         7 |       9 |    5 |    8 |    1 |        2
22  13 |        4 |         7 |       9 |    6 |    9 |    1 |        3
23  14 |        5 |         7 |       9 |    9 |   -1 |    0 |        4
24(14 rows)
25

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 el mejor es \((6 -> 9)\) con un costo de \(1\) (línea: 12 y 13)

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

    • \({(4 -> 3) (9 -> 6)}\) y ambos son igualmente buenos, como también tienen el mismo costo. (líneas: 10 y 11 y líneas: 14 y 15)

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 grafo 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 (origen, objetivo) 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 (objetivo, origen) 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 DE (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) O CONJUNTO VACÍO

Columna

Tipo

Descripción

seq

BIGINT

Valor secuencial a partir de 1.

path_seq

BIGINT

Valor secuencial a partir de 1 para cada ruta \((start\_vid \to end\_vid)\).

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 posición path_seq en la ruta \((start\_vid \to end\_vid)\).

edge

BIGINT

Identificador del borde utilizado para ir del nodo en path_seq al nodo en path_seq + 1 en la ruta:math:(start_vid to end_vid).

  • \(-1\) 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.

  • \(0\) para la última fila de la ruta.

agg_cost

FLOAT

Costo total de recorrer \((start\_vid \to node)\) sección de la ruta \((start\_vid \to end\_vid)\).

Ver también

Índices y tablas