pgr_withPoints - Propuesto

pgr_withPoints - Devuelve la ruta más corta de un grafo con vértices temporales adicionales.

Advertencia

Funciones propuestas para el próximo lanzamineto.

  • No están oficialmente en la versión actual.

  • Es probable que oficialmente formen parte del próximo lanzamiento:

    • Las funciones hacen uso de ANY-INTEGER y ANY-NUMERICAL

    • 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 de pgTap. Pero tal vez necesite más.

    • Es posible que la documentación necesite un refinamiento.

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • Versión 3.2.0

    • Nueva función propuesta:

      • pgr_withPoints(Combinaciones)

  • Version 2.2.0

    • Nueva función propuesta

Soporte

Descripción

Modifique el grafo para incluir puntos definidos por points_sql. Usando el algoritmo Dijkstra, busque la o las rutas más cortas

Las características principales son:

  • El proceso se realiza sólo en las aristas con costos positivos.

  • Los vértices del grafo son:

    • positivo cuando pertenece a edges_sql

    • negativo cuando pertenece a points_sql

  • Valores son regresados cuando hay un camino.

    • Cuando el vértice inicial y el vértice final son los mismos, no hay ninguna ruta. - El agg_cost los valores no incluidos (v, v) es 0

    • Cuando el vértice inicial y el vértice final son diferentes y no hay ninguna ruta: - En ell agg_cost los valores no incluidos (u, v) es ∞

  • Para fines de optimización, se omite cualquier valor duplicado en start_vids o end_vids.

  • Los valores devueltos se ordenan: - start_vid ascendente - end_vid ascendente

  • Tiempo de ejecución: \(O(|start\_vids|\times(V \log V + E))\)

Firmas

Resumen

pgr_withPoints(edges_sql, points_sql, from_vid,  to_vid  [, directed] [, driving_side] [, details])
pgr_withPoints(edges_sql, points_sql, from_vid,  to_vids [, directed] [, driving_side] [, details])
pgr_withPoints(edges_sql, points_sql, from_vids, to_vid  [, directed] [, driving_side] [, details])
pgr_withPoints(edges_sql, points_sql, from_vids, to_vids [, directed] [, driving_side] [, details])
pgr_withPoints(Edges SQL, Points SQL, Combinations SQL [, directed] [, driving_side] [, details])
RETURNS SET OF (seq, path_seq, [start_vid,] [end_vid,] node, edge, cost, agg_cost)

Uso de valores predeterminados

pgr_withPoints(edges_sql, points_sql, from_vid, to_vid)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
Ejemplo

Del punto \(1\) al punto \(3\)

  • Para un grafo dirigido.

  • Ambos lados de conducción se establecen como b. Así que llegar/partir hacia/desde el o los puntos, puede ser en cualquier dirección.

  • No se proporcionan detalles sobre la distancia de otros puntos de la consulta points_sql.

SELECT * FROM pgr_withPoints(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    'SELECT pid, edge_id, fraction, side from pointsOfInterest',
    -1, -3);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |   -1 |    1 |  0.6 |        0
   2 |        2 |    2 |    4 |    1 |      0.6
   3 |        3 |    5 |   10 |    1 |      1.6
   4 |        4 |   10 |   12 |  0.6 |      2.6
   5 |        5 |   -3 |   -1 |    0 |      3.2
(5 rows)

Uno a Uno

pgr_withPoints(edges_sql, points_sql, from_vid,  to_vid  [, directed] [, driving_side] [, details])
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
Ejemplo

Del punto \(1\) al vértice \(3\) con detalles de puntos de paso

SELECT * FROM pgr_withPoints(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    'SELECT pid, edge_id, fraction, side from pointsOfInterest',
    -1, 3,
    details := true);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |   -1 |    1 |  0.6 |        0
   2 |        2 |    2 |    4 |  0.7 |      0.6
   3 |        3 |   -6 |    4 |  0.3 |      1.3
   4 |        4 |    5 |    8 |    1 |      1.6
   5 |        5 |    6 |    9 |    1 |      2.6
   6 |        6 |    9 |   16 |    1 |      3.6
   7 |        7 |    4 |    3 |    1 |      4.6
   8 |        8 |    3 |   -1 |    0 |      5.6
(8 rows)

Uno a Muchos

pgr_withPoints(edges_sql, points_sql, from_vid,  to_vids [, directed] [, driving_side] [, details])
RETURNS SET OF (seq, path_seq, end_vid, node, edge, cost, agg_cost)
Ejemplo

Del punto \(1\) al punto \(3\) y al vértice \(5\)

SELECT * FROM pgr_withPoints(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    'SELECT pid, edge_id, fraction, side from pointsOfInterest',
    -1, ARRAY[-3,5]);
 seq | path_seq | end_pid | node | edge | cost | agg_cost
-----+----------+---------+------+------+------+----------
   1 |        1 |      -3 |   -1 |    1 |  0.6 |        0
   2 |        2 |      -3 |    2 |    4 |    1 |      0.6
   3 |        3 |      -3 |    5 |   10 |    1 |      1.6
   4 |        4 |      -3 |   10 |   12 |  0.6 |      2.6
   5 |        5 |      -3 |   -3 |   -1 |    0 |      3.2
   6 |        1 |       5 |   -1 |    1 |  0.6 |        0
   7 |        2 |       5 |    2 |    4 |    1 |      0.6
   8 |        3 |       5 |    5 |   -1 |    0 |      1.6
(8 rows)

Muchos a Uno

pgr_withPoints(edges_sql, points_sql, from_vids, to_vid  [, directed] [, driving_side] [, details])
RETURNS SET OF (seq, path_seq, start_vid, node, edge, cost, agg_cost)
Ejemplo

Desde el punto \(1\) y el vértice \(2\) al punto \(3\)

SELECT * FROM pgr_withPoints(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    'SELECT pid, edge_id, fraction, side from pointsOfInterest',
    ARRAY[-1,2], -3);
 seq | path_seq | start_pid | node | edge | cost | agg_cost
-----+----------+-----------+------+------+------+----------
   1 |        1 |        -1 |   -1 |    1 |  0.6 |        0
   2 |        2 |        -1 |    2 |    4 |    1 |      0.6
   3 |        3 |        -1 |    5 |   10 |    1 |      1.6
   4 |        4 |        -1 |   10 |   12 |  0.6 |      2.6
   5 |        5 |        -1 |   -3 |   -1 |    0 |      3.2
   6 |        1 |         2 |    2 |    4 |    1 |        0
   7 |        2 |         2 |    5 |   10 |    1 |        1
   8 |        3 |         2 |   10 |   12 |  0.6 |        2
   9 |        4 |         2 |   -3 |   -1 |    0 |      2.6
(9 rows)

Muchos a Muchos

pgr_withPoints(edges_sql, points_sql, from_vids, to_vids [, directed] [, driving_side] [, details])
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
Ejemplo

Desde el punto \(1\) y el vértice \(2\) al punto \(3\) y al vértice \(7\)

SELECT * FROM pgr_withPoints(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    'SELECT pid, edge_id, fraction, side from pointsOfInterest',
    ARRAY[-1,2], ARRAY[-3,7]);
 seq | path_seq | start_pid | end_pid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |        -1 |      -3 |   -1 |    1 |  0.6 |        0
   2 |        2 |        -1 |      -3 |    2 |    4 |    1 |      0.6
   3 |        3 |        -1 |      -3 |    5 |   10 |    1 |      1.6
   4 |        4 |        -1 |      -3 |   10 |   12 |  0.6 |      2.6
   5 |        5 |        -1 |      -3 |   -3 |   -1 |    0 |      3.2
   6 |        1 |        -1 |       7 |   -1 |    1 |  0.6 |        0
   7 |        2 |        -1 |       7 |    2 |    4 |    1 |      0.6
   8 |        3 |        -1 |       7 |    5 |    7 |    1 |      1.6
   9 |        4 |        -1 |       7 |    8 |    6 |    1 |      2.6
  10 |        5 |        -1 |       7 |    7 |   -1 |    0 |      3.6
  11 |        1 |         2 |      -3 |    2 |    4 |    1 |        0
  12 |        2 |         2 |      -3 |    5 |   10 |    1 |        1
  13 |        3 |         2 |      -3 |   10 |   12 |  0.6 |        2
  14 |        4 |         2 |      -3 |   -3 |   -1 |    0 |      2.6
  15 |        1 |         2 |       7 |    2 |    4 |    1 |        0
  16 |        2 |         2 |       7 |    5 |    7 |    1 |        1
  17 |        3 |         2 |       7 |    8 |    6 |    1 |        2
  18 |        4 |         2 |       7 |    7 |   -1 |    0 |        3
(18 rows)

Combinaciones SQL

pgr_withPoints(Edges SQL, Points SQL, Combinations SQL [, directed] [, driving_side] [, details])
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
Ejemplo

Dos combinaciones (origen, destino): (desde el punto \(1\) hasta el vértice \(3\)), y (desde el vértice \(2\) hasta el punto \(3\)) con la topología de conducción del lado derecho.

SELECT * FROM pgr_withPoints(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    'SELECT pid, edge_id, fraction, side from pointsOfInterest',
    'SELECT * FROM ( VALUES (-1, 3), (2, -3) ) AS t(source, target)',
    driving_side => 'r',
    details => true);
 seq | path_seq | start_pid | end_pid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |        -1 |       3 |   -1 |    1 |  0.4 |        0
   2 |        2 |        -1 |       3 |    1 |    1 |    1 |      0.4
   3 |        3 |        -1 |       3 |    2 |    4 |  0.7 |      1.4
   4 |        4 |        -1 |       3 |   -6 |    4 |  0.3 |      2.1
   5 |        5 |        -1 |       3 |    5 |    8 |    1 |      2.4
   6 |        6 |        -1 |       3 |    6 |    9 |    1 |      3.4
   7 |        7 |        -1 |       3 |    9 |   16 |    1 |      4.4
   8 |        8 |        -1 |       3 |    4 |    3 |    1 |      5.4
   9 |        9 |        -1 |       3 |    3 |   -1 |    0 |      6.4
  10 |        1 |         2 |      -3 |    2 |    4 |  0.7 |        0
  11 |        2 |         2 |      -3 |   -6 |    4 |  0.3 |      0.7
  12 |        3 |         2 |      -3 |    5 |   10 |    1 |        1
  13 |        4 |         2 |      -3 |   10 |   12 |  0.6 |        2
  14 |        5 |         2 |      -3 |   -3 |   -1 |    0 |      2.6
(14 rows)

Parámetros

Parámetro

Tipo

Descripción

Edges SQL

TEXT

Consulta de bordes como se describió anteriormente.

Puntos SQL

TEXT

Consulta de puntos como se ha descrito anteriormente.

Combinaciones SQL

TEXT

Consulta de combinaciones como se describe a continuación.

start_vid

ANY-INTEGER

Identificador de vértice inicial. Cuando es negativo: es el pid de un punto.

end_vid

ANY-INTEGER

Identificador de vértice final. Cuando es negativo: es el pid de un punto.

start_vids

ARRAY[ANY-INTEGER]

Arreglo de identificadores de vértices iniciales. Cuando es negativo: es el pid de un punto.

end_vids

ARRAY[ANY-INTEGER]

Arreglo de identificadores de vértices finales. Cuando es negativo: es el pid de un punto.

dirigido

BOOLEAN

(opcional). En caso de false el grafo se considera como No Dirigido. El valor predeterminado es true que considera el grafo como Dirigido.

driving_side

CHAR
(opcional) Valor en [“b”, “r”, “l”, NULL] que indica si el lado de conducción es:

  • A la derecha o a la izquierda o

  • Si no importa con “b” o NULL.

  • Si la columna no presente “b” es considerada

detalles

BOOLEAN

(opcional). Cuando es true los resultados incluirán los puntos en points_sql que están en la ruta de acceso. El valor predeterminado es``false`` que omite otros puntos de points_sql.

Consulta interna

Consulta de aristas

Columna

Tipo

Valores predeterminados

Descripción

id

ANY-INTEGER

Identificador de la arista.

origen

ANY-INTEGER

Identificador del primer punto final en el vértice de la arista.

objetivo

ANY-INTEGER

Identificador del segundo punto final en el vértice de la arista.

cost

ANY-NUMERICAL

Peso de la arista (source, target)

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

reverse_cost

ANY-NUMERICAL

-1

Peso de la arista (target, source),

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

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Consulta de puntos

Descripción de la consulta SSQL de Puntos

points_sql

Una consulta SQL, que debe regresar un conjunto de filas con las siguientes columnas:

Columna

Tipo

Descripción

pid

ANY-INTEGER

