`pgr_bdAstar`¶

pgr_bdAstar — Devuelve la ruta más corta usando el algoritmo Bidireccional A*.

Disponibilidad

Versión 4.0.0

Firmas de combinaciones promovidas a oficial.

Versión 3.6.0

Standardizing output columns to (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- pgr_bdAstar(Uno a Uno) ha añadido las columnas start_vid y end_vid.
- pgr_bdAstar(Uno a Muchos) ha añadido la columna end_vid.
- pgr_bdAstar(Muchos a Uno) ha añadido la columna start_vid.

Versión 3.2.0

Nuevas firmas propuesta:
- pgr_bdAstar(Combinaciones)

Versión 3.0.0

Función promovida a oficial.

Versión 2.5.0

Nuevas firmas propuestas:
- pgr_bdAstar(Uno a Muchos)
- pgr_bdAstar(Muchos a Uno)
- pgr_bdAstar(Muchos a Muchos)
Cambio de firma en pgr_bdAstar(Uno a Uno)
- Firma antigua ya no soportada

Versión 2.0.0

Nueva función oficial.

Descripción¶

Las principales características son:

El proceso 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)\)

Los resultados son equivalentes a la unión de los resultados de pgr_bdAStar(Uno a Uno) en:
- pgr_bdAstar(Uno a Muchos)
- pgr_bdAstar(Muchos a Uno)
- pgr_bdAstar(Muchos a Muchos)
- pgr_bdAstar(Combinaciones)

Adentro: Boost Graph

Firmas¶

Resumen

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

Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

O CONJUNTO VACÍO

Los parámetros opcionales son parámetros con nombre y tienen un valor predeterminado.

Uno a Uno¶

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

opcionales: [directed, heuristic, factor, epsilon]

Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

O CONJUNTO VACÍO

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

SELECT * FROM pgr_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  6, 12,
  directed => true, heuristic => 2
);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         6 |      12 |    6 |    4 |    1 |        0
   2 |        2 |         6 |      12 |    7 |   10 |    1 |        1
   3 |        3 |         6 |      12 |    8 |   12 |    1 |        2
   4 |        4 |         6 |      12 |   12 |   -1 |    0 |        3
(4 rows)

Uno a Muchos¶

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

opcionales: [directed, heuristic, factor, epsilon]

Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

O CONJUNTO VACÍO

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_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  6, ARRAY[10, 12],
  heuristic => 3, factor := 3.5
);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         6 |      10 |    6 |    4 |    1 |        0
   2 |        2 |         6 |      10 |    7 |    8 |    1 |        1
   3 |        3 |         6 |      10 |   11 |    9 |    1 |        2
   4 |        4 |         6 |      10 |   16 |   16 |    1 |        3
   5 |        5 |         6 |      10 |   15 |    3 |    1 |        4
   6 |        6 |         6 |      10 |   10 |   -1 |    0 |        5
   7 |        1 |         6 |      12 |    6 |    4 |    1 |        0
   8 |        2 |         6 |      12 |    7 |    8 |    1 |        1
   9 |        3 |         6 |      12 |   11 |   11 |    1 |        2
  10 |        4 |         6 |      12 |   12 |   -1 |    0 |        3
(10 rows)

Muchos a Uno¶

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

opcionales: [directed, heuristic, factor, epsilon]

Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

O CONJUNTO VACÍO

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

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

Muchos a Muchos¶

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

opcionales: [directed, heuristic, factor, epsilon]

Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

