18 #include <grass/gis.h>
19 #include <grass/Vect.h>
20 #include <grass/glocale.h>
21 #include <grass/dgl/graph.h>
28 static int uf_initialize(
struct union_find *uf,
int size)
31 uf->
parent = (
int *)G_calloc(size,
sizeof(
int));
34 for (i = 0; i < size; i++)
44 static int uf_find(
struct union_find *uf,
int v)
48 while (uf->
parent[cur] != cur)
50 while (uf->
parent[v] != v) {
59 static void uf_union(
struct union_find *uf,
int u,
int v)
61 int parent_u = uf_find(uf, u);
62 int parent_v = uf_find(uf, v);
64 if (parent_u != parent_v)
65 uf->
parent[parent_u] = parent_v;
74 static int cmp_edge(
const void *pa,
const void *pb)
90 int nnodes, edges, nedges, i, index;
98 if (!perm || !uf_initialize(&uf, nnodes + 1)) {
104 G_message(_(
"Computing minimum spanning tree..."));
106 for (i = 1; i <= nnodes; i++) {
118 perm[index].
edge = edge;
127 for (i = 0; i < index; i++) {
128 G_percent(i + nnodes, nnodes + nedges, 1);
133 if (uf_find(&uf, head) != uf_find(&uf, tail)) {
134 uf_union(&uf, head, tail);