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

Version 3.7.0:

  • Estandarización de columnas de resultados a (seq, depth, start_vid, pred, node, edge, cost, agg_cost)

    • Added pred result columns.

Versión 3.0.0:
  • Nueva función Oficial

Descripción

Visits and extracts the nodes information in Breath First Search ordering of the Minimum Spanning Tree created using Prims’s algorithm.

Las características principales son:

  • Su implementación es solo para grafo no dirigido.

  • El proceso se realiza sólo en aristas con costos positivos.

  • Cuando el grafo es 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(SQL de aristas, Raíz, [max_depth])
pgr_primBFS(SQL de aristas, Raíces, [max_depth])
Regresa el conjunto de (seq, depth, start_vid, pred, node, edge, cost, agg_cost)

Vértice único

pgr_primBFS(SQL de aristas, Raíz, [max_depth])
Regresa el conjunto de (seq, depth, start_vid, pred, node, edge, cost, agg_cost)
Ejemplo:

El Árbol de Expansión Mínimo que tiene como vértice raíz \(6\)

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

Múltiples vértices

pgr_primBFS(SQL de aristas, Raíces, [max_depth])
Regresa el conjunto de (seq, depth, start_vid, pred, node, edge, cost, agg_cost)
Ejemplo:

El Árbol de Expansión Mínimo que comienza en los vértices \(\{9, 6\}\) con :\(depth \leq 3\)

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

Parámetros

Parámetro

Tipo

Descripción

SQL de aristas

TEXT

SQL de aristas como se describen abajo.

Raíz

BIGINT

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

Raíces

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

distancia

FLOAT

Límite superior para la inclusión del nodo en el resultado.

Donde:

FLOTANTE:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Párametros opcionales de BFS

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 el conjunto de (seq, depth, start_vid, pred, 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.

  • \(depth-1\) es la profundidad de pred

start_vid

BIGINT

Identificador del vértice raíz.

pred

BIGINT

Presdecesor de node.

  • Cuando node = start_vid entonces tiene el valor node.

node

BIGINT

Identificador del node alcanzado usando edge.

edge

BIGINT

Identificador del edge utilizado para llegar desde pred hasta node.

  • \(-1\) cuando node = start_vid.

cost

FLOAT

Costo por recorrer edge.

agg_cost

FLOAT

Costo agregado desde start_vid hasta node.

Ver también

Índices y tablas