Supported versions: Latest (3.2) 3.1 3.0

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