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.

_images/boost-inside.jpeg

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

Usar pgr_findCloseEdges en el SQL de puntos.

Obtener \(2\) caminos usando el lado izquierdo de manejo, desde el vértice \(1\) a la ubicación mpas cercana en el grafo al punto (2.9, 1.8).

SELECT * FROM pgr_withPointsKSP(
  $e$ SELECT * FROM edges $e$,
  $p$ SELECT edge_id, round(fraction::numeric, 2) AS fraction, side
      FROM pgr_findCloseEdges(
        $$SELECT id, geom FROM edges$$,
        (SELECT ST_POINT(2.9, 1.8)),
        0.5, cap => 2)
  $p$,
  1, -1, 2,
  driving_side := 'r');
 seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
   1 |       1 |        1 |    1 |    6 |    1 |        0
   2 |       1 |        2 |    3 |    7 |    1 |        1
   3 |       1 |        3 |    7 |    8 |    1 |        2
   4 |       1 |        4 |   11 |    9 |    1 |        3
   5 |       1 |        5 |   16 |   16 |    1 |        4
   6 |       1 |        6 |   15 |    3 |    1 |        5
   7 |       1 |        7 |   10 |    5 |  0.8 |        6
   8 |       1 |        8 |   -1 |   -1 |    0 |      6.8
   9 |       2 |        1 |    1 |    6 |    1 |        0
  10 |       2 |        2 |    3 |    7 |    1 |        1
  11 |       2 |        3 |    7 |   10 |    1 |        2
  12 |       2 |        4 |    8 |   12 |    1 |        3
  13 |       2 |        5 |   12 |   13 |    1 |        4
  14 |       2 |        6 |   17 |   15 |    1 |        5
  15 |       2 |        7 |   16 |   16 |    1 |        6
  16 |       2 |        8 |   15 |    3 |    1 |        7
  17 |       2 |        9 |   10 |    5 |  0.8 |        8
  18 |       2 |       10 |   -1 |   -1 |    0 |      8.8
(18 rows)

  • Punto \(-1\) corresponde a la arista más cercana al punto (2.9, 1.8).

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

Índices y tablas