pgr_bdAstarCost¶

pgr_bdAstarCost - Devuelve el costo agregado de la ruta más corta usando el algoritmo bidireccional A*.

_images/boost-inside.jpeg — Adentro: Boost Graph¶

Disponibilidad

Versión 3.2.0
- Nueva firma propuesta:
  - pgr_bdAstarCost (Combinaciones)
Versión 3.0.0
- Función oficial
Versión 2.4.0
- Nueva función propuesta

Descripción¶

La función pgr_bdAstarCost Sumariza el costo del camino más corto utilizando el algoritmo bidireccional A*.

Las principales características son:

Funciona para grafos dirigidos y no dirigidos.
Ordenamiento es:
- primero por start_vid (si existe)
- luego por end_vid
Los valores se devuelven cuando hay una ruta.
Sean \(v\) y \(u\) nodos en el grafo:
- Si no hay camino de \(v\) a \(u\):
  - no se devuelve ninguna fila correspondiente
  - agg_cost de \(v\) a \(u\) es \(\infty\)
- No hay camino cuando \(v = u\) por lo tanto
  - no se devuelve ninguna fila correspondiente
  - agg_cost de v a u es \(0\)
Cuando las coordenadas (x,y) para el mismo identificador de vértice difieren:
- Se utiliza una selección aleatoria de las coordenadas del vértice \((x,y)\).
Tiempo de ejecución: \(O((E + V) * \log V)\)

No devuelve una ruta.
Devuelve la suma de los costos de la ruta más corta para cada par de combinación de nodos requeridos.
Sea el caso de que los resultados se almacenen en una tabla, el índice unico lo conformarían el par (start_vid, end_vid)
Para grafos no dirigidos, los resultados son simétricos.
- El agg_cost de (u, v) es el mismo que para (v, u).
Loas valores regresandos son ordenados en orden ascendente:
- start_vid ascendente
- end_vid ascendente

Firmas¶

Resumen

pgr_bdAstarCost(SQL de aristas, salida, destino, [opciones])
pgr_bdAstarCost(SQL de aristas, salida, destinos, [opciones])
pgr_bdAstarCost(SQL de aristas, salidas, destino, [opciones])
pgr_bdAstarCost(SQL de aristas, salidas, destinos, [opciones])
pgr_bdAstarCost(SQL de aristas, SQL de combinaciones, [opciones])
options: [directed, heuristic, factor, epsilon]

Regresa conjunto de (start_vid, end_vid, agg_cost)

OR EMPTY SET

Uno a Uno¶

pgr_bdAstarCost(SQL de aristas, salida, destino, [opciones])

options: [directed, heuristic, factor, epsilon]

Regresa conjunto de (start_vid, end_vid, agg_cost)

OR EMPTY SET

Ejemplo:: De vértice \(6\) a vértice \(12\) en un grafo dirigido usando la heurística \(2\)

SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  6, 12,
  directed => true, heuristic => 2
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |      12 |        3
(1 row)

Uno a Muchos¶

pgr_bdAstarCost(SQL de aristas, salida, destinos, [opciones])

options: [directed, heuristic, factor, epsilon]

Regresa conjunto de (start_vid, end_vid, agg_cost)

OR EMPTY SET

Ejemplo:: Desde el vértice \(6\) a los vértices \(\{12, 10\}\) en un grafo dirigido usando la heurística \(3\) con factor \(3.5\)

SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  6, ARRAY[10, 12],
  heuristic => 3, factor := 3.5
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |      10 |        5
         6 |      12 |        3
(2 rows)

Muchos a Uno¶

pgr_bdAstarCost(SQL de aristas, salidas, destino, [opciones])

options: [directed, heuristic, factor, epsilon]

Regresa conjunto de (start_vid, end_vid, agg_cost)

OR EMPTY SET

Ejemplo:: De los vértices \(\{6, 8\}\) al vértice \(10\) en un grafo no dirigido usando la heurística \(4\)

SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[6, 8], 10,
  false, heuristic => 4
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |      10 |        1
         8 |      10 |        3
(2 rows)

Muchos a Muchos¶

pgr_bdAstarCost(SQL de aristas, salidas, destinos, [opciones])

options: [directed, heuristic, factor, epsilon]

Regresa conjunto de (start_vid, end_vid, agg_cost)

OR EMPTY SET

Ejemplo:: De los vértices \(\{6, 8\}\) a los vértices \(\{10, 12\}\) en un gráfico dirigido con factor \(0.5\)

SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[6, 8], ARRAY[10, 12],
  factor => 0.5
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |      10 |        5
         6 |      12 |        3
         8 |      10 |        5
         8 |      12 |        1
(4 rows)

Combinaciones¶

pgr_bdAstarCost(SQL de aristas, SQL de combinaciones, [opciones])

options: [directed, heuristic, factor, epsilon]

Regresa conjunto de (start_vid, end_vid, agg_cost)

OR EMPTY SET

