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

Boost Graph Inside¶
Disponibilidad
Versión 3.0.0
Nueva función Oficial
Descripción¶
Using Kruskal’s algorithm, extracts the nodes that have aggregate costs less than or equal to a distance from a root vertex (or vertices) within the calculated minimum spanning tree.
Las características principales son:
Su implementación solo para grafo no direccionado.
El proceso se realiza sólo en las 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)\)
Extracts all the nodes that have costs less than or equal to the value distance.
The edges extracted will conform to the corresponding spanning tree. Edge
Edge \((u, v)\) will not be included when:
The distance from the root to \(u\) > limit distance.
The distance from the root to \(v\) > limit distance.
No new nodes are created on the graph, so when is within the limit and is not within the limit, the edge is not included.
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
The Minimum Spanning Tree starting on vertex \(2\) with distance \(<= 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
The Minimum Spanning Tree starting on vertices \(\{13, 2\}\) with distance \(<= 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 as described below. |
|
Root vid |
|
Identificador del vértice raíz del árbol. |
Root vids |
|
Arreglo de identificadores de los vértices raíz.
|
distance |
|
Upper limit for the inclusion of a node in the result.
|
Donde:
- ANY-INTEGER
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERIC
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
,NUMERIC
Consulta interna¶
Edges SQL¶
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ANY-INTEGER |
Identificador de la arista. |
|
|
ANY-INTEGER |
Identificador del primer vértice extremo de la arista. |
|
|
ANY-INTEGER |
Identificador del segundo vértice extremo de la arista. |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Donde:
- ANY-INTEGER
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Columnas de Resultados¶
Regresa SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
Parámetro |
Tipo |
Descripción |
---|---|---|
|
|
Valor secuencial a partir de \(1\). |
|
|
Profundidad del
|
|
|
Identificador del vértice raíz. |
|
|
Identificador del |
|
|
Identificador del
|
|
|
Costo por recorrer |
|
|
Costo agregado desde |
Donde:
- ANY-INTEGER
SMALLINT, INTEGER, BIGINT
- ANY-NUMERIC
SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC
Ver también¶
Índices y tablas