• Supported versions:

pgr_withPointsKSP - Propuesto

pgr_withPointsKSP - Encuentra las rutas más cortas de K usando el algoritmo de Yen.

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

• Version 2.2.0

  • Nueva función propuesta

Descripción

Modifica el grafo para incluir los puntos definidos en el SQL de puntos y utilizando el algoritmo Yen, encuentra las \(K\) rutas más cortas.

Firmas

pgr_withPointsKSP(SQL de aristas, SQL de puntos, salida, destino, K, [options])

opciones: [directed, heap_paths, driving_side, details]

RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)

OR EMPTY SET

Ejemplo:

Obtener 2 rutas desde el punto \(1\) al punto \(2\) en un grafo dirigido.

• Para un grafo dirigido.

• Ambos lados de conducción se establecen como b. Así que llegar/partir hacia/desde el o los puntos, puede ser en cualquier dirección.

• No se proporcionan detalles sobre la distancia de otros puntos de la consulta.

• No se devuelven rutas pre-calculadas.

SELECT * FROM pgr_withPointsKSP(
    'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
    'SELECT pid, edge_id, fraction, side from pointsOfInterest',
    -1, -2, 2);
 seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
   1 |       1 |        1 |   -1 |    1 |  0.6 |        0
   2 |       1 |        2 |    6 |    4 |    1 |      0.6
   3 |       1 |        3 |    7 |    8 |    1 |      1.6
   4 |       1 |        4 |   11 |    9 |    1 |      2.6
   5 |       1 |        5 |   16 |   15 |  0.4 |      3.6
   6 |       1 |        6 |   -2 |   -1 |    0 |        4
   7 |       2 |        1 |   -1 |    1 |  0.6 |        0
   8 |       2 |        2 |    6 |    4 |    1 |      0.6
   9 |       2 |        3 |    7 |    8 |    1 |      1.6
  10 |       2 |        4 |   11 |   11 |    1 |      2.6
  11 |       2 |        5 |   12 |   13 |    1 |      3.6
  12 |       2 |        6 |   17 |   15 |  0.6 |      4.6
  13 |       2 |        7 |   -2 |   -1 |    0 |      5.2
(13 rows)

Parámetros

Columna	Tipo	Descripción
SQL de aristas	TEXT	SQL de aristas como se describen.
SQL de puntos	TEXT	SQL de puntos como se describe.
salida	ENTEROS	Identificador del vértice de salida. Valores negativos representan un punto
destino	ENTEROS	Identificador del vértice destino. Valores negativos representan un punto
K	ENTEROS	Cantidad de rutas requeridas

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

Parámetros opcionales

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 KSP

Columna	Tipo	x Defecto	Descripción
heap_paths	BOOLEAN	false	Cuando false Regresa a lo más K caminos Cuando true se regresan todos los caminos calulados mientras se procesa. Aproximadamente, si la ruta más corta tiene N aristas, las procesadas contendrán aproximadamente N * K rutas para valores pequeños de K y K > 5.

Parámetros opcionales para Con puntos

Parámetro	Tipo	x Defecto	Descripción
driving_side	CHAR	b	Valor en [r, l, b] indica si el lado de manejo es: r para manejo del lado derecho. l para lado de manejo izquierdo. b for ambos.
details	BOOLEAN	false	Cuando true los resultados incluyen los puntos que están en el camino. Cuando false los resultados no incluyen los puntos que están en el camino.

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 de puntos

Parámetro	Tipo	x Defecto	Descripción
pid	ENTEROS	valor	Identificador del punto. Use con un valor positivo, dado que internamente se convertirá a un valor negativo Si columna esta presente, no puede ser NULL. Si columna no esta presente, un valor secuencial negativo se otorgará automáticamente.
edge_id	ENTEROS		Identificador de la arista «más cercana» al punto.
fraction	FLOTANTES		El valor en <0,1> que indica la posición relativa desde el primer punto de la arista.
side	CHAR	b	Valor en [b, r, l, NULL] que indica si el punto es: A la derecha r, A la izquierda l, En ambos lados b, NULL

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Resultados

