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
Nuevas firmas propuestas
pgr_trsp(Uno a Uno)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_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(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