18 #include <grass/gis.h>
19 #include <grass/Vect.h>
20 #include <grass/glocale.h>
21 #include <grass/dgl/graph.h>
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);
dglInt32_t * dglEdgeGet_Tail(dglGraph_s *pGraph, dglInt32_t *pnEdge)
dglInt32_t dglNodeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnNode)
void G_free(void *buf)
Free allocated memory.
int dglEdgeset_T_Initialize(dglEdgesetTraverser_s *pT, dglGraph_s *pGraph, dglInt32_t *pnEdgeset)
dglInt32_t dglEdgeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnEdge)
int G_percent(long n, long d, int s)
Print percent complete messages.
void dglEdgeset_T_Release(dglEdgesetTraverser_s *pT)
int G_percent_reset(void)
Reset G_percent() to 0%; do not add newline.
dglInt32_t * dglEdgeset_T_First(dglEdgesetTraverser_s *pT)
dglInt32_t * dglGetNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
void G_message(const char *msg,...)
Print a message to stderr.
int Vect_list_append(struct ilist *list, int val)
Append new item to the end of list if not yet present.
dglInt32_t * dglEdgeGet_Head(dglGraph_s *pGraph, dglInt32_t *pnEdge)
int dglGet_EdgeCount(dglGraph_s *pgraph)
int NetA_spanning_tree(dglGraph_s *graph, struct ilist *tree_list)
Get number of edges in the spanning forest.
dglInt32_t * dglNodeGet_OutEdgeset(dglGraph_s *pGraph, dglInt32_t *pnNode)
dglInt32_t dglEdgeGet_Cost(dglGraph_s *pGraph, dglInt32_t *pnEdge)
int dglGet_NodeCount(dglGraph_s *pgraph)
int G_fatal_error(const char *msg,...)
Print a fatal error message to stderr.
dglInt32_t * dglEdgeset_T_Next(dglEdgesetTraverser_s *pT)