O CONJUNTO VACÍO

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_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[6, 8], ARRAY[10, 12],
  factor => 0.5
);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         6 |      10 |    6 |    4 |    1 |        0
   2 |        2 |         6 |      10 |    7 |    8 |    1 |        1
   3 |        3 |         6 |      10 |   11 |    9 |    1 |        2
   4 |        4 |         6 |      10 |   16 |   16 |    1 |        3
   5 |        5 |         6 |      10 |   15 |    3 |    1 |        4
   6 |        6 |         6 |      10 |   10 |   -1 |    0 |        5
   7 |        1 |         6 |      12 |    6 |    4 |    1 |        0
   8 |        2 |         6 |      12 |    7 |    8 |    1 |        1
   9 |        3 |         6 |      12 |   11 |   11 |    1 |        2
  10 |        4 |         6 |      12 |   12 |   -1 |    0 |        3
  11 |        1 |         8 |      10 |    8 |   10 |    1 |        0
  12 |        2 |         8 |      10 |    7 |    8 |    1 |        1
  13 |        3 |         8 |      10 |   11 |    9 |    1 |        2
  14 |        4 |         8 |      10 |   16 |   16 |    1 |        3
  15 |        5 |         8 |      10 |   15 |    3 |    1 |        4
  16 |        6 |         8 |      10 |   10 |   -1 |    0 |        5
  17 |        1 |         8 |      12 |    8 |   12 |    1 |        0
  18 |        2 |         8 |      12 |   12 |   -1 |    0 |        1
(18 rows)

Combinaciones¶

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

opcionales: [directed, heuristic, factor, epsilon]

Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

O CONJUNTO VACÍO

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_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  'SELECT * FROM combinations',
  factor => 0.5
);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         5 |       6 |    5 |    1 |    1 |        0
   2 |        2 |         5 |       6 |    6 |   -1 |    0 |        1
   3 |        1 |         5 |      10 |    5 |    1 |    1 |        0
   4 |        2 |         5 |      10 |    6 |    4 |    1 |        1
   5 |        3 |         5 |      10 |    7 |    8 |    1 |        2
   6 |        4 |         5 |      10 |   11 |    9 |    1 |        3
   7 |        5 |         5 |      10 |   16 |   16 |    1 |        4
   8 |        6 |         5 |      10 |   15 |    3 |    1 |        5
   9 |        7 |         5 |      10 |   10 |   -1 |    0 |        6
  10 |        1 |         6 |       5 |    6 |    1 |    1 |        0
  11 |        2 |         6 |       5 |    5 |   -1 |    0 |        1
  12 |        1 |         6 |      15 |    6 |    4 |    1 |        0
  13 |        2 |         6 |      15 |    7 |    8 |    1 |        1
  14 |        3 |         6 |      15 |   11 |    9 |    1 |        2
  15 |        4 |         6 |      15 |   16 |   16 |    1 |        3
  16 |        5 |         6 |      15 |   15 |   -1 |    0 |        4
(16 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\).

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 partida.
`target`	ENTEROS	Identificador del vértice de llegada.

Donde:

ENTEROS:: SMALLINT, INTEGER, BIGINT

Columnas de resultados¶

