Versiones no soportadas:2.6 2.5 2.4 2.3 2.2
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.
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(One to One)
Signature change:
driving_side
parameter changed from named optional to unnamed compulsory driving side.Añadidas las columnas de resultados
start_vid
yend_vid
.
New proposed signatures:
pgr_withPointsKSP(One to Many)
pgr_withPointsKSP(Many to One)
pgr_withPointsKSP(Many to Many)
pgr_withPointsKSP(Combinations)
Deprecated signature
pgr_withpointsksp(text,text,bigint,bigint,integer,boolean,boolean,char,boolean)``
Version 2.2.0
New proposed function.
Descripción¶
Modifica el grafo para incluir los puntos definidos en el SQL de puntos y utilizando el algoritmo Yen, encuentra las
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
al punto 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
al punto y al vértice 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
y del vértice al punto en un grafo dirigido, con lado de manejo a la derecha y condetails
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
y el vértice al punto y al vértice en un grafo dirigido con lado de manejo izquierda, conheap_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 - Proposed en el SQL de puntos.¶
Obtener
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
corresponde a la arista más cercana al punto (2.9, 1.8).
Lado de manejo izquierdo¶
Obtener
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
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)
Ver también¶
Índices y tablas