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

  • Version 2.2.0

    • Nueva función propuesta

Soporte

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

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

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

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 .