pgr_binaryBreadthFirstSearch — Devuelve la(s) ruta(s) 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
Advertencia
Funciones experimentales
Disponibilidad
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|)\)
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])
RETURNS SET OF (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
OR EMPTY SET
pgr_binaryBreadthFirstSearch(TEXT edges_sql, BIGINT start_vid, BIGINT 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)
pgr_binaryBreadthFirstSearch(TEXT edges_sql, BIGINT start_vid, BIGINT end_vid,
BOOLEAN directed:=true);
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)
pgr_binaryBreadthFirstSearch(TEXT edges_sql, BIGINT start_vid, ARRAY[ANY_INTEGER] end_vids,
BOOLEAN directed:=true);
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)
pgr_binaryBreadthFirstSearch(TEXT edges_sql, ARRAY[ANY_INTEGER] start_vids, BIGINT end_vid,
BOOLEAN directed:=true);
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)
pgr_binaryBreadthFirstSearch(TEXT edges_sql, ARRAY[ANY_INTEGER] start_vids, ARRAY[ANY_INTEGER] end_vids,
BOOLEAN directed:=true);
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)
| Parámetro | Tipo | Valores predeterminados | Descripción |
|---|---|---|---|
| edges_sql | TEXT |
Consulta SQL interna 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 |
|
| 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)
|
|
| reverse_cost | ANY-NUMERICAL |
-1 | Peso de la arista (target, source),
|
Donde:
| ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
|---|---|
| ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT |
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. |
| end_vid | BIGINT |
Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta. |
| 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. |
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.
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