pgr_binaryBreadthFirstSearch - Experimental

pgr_binaryBreadthFirstSearch — Devuelve la(s) rutas más cortas en un grafo binario. Cualquier gráfico cuyos pesos de borde pertenecen al conjunto {0, X}, donde “X” es cualquier número entero real no negativo, se denomina como “grafo binario”.

Adentro: Boost Graph

Advertencia

Posible bloqueo del servidor

• Estas funciones pueden crear un bloqueo del servidor

Advertencia

Funciones experimentales

• No son oficialmente de la versión actual.

• Es probable que oficialmente no formen parte de la siguiente versión:

  • Las funciones no podrían hacer uso de ANY-INTEGER ni ANY-NUMERICAL

  • El nombre puede cambiar.

  • La firma o declaración de funciones podría cambiar.

  • La funcionalidad puede cambiar.

  • Las pruebas de pgTap pueden estar ausentes.

  • Posiblemente necesite codificación c/c++.

  • Puede haber carencia de documentación.

  • Hay documentación que, en dado caso, podría ser necesario reescribir.

  • Ejemplos de documentación que puede ser necesario generar automáticamente.

  • Puede ser necesaria más retroalimentación por parte de la comunidad.

  • Puede depender de una función propuesta de pgRouting.

  • Podría depender de una función obsoleta de pgRouting

Disponibilidad

• Versión 3.2.0

  • Nueva función experimental:

    • pgr_binaryBreadthFirstSearch(Combinaciones)

• Versión 3.0.0

  • Nueva función experimental

Descripción

Es bien sabido que las rutas más cortas entre una sola fuente y todos los demás vértices se pueden encontrar usando Breadth First Search en \(O(|E|)\) en un grafo no ponderado, es decir, la distancia es el número mínimo de aristas que necesita atravesar desde el origen a otro vértice. Podemos interpretar tal grafo también como un grafo ponderado, donde cada arista tiene el peso 1. Si no todas las aristas del grafo tienen el mismo peso, que necesitamos un algoritmo más general, como el Algoritmo de Dijkstra que se ejecuta en \(O(|E|log|V|)\) tiempo.

Sin embargo, si los pesos están más restringidos, podemos usar un algoritmo más rápido. Este algoritmo, llamado “Binary Breadth First Search” así como “0-1 BFS”, es una variación del problema estándar de Breadth First Search para resolver el problema SSSP (ruta más corta de una sola fuente) en \(O(|E|)\), si los pesos de cada arista pertenecen al conjunto de caracteres de {0,X}, donde “X” es cualquier entero real no negativo.

Las características principales son:

• El proceso se realiza sólo en “grafos binarios”. (“Grafo binario”: Cualquier grafo cuyos pesos de aristas pertenezcan al conjunto {0, X}, donde “X” es cualquier entero real no negativo).

• 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 | * |E|)\)

Firmas

pgr_binaryBreadthFirstSearch(Edges SQL, start_vid,  end_vid  [, directed])
pgr_binaryBreadthFirstSearch(Edges SQL, start_vid,  end_vids [, directed])
pgr_binaryBreadthFirstSearch(Edges SQL, start_vids, end_vid  [, directed])
pgr_binaryBreadthFirstSearch(Edges SQL, start_vids, end_vids [, directed])
pgr_binaryBreadthFirstSearch(Edges SQL, Combinations SQL [, directed]) -- Proposed on v3.2
RETURNS SET OF (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
OR EMPTY SET

pgr_binaryBreadthFirstSearch(Edges SQL, start_vid, end_vid)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost) or EMPTY SET

Ejemplo

Del vértice \(2\) al vértice \(3\) en un grafo binario dirigido

SELECT * FROM pgr_binaryBreadthFirstSearch(
    'SELECT id, source, target, road_work as cost, reverse_road_work as reverse_cost FROM roadworks',
    2, 3
);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |    2 |    4 |    0 |        0
   2 |        2 |    5 |    8 |    1 |        0
   3 |        3 |    6 |    9 |    1 |        1
   4 |        4 |    9 |   16 |    0 |        2
   5 |        5 |    4 |    3 |    0 |        2
   6 |        6 |    3 |   -1 |    0 |        2
(6 rows)

Uno a Uno

pgr_binaryBreadthFirstSearch(Edges SQL, start_vid, end_vid [, directed]);
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo

Del vértice \(2\) al vértice \(3\) en un grafo binario no dirigido

SELECT * FROM pgr_binaryBreadthFirstSearch(
    'SELECT id, source, target, road_work as cost, reverse_road_work as reverse_cost FROM roadworks',
    2, 3,
    FALSE
);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |    2 |    2 |    1 |        0
   2 |        2 |    3 |   -1 |    0 |        1
(2 rows)

Uno a muchos

pgr_binaryBreadthFirstSearch(Edges SQL, start_vid, end_vids [, directed]);
RETURNS SET OF (seq, path_seq, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo

Del vértice \(2\) a los vértices \(\{3, 5\}\) en un grafo binario no dirigido

SELECT * FROM pgr_binaryBreadthFirstSearch(
    'SELECT id, source, target, road_work as cost FROM roadworks',
    2, ARRAY[3,5],
    FALSE
);
 seq | path_seq | end_vid | node | edge | cost | agg_cost
-----+----------+---------+------+------+------+----------
   1 |        1 |       3 |    2 |    4 |    0 |        0
   2 |        2 |       3 |    5 |    8 |    1 |        0
   3 |        3 |       3 |    6 |    5 |    1 |        1
   4 |        4 |       3 |    3 |   -1 |    0 |        2
   5 |        1 |       5 |    2 |    4 |    0 |        0
   6 |        2 |       5 |    5 |   -1 |    0 |        0
(6 rows)

Muchos a Uno

pgr_binaryBreadthFirstSearch(Edges SQL, start_vids, end_vid [, directed]);
RETURNS SET OF (seq, path_seq, start_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo

De los vértices \(\{2, 11\}\) al vértice \(5\) en un grafo binario dirigido

SELECT * FROM pgr_binaryBreadthFirstSearch(
    'SELECT id, source, target, road_work as cost, reverse_road_work as reverse_cost FROM roadworks',
    ARRAY[2,11], 5
);
 seq | path_seq | start_vid | node | edge | cost | agg_cost
-----+----------+-----------+------+------+------+----------
   1 |        1 |         2 |    2 |    4 |    0 |        0
   2 |        2 |         2 |    5 |   -1 |    0 |        0
   3 |        1 |        11 |   11 |   13 |    1 |        0
   4 |        2 |        11 |   12 |   15 |    0 |        1
   5 |        3 |        11 |    9 |   16 |    0 |        1
   6 |        4 |        11 |    4 |    3 |    0 |        1
   7 |        5 |        11 |    3 |    2 |    1 |        1
   8 |        6 |        11 |    2 |    4 |    0 |        2
   9 |        7 |        11 |    5 |   -1 |    0 |        2
(9 rows)

Muchos a Muchos

pgr_binaryBreadthFirstSearch(Edges SQL, start_vids, end_vids [, directed]);
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo

De los vértices \(\{2, 11\}\) a los vértices \(\{3, 5\}\) en un grafo binario no dirigido

SELECT * FROM pgr_binaryBreadthFirstSearch(
    'SELECT id, source, target, road_work as cost, reverse_road_work as reverse_cost FROM roadworks',
    ARRAY[2,11], ARRAY[3,5],
    FALSE
);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         2 |       3 |    2 |    2 |    1 |        0
   2 |        2 |         2 |       3 |    3 |   -1 |    0 |        1
   3 |        1 |         2 |       5 |    2 |    4 |    0 |        0
   4 |        2 |         2 |       5 |    5 |   -1 |    0 |        0
   5 |        1 |        11 |       3 |   11 |   13 |    1 |        0
   6 |        2 |        11 |       3 |   12 |   15 |    0 |        1
   7 |        3 |        11 |       3 |    9 |   16 |    0 |        1
   8 |        4 |        11 |       3 |    4 |    3 |    0 |        1
   9 |        5 |        11 |       3 |    3 |   -1 |    0 |        1
  10 |        1 |        11 |       5 |   11 |   12 |    0 |        0
  11 |        2 |        11 |       5 |   10 |   10 |    1 |        0
  12 |        3 |        11 |       5 |    5 |   -1 |    0 |        1
(12 rows)

Combinaciones

pgr_binaryBreadthFirstSearch(Edges SQL, Combinations SQL [, directed]);
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo

Uso de una tabla de combinaciones en un grafo binario no dirigido.

SELECT * FROM pgr_binaryBreadthFirstSearch(
    'SELECT id, source, target, road_work as cost, reverse_road_work as reverse_cost FROM roadworks',
    'SELECT * FROM ( VALUES (2, 3), (11, 5) ) AS t(source, target)',
    FALSE
);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         2 |       3 |    2 |    2 |    1 |        0
   2 |        2 |         2 |       3 |    3 |   -1 |    0 |        1
   3 |        1 |        11 |       5 |   11 |   12 |    0 |        0
   4 |        2 |        11 |       5 |   10 |   10 |    1 |        0
   5 |        3 |        11 |       5 |    5 |   -1 |    0 |        1
(5 rows)

Parámetros

Parámetro	Tipo	Valores predeterminados	Descripción
Edges SQL	TEXT		Consulta de bordes como se describe a continuación.
Combinaciones SQL	TEXT		Consulta de combinaciones como se describe a continuación.
start_vid	BIGINT		Identificador del vértice inicial de la ruta.
start_vids	ARRAY[BIGINT]		Arreglo de identificadores de vértices iniciales.
end_vid	BIGINT		Identificador del vértice final de la ruta.
end_vids	ARRAY[BIGINT]		Arreglo de identificadores de vértices finales.
dirigido	BOOLEAN	true	Cuando true el gráfo se considera Dirigido Cuando false el gráfo se considera No Dirigido

Consultas internas

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.
costo	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 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 Devoluciones

Devuelve el conjunto de (seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)

Columna	Tipo	Descripción
seq	INT	Valor secuencial a partir de 1.
path_id	INT	Identificador de ruta. Tiene el valor 1 para el primero de una ruta. Se utiliza cuando hay varias rutas para la misma combinación de start_vid a end_vid.
path_seq	INT	Posición relativa en la ruta. Tiene el valor 1 para el principio de una ruta.
start_vid	BIGINT	Identificador del vértice inicial. Se devuelve cuando hay varias vetrices iniciales en la consulta. Muchos a Uno Many to Many
end_vid	BIGINT	Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta. Uno a Muchos Many to Many
nodo	BIGINT	Identificador del nodo en la ruta de start_vid a end_vid.
arista	BIGINT	Identificador del borde utilizado para ir del nodo al siguiente nodo de la secuencia de ruta. -1 para el último nodo de la ruta.
costo	FLOAT	Costo de desplazamiento desde node usando `` edge`` hasta el siguiente nodo en la secuencia de ruta.
agg_cost	FLOAT	Coste agregado de start_v to node.

Datos de ejemplo

Este tipo de datos se utiliza en los ejemplos de esta página.

El Algoritmo Edwards-Moore se aplica mejor cuando se intenta responder a consultas como las siguientes: “Encuentra la ruta con el número mínimo de Origen a Destino” Aquí: * Fuente = Vértice de origen, Destino = Cualquier vértice de destino arbitrario * X es un evento/propiedad * Cada arista del grafo es “X” o “Not X” .

Ejemplo: «Encuentra la ruta con el número mínimo de obras de carretera de Origen a Destino»

Aquí, una carretera en obras (también conocida como obras viales) significa que parte de la carretera está ocupada para trabajos de construcción/mantenimiento.

Aquí: * Arista ( u , v ) pesa = 0 si no hay obras viales en ese momento en la carreterea desde u a v. * Arista ( u, v) pesa = 1 si hay obras viales en ese momento desde u a v.

Luego, al ejecutar el algoritmo, obtenemos la ruta con el número mínimo de obras viales desde el origen y el destino dados.

Por lo tanto, las consultas utilizadas en la sección anterior se pueden interpretar de esta manera.

Datos de la Tabla

Las consultas de las secciones anteriores utilizan la tabla “roadworks”. Los datos de la tabla:

DROP TABLE IF EXISTS roadworks CASCADE;
NOTICE:  table "roadworks" does not exist, skipping
DROP TABLE
CREATE table roadworks (
    id BIGINT not null primary key,
    source BIGINT,
    target BIGINT,
    road_work FLOAT,
    reverse_road_work FLOAT
);
CREATE TABLE
INSERT INTO roadworks(
  id, source, target, road_work, reverse_road_work) VALUES
  (1,  1,  2,  0,  0),
  (2,  2,  3,  -1,  1),
  (3,  3,  4,  -1,  0),
  (4,  2,  5,  0,  0),
  (5,  3,  6,  1,  -1),
  (6,  7,  8,  1,  1),
  (7,  8,  5,  0,  0),
  (8,  5,  6,  1,  1),
  (9,  6,  9,  1,  1),
  (10,  5,  10,  1,  1),
  (11,  6,  11,  1,  -1),
  (12,  10,  11,  0,  -1),
  (13,  11,  12,  1,  -1),
  (14,  10,  13,  1,  1),
  (15,  9,  12,  0,  0),
  (16,  4,  9,  0,  0),
  (17,  14,  15,  0,  0),
  (18,  16,  17,  0,  0);
INSERT 0 18

Ver también

• https://cp-algorithms.com/graph/01_bfs.html

• https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Specialized_variants

Índices y tablas

• Índice

• Página de Búsqueda