pgr_dijkstraNearCost - Proposed

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

    • 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_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:

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_dijkstraNearCost(
2  'SELECT id, source, target, cost, reverse_cost FROM edges',
3  6, ARRAY[10, 11, 1]);
4 start_vid | end_vid | agg_cost
5-----------+---------+----------
6         6 |      11 |        2
7(1 row)
8

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

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:

Departing on a car from a subway station find the nearest two stations to vertex \(6\)

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

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

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 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_dijkstraNearCost(
2  'SELECT id, source, target, cost, reverse_cost FROM edges',
3  ARRAY[15, 16], ARRAY[10, 11, 1],
4  directed => false);
5 start_vid | end_vid | agg_cost
6-----------+---------+----------
7        15 |      10 |        1
8(1 row)
9

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_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 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)

La consulta:

  • lines 3~4 sets the start vertices to be from the fisrt 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_dijkstraNearCost(
 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 start_vid | end_vid | agg_cost
10-----------+---------+----------
11        11 |      16 |        1
12        15 |      10 |        1
13        16 |      11 |        1
14        10 |      16 |        2
15         1 |      16 |        4
16(5 rows)
17

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: 1)

  • 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: 12 and 13)

Parámetros

Columna

Tipo

Descripción

SQL Aristas

TEXT

Consulta de aristas como se describe a continuación

SQL Combinaciones

TEXT

SQL Combinaciones como se describe a abajo

vid de salida

BIGINT

Identificador del vértice inicial de la ruta.

vid salidas

ARRAY[BIGINT]

Arreglo de identificadores de vértices iniciales.

vid destino

BIGINT

Identificador del vértice final de la ruta.

vids destinos

ARRAY[BIGINT]

Arreglo de identificadores de vértices finales.

Dijkstra optional parameters

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.

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

Consultas internas

SQL de 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 final.

agg_cost

FLOAT

Costo afregado desde start_vid hasta end_vid.

Ver también

Índices y tablas