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

  • 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])
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)

Parámetros

Parámetro Tipo Descripción
edges_sql TEXT Consulta de aristas SQL como se describió anteriormente.
points_sql TEXT Consulta SQL de puntos como se describe arriba.
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

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

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

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