pgr_trsp
¶
pgr_trsp
- Ruteo con restricciones.
Disponibilidad
Version 4.0.0
Function promoted to official.
Versión 3.4.0
New proposed signatures:
pgr_trsp(One to One)
pgr_trsp(One to Many)
pgr_trsp(Many to One)
pgr_trsp(Many to Many)
pgr_trsp(Combinations)
Firmas obsoletas
pgr_trsp(text,integer,integer,boolean,boolean,text)
pgr_trsp(text,integer,float,integer,float,boolean,boolean,text)
pgr_trspViaVertices(text,anyarray,boolean,boolean,text)
pgr_trspviaedges(text,integer[],double precision[],boolean,boolean,text)
Versión 2.1.0
Nuevos prototipos
pgr_trspViaVertices
pgr_trspViaEdges
Versión 2.0.0
Official function.
Descripción¶
Turn restricted shortest path (TRSP) is an algorithm that receives turn restrictions in form of a query like those found in real world navigable road networks.
Las principales características son:
It does no guarantee the shortest path as it might contain restriction paths.
The general algorithm is as follows:
Execute a Dijkstra.
If the solution passes thru a restriction then.
Execute the TRSP algorithm with restrictions.
Firmas¶
Resumen
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
Uno a Uno¶
pgr_trsp(SQL de aristas, SQL de restricciones, salida, destino, [directed
])
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
Del vértice \(6\) al vértice \(10\) en un grafo no dirigido.
SELECT * FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
6, 10,
false);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 10 | 6 | 2 | 1 | 0
2 | 2 | 6 | 10 | 10 | -1 | 0 | 1
(2 rows)
Uno a Muchos¶
pgr_trsp(SQL de aristas, SQL de restricciones, salida, destinos, [directed
])
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
From vertex \(6\) to vertices \(\{10, 1\}\) on an undirected graph.
SELECT * FROM pgr_trsp(
$$SELECT id, source, target, cost FROM edges$$,
$$SELECT * FROM restrictions$$,
6, ARRAY[10, 1],
false);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 1 | 6 | 4 | 1 | 0
2 | 2 | 6 | 1 | 7 | 10 | 1 | 1
3 | 3 | 6 | 1 | 8 | 12 | 1 | 2
4 | 4 | 6 | 1 | 12 | 11 | 1 | 3
5 | 5 | 6 | 1 | 11 | 8 | 1 | 4
6 | 6 | 6 | 1 | 7 | 7 | 1 | 5
7 | 7 | 6 | 1 | 3 | 6 | 1 | 6
8 | 8 | 6 | 1 | 1 | -1 | 0 | 7
9 | 1 | 6 | 10 | 6 | 4 | 1 | 0
10 | 2 | 6 | 10 | 7 | 8 | 1 | 1
11 | 3 | 6 | 10 | 11 | 5 | 1 | 2
12 | 4 | 6 | 10 | 10 | -1 | 0 | 3
(12 rows)
Muchos a Uno¶
pgr_trsp(SQL de aristas, SQL de restricciones, salidas, destino, [directed
])
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
From vertices \(\{6, 1\}\) to vertex \(8\) on a directed graph.
SELECT * FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[6, 1], 8);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 8 | 1 | 6 | 1 | 0
2 | 2 | 1 | 8 | 3 | 7 | 1 | 1
3 | 3 | 1 | 8 | 7 | 10 | 101 | 2
4 | 4 | 1 | 8 | 8 | -1 | 0 | 103
5 | 1 | 6 | 8 | 6 | 4 | 1 | 0
6 | 2 | 6 | 8 | 7 | 10 | 1 | 1
7 | 3 | 6 | 8 | 8 | -1 | 0 | 2
(7 rows)
Muchos a Muchos¶
pgr_trsp(SQL de aristas, SQL de restricciones, salidas, destinos, [directed
])
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
From vertices \(\{6, 1\}\) to vertices \(\{10, 8\}\) on an undirected graph.
SELECT * FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[6, 1], ARRAY[10, 8],
false);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 8 | 1 | 6 | 1 | 0
2 | 2 | 1 | 8 | 3 | 7 | 1 | 1
3 | 3 | 1 | 8 | 7 | 4 | 1 | 2
4 | 4 | 1 | 8 | 6 | 2 | 1 | 3
5 | 5 | 1 | 8 | 10 | 5 | 1 | 4
6 | 6 | 1 | 8 | 11 | 11 | 1 | 5
7 | 7 | 1 | 8 | 12 | 12 | 1 | 6
8 | 8 | 1 | 8 | 8 | -1 | 0 | 7
9 | 1 | 1 | 10 | 1 | 6 | 1 | 0
10 | 2 | 1 | 10 | 3 | 7 | 1 | 1
11 | 3 | 1 | 10 | 7 | 4 | 1 | 2
12 | 4 | 1 | 10 | 6 | 2 | 1 | 3
13 | 5 | 1 | 10 | 10 | -1 | 0 | 4
14 | 1 | 6 | 8 | 6 | 4 | 1 | 0
15 | 2 | 6 | 8 | 7 | 10 | 1 | 1
16 | 3 | 6 | 8 | 8 | -1 | 0 | 2
17 | 1 | 6 | 10 | 6 | 2 | 1 | 0
18 | 2 | 6 | 10 | 10 | -1 | 0 | 1
(18 rows)
Combinaciones¶
pgr_trsp(SQL de aristas, SQL de restricciones, SQL de combinaciones, [directed
])
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
Usando una tabla de combinaciones en un grafo no dirigido.
SELECT * FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
$$SELECT * FROM (VALUES (6, 10), (6, 1), (6, 8), (1, 8)) AS combinations (source, target)$$);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 8 | 1 | 6 | 1 | 0
2 | 2 | 1 | 8 | 3 | 7 | 1 | 1
3 | 3 | 1 | 8 | 7 | 10 | 101 | 2
4 | 4 | 1 | 8 | 8 | -1 | 0 | 103
5 | 1 | 6 | 1 | 6 | 4 | 1 | 0
6 | 2 | 6 | 1 | 7 | 10 | 1 | 1
7 | 3 | 6 | 1 | 8 | 12 | 1 | 2
8 | 4 | 6 | 1 | 12 | 13 | 1 | 3
9 | 5 | 6 | 1 | 17 | 15 | 1 | 4
10 | 6 | 6 | 1 | 16 | 9 | 1 | 5
11 | 7 | 6 | 1 | 11 | 8 | 1 | 6
12 | 8 | 6 | 1 | 7 | 7 | 1 | 7
13 | 9 | 6 | 1 | 3 | 6 | 1 | 8
14 | 10 | 6 | 1 | 1 | -1 | 0 | 9
15 | 1 | 6 | 8 | 6 | 4 | 1 | 0
16 | 2 | 6 | 8 | 7 | 10 | 1 | 1
17 | 3 | 6 | 8 | 8 | -1 | 0 | 2
18 | 1 | 6 | 10 | 6 | 4 | 1 | 0
19 | 2 | 6 | 10 | 7 | 10 | 1 | 1
20 | 3 | 6 | 10 | 8 | 12 | 1 | 2
21 | 4 | 6 | 10 | 12 | 13 | 1 | 3
22 | 5 | 6 | 10 | 17 | 15 | 1 | 4
23 | 6 | 6 | 10 | 16 | 16 | 1 | 5
24 | 7 | 6 | 10 | 15 | 3 | 1 | 6
25 | 8 | 6 | 10 | 10 | -1 | 0 | 7
(25 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 partida. |
salidas |
|
Arreglo de identificadores de vértices destino. |
destino |
ENTEROS |
Identificador del vértice de partida. |
destinos |
|
Arreglo de identificadores de vértices destino. |
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
Parámetros opcionales¶
Columna |
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 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 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¶
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 |
Ver también¶
Índices y tablas