pgr_trsp - Proposed

pgr_trsp - Ruteo con restricciones.

_images/boost-inside.jpeg

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

    • 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

    • 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

pgr_trsp(SQL de aristas, SQL de restricciones, salida, destino, [directed])
pgr_trsp(SQL de aristas, SQL de restricciones, salida, destinos, [directed])
pgr_trsp(SQL de aristas, SQL de restricciones, salidas, destino, [directed])
pgr_trsp(SQL de aristas, SQL de restricciones, salidas, destinos, [directed])
Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
O CONJUNTO VACÍO

Uno a Uno

pgr_trsp(SQL de aristas, SQL de restricciones, salida, destino, [directed])

Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
O CONJUNTO VACÍO
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])

Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
O CONJUNTO VACÍO
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])

Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
O CONJUNTO VACÍO
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])

Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
O CONJUNTO VACÍO
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])

Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
O CONJUNTO VACÍO
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

SQL de aristas

TEXT

Consulta SQL como se describe.

SQL de restricciones

TEXT

Consulta SQL como se describe.

SQL de combinaciones

TEXT

SQL de combinaciones como se describe a abajo

salida

ENTEROS

Identificador del vértice de partida.

salidas

ARRAY [ENTEROS]

Arreglo de identificadores de vértices destino.

destino

ENTEROS

Identificador del vértice de partida.

destinos

ARRAY [ENTEROS]

Arreglo de identificadores de vértices destino.

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.

Consultas Internas

SQL 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

SQL restricciones

Columna

Tipo

Descripción

path

ARRAY [ENTEROS]

Secuencia de identificadores de aristas que forman un camino que no se permite tomar. - Arreglos vacios o NULL son ignorados. - Arreglos que tienen NULL arrojan una excepción.

Cost

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

source

ENTEROS

Identificador del vértice de partida.

target

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

seq

INTEGER

Valor secuencial a partir de 1.

path_id

INTEGER

Identificador del camino.

  • Tiene valor 1 para el primero de la ruta de start_vid a end_vid.

path_seq

INTEGER

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

start_vid

BIGINT

Identificador del vértice de salida.

end_vid

BIGINT

Identificador del vértice final.

node

BIGINT

Identificador del nodo en la ruta de start_vid a end_vid.

edge

BIGINT

Identificador de la arista utilizado para ir del node al siguiente nodo de la secuencia de ruta. -1 para el último nodo de la ruta.

cost

FLOAT

Costo para atravesar desde node usando edge hasta el siguiente nodo en la secuencia de la ruta.

agg_cost

FLOAT

Costo agregado desde start_vid hasta node.

Ver también

Índices y tablas