Devuelve el conjunto de (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

Columna	Tipo	Descripción
seq	INTEGER	Valor secuencial a partir de 1.
path_id	INTEGER	Identificador del camino. Tiene valor 1 para el primer camnio desde start vid a end_vid
path_seq	INTEGER	Posición relativa en la ruta. Tiene el valor 1 para el inicio de una ruta.
node	BIGINT	Identificador del nodo en la ruta como nodo de salida o nodo destino
edge	BIGINT	Identificador de la arista utilizado para ir del node al siguiente nodo de la secuencia de ruta. -1 para el último nodo de la ruta.
cost	FLOAT	Costo para atravesar desde node usando edge hasta el siguiente nodo en la secuencia de la ruta. \(0\) para el último node de la ruta.
agg_cost	FLOAT	Costo agregado desde vid inicial hasta node.

Ejemplos Adicionales

Lado de manejo izquierdo

Obtener \(2\) rutas, usando topología de manejo por la izquierda, desde el punto \(1\) al punto \(2\), detallado.

SELECT * FROM pgr_withPointsKSP(
    'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
    'SELECT pid, edge_id, fraction, side from pointsOfInterest',
    -1, -2, 2,
    driving_side := 'l', details := true);
 seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
   1 |       1 |        1 |   -1 |    1 |  0.6 |        0
   2 |       1 |        2 |    6 |    4 |  0.7 |      0.6
   3 |       1 |        3 |   -6 |    4 |  0.3 |      1.3
   4 |       1 |        4 |    7 |    8 |    1 |      1.6
   5 |       1 |        5 |   11 |   11 |    1 |      2.6
   6 |       1 |        6 |   12 |   13 |    1 |      3.6
   7 |       1 |        7 |   17 |   15 |  0.6 |      4.6
   8 |       1 |        8 |   -2 |   -1 |    0 |      5.2
   9 |       2 |        1 |   -1 |    1 |  0.6 |        0
  10 |       2 |        2 |    6 |    4 |  0.7 |      0.6
  11 |       2 |        3 |   -6 |    4 |  0.3 |      1.3
  12 |       2 |        4 |    7 |    8 |    1 |      1.6
  13 |       2 |        5 |   11 |    9 |    1 |      2.6
  14 |       2 |        6 |   16 |   15 |    1 |      3.6
  15 |       2 |        7 |   17 |   15 |  0.6 |      4.6
  16 |       2 |        8 |   -2 |   -1 |    0 |      5.2
(16 rows)

Lado de manejo derecho

Obtener \(2\) rutas, usando topología de manejo por la derecha, desde el punto \(1\) al punto \(2\), detallado y con rutas procesadas.

SELECT * FROM pgr_withPointsKSP(
    'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
    'SELECT pid, edge_id, fraction, side from pointsOfInterest',
    -1, -2, 2,
    heap_paths := true, driving_side := 'r', details := true);
 seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
   1 |       1 |        1 |   -1 |    1 |  0.4 |        0
   2 |       1 |        2 |    5 |    1 |    1 |      0.4
   3 |       1 |        3 |    6 |    4 |  0.7 |      1.4
   4 |       1 |        4 |   -6 |    4 |  0.3 |      2.1
   5 |       1 |        5 |    7 |    8 |    1 |      2.4
   6 |       1 |        6 |   11 |    9 |    1 |      3.4
   7 |       1 |        7 |   16 |   15 |  0.4 |      4.4
   8 |       1 |        8 |   -2 |   -1 |    0 |      4.8
   9 |       2 |        1 |   -1 |    1 |  0.4 |        0
  10 |       2 |        2 |    5 |    1 |    1 |      0.4
  11 |       2 |        3 |    6 |    4 |  0.7 |      1.4
  12 |       2 |        4 |   -6 |    4 |  0.3 |      2.1
  13 |       2 |        5 |    7 |    8 |    1 |      2.4
  14 |       2 |        6 |   11 |   11 |    1 |      3.4
  15 |       2 |        7 |   12 |   13 |    1 |      4.4
  16 |       2 |        8 |   17 |   15 |    1 |      5.4
  17 |       2 |        9 |   16 |   15 |  0.4 |      6.4
  18 |       2 |       10 |   -2 |   -1 |    0 |      6.8
  19 |       3 |        1 |   -1 |    1 |  0.4 |        0
  20 |       3 |        2 |    5 |    1 |    1 |      0.4
  21 |       3 |        3 |    6 |    4 |  0.7 |      1.4
  22 |       3 |        4 |   -6 |    4 |  0.3 |      2.1
  23 |       3 |        5 |    7 |   10 |    1 |      2.4
  24 |       3 |        6 |    8 |   12 |  0.6 |      3.4
  25 |       3 |        7 |   -3 |   12 |  0.4 |        4
  26 |       3 |        8 |   12 |   13 |    1 |      4.4
  27 |       3 |        9 |   17 |   15 |    1 |      5.4
  28 |       3 |       10 |   16 |   15 |  0.4 |      6.4
  29 |       3 |       11 |   -2 |   -1 |    0 |      6.8
(29 rows)

Las consultas utilizan la red Datos Muestra .

Ver también

• withPoints - Familia de funciones

• Rutas más cortas K - Categoría

• Datos Muestra

Índices y tablas

• Índice

• Página de Búsqueda