pgr_withPointsKSP - Propuesto

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

Advertencia

Funciones propuestas para el próximo lanzamineto.

  • No están oficialmente en la versión actual.
  • Es probable que oficialmente formen parte del próximo lanzamiento:
    • Las funciones hacen uso de ANY-INTEGER y ANY-NUMERICAL
    • 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 de pgTap. Pero tal vez necesite 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

Soporte

Descripción

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

Firmas

Resumen

pgr_withPointsKSP(edges_sql, points_sql, start_pid, end_pid, K [, directed] [, heap_paths] [, driving_side] [, details])
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)

Uso de valores predeterminados

pgr_withPointsKSP(edges_sql, points_sql, start_pid, end_pid, K)
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)
Ejemplo:Del punto \(1\) al punto \(2\) in \(2\) ciclos
  • 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 montones de rutas.
SELECT * FROM pgr_withPointsKSP(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table 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 |    2 |    4 |    1 |      0.6
   3 |       1 |        3 |    5 |    8 |    1 |      1.6
   4 |       1 |        4 |    6 |    9 |    1 |      2.6
   5 |       1 |        5 |    9 |   15 |  0.4 |      3.6
   6 |       1 |        6 |   -2 |   -1 |    0 |        4
   7 |       2 |        1 |   -1 |    1 |  0.6 |        0
   8 |       2 |        2 |    2 |    4 |    1 |      0.6
   9 |       2 |        3 |    5 |    8 |    1 |      1.6
  10 |       2 |        4 |    6 |   11 |    1 |      2.6
  11 |       2 |        5 |   11 |   13 |    1 |      3.6
  12 |       2 |        6 |   12 |   15 |  0.6 |      4.6
  13 |       2 |        7 |   -2 |   -1 |    0 |      5.2
(13 rows)

Firma completa

Encuentra las rutas más cortas \(K\) dependiendo de la configuración de parámetros opcionales.

pgr_withPointsKSP(edges_sql, points_sql, start_pid, end_pid, K [, directed] [, heap_paths] [, driving_side] [, details])
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)
Ejemplo:Del punto \(1\) al vértice \(6\) en \(2\) ciclos con detalles.
SELECT * FROM pgr_withPointsKSP(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    'SELECT pid, edge_id, fraction, side from pointsOfInterest',
    -1, 6, 2, details := true);
 seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
   1 |       1 |        1 |   -1 |    1 |  0.6 |        0
   2 |       1 |        2 |    2 |    4 |  0.7 |      0.6
   3 |       1 |        3 |   -6 |    4 |  0.3 |      1.3
   4 |       1 |        4 |    5 |    8 |    1 |      1.6
   5 |       1 |        5 |    6 |   -1 |    0 |      2.6
   6 |       2 |        1 |   -1 |    1 |  0.6 |        0
   7 |       2 |        2 |    2 |    4 |  0.7 |      0.6
   8 |       2 |        3 |   -6 |    4 |  0.3 |      1.3
   9 |       2 |        4 |    5 |   10 |    1 |      1.6
  10 |       2 |        5 |   10 |   12 |  0.6 |      2.6
  11 |       2 |        6 |   -3 |   12 |  0.4 |      3.2
  12 |       2 |        7 |   11 |   13 |    1 |      3.6
  13 |       2 |        8 |   12 |   15 |  0.6 |      4.6
  14 |       2 |        9 |   -2 |   15 |  0.4 |      5.2
  15 |       2 |       10 |    9 |    9 |    1 |      5.6
  16 |       2 |       11 |    6 |   -1 |    0 |      6.6
(16 rows)

Parámetros

Parámetro Tipo Descripción
edges_sql TEXT Consulta de aristas SQL como se describió anteriormente.
points_sql TEXT Consulta SQL de puntos como se describe arriba.
start_pid ANY-INTEGER Identificador de punto de partida.
end_pid ANY-INTEGER Identificador de punto final.
K INTEGER Número de rutas más cortas.
dirigido BOOLEAN (opcional). En caso de false el grafo se considera como No Dirigido. El valor predeterminado es true que considera el grafo como Dirigido.
heap_paths BOOLEAN (opcional). En caso de true también se devolverán las rutas calculadas para obtener las rutas más cortas. El valor predeterminado es false, solo se devuelven las rutas más cortas K.
driving_side CHAR
(opcional) Valor en [“b”, “r”, “l”, NULL] que indica si el lado de conducción es:
  • A la derecha o a la izquierda o
  • Si no importa con “b” o NULL.
  • Si la columna no presente “b” es considerada
detalles BOOLEAN (opcional). En caso de true los resultados incluirán la distancia de conducción a los puntos con la distancia. El valor predeterminado es false que omite otros puntos de points_sql.

