pgr_trspVia - Proposed

pgr_trspVia Route that goes through a list of vertices 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

    • Es posible que el nombre no cambie. (Pero todavía puede)

    • Es posible que la firma no cambie. (Pero todavía puede)

    • Es posible que 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.

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • Version 3.4.0

    • New proposed function pgr_trspVia (One Via)

Descripción

Given a list of vertices and a graph, this function is equivalent to finding the shortest path between \(vertex_i\) and \(vertex_{i+1}\) for all \(i < size\_of(via\;vertices)\) trying not to use restricted paths.

Las trayectorias representan los tramos de la ruta.

The general algorithm is as follows:

  • Execute a pgr_dijkstraVia - Proposed.

  • For the set of sub paths of the solution that pass through a restriction then

    • Execute the TRSP algorithm with restrictions for the paths.

    • NOTE when this is done, U_turn_on_edge flag is ignored.

Firmas

One Via

pgr_trspVia(Edges SQL, Restrictions SQL, via vertices
           [, directed] [, strict] [, U_turn_on_edge]) - Proposed on v3.4
RETURNS SET OF (seq, path_pid, path_seq, start_vid, end_vid,
                node, edge, cost, agg_cost, route_agg_cost)
OR EMPTY SET
Ejemplo:

Find the route that visits the vertices \(\{ 5, 1, 8\}\) in that order on an directed graph.

SELECT * FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[5, 1, 8]);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         5 |       1 |    5 |    1 |    1 |        0 |              0
   2 |       1 |        2 |         5 |       1 |    6 |    4 |    1 |        1 |              1
   3 |       1 |        3 |         5 |       1 |    7 |   10 |    1 |        2 |              2
   4 |       1 |        4 |         5 |       1 |    8 |   12 |    1 |        3 |              3
   5 |       1 |        5 |         5 |       1 |   12 |   13 |    1 |        4 |              4
   6 |       1 |        6 |         5 |       1 |   17 |   15 |    1 |        5 |              5
   7 |       1 |        7 |         5 |       1 |   16 |    9 |    1 |        6 |              6
   8 |       1 |        8 |         5 |       1 |   11 |    8 |    1 |        7 |              7
   9 |       1 |        9 |         5 |       1 |    7 |    7 |    1 |        8 |              8
  10 |       1 |       10 |         5 |       1 |    3 |    6 |    1 |        9 |              9
  11 |       1 |       11 |         5 |       1 |    1 |   -1 |    0 |       10 |             10
  12 |       2 |        1 |         1 |       8 |    1 |    6 |    1 |        0 |             10
  13 |       2 |        2 |         1 |       8 |    3 |    7 |    1 |        1 |             11
  14 |       2 |        3 |         1 |       8 |    7 |   10 |  101 |        2 |             12
  15 |       2 |        4 |         1 |       8 |    8 |   -2 |    0 |      103 |            113
(15 rows)

Parámetros

Parámetro

Tipo

Descripción

SQL Aristas

TEXT

Edges SQL query as described.

SQL de restricciones

TEXT

Restrictions SQL query as described.

vía vértices

ARRAY[ ENTEROS ]

Arreglo ordenado de identificadores de vértices que serán visitados.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

Parámetros opcionales

Columna

Tipo

x Defecto

Descripción

directed

BOOLEAN

true

  • Cuando true el gráfo se considera Dirigido

  • Cuando false el gráfo se considera No Dirigido.

Vía parámetros opcional

Parámetro

Tipo

x Defecto

Descripción

strict

BOOLEAN

false

  • Cuando true si un camino le faltan paradas y regresa EMPTY SET

  • En caso de false, ignora las rutas faltantes y devuelve todas las rutas encontradas

U_turn_on_edge

BOOLEAN

true

  • Cuando true saliendo desde un vértice visitado no intentara esquivarlo

Consultas internas

SQL de aristas

Columna

Tipo

x Defecto

Descripción

id

ENTEROS

Identificador de la arista.

source

ENTEROS

Identificador del primer vértice de la arista.

target

ENTEROS

Identificador del segundo vértice de la arista.

cost

FLOTANTES

Peso de la arista (source, target)

reverse_cost

FLOTANTES

-1

