pgr_dijkstraNear - Proposed

pgr_dijkstraNear — Using Dijkstra’s algorithm, finds the route that leads to the nearest vertex.

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

    • 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 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(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 (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 (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo:

Departing on car from vertex \(6\) find the nearest subway station.

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

  • The subway stations are on the following vertices \(\{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

The result shows that station at vertex \(11\) is the nearest.

Muchos a Uno

pgr_dijkstraNear(Edges SQL, start vids, end vid
           [, directed] [, cap])
RETURNS (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.

  • The subway stations are on the following vertices \(\{ 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

The result shows that station at vertex \(10\) is the nearest and the next best is \(11\).

Muchos a Muchos

pgr_dijkstraNear(Edges SQL, start vids, end vids
           [, directed] [, cap], [global])
pgr_dijkstraNear(Edges SQL, Start vids, End vids
           [, directed] [, cap], [global])
RETURNS (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

  • The first subway line stations are at \(\{15, 16\}\)

  • The second subway line stations stops are at \(\{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

For a pedestrian the best connection is to get on/off is at vertex \(15\) of the first subway line and at vertex \(10\) of the second subway line.

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

Combinaciones

pgr_dijkstraNear(Edges SQL, Combinations SQL
           [, directed] [, cap] [, global])
RETURNS (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.

  • The first subway line stations stops are at \(\{1, 10, 11\}\)

  • The second subway line stations are at \(\{15, 16\}\)

The combinations contents:

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)

The query:

  • lines 3~4 sets the start vertices to be from the first subway line and the ending vertices to be from the second subway line

  • lines 6~7 sets the start vertices to be from the first subway line and the ending vertices to be from the first subway line

  • On line 8: using the named parameter is 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:

  • making a connection from the first subway line \(\{1, 10, 11\}\) to the second \(\{15, 16\}\):

    • The best connections from all the stations from the first line are: \({(1 \rightarrow 16) (10 \rightarrow 16) (11 \rightarrow 16)}\)

    • The best one is \((11 \rightarrow 16)\) with a cost of \(1\) (lines: 11 and 12)

  • making a connection from the second subway line \(\{15, 16\}\) to the first \(\{1, 10, 11\}\):

    • The best connections from all the stations from the second line are: \({(15 \rightarrow 10) (16 \rightarrow 11)}\)

    • Both are equaly good as they have the same cost. (lines: 13 and 14 and lines: 15 and 16)

Parámetros

Columna

Tipo

Descripción

Edges SQL

TEXT

Edges SQL as described below

Combinations SQL

TEXT

Combinations SQL as described below

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.

Dijkstra optional parameters

Columna

Tipo

x Defecto

Descripción

directed

BOOLEAN

true

  • En caso de true, el grafo se considera dirigido

  • Cuando false el gráfo se considera No Dirigido.

Near optional parameters

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

Inner Queries

Edges SQL

Columna

Tipo

x Defecto

Descripción

id

ANY-INTEGER

Identificador de la arista.

source

ANY-INTEGER

Identificador del primer vértice de la arista.

target

ANY-INTEGER

Identificador del segundo vértice de la arista.

cost

ANY-NUMERICAL

Weight of the edge (source, target)

reverse_cost

ANY-NUMERICAL

-1

Weight of the edge (target, source)

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Combinations SQL

Parámetro

Tipo

Descripción

source

ANY-INTEGER

Identifier of the departure vertex.

target

ANY-INTEGER

Identifier of the arrival vertex.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

Result Columns

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

Columna

Tipo

Descripción

seq

INTEGER

Sequential value starting from 1.

path_seq

INTEGER

Relative position in the path. Has value 1 for the beginning of a path.

start_vid

BIGINT

Identifier of the starting vertex of the current path.

end_vid

BIGINT

Identifier of the ending vertex of the current path.

node

BIGINT

Identifier of the node in the path from start_vid to end_vid.

edge

BIGINT

Identifier of the edge used to go from node to the next node in the path sequence. -1 for the last node of the path.

cost

FLOAT

Cost to traverse from node using edge to the next node in the path sequence.

agg_cost

FLOAT

Aggregate cost from start_vid to node.

Ver también

Índices y tablas