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

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])
opcionales: [max_depth, directed]
Regresa el conjunto de (seq, depth, start_vid, node, edge, cost, agg_cost)

Vértice único

pgr_breadthFirstSearch(SQL de aristas, raíz, [options])
opcionales: [max_depth, directed]
Regresa el conjunto de (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])
opcionales: [max_depth, directed]
Regresa el conjunto de (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.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTE:

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.

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

Devuelve el conjunto de (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

FLOTANTE:

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.

ascendente descendente

Ver también

Índices y tablas