• Supported versions:

pgr_kruskalDD

pgr_kruskalDD — Nodos de captación utilizando el algoritmo de Kruskal.

Boost Graph Interno

Disponibilidad

• Versión 3.0.0

  • Nueva función Oficial

Descripción

Usando el algoritmo de Kruskal, extraerá los nodos que tienen costos agregados menores o iguales al valor Distance de un vértice (o vértices) raíz dentro del árbol de expansión mínimo calculado.

Las características principales son:

• Su implementación solo está en el grafo no direccionado.

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

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

• 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 Kruskal: \(O(E * log E)\)

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

• Depth First Search running time: \(O(E + V)\)

Firmas

pgr_kruskalDD(edges_sql, root_vid, distance)
pgr_kruskalDD(edges_sql, root_vids, distance)

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

Vértice único

pgr_kruskalDD(edges_sql, root_vid, distance)

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

Ejemplo

El árbol de expansión mínimo que comienza en el vértice:math:2 con \(agg\_cost <= 3.5\)

SELECT * FROM pgr_kruskalDD(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    2, 3.5
);
 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 |     2 |         2 |    4 |    3 |    1 |        2
   5 |     3 |         2 |    9 |   16 |    1 |        3
(5 rows)

Múltiples Vértices

pgr_kruskalDD(edges_sql, root_vids, distance)

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 \(agg\_cost <= 3.5\);

SELECT * FROM pgr_kruskalDD(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    ARRAY[13,2],
    3.5
);
 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 |     2 |         2 |    4 |    3 |    1 |        2
   5 |     3 |         2 |    9 |   16 |    1 |        3
   6 |     0 |        13 |   13 |   -1 |    0 |        0
   7 |     1 |        13 |   10 |   14 |    1 |        1
   8 |     2 |        13 |    5 |   10 |    1 |        2
   9 |     3 |        13 |    8 |    7 |    1 |        3
  10 |     2 |        13 |   11 |   12 |    1 |        2
  11 |     3 |        13 |    6 |   11 |    1 |        3
  12 |     3 |        13 |   12 |   13 |    1 |        3
(12 rows)

Parámetros

Parámetro	Tipo	Descripción
Edges SQL	TEXT	Consulta SQL descrita en Consulta Interna.
Root vid	BIGINT	Identificador del vértice raíz del árbol. Se utiliza en Vértice único En caso de \(0\) se consigue que el bosque de expansión comience en nodos aleatorios para cada árbol.
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.
Distancia	ANY-NUMERIC	Límite superior para la inclusión del nodo en el resultado. Cuando el valor es Negativo arroja error

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERIC

SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

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 Múltiples Vértices 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.

Ver también

• Árbol de expansión - Categoría

• Kruskal - Familia de funciones

• Las consultas utilizan la red Datos Muestra .

• Boost: algoritmo de documentación de Kruskal

• Wikipedia: algoritmo de Kruskal

Índices y tablas

• Índice

• Página de Búsqueda