pgr_trsp - Proposed¶
pgr_trsp - Ruteo con restricciones.
Adentro: Boost Graph¶
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(One to One)pgr_trsp(One to Many)pgr_trsp(Many to One)pgr_trsp(Many to Many)pgr_trsp(Combinations)
Deprecated signatures:
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
New prototypes:
pgr_trspViaVerticespgr_trspViaEdges
Versión 2.0.0
Función oficial
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¶
Propuesto
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)Uno a Uno¶
pgr_trsp(Edges SQL, Restrictions SQL, start vid, end vid, [directed])
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- Ejemplo:
From vertex \(6\) to vertex \(10\) on an undirected graph.
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(Edges SQL, Restrictions SQL, start vid, end vids, [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(Edges SQL, Restrictions SQL, start vids, end vid, [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(Edges SQL, Restrictions SQL, start vids, end vids,
[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(Edges SQL, Restrictions SQL, Combinations SQL, [directed])
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- Ejemplo:
Using a combinations table on an undirected graph.
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 Combinaciones como se describe a abajo |
|
vid de salida |
ENTEROS |
Identificador del vértice de salida. |
vid salidas |
|
Arreglo de identificadores de vértices destino. |
vid destino |
ENTEROS |
Identificador del vértice de salida. |
vids 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 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 destino. |
|
|
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