pgr_binaryBreadthFirstSearch - Experimental

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”.

_images/boost-inside.jpeg

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 (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

  • Para ser experimental en v3.0.0

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

Uno a Uno

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)

Uno a muchos

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)

Muchos a Uno

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)

Muchos a Muchos

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ámetros

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

  • Cuando true el gráfo se considera Dirigido

  • Cuando false el gráfo se considera No Dirigido

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.

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

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.

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.

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