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++)
39 static void uf_release(
struct union_find *uf)
44 static int uf_find(
struct union_find *uf,
int v)
48 while (uf->parent[cur] != cur)
49 cur = uf->parent[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)
76 if (((edge_cost_pair *) pa)->cost < ((edge_cost_pair *) pb)->cost)
79 return (((edge_cost_pair *) pa)->cost > ((edge_cost_pair *) pb)->cost);
93 int nnodes, edges, nedges, i, index;
102 perm = (edge_cost_pair *)
G_calloc(nedges,
sizeof(edge_cost_pair));
103 if (!perm || !uf_initialize(&uf, nnodes + 1)) {
109 G_message(
_(
"Computing minimum spanning tree..."));
111 for (i = 1; i <= nnodes; i++) {
123 perm[index].edge = edge;
131 qsort((
void *)perm, index,
sizeof(edge_cost_pair), cmp_edge);
132 for (i = 0; i < index; i++) {
133 G_percent(i + nnodes, nnodes + nedges, 1);
138 if (uf_find(&uf, head) != uf_find(&uf, tail)) {
139 uf_union(&uf, head, tail);
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
void G_percent_reset(void)
Reset G_percent() to 0%; do not add newline.
dglInt32_t * dglGetNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
dglInt32_t dglNodeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnNode)
dglInt32_t dglEdgeGet_Cost(dglGraph_s *pGraph, dglInt32_t *pnEdge)
void G_free(void *)
Free allocated memory.
dglInt32_t * dglEdgeGet_Head(dglGraph_s *pGraph, dglInt32_t *pnEdge)
int dglGet_NodeCount(dglGraph_s *pgraph)
dglInt32_t * dglEdgeGet_Tail(dglGraph_s *pGraph, dglInt32_t *pnEdge)
void G_message(const char *,...) __attribute__((format(printf
dglInt32_t * dglEdgeset_T_First(dglEdgesetTraverser_s *pT)
void dglEdgeset_T_Release(dglEdgesetTraverser_s *pT)
int NetA_spanning_tree(dglGraph_s *graph, struct ilist *tree_list)
Get number of edges in the spanning forest.
void G_percent(long, long, int)
Print percent complete messages.
int Vect_list_append(struct ilist *, int)
Append new item to the end of list if not yet present.
int dglGet_EdgeCount(dglGraph_s *pgraph)
dglInt32_t * dglEdgeset_T_Next(dglEdgesetTraverser_s *pT)
dglInt32_t * dglNodeGet_OutEdgeset(dglGraph_s *pGraph, dglInt32_t *pnNode)
int dglEdgeset_T_Initialize(dglEdgesetTraverser_s *pT, dglGraph_s *pGraph, dglInt32_t *pnEdgeset)
dglInt32_t dglEdgeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnEdge)