Supported versions:

`pgr_breadthFirstSearch` - Experimental¶

pgr_breadthFirstSearch — Devuelve los orden(es) transversales mediante el algoritmo Breadth First Search.

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

Advertencia

Posible bloqueo del servidor

Estas funciones pueden crear una caída 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 puede cambiar.
- La funcionalidad puede cambiar.
- Las pruebas de pgTap pueden faltar.
- Posiblemente necesite codificación c/c++.
- Puede carecer documentación.
- Hay documentación que, en dado caso, podría ser necesario reescribir.
- Puede ser necesario que los ejemplos de documentación se generen automáticamente.
- Puede ser necesaria 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.0.0
- Nueva firma experimental:
  - pgr_breadthFirstSearch (Vértice único)
  - pgr_breadthFirstSearch (Múltiples Vértices)

Descripción¶

Proporciona el orden transversal de Primera Búsqueda de Amplitud desde un vértice raíz hasta una profundidad particular.

Las características principales son:

La implementación funcionará en cualquier tipo de grafo.
Proporciona el orden de recorrido de Búsqueda de Primero Amplitud desde un nodo de origen a un nivel de profundidad objetivo.
Tiempo de ejecución: \(O(E + V)\)

Firmas¶

Resumen

pgr_breadthFirstSearch(SQL de aristas, raíz, [options])
pgr_breadthFirstSearch(SQL de aristas, raices, [options])
options: [max_depth, directed]

RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Vértice único¶

pgr_breadthFirstSearch(SQL de aristas, raíz, [options])

options: [max_depth, directed]

RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Ejemplo:: Desde el vértice raíz \(6\) en un grafo dirigido con aristas en orden ascendente de id

SELECT * FROM pgr_breadthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges ORDER BY id',
  6);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    5 |    1 |    1 |        1
   3 |     1 |         6 |    7 |    4 |    1 |        1
   4 |     2 |         6 |    3 |    7 |    1 |        2
   5 |     2 |         6 |   11 |    8 |    1 |        2
   6 |     2 |         6 |    8 |   10 |    1 |        2
   7 |     3 |         6 |    1 |    6 |    1 |        3
   8 |     3 |         6 |   16 |    9 |    1 |        3
   9 |     3 |         6 |   12 |   11 |    1 |        3
  10 |     3 |         6 |    9 |   14 |    1 |        3
  11 |     4 |         6 |   17 |   15 |    1 |        4
  12 |     4 |         6 |   15 |   16 |    1 |        4
  13 |     5 |         6 |   10 |    3 |    1 |        5
(13 rows)

Múltiples vértices¶

pgr_breadthFirstSearch(SQL de aristas, raices, [options])

options: [max_depth, directed]

RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Ejemplo:: A partir de los vértices de la raíz \(\{12, 6\}\) en un grafo no dirigido con profundidad \(<= 2\) y aristas ordenadas ascendentemente in términos de id

SELECT * FROM pgr_breadthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges ORDER BY id',
  ARRAY[12, 6], directed => false, max_depth => 2);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    5 |    1 |    1 |        1
   3 |     1 |         6 |   10 |    2 |    1 |        1
   4 |     1 |         6 |    7 |    4 |    1 |        1
   5 |     2 |         6 |   15 |    3 |    1 |        2
   6 |     2 |         6 |   11 |    5 |    1 |        2
   7 |     2 |         6 |    3 |    7 |    1 |        2
   8 |     2 |         6 |    8 |   10 |    1 |        2
   9 |     0 |        12 |   12 |   -1 |    0 |        0
  10 |     1 |        12 |   11 |   11 |    1 |        1
  11 |     1 |        12 |    8 |   12 |    1 |        1
  12 |     1 |        12 |   17 |   13 |    1 |        1
  13 |     2 |        12 |   10 |    5 |    1 |        2
  14 |     2 |        12 |    7 |    8 |    1 |        2
  15 |     2 |        12 |   16 |    9 |    1 |        2
  16 |     2 |        12 |    9 |   14 |    1 |        2
(16 rows)

Parámetros¶

Parámetro	Tipo	Descripción
SQL de aristas	`TEXT`	SQL de aristas descritas más adelante.
raíz	`BIGINT`	Identificador del vértice raíz del árbol. Cuando el valor es \(0\) se obtiene el bosque de expansión que comienza en nodos aleatorios para cada árbol del bosque.
raices	`ARRAY` [ENTEROS ]	Arreglo de identificadores de los vértices raíz. Valores \(0\) son ignorados Con el propósito de optimización, valores duplicados son ignorados.