Returns (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

Columna	Tipo	Descripción
`seq`	`INTEGER`	Valor secuencial a partir de 1.
`path_seq`	`INTEGER`	Posición relativa en la ruta. Tiene el valor 1 para el inicio de una ruta.
`start_vid`	`BIGINT`	Identificador del vértice inicial de la ruta actual.
`end_vid`	`BIGINT`	Identificador del vértice final de la ruta actual.
`node`	`BIGINT`	Identificador del nodo en la ruta de `start_vid` a `end_vid`.
`edge`	`BIGINT`	Identificador de la arista utilizado para ir del `node` al siguiente nodo de la secuencia de ruta. `-1` para el último nodo de la ruta.
`cost`	`FLOAT`	Costo para atravesar desde `node` usando `edge` hasta el siguiente nodo en la secuencia de la ruta.
`agg_cost`	`FLOAT`	Costo agregado desde `start_vid` hasta `node`.

Ejemplos Adicionales¶

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

 SELECT * FROM pgr_bdAstar(
  '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]);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
|        1 |         7 |      10 |    7 |    8 |    1 |        0
|        2 |         7 |      10 |   11 |    9 |    1 |        1
|        3 |         7 |      10 |   16 |   16 |    1 |        2
|        4 |         7 |      10 |   15 |    3 |    1 |        3
|        5 |         7 |      10 |   10 |   -1 |    0 |        4
|        1 |         7 |      15 |    7 |    8 |    1 |        0
|        2 |         7 |      15 |   11 |    9 |    1 |        1
|        3 |         7 |      15 |   16 |   16 |    1 |        2
|        4 |         7 |      15 |   15 |   -1 |    0 |        3
|        1 |        10 |       7 |   10 |    5 |    1 |        0
|        2 |        10 |       7 |   11 |    8 |    1 |        1
|        3 |        10 |       7 |    7 |   -1 |    0 |        2
|        1 |        10 |      15 |   10 |    5 |    1 |        0
|        2 |        10 |      15 |   11 |    9 |    1 |        1
|        3 |        10 |      15 |   16 |   16 |    1 |        2
|        4 |        10 |      15 |   15 |   -1 |    0 |        3
|        1 |        15 |       7 |   15 |    3 |    1 |        0
|        2 |        15 |       7 |   10 |    5 |    1 |        1
|        3 |        15 |       7 |   11 |    8 |    1 |        2
|        4 |        15 |       7 |    7 |   -1 |    0 |        3
|        1 |        15 |      10 |   15 |    3 |    1 |        0
|        2 |        15 |      10 |   10 |   -1 |    0 |        1
(22 rows)

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

SELECT * FROM pgr_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[7, 10, 15], ARRAY[7, 10, 15]);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
|        1 |         7 |      10 |    7 |    8 |    1 |        0
|        2 |         7 |      10 |   11 |    9 |    1 |        1
|        3 |         7 |      10 |   16 |   16 |    1 |        2
|        4 |         7 |      10 |   15 |    3 |    1 |        3
|        5 |         7 |      10 |   10 |   -1 |    0 |        4
|        1 |         7 |      15 |    7 |    8 |    1 |        0
|        2 |         7 |      15 |   11 |    9 |    1 |        1
|        3 |         7 |      15 |   16 |   16 |    1 |        2
|        4 |         7 |      15 |   15 |   -1 |    0 |        3
|        1 |        10 |       7 |   10 |    5 |    1 |        0
|        2 |        10 |       7 |   11 |    8 |    1 |        1
|        3 |        10 |       7 |    7 |   -1 |    0 |        2
|        1 |        10 |      15 |   10 |    5 |    1 |        0
|        2 |        10 |      15 |   11 |    9 |    1 |        1
|        3 |        10 |      15 |   16 |   16 |    1 |        2
|        4 |        10 |      15 |   15 |   -1 |    0 |        3
|        1 |        15 |       7 |   15 |    3 |    1 |        0
|        2 |        15 |       7 |   10 |    5 |    1 |        1
|        3 |        15 |       7 |   11 |    8 |    1 |        2
|        4 |        15 |       7 |    7 |   -1 |    0 |        3
|        1 |        15 |      10 |   15 |    3 |    1 |        0
|        2 |        15 |      10 |   10 |   -1 |    0 |        1
(22 rows)

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

SELECT * FROM pgr_bdAstar(
  '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)');
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         6 |       7 |    6 |    4 |    1 |        0
   2 |        2 |         6 |       7 |    7 |   -1 |    0 |        1
   3 |        1 |         6 |      10 |    6 |    4 |    1 |        0
   4 |        2 |         6 |      10 |    7 |    8 |    1 |        1
   5 |        3 |         6 |      10 |   11 |    9 |    1 |        2
   6 |        4 |         6 |      10 |   16 |   16 |    1 |        3
   7 |        5 |         6 |      10 |   15 |    3 |    1 |        4
   8 |        6 |         6 |      10 |   10 |   -1 |    0 |        5
   9 |        1 |        12 |      10 |   12 |   13 |    1 |        0
  10 |        2 |        12 |      10 |   17 |   15 |    1 |        1
  11 |        3 |        12 |      10 |   16 |   16 |    1 |        2
  12 |        4 |        12 |      10 |   15 |    3 |    1 |        3
  13 |        5 |        12 |      10 |   10 |   -1 |    0 |        4
(13 rows)

Ver también¶

Índices y tablas

pgr_bdAstar¶

Descripción¶

Firmas¶

Uno a Uno¶

Uno a Muchos¶

Muchos a Uno¶

Muchos a Muchos¶

Combinaciones¶

Parámetros¶

Parámetros opcionales¶

Parámetros opcionales de aStar¶

Consultas Internas¶

SQL aristas¶

SQL Combinaciones¶

Columnas de resultados¶

Ejemplos Adicionales¶

Ver también¶

`pgr_bdAstar`¶