pgr_withPointsVia - Proposed

pgr_withPointsVia - Route that goes through a list of vertices and/or points.

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_withPointsVia (One Via)

Descripción

Given a graph, a set of points on the graphs edges and a list of vertices, this function is equivalent to finding the shortest path between \(vertex_i\) and \(vertex_{i+1}\) (where \(vertex\) can be a vertex or a point on the graph) for all \(i < size\_of(via\;vertices)\).

Route:

is a sequence of paths.

Path:

is a section of the route.

The general algorithm is as follows:

  • Build the Graph with the new points.

    • The points identifiers will be converted to negative values.

    • The vertices identifiers will remain positive.

  • Execute a pgr_dijkstraVia - Proposed.

Firmas

One Via

pgr_withPointsVia(Edges SQL, Points 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 \(\{ -6, 15, -1\}\) in that order on a directed graph.

SELECT * FROM pgr_withPointsVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  'SELECT pid, edge_id, fraction, side from pointsOfInterest',
  ARRAY[-6, 15, -1]);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |        -6 |      15 |   -6 |    4 |  0.3 |        0 |              0
   2 |       1 |        2 |        -6 |      15 |    7 |    8 |    1 |      0.3 |            0.3
   3 |       1 |        3 |        -6 |      15 |   11 |    9 |    1 |      1.3 |            1.3
   4 |       1 |        4 |        -6 |      15 |   16 |   16 |    1 |      2.3 |            2.3
   5 |       1 |        5 |        -6 |      15 |   15 |   -1 |    0 |      3.3 |            3.3
   6 |       2 |        1 |        15 |      -1 |   15 |    3 |    1 |        0 |            3.3
   7 |       2 |        2 |        15 |      -1 |   10 |    2 |    1 |        1 |            4.3
   8 |       2 |        3 |        15 |      -1 |    6 |    1 |  0.6 |        2 |            5.3
   9 |       2 |        4 |        15 |      -1 |   -1 |   -2 |    0 |      2.6 |            5.9
(9 rows)

Parámetros

Parámetro

Tipo

x Defecto

Descripción

SQL Aristas

TEXT

consulta SQL como descrito.

Points SQL

TEXT

consulta SQL como descrito.

vía vértices

ARRAY[ ENTEROS ]

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

  • Cuando sea positivo se considera como un identificador de vértice

  • Cuando sea negativo se considera como un identificador de punto

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

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

With points optional parameters

Parámetro

Tipo

x Defecto

Descripción

driving_side

CHAR

b

Value in [r, l, b] indicating if the driving side is:

  • r for right driving side.

  • l for left driving side.

  • b for both.

details

BOOLEAN

false

  • When true the results will include the points that are in the path.

  • When false the results will not include the points that are in the path.

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

Puntos SQL

Parámetro

Tipo

x Defecto

Descripción

pid

ENTEROS

valor

Identificador del punto.

  • Use con un valor positivo, dado que internamente se convertirá a un valor negativo

  • Si columna esta presente, no puede ser NULL.

  • Si columna no esta presente, un valor secuencial negativo automáticamente se otorgará..

edge_id

ENTEROS

Identificador de la arista «más cercana» al punto.

fraction

FLOTANTES

El valor en <0,1> que indica la posición relativa desde el primer punto de la arista.

side

CHAR

b

Valor en [b, r, l, NULL] indicando si el punto es:

  • A la derecha r,

  • A la izquierda l,

  • In both sides b, NULL

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.

Nota

Cuando las columnas start_vid, end_vid y``node`` tengan valores negativos, el identificador es para un Punto.

Ejemplos Adicionales

Use pgr_findCloseEdges in the Points SQL

Visit from vertex \(1\) to the two locations on the graph of point (2.9, 1.8) in order of closeness to the graph.

SELECT * FROM pgr_withPointsVia(
  $e$ SELECT * FROM edges $e$,
  $p$ SELECT edge_id, round(fraction::numeric, 2) AS fraction, side
      FROM pgr_findCloseEdges(
        $$SELECT id, geom FROM edges$$,
        (SELECT ST_POINT(2.9, 1.8)),
        0.5, cap => 2)
  $p$,
  ARRAY[1, -1, -2], details => true);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         1 |      -1 |    1 |    6 |    1 |        0 |              0
   2 |       1 |        2 |         1 |      -1 |    3 |    7 |    1 |        1 |              1
   3 |       1 |        3 |         1 |      -1 |    7 |    8 |  0.9 |        2 |              2
   4 |       1 |        4 |         1 |      -1 |   -2 |    8 |  0.1 |      2.9 |            2.9
   5 |       1 |        5 |         1 |      -1 |   11 |    9 |    1 |        3 |              3
   6 |       1 |        6 |         1 |      -1 |   16 |   16 |    1 |        4 |              4
   7 |       1 |        7 |         1 |      -1 |   15 |    3 |    1 |        5 |              5
   8 |       1 |        8 |         1 |      -1 |   10 |    5 |  0.8 |        6 |              6
   9 |       1 |        9 |         1 |      -1 |   -1 |   -1 |    0 |      6.8 |            6.8
  10 |       2 |        1 |        -1 |      -2 |   -1 |    5 |  0.2 |        0 |            6.8
  11 |       2 |        2 |        -1 |      -2 |   11 |    8 |  0.1 |      0.2 |              7
  12 |       2 |        3 |        -1 |      -2 |   -2 |   -2 |    0 |      0.3 |            7.1
