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.

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 |  0.4 |        0
|       1 |        2 |    1 |    1 |    1 |      0.4
|       1 |        3 |    2 |    4 |  0.7 |      1.4
|       1 |        4 |   -6 |    4 |  0.3 |      2.1
|       1 |        5 |    5 |    8 |    1 |      2.4
|       1 |        6 |    6 |    9 |    1 |      3.4
|       1 |        7 |    9 |   15 |  0.4 |      4.4
|       1 |        8 |   -2 |   -1 |    0 |      4.8
|       2 |        1 |   -1 |    1 |  0.4 |        0
|       2 |        2 |    1 |    1 |    1 |      0.4
|       2 |        3 |    2 |    4 |  0.7 |      1.4
|       2 |        4 |   -6 |    4 |  0.3 |      2.1
|       2 |        5 |    5 |    8 |    1 |      2.4
|       2 |        6 |    6 |   11 |    1 |      3.4
|       2 |        7 |   11 |   13 |    1 |      4.4
|       2 |        8 |   12 |   15 |    1 |      5.4
|       2 |        9 |    9 |   15 |  0.4 |      6.4
|       2 |       10 |   -2 |   -1 |    0 |      6.8
|       3 |        1 |   -1 |    1 |  0.4 |        0
|       3 |        2 |    1 |    1 |    1 |      0.4
|       3 |        3 |    2 |    4 |  0.7 |      1.4
|       3 |        4 |   -6 |    4 |  0.3 |      2.1
|       3 |        5 |    5 |   10 |    1 |      2.4
|       3 |        6 |   10 |   12 |  0.6 |      3.4
|       3 |        7 |   -3 |   12 |  0.4 |        4
|       3 |        8 |   11 |   13 |    1 |      4.4
|       3 |        9 |   12 |   15 |    1 |      5.4
|       3 |       10 |    9 |   15 |  0.4 |      6.4
|       3 |       11 |   -2 |   -1 |    0 |      6.8
(29 rows)

Las consultas utilizan la red Datos Muestra .

Ver también¶

withPoints - Familia de funciones

Índices y tablas