GRASS Programmer's Manual  6.4.3(2013)-r
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Macros Pages
spanningtree.c
Go to the documentation of this file.
1 
16 #include <stdio.h>
17 #include <stdlib.h>
18 #include <grass/gis.h>
19 #include <grass/Vect.h>
20 #include <grass/glocale.h>
21 #include <grass/dgl/graph.h>
22 
23 struct union_find
24 {
25  int *parent;
26 };
27 
28 static int uf_initialize(struct union_find *uf, int size)
29 {
30  int i;
31  uf->parent = (int *)G_calloc(size, sizeof(int));
32  if (!uf->parent)
33  return 0;
34  for (i = 0; i < size; i++)
35  uf->parent[i] = i;
36  return 1;
37 }
38 
39 static void uf_release(struct union_find *uf)
40 {
41  G_free(uf->parent);
42 }
43 
44 static int uf_find(struct union_find *uf, int v)
45 {
46  int cur = v, tmp;
47 
48  while (uf->parent[cur] != cur)
49  cur = uf->parent[cur];
50  while (uf->parent[v] != v) {
51  tmp = uf->parent[v];
52  uf->parent[v] = cur;
53  v = tmp;
54  }
55  return cur;
56 }
57 
58 /*TODO: union by rank */
59 static void uf_union(struct union_find *uf, int u, int v)
60 {
61  int parent_u = uf_find(uf, u);
62  int parent_v = uf_find(uf, v);
63 
64  if (parent_u != parent_v)
65  uf->parent[parent_u] = parent_v;
66 }
67 
68 typedef struct
69 {
73 
74 static int cmp_edge(const void *pa, const void *pb)
75 {
76  return ((edge_cost_pair *) pa)->cost - ((edge_cost_pair *) pb)->cost;
77 }
78 
88 int NetA_spanning_tree(dglGraph_s * graph, struct ilist *tree_list)
89 {
90  int nnodes, edges, nedges, i, index;
91  edge_cost_pair *perm; /*permutaion of edges in ascending order */
92  struct union_find uf;
94 
95  nnodes = dglGet_NodeCount(graph);
96  nedges = dglGet_EdgeCount(graph);
97  perm = (edge_cost_pair *) G_calloc(nedges, sizeof(edge_cost_pair));
98  if (!perm || !uf_initialize(&uf, nnodes + 1)) {
99  G_fatal_error(_("Out of memory"));
100  return -1;
101  }
102  /*for some obscure reasons, dglGetEdge always returns NULL. Therefore this complicated enumeration of the edges... */
103  index = 0;
104  G_message(_("Computing minimum spanning tree..."));
105  G_percent_reset();
106  for (i = 1; i <= nnodes; i++) {
107  G_percent(i, nnodes + nedges, 1);
108  dglInt32_t *edge;
109 
110  dglEdgeset_T_Initialize(&et, graph,
111  dglNodeGet_OutEdgeset(graph,
112  dglGetNode(graph,
113  (dglInt32_t)
114  i)));
115  for (edge = dglEdgeset_T_First(&et); edge;
116  edge = dglEdgeset_T_Next(&et))
117  if (dglEdgeGet_Id(graph, edge) > 0) {
118  perm[index].edge = edge;
119  perm[index].cost = dglEdgeGet_Cost(graph, edge);
120  index++;
121  }
122 
124  }
125  edges = 0;
126  qsort((void *)perm, index, sizeof(edge_cost_pair), cmp_edge);
127  for (i = 0; i < index; i++) {
128  G_percent(i + nnodes, nnodes + nedges, 1);
129  dglInt32_t head =
130  dglNodeGet_Id(graph, dglEdgeGet_Head(graph, perm[i].edge));
131  dglInt32_t tail =
132  dglNodeGet_Id(graph, dglEdgeGet_Tail(graph, perm[i].edge));
133  if (uf_find(&uf, head) != uf_find(&uf, tail)) {
134  uf_union(&uf, head, tail);
135  edges++;
136  Vect_list_append(tree_list, dglEdgeGet_Id(graph, perm[i].edge));
137  }
138  }
139  G_free(perm);
140  uf_release(&uf);
141  return edges;
142 }