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.
Disponibilidad
Versión 3.6.0
Standarizing output columns to
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
pgr_withPointsKSP
(Uno a Uno)Signature change:
driving_side
parameter changed from named optional to unnamed compulsory driving side.Añadidas las columnas de resultados
start_vid
yend_vid
.
Nuevas funciones de sobrecarga
pgr_withPointsKSP
(Uno a Muchos)pgr_withPointsKSP
(Muchos a Uno)pgr_withPointsKSP
(Muchos a Muchos)pgr_withPointsKSP
(Combinaciones)
Deprecated signature
pgr_withpointsksp(text,text,bigint,bigint,integer,boolean,boolean,char,boolean)
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¶
[directed, heap_paths, details]
(seq, path_id, path_seq, node, edge, cost, agg_cost)
Uno a Uno¶
[directed, heap_paths, details]
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
Obtener 2 rutas desde el punto \(1\) al punto \(2\) en un grafo dirigido con lado de manejo izquierdo.
Para un grafo dirigido.
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, 'l');
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | -1 | -2 | -1 | 1 | 0.6 | 0
2 | 1 | 2 | -1 | -2 | 6 | 4 | 1 | 0.6
3 | 1 | 3 | -1 | -2 | 7 | 8 | 1 | 1.6
4 | 1 | 4 | -1 | -2 | 11 | 11 | 1 | 2.6
5 | 1 | 5 | -1 | -2 | 12 | 13 | 1 | 3.6
6 | 1 | 6 | -1 | -2 | 17 | 15 | 0.6 | 4.6
7 | 1 | 7 | -1 | -2 | -2 | -1 | 0 | 5.2
8 | 2 | 1 | -1 | -2 | -1 | 1 | 0.6 | 0
9 | 2 | 2 | -1 | -2 | 6 | 4 | 1 | 0.6
10 | 2 | 3 | -1 | -2 | 7 | 8 | 1 | 1.6
11 | 2 | 4 | -1 | -2 | 11 | 9 | 1 | 2.6
12 | 2 | 5 | -1 | -2 | 16 | 15 | 1.6 | 3.6
13 | 2 | 6 | -1 | -2 | -2 | -1 | 0 | 5.2
(13 rows)
Uno a Muchos¶
[directed, heap_paths, details]
(seq, path_id, path_seq, node, edge, cost, agg_cost)
- Ejemplo:
Obtener 2 rutas desde el punto \(1\) al punto \(3\) y al vértice \(7\) en un grafo no dirigido
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, ARRAY[-3, 7], 2, 'B',
directed => false);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | -1 | -3 | -1 | 1 | 0.6 | 0
2 | 1 | 2 | -1 | -3 | 6 | 4 | 1 | 0.6
3 | 1 | 3 | -1 | -3 | 7 | 10 | 1 | 1.6
4 | 1 | 4 | -1 | -3 | 8 | 12 | 0.6 | 2.6
5 | 1 | 5 | -1 | -3 | -3 | -1 | 0 | 3.2
6 | 2 | 1 | -1 | -3 | -1 | 1 | 0.6 | 0
7 | 2 | 2 | -1 | -3 | 6 | 4 | 1 | 0.6
8 | 2 | 3 | -1 | -3 | 7 | 8 | 1 | 1.6
9 | 2 | 4 | -1 | -3 | 11 | 11 | 1 | 2.6
10 | 2 | 5 | -1 | -3 | 12 | 12 | 0.4 | 3.6
11 | 2 | 6 | -1 | -3 | -3 | -1 | 0 | 4
12 | 3 | 1 | -1 | 7 | -1 | 1 | 0.6 | 0
13 | 3 | 2 | -1 | 7 | 6 | 4 | 1 | 0.6
14 | 3 | 3 | -1 | 7 | 7 | -1 | 0 | 1.6
15 | 4 | 1 | -1 | 7 | -1 | 1 | 0.6 | 0
16 | 4 | 2 | -1 | 7 | 6 | 2 | 1 | 0.6
17 | 4 | 3 | -1 | 7 | 10 | 5 | 1 | 1.6
18 | 4 | 4 | -1 | 7 | 11 | 8 | 1 | 2.6
19 | 4 | 5 | -1 | 7 | 7 | -1 | 0 | 3.6
(19 rows)
Muchos a Uno¶
[directed, heap_paths, details]
(seq, path_id, path_seq, node, edge, cost, agg_cost)
- Ejemplo:
Obtener una ruta desde el punto \(1\) y del vértice \(6\) al punto \(3\) en un grafo dirigido, con lado de manejo a la derecha y con
details
puesto entrue
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
ARRAY[-1, 6], -3, 1, 'r', details=> true);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | -1 | -3 | -1 | 1 | 0.4 | 0
2 | 1 | 2 | -1 | -3 | 5 | 1 | 1 | 0.4
3 | 1 | 3 | -1 | -3 | 6 | 4 | 0.7 | 1.4
4 | 1 | 4 | -1 | -3 | -6 | 4 | 0.3 | 2.1
5 | 1 | 5 | -1 | -3 | 7 | 10 | 1 | 2.4
6 | 1 | 6 | -1 | -3 | 8 | 12 | 0.6 | 3.4
7 | 1 | 7 | -1 | -3 | -3 | -1 | 0 | 4
8 | 2 | 1 | 6 | -3 | 6 | 4 | 0.7 | 0
9 | 2 | 2 | 6 | -3 | -6 | 4 | 0.3 | 0.7
10 | 2 | 3 | 6 | -3 | 7 | 10 | 1 | 1
11 | 2 | 4 | 6 | -3 | 8 | 12 | 0.6 | 2
12 | 2 | 5 | 6 | -3 | -3 | -1 | 0 | 2.6
(12 rows)
Muchos a Muchos¶
[directed, heap_paths, details]
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
Obtener una ruta desde el punto \(1\) y el vértice \(6\) al punto \(3\) y al vértice \(1\) en un grafo dirigido con lado de manejo izquierda, con
heap_paths
puesto entrue
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
ARRAY[-1, 6], ARRAY[-3, 1], 1, 'l', heap_paths => true);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | -1 | -3 | -1 | 1 | 0.6 | 0
2 | 1 | 2 | -1 | -3 | 6 | 4 | 1 | 0.6
3 | 1 | 3 | -1 | -3 | 7 | 10 | 1 | 1.6
4 | 1 | 4 | -1 | -3 | 8 | 12 | 0.6 | 2.6
5 | 1 | 5 | -1 | -3 | -3 | -1 | 0 | 3.2
6 | 2 | 1 | -1 | 1 | -1 | 1 | 0.6 | 0
7 | 2 | 2 | -1 | 1 | 6 | 4 | 1 | 0.6
8 | 2 | 3 | -1 | 1 | 7 | 7 | 1 | 1.6
9 | 2 | 4 | -1 | 1 | 3 | 6 | 1 | 2.6
10 | 2 | 5 | -1 | 1 | 1 | -1 | 0 | 3.6
11 | 3 | 1 | 6 | -3 | 6 | 4 | 1 | 0
12 | 3 | 2 | 6 | -3 | 7 | 10 | 1 | 1
13 | 3 | 3 | 6 | -3 | 8 | 12 | 0.6 | 2
14 | 3 | 4 | 6 | -3 | -3 | -1 | 0 | 2.6
15 | 4 | 1 | 6 | 1 | 6 | 4 | 1 | 0
16 | 4 | 2 | 6 | 1 | 7 | 7 | 1 | 1
17 | 4 | 3 | 6 | 1 | 3 | 6 | 1 | 2
18 | 4 | 4 | 6 | 1 | 1 | -1 | 0 | 3
(18 rows)
Combinaciones¶
[directed, heap_paths, details]
(seq, path_id, path_seq, node, edge, cost, agg_cost)
- Ejemplo:
Usando una tabla de combinaciones en un grafo dirigido
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
'SELECT * FROM (VALUES (-1, 10), (6, -3)) AS combinations(source, target)',
2, 'r', details => true);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | -1 | 10 | -1 | 1 | 0.4 | 0
2 | 1 | 2 | -1 | 10 | 5 | 1 | 1 | 0.4
3 | 1 | 3 | -1 | 10 | 6 | 4 | 0.7 | 1.4
4 | 1 | 4 | -1 | 10 | -6 | 4 | 0.3 | 2.1
5 | 1 | 5 | -1 | 10 | 7 | 8 | 1 | 2.4
6 | 1 | 6 | -1 | 10 | 11 | 9 | 1 | 3.4
7 | 1 | 7 | -1 | 10 | 16 | 16 | 1 | 4.4
8 | 1 | 8 | -1 | 10 | 15 | 3 | 1 | 5.4
9 | 1 | 9 | -1 | 10 | 10 | -1 | 0 | 6.4
10 | 2 | 1 | -1 | 10 | -1 | 1 | 0.4 | 0
11 | 2 | 2 | -1 | 10 | 5 | 1 | 1 | 0.4
12 | 2 | 3 | -1 | 10 | 6 | 4 | 0.7 | 1.4
13 | 2 | 4 | -1 | 10 | -6 | 4 | 0.3 | 2.1
14 | 2 | 5 | -1 | 10 | 7 | 8 | 1 | 2.4
15 | 2 | 6 | -1 | 10 | 11 | 11 | 1 | 3.4
16 | 2 | 7 | -1 | 10 | 12 | 13 | 1 | 4.4
17 | 2 | 8 | -1 | 10 | 17 | 15 | 1 | 5.4
18 | 2 | 9 | -1 | 10 | 16 | 16 | 1 | 6.4
19 | 2 | 10 | -1 | 10 | 15 | 3 | 1 | 7.4
20 | 2 | 11 | -1 | 10 | 10 | -1 | 0 | 8.4
21 | 3 | 1 | 6 | -3 | 6 | 4 | 0.7 | 0
22 | 3 | 2 | 6 | -3 | -6 | 4 | 0.3 | 0.7
23 | 3 | 3 | 6 | -3 | 7 | 10 | 1 | 1
24 | 3 | 4 | 6 | -3 | 8 | 12 | 0.6 | 2
25 | 3 | 5 | 6 | -3 | -3 | -1 | 0 | 2.6
(25 rows)
Parámetros¶
Columna |
Tipo |
Descripción |
---|---|---|
|
SQL de aristas como se describen. |
|
|
SQL de puntos como se describe. |
|
salida |
ENTEROS |
Identificador del vértice de partida.
|
destino |
ENTEROS |
Identificador del vértice destino.
|
K |
ENTEROS |
Cantidad de rutas requeridas |
Lado de_manejo |
CHAR |
Valor en [
|
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
Parámetros opcionales¶
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
|
|
|
Parámetros opcionales de KSP¶
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
|
|
|
Parámetros opcionales para withPointsKSP¶
Parámetro |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
|
|
|
Consultas Internas¶
SQL aristas¶
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ENTEROS |
Identificador de la arista. |
|
|
ENTEROS |
Identificador del primer vértice de la arista. |
|
|
ENTEROS |
Identificador del segundo vértice de la arista. |
|
|
FLOTANTES |
Peso de la arista ( |
|
|
FLOTANTES |
-1 |
Peso de la arista (
|
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
- FLOTANTES:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
SQL de puntos¶
Parámetro |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ENTEROS |
valor |
Identificador del punto.
|
|
ENTEROS |
Identificador de la arista «más cercana» al punto. |
|
|
FLOTANTES |
El valor en <0,1> que indica la posición relativa desde el primer punto de la arista. |
|
|
|
|
Valor en [
|
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
- FLOTANTES:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
SQL Combinaciones¶
Parámetro |
Tipo |
Descripción |
---|---|---|
|
ENTEROS |
Identificador del vértice de partida. |
|
ENTEROS |
Identificador del vértice de llegada. |
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
Columnas de resultados¶
Regresa conjunto de (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Valor secuencial a partir de 1. |
|
|
Identificador del camino.
|
|
|
Posición relativa en la ruta. Tiene el valor 1 para el inicio de una ruta. |
|
|
Identificador del nodo en la ruta de |
|
|
Identificador de la arista utilizado para ir del |
|
|
Costo para atravesar desde
|
|
|
Costo agregado desde vid inicial hasta |
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,'r');
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 1 | -1 | 1 | 6 | 1 | 0
2 | 1 | 2 | 1 | -1 | 3 | 7 | 1 | 1
3 | 1 | 3 | 1 | -1 | 7 | 8 | 1 | 2
4 | 1 | 4 | 1 | -1 | 11 | 9 | 1 | 3
5 | 1 | 5 | 1 | -1 | 16 | 16 | 1 | 4
6 | 1 | 6 | 1 | -1 | 15 | 3 | 1 | 5
7 | 1 | 7 | 1 | -1 | 10 | 5 | 0.8 | 6
8 | 1 | 8 | 1 | -1 | -1 | -1 | 0 | 6.8
9 | 2 | 1 | 1 | -1 | 1 | 6 | 1 | 0
10 | 2 | 2 | 1 | -1 | 3 | 7 | 1 | 1
11 | 2 | 3 | 1 | -1 | 7 | 10 | 1 | 2
12 | 2 | 4 | 1 | -1 | 8 | 12 | 1 | 3
13 | 2 | 5 | 1 | -1 | 12 | 13 | 1 | 4
14 | 2 | 6 | 1 | -1 | 17 | 15 | 1 | 5
15 | 2 | 7 | 1 | -1 | 16 | 16 | 1 | 6
16 | 2 | 8 | 1 | -1 | 15 | 3 | 1 | 7
17 | 2 | 9 | 1 | -1 | 10 | 5 | 0.8 | 8
18 | 2 | 10 | 1 | -1 | -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 \(3\), 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, -3, 2, 'l', details => true);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | -1 | -3 | -1 | 1 | 0.6 | 0
2 | 1 | 2 | -1 | -3 | 6 | 4 | 0.7 | 0.6
3 | 1 | 3 | -1 | -3 | -6 | 4 | 0.3 | 1.3
4 | 1 | 4 | -1 | -3 | 7 | 10 | 1 | 1.6
5 | 1 | 5 | -1 | -3 | 8 | 12 | 0.6 | 2.6
6 | 1 | 6 | -1 | -3 | -3 | -1 | 0 | 3.2
(6 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, 'r',
heap_paths => true, details => true);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | -1 | -2 | -1 | 1 | 0.4 | 0
2 | 1 | 2 | -1 | -2 | 5 | 1 | 1 | 0.4
3 | 1 | 3 | -1 | -2 | 6 | 4 | 0.7 | 1.4
4 | 1 | 4 | -1 | -2 | -6 | 4 | 0.3 | 2.1
5 | 1 | 5 | -1 | -2 | 7 | 8 | 1 | 2.4
6 | 1 | 6 | -1 | -2 | 11 | 9 | 1 | 3.4
7 | 1 | 7 | -1 | -2 | 16 | 15 | 0.4 | 4.4
8 | 1 | 8 | -1 | -2 | -2 | -1 | 0 | 4.8
9 | 2 | 1 | -1 | -2 | -1 | 1 | 0.4 | 0
10 | 2 | 2 | -1 | -2 | 5 | 1 | 1 | 0.4
11 | 2 | 3 | -1 | -2 | 6 | 4 | 0.7 | 1.4
12 | 2 | 4 | -1 | -2 | -6 | 4 | 0.3 | 2.1
13 | 2 | 5 | -1 | -2 | 7 | 8 | 1 | 2.4
14 | 2 | 6 | -1 | -2 | 11 | 11 | 1 | 3.4
15 | 2 | 7 | -1 | -2 | 12 | 13 | 1 | 4.4
16 | 2 | 8 | -1 | -2 | 17 | 15 | 1 | 5.4
17 | 2 | 9 | -1 | -2 | 16 | 15 | 0.4 | 6.4
18 | 2 | 10 | -1 | -2 | -2 | -1 | 0 | 6.8
19 | 3 | 1 | -1 | -2 | -1 | 1 | 0.4 | 0
20 | 3 | 2 | -1 | -2 | 5 | 1 | 1 | 0.4
21 | 3 | 3 | -1 | -2 | 6 | 4 | 0.7 | 1.4
22 | 3 | 4 | -1 | -2 | -6 | 4 | 0.3 | 2.1
23 | 3 | 5 | -1 | -2 | 7 | 10 | 1 | 2.4
24 | 3 | 6 | -1 | -2 | 8 | 12 | 0.6 | 3.4
25 | 3 | 7 | -1 | -2 | -3 | 12 | 0.4 | 4
26 | 3 | 8 | -1 | -2 | 12 | 13 | 1 | 4.4
27 | 3 | 9 | -1 | -2 | 17 | 15 | 1 | 5.4
28 | 3 | 10 | -1 | -2 | 16 | 15 | 0.4 | 6.4
29 | 3 | 11 | -1 | -2 | -2 | -1 | 0 | 6.8
(29 rows)
Las consultas utilizan la red Datos Muestra .
Ver también¶
Índices y tablas