Consulta interna

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 (source, target) 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 (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ANY-INTEGER:SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Descripción de la consulta SSQL de Puntos

points_sql:Una consulta SQL, que debe regresar un conjunto de filas con las siguientes columnas:
Columna Tipo Descripción
pid ANY-INTEGER

(opcional) Identificador del punto.

  • Si la columna está presente, no puede ser NULL.
  • Si la columna no está presente, se proporcionará automáticamente un identificador secuencial.
edge_id ANY-INTEGER Identificador de la arista «más cercano» al punto.
fraction ANY-NUMERICAL El valor en <0,1> que indica la posición relativa desde el primer punto final de la arista.
side CHAR

(opcional) Valor en [“b”, “r”, “l”, NULL] que indica si el punto es:

  • A la derecha, a la izquierda del borde o
  • Si no importa con “b” o NULL.
  • Si la columna no presente “b” es considerada

Donde:

ANY-INTEGER:smallint, int, bigint
ANY-NUMERICAL:smallint, int, bigint, real, float

Columnas de Resultados

Columna Tipo Descripción
seq INTEGER Secuencia de filas.
path_seq INTEGER Posición relativa en la ruta de acceso de nodo y arista. Tiene el valor 1 para el principio de una ruta.
path_id INTEGER Identificador de ruta. El orden de los caminos: Para dos caminos i, j if i < j entonces agg_cost(i) <= agg_cost(j).
node BIGINT Identificador del nodo en la ruta. Los valores negativos son los identificadores de un punto.
edge BIGINT
Identificador del borde utilizado para ir de node al siguiente nodo de la secuencia de ruta.
  • -1 para la última fila de la secuencia de ruta.
cost FLOAT
Coste para atravesar desde node usando edge para el siguiente node en la secuncia de ruta.
  • 0 para la última fila de la secuencia de ruta.
agg_cost FLOAT
Coste agregado de start_pid a node.
  • 0 para la primera fila de la secuencia de ruta.

Ejemplos Adicionales

Ejemplo:Topología de conducción del lado izquierdo desde el punto \(1\) a punto \(2\) en \(2\) ciclos, con detalles
SELECT * FROM pgr_withPointsKSP(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table 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 |    2 |    4 |  0.7 |      0.6
   3 |       1 |        3 |   -6 |    4 |  0.3 |      1.3
   4 |       1 |        4 |    5 |    8 |    1 |      1.6
   5 |       1 |        5 |    6 |    9 |    1 |      2.6
   6 |       1 |        6 |    9 |   15 |    1 |      3.6
   7 |       1 |        7 |   12 |   15 |  0.6 |      4.6
   8 |       1 |        8 |   -2 |   -1 |    0 |      5.2
   9 |       2 |        1 |   -1 |    1 |  0.6 |        0
  10 |       2 |        2 |    2 |    4 |  0.7 |      0.6
  11 |       2 |        3 |   -6 |    4 |  0.3 |      1.3
  12 |       2 |        4 |    5 |    8 |    1 |      1.6
  13 |       2 |        5 |    6 |   11 |    1 |      2.6
  14 |       2 |        6 |   11 |   13 |    1 |      3.6
  15 |       2 |        7 |   12 |   15 |  0.6 |      4.6
  16 |       2 |        8 |   -2 |   -1 |    0 |      5.2
(16 rows)

Ejemplo:Topología de conducción del lado derecho desde el punto \(1\) al punto \(2\) en \(2\) ciclos, con montones de rutas y detalles
SELECT * FROM pgr_withPointsKSP(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table 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 |    1 |    1 |    1 |      0.4
   3 |       1 |        3 |    2 |    4 |  0.7 |      1.4
   4 |       1 |        4 |   -6 |    4 |  0.3 |      2.1
   5 |       1 |        5 |    5 |    8 |    1 |      2.4
   6 |       1 |        6 |    6 |    9 |    1 |      3.4
   7 |       1 |        7 |    9 |   15 |  0.4 |      4.4
   8 |       1 |        8 |   -2 |   -1 |    0 |      4.8
   9 |       2 |        1 |   -1 |    1 |  0.4 |        0
  10 |       2 |        2 |    1 |    1 |    1 |      0.4
  11 |       2 |        3 |    2 |    4 |  0.7 |      1.4
  12 |       2 |        4 |   -6 |    4 |  0.3 |      2.1
  13 |       2 |        5 |    5 |    8 |    1 |      2.4
  14 |       2 |        6 |    6 |   11 |    1 |      3.4
  15 |       2 |        7 |   11 |   13 |    1 |      4.4
  16 |       2 |        8 |   12 |   15 |    1 |      5.4
  17 |       2 |        9 |    9 |   15 |  0.4 |      6.4
  18 |       2 |       10 |   -2 |   -1 |    0 |      6.8
  19 |       3 |        1 |   -1 |    1 |  0.4 |        0
  20 |       3 |        2 |    1 |    1 |    1 |      0.4
  21 |       3 |        3 |    2 |    4 |  0.7 |      1.4
  22 |       3 |        4 |   -6 |    4 |  0.3 |      2.1
  23 |       3 |        5 |    5 |   10 |    1 |      2.4
  24 |       3 |        6 |   10 |   12 |  0.6 |      3.4
  25 |       3 |        7 |   -3 |   12 |  0.4 |        4
  26 |       3 |        8 |   11 |   13 |    1 |      4.4
  27 |       3 |        9 |   12 |   15 |    1 |      5.4
  28 |       3 |       10 |    9 |   15 |  0.4 |      6.4
  29 |       3 |       11 |   -2 |   -1 |    0 |      6.8
(29 rows)

Las consultas utilizan la red Datos Muestra .