pgr_primBFS

pgr_primBFS — Algoritmo de Prim para el árbol de expansión mínimo con orden de primera búsqueda de profundidad.

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • Versión 3.0.0
    • Nueva función Oficial

Soporte

Descripción

Visita y extrae la información de los nodos en el orden de búsqueda de Primera Búsqueda de Respiración del Árbol de Expansión Mínimo creado con el algoritmo de Prim.

Las características principales son:

  • Su implementación solo está en grafo no dirigido.
  • El proceso se realiza sólo en las aristas con costos positivos.
  • Cuando el grafo está conectado
    • Las aristas resultantes componen un árbol
  • Cuando el grafo no está conectado,
    • Encuentra un árbol de expansión mínimo para cada componente conectado.
    • Las aristas resultantes conforman un bosque.
  • Tiempo de ejecución de Prim: \(O(E*log V)\)
  • Los nodos de árbol devueltos desde un vértice raíz están en orden de la Primera Búsqueda de Anchura
  • Tiempo de ejecución de la Primera Búsqueda de Anchura: \(O(E + V)\)

Firmas

pgr_primBFS(Edges SQL, Root vid [, max_depth])
pgr_primBFS(Edges SQL, Root vids [, max_depth])

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

Un solo vértice

pgr_primBFS(Edges SQL, Root vid [, max_depth])

RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
Ejemplo:El Árbol de Expansión Mínimo que tiene como vértice raíz \(2\) 
SELECT * FROM pgr_primBFS(
    '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 |    3 |    2 |    1 |        1
   4 |     1 |         2 |    5 |    4 |    1 |        1
   5 |     2 |         2 |    4 |    3 |    1 |        2
   6 |     2 |         2 |    6 |    5 |    1 |        2
   7 |     2 |         2 |    8 |    7 |    1 |        2
   8 |     2 |         2 |   10 |   10 |    1 |        2
   9 |     3 |         2 |    9 |    9 |    1 |        3
  10 |     3 |         2 |   11 |   11 |    1 |        3
  11 |     3 |         2 |    7 |    6 |    1 |        3
  12 |     3 |         2 |   13 |   14 |    1 |        3
  13 |     4 |         2 |   12 |   13 |    1 |        4
(13 rows)

Múltiples Vértices

pgr_primBFS(Edges SQL, Root vids [, max_depth])

RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
Ejemplo:El Árbol de Expansión Mínimo que comienza en los vértices \(\{13, 2\}\) con \(depth <= 3\) 
SELECT * FROM pgr_primBFS(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    ARRAY[13,2], max_depth := 3
);
 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 |    3 |    2 |    1 |        1
   4 |     1 |         2 |    5 |    4 |    1 |        1
   5 |     2 |         2 |    4 |    3 |    1 |        2
   6 |     2 |         2 |    6 |    5 |    1 |        2
   7 |     2 |         2 |    8 |    7 |    1 |        2
   8 |     2 |         2 |   10 |   10 |    1 |        2
   9 |     3 |         2 |    9 |    9 |    1 |        3
  10 |     3 |         2 |   11 |   11 |    1 |        3
  11 |     3 |         2 |    7 |    6 |    1 |        3
  12 |     3 |         2 |   13 |   14 |    1 |        3
  13 |     0 |        13 |   13 |   -1 |    0 |        0
  14 |     1 |        13 |   10 |   14 |    1 |        1
  15 |     2 |        13 |    5 |   10 |    1 |        2
  16 |     3 |        13 |    2 |    4 |    1 |        3
  17 |     3 |        13 |    8 |    7 |    1 |        3
(17 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 Vértice único
  • Cuando el valor es \(0\) se obtiene el bosque de expansión que comienza en nodos aleatorios para cada árbol del bosque.
Root vids ARRAY[ANY-INTEGER]

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

  • Utilizado en Múltiples Vértices
  • los valores \(0\) son ignorados
  • 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

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