pgr_withPointsCost - Propuesto

pgr_withPointsCost - Calcula la ruta más corta y devuelve solo el costo agregado de la(s) rutas más cortas encontradas, para la combinación de puntos dados.

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

Boost Graph Interno

Disponibilidad

  • Versión 3.2.0

    • Nueva función propuesta:

      • pgr_withPointsCost(Combinaciones)

  • Version 2.2.0

    • Nueva función propuesta

Descripción

Modifica el grafo para incluir puntos definidos por points_sql. Con el algoritmo Dijkstra, devuelva solo el costo agregado de la(s) rutas más cortas encontradas.

Las principales características son:

  • No devuelve una ruta.

  • Devuelve la suma de los costes de la ruta más corta para la combinación de pares de vértices en el grafo modificado.

  • Los vértices del grafo son:

    • positivo cuando pertenece a edges_sql

    • negativo cuando pertenece a points_sql

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

  • Valores son regresados cuando hay un camino.

    • Los valores devueltos tienen la forma de un conjunto de (start_vid, end_vid, agg_cost).

    • Cuando el vértice inicial y el vértice final son iguales, no hay camino.

      • El agg_cost en 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.

      • El agg_cost en los valores no incluidos (u, v) es \(\infty\)

  • Si los valores devueltos se almacenan en una tabla, el índice único sería el par: (start_vid, end_vid).

  • Para los grafos no dirigidos, los resultados son simétricos.

    • El agg_cost de (u, v) es el mismo que para (v, u).

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

  • Los valores regresados se ordenan:

    • start_vid ascendente

    • end_vid ascendente

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

Firmas

Resumen

pgr_withPointsCost(edges_sql, points_sql, from_vid,  to_vid  [, directed] [, driving_side])
pgr_withPointsCost(edges_sql, points_sql, from_vid,  to_vids [, directed] [, driving_side])
pgr_withPointsCost(edges_sql, points_sql, from_vids, to_vid  [, directed] [, driving_side])
pgr_withPointsCost(edges_sql, points_sql, from_vids, to_vids [, directed] [, driving_side])
pgr_withPointsCost(Edges SQL, Points SQL, Combinations SQL  [, directed] [, driving_side] [, details])
RETURNS SET OF (start_vid, end_vid, agg_cost)

Nota

No hay identificador de details, a diferencia de los otros miembros de la familia de funciones withPoints.

Uso de valores predeterminados

pgr_withPointsCost(edges_sql, points_sql, start_vid, end_vid)
RETURNS SET OF (start_vid, end_vid, 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.

SELECT * FROM pgr_withPointsCost(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    'SELECT pid, edge_id, fraction, side from pointsOfInterest',
    -1, -3);
 start_pid | end_pid | agg_cost
-----------+---------+----------
        -1 |      -3 |      3.2
(1 row)

Uno a Uno

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

Desde el punto \(1\) al vértice \(3\) en un grafo no dirigido.

SELECT * FROM pgr_withPointsCost(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    'SELECT pid, edge_id, fraction, side from pointsOfInterest',
    -1, 3,
    directed := false);
 start_pid | end_pid | agg_cost
-----------+---------+----------
        -1 |       3 |      1.6
(1 row)

Uno a Muchos

pgr_withPointsCost(edges_sql, points_sql, from_vid,  to_vids [, directed] [, driving_side])
RETURNS SET OF (start_vid, end_vid, agg_cost)
Ejemplo

Desde el punto \(1\) al punto \(3\) y al vértice \(5\) en un grafo dirigido.

SELECT * FROM pgr_withPointsCost(
    '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]);
 start_pid | end_pid | agg_cost
-----------+---------+----------
        -1 |      -3 |      3.2
        -1 |       5 |      1.6
(2 rows)

Muchos a Uno

pgr_withPointsCost(edges_sql, points_sql, from_vids, to_vid  [, directed] [, driving_side])
RETURNS SET OF (start_vid, end_vid, agg_cost)
Ejemplo

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

SELECT * FROM pgr_withPointsCost(
    '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);
 start_pid | end_pid | agg_cost
-----------+---------+----------
        -1 |      -3 |      3.2
         2 |      -3 |      2.6
(2 rows)

Muchos a Muchos

pgr_withPointsCost(edges_sql, points_sql, from_vids, to_vids [, directed] [, driving_side])
RETURNS SET OF (start_vid, end_vid, agg_cost)
Ejemplo

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

SELECT * FROM pgr_withPointsCost(
    '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]);
 start_pid | end_pid | agg_cost
-----------+---------+----------
        -1 |      -3 |      3.2
        -1 |       7 |      3.6
         2 |      -3 |      2.6
         2 |       7 |        3
(4 rows)

Combinaciones SQL

pgr_withPointsCost(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_withPointsCost(
    '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');
 start_pid | end_pid | agg_cost
-----------+---------+----------
        -1 |       3 |      6.4
         2 |      -3 |      2.6
(2 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

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

start_vid

BIGINT

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

end_vid

BIGINT

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

agg_cost

FLOAT

Coste agregado de start_vid a end_vid.

Ejemplos Adicionales

Ejemplo

Desde el punto \(1\) y el vértice \(2\) al punto \(3\) y al vértice \(7\), con topología de conducción de lado derecho

SELECT * FROM pgr_withPointsCost(
    '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],
    driving_side := 'l');
 start_pid | end_pid | agg_cost
-----------+---------+----------
        -1 |      -3 |      3.2
        -1 |       7 |      3.6
         2 |      -3 |      2.6
         2 |       7 |        3
(4 rows)
Ejemplo

Desde el punto \(1\) y el vértice \(2\) al punto \(3\) y al vértice \(7\), con topología de conducción de lado izquierdo.

SELECT * FROM pgr_withPointsCost(
    '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],
    driving_side := 'r');
 start_pid | end_pid | agg_cost
-----------+---------+----------
        -1 |      -3 |        4
        -1 |       7 |      4.4
         2 |      -3 |      2.6
         2 |       7 |        3
(4 rows)
Ejemplo

Desde el punto \(1\) y el vértice \(2\) al punto \(3\) y al vértice \(7\), sin importar el lado de conducción.

SELECT * FROM pgr_withPointsCost(
    '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],
    driving_side := 'b');
 start_pid | end_pid | agg_cost
-----------+---------+----------
        -1 |      -3 |      3.2
        -1 |       7 |      3.6
         2 |      -3 |      2.6
         2 |       7 |        3
(4 rows)

Las consultas utilizan la red Datos Muestra .

Ver también

Índices y tablas