Peso de la arista (target, source)

  • Cuando negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Restricciones SQL

Columna

Tipo

Descripción

path

ARRAY[ ENTEROS ]

Sequence of edge identifiers that form a path that is not allowed to be taken. - Empty arrays or NULL arrays are ignored. - Arrays that have a NULL element will raise an exception.

Cost

FLOTANTES

Costo de tomar el camino prohibido.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Resultados

Columna

Tipo

Descripción

seq

INTEGER

Valor secuencial a partir de 1.

path_id

INTEGER

Identificador del camino. Tiene valor 1 para el primer camino.

path_seq

INTEGER

Posición relativa en la ruta. Tiene el valor 1 para el principio de una ruta.

start_vid

BIGINT

Identificador del vértice inicial de la ruta.

end_vid

BIGINT

Identificador del vértice final de la ruta.

node

BIGINT

Identificador del nodo en la ruta de start_vid a end_vid.

edge

BIGINT

Identificador del borde utilizado para ir del node al siguiente nodo de la secuencia de ruta.

  • -1 para el último nodo de la ruta.

  • -2 para el último nodo de la ruta.

cost

FLOAT

Costo del desplazamiento desde node usando `` edge`` hasta el siguiente nodo en la secuencia de ruta.

agg_cost

FLOAT

Coste agregado desde start_vid al node.

route_agg_cost

FLOAT

Costo total desde start_vid en seq = 1 hasta end_vid del seq actual.

Ejemplos Adicionales

All this examples are about the route that visits the vertices \(\{5, 7, 1, 8, 15\}\) in that order on a directed graph.

The main query

SELECT * FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[5, 7, 1, 8, 15]);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         5 |       7 |    5 |    1 |    1 |        0 |              0
   2 |       1 |        2 |         5 |       7 |    6 |    4 |    1 |        1 |              1
   3 |       1 |        3 |         5 |       7 |    7 |   -1 |    0 |        2 |              2
   4 |       2 |        1 |         7 |       1 |    7 |    7 |    1 |        0 |              2
   5 |       2 |        2 |         7 |       1 |    3 |    6 |    1 |        1 |              3
   6 |       2 |        3 |         7 |       1 |    1 |   -1 |    0 |        2 |              4
   7 |       3 |        1 |         1 |       8 |    1 |    6 |    1 |        0 |              4
   8 |       3 |        2 |         1 |       8 |    3 |    7 |    1 |        1 |              5
   9 |       3 |        3 |         1 |       8 |    7 |   10 |  101 |        2 |              6
  10 |       3 |        4 |         1 |       8 |    8 |   -1 |    0 |      103 |            107
  11 |       4 |        1 |         8 |      15 |    8 |   12 |    1 |        0 |            107
  12 |       4 |        2 |         8 |      15 |   12 |   13 |    1 |        1 |            108
  13 |       4 |        3 |         8 |      15 |   17 |   15 |    1 |        2 |            109
  14 |       4 |        4 |         8 |      15 |   16 |   16 |    1 |        3 |            110
  15 |       4 |        5 |         8 |      15 |   15 |   -2 |    0 |        4 |            111
(15 rows)

Costo agregado de la tercera ruta.

SELECT agg_cost FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[5, 7, 1, 8, 15])
WHERE path_id = 3 AND edge < 0;
 agg_cost
----------
      103
(1 row)

Costo agregado de al final de la tercera ruta.

SELECT route_agg_cost FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[5, 7, 1, 8, 15])
WHERE path_id = 3 AND edge < 0;
 route_agg_cost
----------------
            107
(1 row)

Nodos visitados en la ruta.

SELECT row_number() over () as node_seq, node
FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[5, 7, 1, 8, 15])
WHERE edge <> -1 ORDER BY seq;
 node_seq | node
----------+------
        1 |    5
        2 |    6
        3 |    7
        4 |    3
        5 |    1
        6 |    3
        7 |    7
        8 |    8
        9 |   12
       10 |   17
       11 |   16
       12 |   15
(12 rows)

Costo agregado de la ruta al llegar a los vértices visitados.

SELECT path_id, route_agg_cost FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[5, 7, 1, 8, 15])
WHERE edge < 0;
 path_id | route_agg_cost