(opcional) Identificador del punto.

  • Si la columna está presente, no puede ser NULL.

  • Si la columna no está presente, se proporcionará automáticamente un identificador secuencial.

edge_id

ANY-INTEGER

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

fraction

ANY-NUMERICAL

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

side

CHAR

(opcional) Valor en [“b”, “r”, “l”, NULL] que indica si el punto es:

  • A la derecha, a la izquierda del borde o

  • Si no importa con “b” o NULL.

  • Si la columna no presente “b” es considerada

Donde:

ANY-INTEGER

smallint, int, bigint

ANY-NUMERICAL

smallint, int, bigint, real, float

Consulta de combinaciones

Columna

Tipo

Valores predeterminados

Descripción

origen

ANY-INTEGER

Identificador del primer punto final en el vértice de la arista.

objetivo

ANY-INTEGER

Identificador del segundo punto final en el vértice de la arista.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

Columnas de Resultados

Columna

Tipo

Descripción

seq

INTEGER

Secuencia de filas.

path_seq

INTEGER

Secuencia de ruta de acceso que indica la posición relativa en la ruta de acceso.

start_vid

BIGINT

Identificador del vértice inicial. Cuando es negativo: es el pid de un punto.

end_vid

BIGINT

Identificador del vértice final. Cuando es negativo: es el pid de un punto.

node

BIGINT
Identificador del nodo:

  • Un valor positivo indica que el nodo es un vértice de edges_sql.

  • Un valor negativo indica que el nodo es un punto de points_sql.

edge

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

  • -1 para la última fila de la secuencia de ruta.

cost

FLOAT
Coste para atravesar desde node usando edge para el siguiente node en la secuncia de ruta.

  • 0 para la última fila de la secuencia de ruta.

agg_cost

FLOAT
Coste agregado de start_pid a node.

  • 0 para la primera fila de la secuencia de ruta.

Ejemplos Adicionales

Ejemplo

Qué ruta (si existe) pasa delante del punto \(6\) o vértice \(6\) con la topología de conducción lateral derecha.

SELECT ('(' || start_pid || ' => ' || end_pid ||') at ' || path_seq || 'th step:')::TEXT AS path_at,
        CASE WHEN edge = -1 THEN ' visits'
            ELSE ' passes in front of'
        END as status,
        CASE WHEN node < 0 THEN 'Point'
            ELSE 'Vertex'
        END as is_a,
        abs(node) as id
    FROM pgr_withPoints(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
        'SELECT pid, edge_id, fraction, side from pointsOfInterest',
        ARRAY[1,-1], ARRAY[-2,-3,-6,3,6],
        driving_side := 'r',
        details := true)
    WHERE node IN (-6,6);
         path_at         |       status        |  is_a  | id
-------------------------+---------------------+--------+----
 (-1 => -6) at 4th step: |  visits             | Point  |  6
 (-1 => -3) at 4th step: |  passes in front of | Point  |  6
 (-1 => -2) at 4th step: |  passes in front of | Point  |  6
 (-1 => -2) at 6th step: |  passes in front of | Vertex |  6
 (-1 => 3) at 4th step:  |  passes in front of | Point  |  6
 (-1 => 3) at 6th step:  |  passes in front of | Vertex |  6
 (-1 => 6) at 4th step:  |  passes in front of | Point  |  6
 (-1 => 6) at 6th step:  |  visits             | Vertex |  6
 (1 => -6) at 3th step:  |  visits             | Point  |  6
 (1 => -3) at 3th step:  |  passes in front of | Point  |  6
 (1 => -2) at 3th step:  |  passes in front of | Point  |  6
 (1 => -2) at 5th step:  |  passes in front of | Vertex |  6
 (1 => 3) at 3th step:   |  passes in front of | Point  |  6
 (1 => 3) at 5th step:   |  passes in front of | Vertex |  6
 (1 => 6) at 3th step:   |  passes in front of | Point  |  6
 (1 => 6) at 5th step:   |  visits             | Vertex |  6
(16 rows)
Ejemplo

Qué ruta (si existe) pasa delante del punto \(6\) o vértice \(6\) con la topología de conducción lateral izquierda.

