pgr_trsp_withPoints - Proposed¶
pgr_trsp_withPoints
Routing Vertex/Point with restrictions.
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.4.0
New proposed signatures:
pgr_trsp_withPoints
(Uno a Uno)pgr_trsp_withPoints
(One to Many)pgr_trsp_withPoints
(Many to One)pgr_trsp_withPoints
(Many to Many)pgr_trsp_withPoints
(Combinations)
Descripción¶
Modificar el grafo para incluir puntos definidos por points_sql. Usando el algoritmo Dijkstra, busar la o las rutas más cortas
Características:
Los vértices del grafo son:
positive when it belongs to the Edges SQL
negative cuando pertence al SQL de puntos
Driving side can not be
b
Los valores se devuelven cuando hay una ruta.
Cuando el vértice inicial y el vértice final son iguales, no hay camino.
The agg_cost the non included values (v, v) is 0
Cuando el vértice de salida y el vértice destino son diferentes y no hay ninguna ruta:
The agg_cost the non included values (u, v) is ∞
Para fines de optimización, se omite cualquier valor duplicado en start_vids o end_vids.
Los valores devueltos se ordenan: - start_vid ascendente - end_vid ascendente
Tiempo de ejecución: \(O(|start\_vids|\times(V \log V + E))\)
Firmas¶
Resumen
[directed, driving_side, details]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
Uno a Uno¶
[directed, driving_side, details]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
Desde el punto \(1\) al vértice \(10\) con detalles en una configuración de manejo por la izquierda en un grafo dirigido con detalles.
SELECT * FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT id, path, cost FROM restrictions$$,
$$SELECT pid, edge_id, fraction, side FROM pointsOfInterest$$,
-1, 10,
details => true);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | -1 | 10 | -1 | 1 | 0.4 | 0
2 | 2 | -1 | 10 | 5 | 1 | 1 | 0.4
3 | 3 | -1 | 10 | 6 | 4 | 0.7 | 1.4
4 | 4 | -1 | 10 | -6 | 4 | 0.3 | 2.1
5 | 5 | -1 | 10 | 7 | 10 | 1 | 2.4
6 | 6 | -1 | 10 | 8 | 12 | 0.6 | 3.4
7 | 7 | -1 | 10 | -3 | 12 | 0.4 | 4
8 | 8 | -1 | 10 | 12 | 13 | 1 | 4.4
9 | 9 | -1 | 10 | 17 | 15 | 1 | 5.4
10 | 10 | -1 | 10 | 16 | 16 | 1 | 6.4
11 | 11 | -1 | 10 | 15 | 3 | 1 | 7.4
12 | 12 | -1 | 10 | 10 | -1 | 0 | 8.4
(12 rows)
Uno a Muchos¶
[directed, driving_side, details]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
Desde el punto \(1\) al punto \(3\) y vértice \(7\).
SELECT * FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT id, path, cost FROM restrictions$$,
$$SELECT pid, edge_id, fraction, side FROM pointsOfInterest$$,
-1, ARRAY[-3, 7]);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | -1 | -3 | -1 | 1 | 1.4 | 0
2 | 2 | -1 | -3 | 6 | 4 | 1 | 1.4
3 | 3 | -1 | -3 | 7 | 10 | 1 | 2.4
4 | 4 | -1 | -3 | 8 | 12 | 0.6 | 3.4
5 | 5 | -1 | -3 | -3 | -1 | 0 | 4
6 | 1 | -1 | 7 | -1 | 1 | 1.4 | 0
7 | 2 | -1 | 7 | 6 | 4 | 1 | 1.4
8 | 3 | -1 | 7 | 7 | -1 | 0 | 2.4
(8 rows)
Muchos a Uno¶
[directed, driving_side, details]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
Desde el punto \(1\) y vértice \(6\) al punto \(3\).
SELECT * FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT id, path, cost FROM restrictions$$,
$$SELECT pid, edge_id, fraction, side FROM pointsOfInterest$$,
ARRAY[-1, 6], -3);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | -1 | -3 | -1 | 1 | 1.4 | 0
2 | 2 | -1 | -3 | 6 | 4 | 1 | 1.4
3 | 3 | -1 | -3 | 7 | 10 | 1 | 2.4
4 | 4 | -1 | -3 | 8 | 12 | 0.6 | 3.4
5 | 5 | -1 | -3 | -3 | -1 | 0 | 4
6 | 1 | 6 | -3 | 6 | 4 | 1 | 0
7 | 2 | 6 | -3 | 7 | 10 | 1 | 1
8 | 3 | 6 | -3 | 8 | 12 | 0.6 | 2
9 | 4 | 6 | -3 | -3 | -1 | 0 | 2.6
(9 rows)
Muchos a Muchos¶
[directed, driving_side, details]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
Desde el punto \(1\) y vértice \(6\) al punto \(3\) y vértice \(1\).
SELECT * FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT id, path, cost FROM restrictions$$,
$$SELECT pid, edge_id, fraction, side FROM pointsOfInterest$$,
ARRAY[-1, 6], ARRAY[-3, 1]);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | -1 | -3 | -1 | 1 | 1.4 | 0
2 | 2 | -1 | -3 | 6 | 4 | 1 | 1.4
3 | 3 | -1 | -3 | 7 | 10 | 1 | 2.4
4 | 4 | -1 | -3 | 8 | 12 | 0.6 | 3.4
5 | 5 | -1 | -3 | -3 | -1 | 0 | 4
6 | 1 | -1 | 1 | -1 | 1 | 1.4 | 0
7 | 2 | -1 | 1 | 6 | 4 | 1 | 1.4
8 | 3 | -1 | 1 | 7 | 10 | 1 | 2.4
9 | 4 | -1 | 1 | 8 | 12 | 1 | 3.4
10 | 5 | -1 | 1 | 12 | 13 | 1 | 4.4
11 | 6 | -1 | 1 | 17 | 15 | 1 | 5.4
12 | 7 | -1 | 1 | 16 | 9 | 1 | 6.4
13 | 8 | -1 | 1 | 11 | 8 | 1 | 7.4
14 | 9 | -1 | 1 | 7 | 7 | 1 | 8.4
15 | 10 | -1 | 1 | 3 | 6 | 1 | 9.4
16 | 11 | -1 | 1 | 1 | -1 | 0 | 10.4
17 | 1 | 6 | -3 | 6 | 4 | 1 | 0
18 | 2 | 6 | -3 | 7 | 10 | 1 | 1
19 | 3 | 6 | -3 | 8 | 12 | 0.6 | 2
20 | 4 | 6 | -3 | -3 | -1 | 0 | 2.6
21 | 1 | 6 | 1 | 6 | 4 | 1 | 0
22 | 2 | 6 | 1 | 7 | 10 | 1 | 1
23 | 3 | 6 | 1 | 8 | 12 | 1 | 2
24 | 4 | 6 | 1 | 12 | 13 | 1 | 3
25 | 5 | 6 | 1 | 17 | 15 | 1 | 4
26 | 6 | 6 | 1 | 16 | 9 | 1 | 5
27 | 7 | 6 | 1 | 11 | 8 | 1 | 6
28 | 8 | 6 | 1 | 7 | 7 | 1 | 7
29 | 9 | 6 | 1 | 3 | 6 | 1 | 8
30 | 10 | 6 | 1 | 1 | -1 | 0 | 9
(30 rows)
Combinaciones¶
[directed, driving_side, details]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
Desde el punto \(1\) al vértice \(10\) y desde el vértice \(6\) al punto \(3\) on una configuración de manejo por la derecha.
SELECT * FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT id, path, cost FROM restrictions$$,
$$SELECT pid, edge_id, fraction, side FROM pointsOfInterest$$,
$$SELECT * FROM (VALUES (-1, 10), (6, -3)) AS t(source, target)$$,
driving_side => 'r',
details => true);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | -1 | 10 | -1 | 1 | 0.4 | 0
2 | 2 | -1 | 10 | 5 | 1 | 1 | 0.4
3 | 3 | -1 | 10 | 6 | 4 | 0.7 | 1.4
4 | 4 | -1 | 10 | -6 | 4 | 0.3 | 2.1
5 | 5 | -1 | 10 | 7 | 10 | 1 | 2.4
6 | 6 | -1 | 10 | 8 | 12 | 0.6 | 3.4
7 | 7 | -1 | 10 | -3 | 12 | 0.4 | 4
8 | 8 | -1 | 10 | 12 | 13 | 1 | 4.4
9 | 9 | -1 | 10 | 17 | 15 | 1 | 5.4
10 | 10 | -1 | 10 | 16 | 16 | 1 | 6.4
11 | 11 | -1 | 10 | 15 | 3 | 1 | 7.4
12 | 12 | -1 | 10 | 10 | -1 | 0 | 8.4
13 | 1 | 6 | -3 | 6 | 4 | 0.7 | 0
14 | 2 | 6 | -3 | -6 | 4 | 0.3 | 0.7
15 | 3 | 6 | -3 | 7 | 10 | 1 | 1
16 | 4 | 6 | -3 | 8 | 12 | 0.6 | 2
17 | 5 | 6 | -3 | -3 | -1 | 0 | 2.6
(17 rows)
Parámetros¶
Columna |
Tipo |
Descripción |
---|---|---|
|
Consulta SQL como se describe. |
|
|
Consulta SQL como se describe. |
|
|
SQL de combinaciones como se describe a abajo |
|
salida |
ENTEROS |
Identificador del vértice de salida. |
salidas |
|
Arreglo de identificadores de vértices destino. |
destino |
ENTEROS |
Identificador del vértice de salida. |
destinos |
|
Arreglo de identificadores de vértices destino. |
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
Parámetros opcionales¶
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
|
|
|
Parámetros opcionales para Con puntos¶
Parámetro |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
|
|
Valor en [
|
|
|
|
|
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 restricciones¶
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Secuencia de identificadores de aristas que forman un camino que no se permite tomar. - Arreglos vacios o |
|
FLOTANTES |
Costo de tomar el camino prohibido. |
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 salida. |
|
ENTEROS |
Identificador del vértice de llegada. |
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
Columnas de resultados¶
Devuelve el 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 vértice de salida. |
|
|
Identificador del vértice final. |
|
|
Identificador del nodo en la ruta de |
|
|
Identificador de la arista utilizado para ir del |
|
|
Costo para atravesar desde |
|
|
Costo agregado desde |
Ejemplos Adicionales¶
Use pgr_findCloseEdges
for points on the fly¶
Usa pgr_findCloseEdges:
Wncontrar las rutas desde el vértice \(1\) a las dos ubicaciones más cercanas en el grafo al punto`(2.9, 1.8)`.
SELECT * FROM pgr_trsp_withPoints(
$e$ SELECT * FROM edges $e$,
$r$ SELECT id, path, cost FROM restrictions $r$,
$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, ARRAY[-1, -2],
driving_side => 'r');
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | -2 | 1 | 6 | 1 | 0
2 | 2 | 1 | -2 | 3 | 7 | 1 | 1
3 | 3 | 1 | -2 | 7 | 8 | 0.9 | 2
4 | 4 | 1 | -2 | -2 | -1 | 0 | 2.9
5 | 1 | 1 | -1 | 1 | 6 | 1 | 0
6 | 2 | 1 | -1 | 3 | 7 | 1 | 1
7 | 3 | 1 | -1 | 7 | 8 | 2 | 2
8 | 4 | 1 | -1 | 7 | 10 | 1 | 4
9 | 5 | 1 | -1 | 8 | 12 | 1 | 5
10 | 6 | 1 | -1 | 12 | 13 | 1 | 6
11 | 7 | 1 | -1 | 17 | 15 | 1 | 7
12 | 8 | 1 | -1 | 16 | 16 | 1 | 8
13 | 9 | 1 | -1 | 15 | 3 | 1 | 9
14 | 10 | 1 | -1 | 10 | 5 | 0.8 | 10
15 | 11 | 1 | -1 | -1 | -1 | 0 | 10.8
(15 rows)
Punto \(-1\) corresponde a la arista más cercana al punto (2.9, 1.8).
Punto \(-2\) corresponde a la segunda arista más cercana al punto (2.9, 1.8).
Pass in front or visits.¶
Which path (if any) passes in front of point \(6\) or vertex \(11\) with right side driving topology.
SELECT ('(' || start_vid || ' => ' || end_vid ||') at ' || path_seq || 'th step:')::TEXT AS path_at,
CASE WHEN edge = -1 THEN ' visits'
ELSE ' passes in front of'
END as status,
CASE WHEN node < 0 THEN 'Point'
ELSE 'Vertex'
END as is_a,
abs(node) as id
FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT id, path, cost FROM restrictions$$,
$$SELECT pid, edge_id, fraction, side FROM pointsOfInterest$$,
ARRAY[5, -1], ARRAY[-6, -3, -6, 10, 11],
driving_side => 'r',
details => true)
WHERE node IN (-6, 11);
path_at | status | is_a | id
-------------------------+---------------------+--------+----
(-1 => -6) at 4th step: | visits | Point | 6
(-1 => -3) at 4th step: | passes in front of | Point | 6
(-1 => 10) at 4th step: | passes in front of | Point | 6
(-1 => 11) at 4th step: | passes in front of | Point | 6
(-1 => 11) at 6th step: | visits | Vertex | 11
(5 => -6) at 3th step: | visits | Point | 6
(5 => -3) at 3th step: | passes in front of | Point | 6
(5 => 10) at 3th step: | passes in front of | Point | 6
(5 => 11) at 3th step: | passes in front of | Point | 6
(5 => 11) at 5th step: | visits | Vertex | 11
(10 rows)
Show details on undirected graph.¶
Desde el punto \(1\) y el vértice \(6\) al punto \(3\) y el vértice \(1\) en un grafo no dirigido, con detalles.
SELECT * FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT id, path, cost FROM restrictions$$,
$$SELECT pid, edge_id, fraction, side FROM pointsOfInterest$$,
ARRAY[-1, 6], ARRAY[-3, 1],
directed => false,
details => true);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | -1 | -3 | -1 | 1 | 0.6 | 0
2 | 2 | -1 | -3 | 6 | 4 | 0.7 | 0.6
3 | 3 | -1 | -3 | -6 | 4 | 0.3 | 1.3
4 | 4 | -1 | -3 | 7 | 10 | 1 | 1.6
5 | 5 | -1 | -3 | 8 | 12 | 0.6 | 2.6
6 | 6 | -1 | -3 | -3 | -1 | 0 | 3.2
7 | 1 | -1 | 1 | -1 | 1 | 0.6 | 0
8 | 2 | -1 | 1 | 6 | 4 | 0.7 | 0.6
9 | 3 | -1 | 1 | -6 | 4 | 0.3 | 1.3
10 | 4 | -1 | 1 | 7 | 7 | 1 | 1.6
11 | 5 | -1 | 1 | 3 | 6 | 0.7 | 2.6
12 | 6 | -1 | 1 | -4 | 6 | 0.3 | 3.3
13 | 7 | -1 | 1 | 1 | -1 | 0 | 3.6
14 | 1 | 6 | -3 | 6 | 4 | 0.7 | 0
15 | 2 | 6 | -3 | -6 | 4 | 0.3 | 0.7
16 | 3 | 6 | -3 | 7 | 10 | 1 | 1
17 | 4 | 6 | -3 | 8 | 12 | 0.6 | 2
18 | 5 | 6 | -3 | -3 | -1 | 0 | 2.6
19 | 1 | 6 | 1 | 6 | 4 | 0.7 | 0
20 | 2 | 6 | 1 | -6 | 4 | 0.3 | 0.7
21 | 3 | 6 | 1 | 7 | 7 | 1 | 1
22 | 4 | 6 | 1 | 3 | 6 | 0.7 | 2
23 | 5 | 6 | 1 | -4 | 6 | 0.3 | 2.7
24 | 6 | 6 | 1 | 1 | -1 | 0 | 3
(24 rows)
Ver también¶
Índices y tablas