---------+----------------
       1 |              2
       2 |              4
       3 |            107
       4 |            111
(4 rows)

Status of «passes in front» or «visits» of the nodes.

SELECT seq, route_agg_cost, node, agg_cost ,
CASE WHEN edge = -1 THEN $$visits$$
ELSE $$passes in front$$
END as status
FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[5, 7, 1, 8, 15])
WHERE agg_cost <> 0 or seq = 1;
 seq | route_agg_cost | node | agg_cost |     status
-----+----------------+------+----------+-----------------
   1 |              0 |    5 |        0 | passes in front
   2 |              1 |    6 |        1 | passes in front
   3 |              2 |    7 |        2 | visits
   5 |              3 |    3 |        1 | passes in front
   6 |              4 |    1 |        2 | visits
   8 |              5 |    3 |        1 | passes in front
   9 |              6 |    7 |        2 | passes in front
  10 |            107 |    8 |      103 | visits
  12 |            108 |   12 |        1 | passes in front
  13 |            109 |   17 |        2 | passes in front
  14 |            110 |   16 |        3 | passes in front
  15 |            111 |   15 |        4 | passes in front
(12 rows)

Sumulación del functionamiento del algoritmo

The algorithm performs a pgr_dijkstraVia - Proposed

SELECT * FROM pgr_dijkstraVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  ARRAY[6, 3, 6]);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         6 |       3 |    6 |    4 |    1 |        0 |              0
   2 |       1 |        2 |         6 |       3 |    7 |    7 |    1 |        1 |              1
   3 |       1 |        3 |         6 |       3 |    3 |   -1 |    0 |        2 |              2
   4 |       2 |        1 |         3 |       6 |    3 |    7 |    1 |        0 |              2
   5 |       2 |        2 |         3 |       6 |    7 |    4 |    1 |        1 |              3
   6 |       2 |        3 |         3 |       6 |    6 |   -2 |    0 |        2 |              4
(6 rows)

Detects which of the sub paths pass through a restriction in this case is for the path_id = 5 from 6 to 3 because the path \(15 \rightarrow 1\) is restricted.

Executes the pgr_trsp - Proposed algorithm for the conflicting paths.

SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  6, 3);
 path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
---------+----------+-----------+---------+------+------+------+----------
       1 |        1 |         6 |       3 |    6 |    4 |    1 |        0
       1 |        2 |         6 |       3 |    7 |   10 |    1 |        1
       1 |        3 |         6 |       3 |    8 |   12 |    1 |        2
       1 |        4 |         6 |       3 |   12 |   13 |    1 |        3
       1 |        5 |         6 |       3 |   17 |   15 |    1 |        4
       1 |        6 |         6 |       3 |   16 |    9 |    1 |        5
       1 |        7 |         6 |       3 |   11 |    8 |    1 |        6
       1 |        8 |         6 |       3 |    7 |    7 |    1 |        7
       1 |        9 |         6 |       3 |    3 |   -1 |    0 |        8
(9 rows)

From the pgr_dijkstraVia - Proposed result it removes the conflicting paths and builds the solution with the results of the pgr_trsp - Proposed algorithm:

WITH
solutions AS (
  SELECT path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_dijkstraVia(
    $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
    ARRAY[6, 3, 6]) WHERE path_id != 1
  UNION
  SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
    $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
    $$SELECT path, cost FROM restrictions$$,
    6, 3)),
with_seq AS (
  SELECT row_number() over(ORDER BY path_id, path_seq) AS seq, *
  FROM solutions),