SELECT ('(' || start_pid || ' => ' || end_pid ||') at ' || path_seq || 'th step:')::TEXT AS path_at,
        CASE WHEN edge = -1 THEN ' visits'
            ELSE ' passes in front of'
        END as status,
        CASE WHEN node < 0 THEN 'Point'
            ELSE 'Vertex'
        END as is_a,
        abs(node) as id
    FROM pgr_withPoints(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
        'SELECT pid, edge_id, fraction, side from pointsOfInterest',
        ARRAY[1,-1], ARRAY[-2,-3,-6,3,6],
        driving_side := 'l',
        details := true)
    WHERE node IN (-6,6);
         path_at         |       status        |  is_a  | id
-------------------------+---------------------+--------+----
 (-1 => -6) at 3th step: |  visits             | Point  |  6
 (-1 => -3) at 3th step: |  passes in front of | Point  |  6
 (-1 => -2) at 3th step: |  passes in front of | Point  |  6
 (-1 => -2) at 5th step: |  passes in front of | Vertex |  6
 (-1 => 3) at 3th step:  |  passes in front of | Point  |  6
 (-1 => 3) at 5th step:  |  passes in front of | Vertex |  6
 (-1 => 6) at 3th step:  |  passes in front of | Point  |  6
 (-1 => 6) at 5th step:  |  visits             | Vertex |  6
 (1 => -6) at 4th step:  |  visits             | Point  |  6
 (1 => -3) at 4th step:  |  passes in front of | Point  |  6
 (1 => -2) at 4th step:  |  passes in front of | Point  |  6
 (1 => -2) at 6th step:  |  passes in front of | Vertex |  6
 (1 => 3) at 4th step:   |  passes in front of | Point  |  6
 (1 => 3) at 6th step:   |  passes in front of | Vertex |  6
 (1 => 6) at 4th step:   |  passes in front of | Point  |  6
 (1 => 6) at 6th step:   |  visits             | Vertex |  6
(16 rows)
Ejemplo

Desde el punto \(1\) y el vértice \(2\) al punto \(3\) al vértice \(7\) en un grafo no dirigido con detalles.

SELECT * FROM pgr_withPoints(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    'SELECT pid, edge_id, fraction, side from pointsOfInterest',
    ARRAY[-1,2], ARRAY[-3,7],
    directed := false,
    details := true);
 seq | path_seq | start_pid | end_pid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |        -1 |      -3 |   -1 |    1 |  0.6 |        0
   2 |        2 |        -1 |      -3 |    2 |    4 |  0.7 |      0.6
   3 |        3 |        -1 |      -3 |   -6 |    4 |  0.3 |      1.3
   4 |        4 |        -1 |      -3 |    5 |   10 |    1 |      1.6
   5 |        5 |        -1 |      -3 |   10 |   12 |  0.6 |      2.6
   6 |        6 |        -1 |      -3 |   -3 |   -1 |    0 |      3.2
   7 |        1 |        -1 |       7 |   -1 |    1 |  0.6 |        0
   8 |        2 |        -1 |       7 |    2 |    4 |  0.7 |      0.6
   9 |        3 |        -1 |       7 |   -6 |    4 |  0.3 |      1.3
  10 |        4 |        -1 |       7 |    5 |    7 |    1 |      1.6
  11 |        5 |        -1 |       7 |    8 |    6 |  0.7 |      2.6
  12 |        6 |        -1 |       7 |   -4 |    6 |  0.3 |      3.3
  13 |        7 |        -1 |       7 |    7 |   -1 |    0 |      3.6
  14 |        1 |         2 |      -3 |    2 |    4 |  0.7 |        0
  15 |        2 |         2 |      -3 |   -6 |    4 |  0.3 |      0.7
  16 |        3 |         2 |      -3 |    5 |   10 |    1 |        1
  17 |        4 |         2 |      -3 |   10 |   12 |  0.6 |        2
  18 |        5 |         2 |      -3 |   -3 |   -1 |    0 |      2.6
  19 |        1 |         2 |       7 |    2 |    4 |  0.7 |        0
  20 |        2 |         2 |       7 |   -6 |    4 |  0.3 |      0.7
  21 |        3 |         2 |       7 |    5 |    7 |    1 |        1
  22 |        4 |         2 |       7 |    8 |    6 |  0.7 |        2
  23 |        5 |         2 |       7 |   -4 |    6 |  0.3 |      2.7
  24 |        6 |         2 |       7 |    7 |   -1 |    0 |        3
(24 rows)

Las consultas usan la red Datos Muestra

Ver también

Índices y tablas