Parámetro

Tipo

Descripción

SQL de aristas

TEXT

SQL de aristas descritas más adelante.

raíz

BIGINT

Identificador del vértice raíz del árbol.

Cuando el valor es \(0\) se obtiene el bosque de expansión que comienza en nodos aleatorios para cada árbol del bosque.

raices

ARRAY [ENTEROS ]

Arreglo de identificadores de los vértices raíz.

Valores \(0\) son ignorados
Con el propósito de optimización, valores duplicados son ignorados.

Donde:

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

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 DFS¶

Parámetro	Tipo	x Defecto	Descripción
`max_depth`	`BIGINT`	\(9223372036854775807\)	Límite superior para la profundidad del árbol. Cuando negativo arroja error.

Parámetro

Tipo

x Defecto

Descripción

max_depth

BIGINT

\(9223372036854775807\)

Límite superior para la profundidad del árbol.

Cuando negativo arroja error.

Consultas Internas¶

SQL aristas¶

Columna	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`)
`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.

Donde:

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

Columnas de Resultados¶

Regresa SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Parámetro	Tipo	Descripción
`seq`	`BIGINT`	Valor secuencial a partir de \(1\).
`depth`	`BIGINT`	Profundidad del `node`. \(0\) cuando `node` = `start_vid`.
`start_vid`	`BIGINT`	Identificador del vértice raíz.
`node`	`BIGINT`	Identificador del `node` alcanzado usando `edge`.
`edge`	`BIGINT`	Identificador del `edge` utilizado para llegar a `node`. \(-1\) cuando `node` = `start_vid`.
`cost`	`FLOAT`	Costo por recorrer `edge`.
`agg_cost`	`FLOAT`	Costo agregado desde `start_vid` hasta `node`.

Donde:

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

Ejemplos Adicionales¶

Ejemplo:: Igual que Vértice único con aritas en orden ascendente de id.

SELECT * FROM pgr_breadthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges ORDER BY id',
  6);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    5 |    1 |    1 |        1
   3 |     1 |         6 |    7 |    4 |    1 |        1
   4 |     2 |         6 |    3 |    7 |    1 |        2
   5 |     2 |         6 |   11 |    8 |    1 |        2
   6 |     2 |         6 |    8 |   10 |    1 |        2
   7 |     3 |         6 |    1 |    6 |    1 |        3
   8 |     3 |         6 |   16 |    9 |    1 |        3
   9 |     3 |         6 |   12 |   11 |    1 |        3
  10 |     3 |         6 |    9 |   14 |    1 |        3
  11 |     4 |         6 |   17 |   15 |    1 |        4
  12 |     4 |         6 |   15 |   16 |    1 |        4
  13 |     5 |         6 |   10 |    3 |    1 |        5
(13 rows)

Ejemplo:: Igual que Vértice único con aritas en orden descendente de id.

SELECT * FROM pgr_breadthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges ORDER BY id DESC',
  6);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    7 |    4 |    1 |        1
   3 |     1 |         6 |    5 |    1 |    1 |        1
   4 |     2 |         6 |    8 |   10 |    1 |        2
   5 |     2 |         6 |   11 |    8 |    1 |        2
   6 |     2 |         6 |    3 |    7 |    1 |        2
   7 |     3 |         6 |    9 |   14 |    1 |        3
   8 |     3 |         6 |   12 |   12 |    1 |        3
   9 |     3 |         6 |   16 |    9 |    1 |        3
  10 |     3 |         6 |    1 |    6 |    1 |        3
  11 |     4 |         6 |   17 |   13 |    1 |        4
  12 |     4 |         6 |   15 |   16 |    1 |        4
  13 |     5 |         6 |   10 |    3 |    1 |        5
(13 rows)

El recorrido resultante es diferente.

La imagen izquierda muestra el resultado con el orden ascendente de los ids y la imagen derecha muestra con el orden descendente de los identificadores de aristas.

Ver también¶

Índices y tablas

pgr_breadthFirstSearch - Experimental¶

Descripción¶

Firmas¶

Vértice único¶

Múltiples vértices¶

Parámetros¶

Parámetros opcionales¶

Parámetros opcionales de DFS¶

Consultas Internas¶

SQL aristas¶

Columnas de Resultados¶

Ejemplos Adicionales¶

Ver también¶

`pgr_breadthFirstSearch` - Experimental¶