aggregation AS (SELECT seq, SUM(cost) OVER(ORDER BY seq) AS route_agg_cost FROM with_seq)
SELECT with_seq.*, COALESCE(route_agg_cost, 0) AS route_agg_cost
FROM with_seq LEFT JOIN aggregation ON (with_seq.seq = aggregation.seq + 1);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         6 |       3 |    6 |    4 |    1 |        0 |              0
   2 |       1 |        2 |         6 |       3 |    7 |   10 |    1 |        1 |              1
   3 |       1 |        3 |         6 |       3 |    8 |   12 |    1 |        2 |              2
   4 |       1 |        4 |         6 |       3 |   12 |   13 |    1 |        3 |              3
   5 |       1 |        5 |         6 |       3 |   17 |   15 |    1 |        4 |              4
   6 |       1 |        6 |         6 |       3 |   16 |    9 |    1 |        5 |              5
   7 |       1 |        7 |         6 |       3 |   11 |    8 |    1 |        6 |              6
   8 |       1 |        8 |         6 |       3 |    7 |    7 |    1 |        7 |              7
   9 |       1 |        9 |         6 |       3 |    3 |   -1 |    0 |        8 |              8
  10 |       2 |        1 |         3 |       6 |    3 |    7 |    1 |        0 |              8
  11 |       2 |        2 |         3 |       6 |    7 |    4 |    1 |        1 |              9
  12 |       2 |        3 |         3 |       6 |    6 |   -2 |    0 |        2 |             10
(12 rows)

Getting the same result as pgr_trspVia:

SELECT * FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[6, 3, 6]);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         6 |       3 |    6 |    4 |    1 |        0 |              0
   2 |       1 |        2 |         6 |       3 |    7 |   10 |    1 |        1 |              1
   3 |       1 |        3 |         6 |       3 |    8 |   12 |    1 |        2 |              2
   4 |       1 |        4 |         6 |       3 |   12 |   13 |    1 |        3 |              3
   5 |       1 |        5 |         6 |       3 |   17 |   15 |    1 |        4 |              4
   6 |       1 |        6 |         6 |       3 |   16 |    9 |    1 |        5 |              5
   7 |       1 |        7 |         6 |       3 |   11 |    8 |    1 |        6 |              6
   8 |       1 |        8 |         6 |       3 |    7 |    7 |    1 |        7 |              7
   9 |       1 |        9 |         6 |       3 |    3 |   -1 |    0 |        8 |              8
  10 |       2 |        1 |         3 |       6 |    3 |    7 |    1 |        0 |              8
  11 |       2 |        2 |         3 |       6 |    7 |    4 |    1 |        1 |              9
  12 |       2 |        3 |         3 |       6 |    6 |   -2 |    0 |        2 |             10
(12 rows)

Ejemplo 8:

Sometimes U_turn_on_edge flag is ignored when is set to false.

The first step, doing a pgr_dijkstraVia - Proposed does consider not making a U turn on the same edge. But the path \(16 \rightarrow 13\) (Rows 4 and 5) is restricted and the result is using it.

SELECT * FROM pgr_dijkstraVia(
    $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
    ARRAY[6, 7, 6], U_turn_on_edge => false);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         6 |       7 |    6 |    4 |    1 |        0 |              0
   2 |       1 |        2 |         6 |       7 |    7 |   -1 |    0 |        1 |              1
   3 |       2 |        1 |         7 |       6 |    7 |    8 |    1 |        0 |              1
   4 |       2 |        2 |         7 |       6 |   11 |    9 |    1 |        1 |              2
   5 |       2 |        3 |         7 |       6 |   16 |   16 |    1 |        2 |              3
   6 |       2 |        4 |         7 |       6 |   15 |    3 |    1 |        3 |              4
   7 |       2 |        5 |         7 |       6 |   10 |    2 |    1 |        4 |              5
   8 |       2 |        6 |         7 |       6 |    6 |   -2 |    0 |        5 |              6
(8 rows)

When executing the pgr_trsp - Proposed algorithm for the conflicting path, there is no U_turn_on_edge flag.

SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  7, 6);
 path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
---------+----------+-----------+---------+------+------+------+----------
       1 |        1 |         7 |       6 |    7 |    4 |    1 |        0
       1 |        2 |         7 |       6 |    6 |   -1 |    0 |        1
(2 rows)

Therefore the result ignores the U_turn_on_edge flag when set to false.

SELECT * FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[6, 7, 6], U_turn_on_edge => false);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         6 |       7 |    6 |    4 |    1 |        0 |              0
   2 |       1 |        2 |         6 |       7 |    7 |   -1 |    0 |        1 |              1
   3 |       2 |        1 |         7 |       6 |    7 |    4 |    1 |        0 |              1
   4 |       2 |        2 |         7 |       6 |    6 |   -2 |    0 |        1 |              2
(4 rows)

Ver también

Índices y tablas