(12 rows)

  • Point \(-1\) corresponds to the closest edge from point (2.9,1.8).

  • Point \(-2\) corresponds to the next close edge from point (2.9,1.8).

  • Point \(-2\) is visited on the route to from vertex \(1\) to Point \(-1\) (See row where \(seq = 4\)).

Usage variations

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

SELECT * FROM pgr_withPointsVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  'SELECT pid, edge_id, fraction, side from pointsOfInterest',
  ARRAY[-1, 7, -3, 16, 15]);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |        -1 |       7 |   -1 |    1 |  0.6 |        0 |              0
   2 |       1 |        2 |        -1 |       7 |    6 |    4 |    1 |      0.6 |            0.6
   3 |       1 |        3 |        -1 |       7 |    7 |   -1 |    0 |      1.6 |            1.6
   4 |       2 |        1 |         7 |      -3 |    7 |   10 |    1 |        0 |            1.6
   5 |       2 |        2 |         7 |      -3 |    8 |   12 |  0.6 |        1 |            2.6
   6 |       2 |        3 |         7 |      -3 |   -3 |   -1 |    0 |      1.6 |            3.2
   7 |       3 |        1 |        -3 |      16 |   -3 |   12 |  0.4 |        0 |            3.2
   8 |       3 |        2 |        -3 |      16 |   12 |   13 |    1 |      0.4 |            3.6
   9 |       3 |        3 |        -3 |      16 |   17 |   15 |    1 |      1.4 |            4.6
  10 |       3 |        4 |        -3 |      16 |   16 |   -1 |    0 |      2.4 |            5.6
  11 |       4 |        1 |        16 |      15 |   16 |   16 |    1 |        0 |            5.6
  12 |       4 |        2 |        16 |      15 |   15 |   -2 |    0 |        1 |            6.6
(12 rows)

Costo agregado de la tercera ruta.

SELECT agg_cost FROM  pgr_withPointsVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  'SELECT pid, edge_id, fraction, side from pointsOfInterest',
  ARRAY[-1, 7, -3, 16, 15])
WHERE path_id = 3 AND edge < 0;
 agg_cost
----------
      2.4
(1 row)

Costo agregado de al final de la tercera ruta.

SELECT route_agg_cost FROM  pgr_withPointsVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  'SELECT pid, edge_id, fraction, side from pointsOfInterest',
  ARRAY[-1, 7, -3, 16, 15])
WHERE path_id = 3 AND edge < 0;
 route_agg_cost
----------------
            5.6
(1 row)

Nodos visitados en la ruta.

SELECT row_number() over () as node_seq, node
FROM  pgr_withPointsVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  'SELECT pid, edge_id, fraction, side from pointsOfInterest',
  ARRAY[-1, 7, -3, 16, 15])
WHERE edge <> -1 ORDER BY seq;
 node_seq | node
----------+------
        1 |   -1
        2 |    6
        3 |    7
        4 |    8
        5 |   -3
        6 |   12
        7 |   17
        8 |   16
        9 |   15
(9 rows)

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

SELECT path_id, route_agg_cost FROM  pgr_withPointsVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  'SELECT pid, edge_id, fraction, side from pointsOfInterest',
  ARRAY[-1, 7, -3, 16, 15])
WHERE edge < 0;
 path_id | route_agg_cost
---------+----------------
       1 |            1.6
       2 |            3.2
       3 |            5.6
       4 |            6.6
(4 rows)

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

SELECT seq, node,
CASE WHEN edge = -1 THEN 'visits'
ELSE 'passes in front'
END as status
FROM  pgr_withPointsVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  'SELECT pid, edge_id, fraction, side from pointsOfInterest',
  ARRAY[-1, 7, -3, 16, 15], details => true)
WHERE agg_cost <> 0 or seq = 1;
 seq | node |     status
-----+------+-----------------
   1 |   -1 | passes in front
   2 |    6 | passes in front
   3 |   -6 | passes in front
   4 |    7 | visits
   6 |    8 | passes in front
   7 |   -3 | visits
   9 |   12 | passes in front
  10 |   17 | passes in front
  11 |   -2 | passes in front
  12 |   16 | visits
  14 |   15 | passes in front
(11 rows)

Ver también

Índices y tablas