pgr_breadthFirstSearch - Experimental

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

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

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 transversal de Primera Búsqueda de Amplitud desde un nodo de origen a un nivel de profundidad del objetivo o destino

• Tiempo de ejecución de la Primera Búsqueda de Anchura: \(O(E + V)\)

Firmas

pgr_breadthFirstSearch(Edges SQL, Root vid [, max_depth] [, directed])
pgr_breadthFirstSearch(Edges SQL, Root vids [, max_depth] [, directed])

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

Vértice Único

pgr_breadthFirstSearch(Edges SQL, Root vid [, max_depth] [, directed])

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

Ejemplo

La Primera Búsqueda de Amplitud transversal con vértice raíz \(2\)

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

Múltiples Vértices

pgr_breadthFirstSearch(Edges SQL, Root vids [, max_depth] [, directed])

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

Ejemplo

La Primera Búsqueda de Amplitud tranversal comienza en vértices \(\{11, 12\}\) con profundidad \(depth <= 2\)

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

Parámetros

Parámetro	Tipo	Descripción
Edges SQL	TEXT	Consulta SQL descrita en Inner query.
Root vid	BIGINT	Identificador del vértice raíz del árbol. Se utiliza en Single Vertex.
Root vids	ARRAY[ANY-INTEGER]	Arreglo de identificadores de los vértices raíz. Se utiliza en Multiple Vertices. Para fines de optimización, se omite cualquier valor duplicado.

Parámetros opcionales

Parámetro	Tipo	Valores predeterminados	Descripción
max_depth	BIGINT	\(9223372036854775807\)	Límite superior para la profundidad del nodo en el árbol Cuando el valor es Negativo entonces produce error
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.
cost	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 Resultados

devuelve el conjunto SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Columna	Tipo	Descripción
seq	BIGINT	Valor secuencial a partir de \(1\).
profundidad	BIGINT	Profundidad del nodo. \(0\) cuando node = start_vid.
start_vid	BIGINT	Identificador del vértice raíz. En Multiple Vertices los resultados están en orden ascendente.
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 para atravesar edge.
agg_cost	FLOAT	Costo agregado de start_vid a node.

Ejemplos Adicionales

Grafo no dirigido

Ejemplo

La Primera Búsqueda de Amplitud transversal desde vértices \(\{11, 12\}\) con profundidad \(depth <= 2\) considerando que el grafo no es dirigido.

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

Vértice Fuera del Grafo

Ejemplo

La salida de la función, cuando un vértice no está presente en el gráfo, se pasa como parámetro.

SELECT * FROM pgr_breadthFirstSearch(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    -10
);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
(0 rows)

Ver también

• Las consultas utilizan la red Datos Muestra .

• Boost: Breadth First Search algorithm documentation

• Wikipedia: Breadth First Search algorithm

Índices y tablas

• Índice

• Página de Búsqueda