Ejemplo:: Usando una tabla de combinaciones en un grafo dirigido con factor \(0.5\).

La tabla de combinaciones:

SELECT * FROM combinations;
 source | target
--------+--------
      5 |      6
      5 |     10
      6 |      5
      6 |     15
      6 |     14
(5 rows)

La consulta:

SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  'SELECT * FROM combinations',
  factor => 0.5
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         5 |       6 |        1
         5 |      10 |        6
         6 |       5 |        1
         6 |      15 |        4
(4 rows)

Parámetros¶

Columna	Tipo	Descripción
SQL de aristas	`TEXT`	SQL de aristas como se describe a continuación
SQL de combinaciones	`TEXT`	SQL de combinaciones como se describe a abajo
salida	`BIGINT`	Identificador del vértice inicial de la ruta.
salidas	`ARRAY[BIGINT]`	Arreglo de identificadores de vértices iniciales.
destino	`BIGINT`	Identificador del vértice final de la ruta.
destinos	`ARRAY[BIGINT]`	Arreglo de identificadores de vértices finales.

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.

Parámetros opcionales de aStar¶

Parámetro	Tipo	x Defecto	Descripción
`heuristic`	`INTEGER`	5	Número heurístico. Valores válidos 0~5. 0: \(h(v) = 0\) (Utilizar este valor para comparar con pgr_dijkstra) 1: \(h(v) = abs(max(\Delta x, \Delta y))\) 2: \(h(v) = abs(min(\Delta x, \Delta y))\) 3: \(h(v) = \Delta x * \Delta x + \Delta y * \Delta y\) 4: \(h(v) = sqrt(\Delta x * \Delta x + \Delta y * \Delta y)\) 5: \(h(v) = abs(\Delta x) + abs(\Delta y)\)
`factor`	`FLOAT`	`1`	Para la manipulación de unidades. math:factor > 0.
`epsilon`	`FLOAT`	`1`	Para resultados menos restringidos. \(epsilon >= 1\).

Parámetro

Tipo

x Defecto

Descripción

heuristic

INTEGER

Número heurístico. Valores válidos 0~5.

0: \(h(v) = 0\) (Utilizar este valor para comparar con pgr_dijkstra)
1: \(h(v) = abs(max(\Delta x, \Delta y))\)
2: \(h(v) = abs(min(\Delta x, \Delta y))\)
3: \(h(v) = \Delta x * \Delta x + \Delta y * \Delta y\)
4: \(h(v) = sqrt(\Delta x * \Delta x + \Delta y * \Delta y)\)
5: \(h(v) = abs(\Delta x) + abs(\Delta y)\)

factor

FLOAT

1

Para la manipulación de unidades. math:factor > 0.

epsilon

FLOAT

1

Para resultados menos restringidos. \(epsilon >= 1\).

Ver heuristicas disponibles y manupulación de factor.

Consultas Internas¶

SQL aristas¶

Parámetro	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`) Cuando es negativo: la arista (`source`, `target`) no existe, por lo tanto no es parte del grafo.
`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.
`x1`	FLOTANTES		Coordenada X del vértice `source`.
`y1`	FLOTANTES		Coordenada Y del vértice `source`.
`x2`	FLOTANTES		Coordenada X del vértice `target`.
`y2`	FLOTANTES		Coordenada Y del vértice `target`.

Donde:

ENTEROS:: SMALLINT, INTEGER, BIGINT
FLOTANTES:: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

SQL Combinaciones¶

Parámetro	Tipo	Descripción
`source`	ENTEROS	Identificador del vértice de salida.
`target`	ENTEROS	Identificador del vértice de llegada.

Donde:

ENTEROS:: SMALLINT, INTEGER, BIGINT

Columnas de Resultados¶

Conjunto de (start_vid, end_vid, agg_cost)

Columna	Tipo	Descripción
`start_vid`	`BIGINT`	Identificador del vértice de salida.
`end_vid`	`BIGINT`	Identificador del vértice destino.
`agg_cost`	`FLOAT`	Costo afregado desde `start_vid` hasta `end_vid`.

Ejemplos Adicionales¶

Ejemplo 1:: Demostración de ignorar los valores repertidos, y resultado ordenado.

 SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[7, 10, 15, 10, 10, 15], ARRAY[10, 7, 10, 15]);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         7 |      10 |        4
         7 |      15 |        3
        10 |       7 |        2
        10 |      15 |        3
        15 |       7 |        3
        15 |      10 |        1
(6 rows)

Ejemplo 2:: Haciendo vids iniciales los mismos que vids destinos.

SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[7, 10, 15], ARRAY[7, 10, 15]);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         7 |      10 |        4
         7 |      15 |        3
        10 |       7 |        2
        10 |      15 |        3
        15 |       7 |        3
        15 |      10 |        1
(6 rows)

Ejemplo 3:: Manualmente asignar combinaciones de vértices.

SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)');
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |       7 |        1
         6 |      10 |        5
        12 |      10 |        4
(3 rows)

Ver también¶

Índices y tablas