GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
spanningtree.c
Go to the documentation of this file.
1 /*!
2  \file vector/neta/spanningtree.c
3 
4  \brief Network Analysis library - spanning tree
5 
6  Computes minimum spanning tree in the network.
7 
8  (C) 2009-2010 by Daniel Bundala, and the GRASS Development Team
9 
10  This program is free software under the GNU General Public License
11  (>=v2). Read the file COPYING that comes with GRASS for details.
12 
13  \author Daniel Bundala (Google Summer of Code 2009)
14  */
15 
16 #include <stdio.h>
17 #include <stdlib.h>
18 #include <grass/gis.h>
19 #include <grass/vector.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 {
70  dglInt32_t cost;
71  dglInt32_t *edge;
72 } edge_cost_pair;
73 
74 static int cmp_edge(const void *pa, const void *pb)
75 {
76  if (((edge_cost_pair *) pa)->cost < ((edge_cost_pair *) pb)->cost)
77  return -1;
78 
79  return (((edge_cost_pair *) pa)->cost > ((edge_cost_pair *) pb)->cost);
80 }
81 
82 /*!
83  \brief Get number of edges in the spanning forest
84 
85  \param graph input graph
86  \param[out] list of edges
87 
88  \return number of edges
89  \return -1 on failure
90  */
91 int NetA_spanning_tree(dglGraph_s * graph, struct ilist *tree_list)
92 {
93  int nnodes, edges, nedges, i, index;
94  edge_cost_pair *perm; /*permutation of edges in ascending order */
95  struct union_find uf;
97 
98  /* TODO: consider closed nodes / node costs */
99 
100  nnodes = dglGet_NodeCount(graph);
101  nedges = dglGet_EdgeCount(graph);
102  perm = (edge_cost_pair *) G_calloc(nedges, sizeof(edge_cost_pair));
103  if (!perm || !uf_initialize(&uf, nnodes + 1)) {
104  G_fatal_error(_("Out of memory"));
105  return -1;
106  }
107  /* dglGetEdge is only supported with graphs version > 1. Therefore this complicated enumeration of the edges... */
108  index = 0;
109  G_message(_("Computing minimum spanning tree..."));
110  G_percent_reset();
111  for (i = 1; i <= nnodes; i++) {
112  G_percent(i, nnodes + nedges, 1);
113  dglInt32_t *edge;
114 
115  dglEdgeset_T_Initialize(&et, graph,
116  dglNodeGet_OutEdgeset(graph,
117  dglGetNode(graph,
118  (dglInt32_t)
119  i)));
120  for (edge = dglEdgeset_T_First(&et); edge;
121  edge = dglEdgeset_T_Next(&et))
122  if (dglEdgeGet_Id(graph, edge) > 0) {
123  perm[index].edge = edge;
124  perm[index].cost = dglEdgeGet_Cost(graph, edge);
125  index++;
126  }
127 
129  }
130  edges = 0;
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);
134  dglInt32_t head =
135  dglNodeGet_Id(graph, dglEdgeGet_Head(graph, perm[i].edge));
136  dglInt32_t tail =
137  dglNodeGet_Id(graph, dglEdgeGet_Tail(graph, perm[i].edge));
138  if (uf_find(&uf, head) != uf_find(&uf, tail)) {
139  uf_union(&uf, head, tail);
140  edges++;
141  Vect_list_append(tree_list, dglEdgeGet_Id(graph, perm[i].edge));
142  }
143  }
144  G_percent(index, index, 1);
145  G_free(perm);
146  uf_release(&uf);
147  return edges;
148 }
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.
Definition: percent.c:119
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.
Definition: gis/alloc.c:149
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)
#define G_calloc(m, n)
Definition: defs/gis.h:113
void G_message(const char *,...) __attribute__((format(printf
dglInt32_t * dglEdgeset_T_First(dglEdgesetTraverser_s *pT)
long dglInt32_t
Definition: type.h:37
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.
Definition: spanningtree.c:91
void G_percent(long, long, int)
Print percent complete messages.
Definition: percent.c:62
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)
#define _(str)
Definition: glocale.h:10
List of integers.
Definition: gis.h:700
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)