pgr_kruskalDFS

pgr_kruskalDFS — Algoritmo Kruskal para el Árbol de Expansión Mínima con orden de Búsqueda Primero en Profundidad.

Adentro: Boost Graph

Disponibilidad

Versión 3.7.0:

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

  • Agregado columna de resultados pred.

Versión 3.0.0:

• Nueva función Oficial

Descripción

Visita y extrae la información de los nodos en el orden de Búsqueda en Primera Profundidad del Árbol de Expansión Mínima creado con el algoritmo de Kruskal.

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.

• Se minimiza el peso total de todos los bordes del árbol o bosque.

• Tiempo de ejecución de Kruskal: \(O(E * log E)\)

• Los nodos de árbol devueltos desde un vértice raíz están en el orden de Primera Búsqueda de Profundidad

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

Firmas

pgr_kruskalDFS(SQL de aristas, raíz, [max_depth])

pgr_kruskalDFS(SQL de aristas, raices, [max_depth])

Regresa el conjunto de (seq, depth, start_vid, pred, node, edge, cost, agg_cost)

Vértice único

pgr_kruskalDFS(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_kruskalDFS(
  '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 |     2 |         6 |   10 |   15 |    3 |    1 |        2
   5 |     3 |         6 |   15 |   16 |   16 |    1 |        3
   6 |     4 |         6 |   16 |   17 |   15 |    1 |        4
   7 |     5 |         6 |   17 |   12 |   13 |    1 |        5
   8 |     6 |         6 |   12 |   11 |   11 |    1 |        6
   9 |     6 |         6 |   12 |    8 |   12 |    1 |        6
  10 |     7 |         6 |    8 |    7 |   10 |    1 |        7
  11 |     8 |         6 |    7 |    3 |    7 |    1 |        8
  12 |     9 |         6 |    3 |    1 |    6 |    1 |        9
  13 |     7 |         6 |    8 |    9 |   14 |    1 |        7
(13 rows)

Múltiples vértices

pgr_kruskalDFS(SQL de aristas, raices, [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_kruskalDFS(
  '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 |     2 |         6 |   10 |   15 |    3 |    1 |        2
   5 |     3 |         6 |   15 |   16 |   16 |    1 |        3
   6 |     0 |         9 |    9 |    9 |   -1 |    0 |        0
   7 |     1 |         9 |    9 |    8 |   14 |    1 |        1
   8 |     2 |         9 |    8 |    7 |   10 |    1 |        2
   9 |     3 |         9 |    7 |    3 |    7 |    1 |        3
  10 |     2 |         9 |    8 |   12 |   12 |    1 |        2
  11 |     3 |         9 |   12 |   11 |   11 |    1 |        3
  12 |     3 |         9 |   12 |   17 |   13 |    1 |        3
(12 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

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

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

• Árbol de expansión - Categoría

• Kruskal - Familia de funciones

• Datos Muestra

• Boost: algoritmo de Kruskal

• Wikipedia: algoritmo de Kruskal

Índices y tablas

• Índice

• Página de Búsqueda