• Supported versions:

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

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 .

Ver también

Índices y tablas