GRASS GIS 8 Programmer's Manual  8.5.0dev(2024)-3f124c5c78
components.c
Go to the documentation of this file.
1 /*!
2  \file vector/neta/components.c
3 
4  \brief Network Analysis library - graph components
5 
6  Computes strongly and weakly connected components.
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  \author Markus Metz
15  */
16 
17 /* example:
18  *
19  * X -->-- X ---- X --<-- X ---- X
20  * N1 N2 N3 N4 N5
21  *
22  * -->--, --<-- one-way
23  * ---- both ways
24  *
25  * weakly connected:
26  * all 5 nodes, even though there is no direct path from N1 to N4, 5
27  * but N1 connects to N2, 3, and N4, 5 also connect to N2, 3
28  *
29  * strongly connected:
30  * no path from N2 to N1, no path from N3 to N4
31  * component 1: N1
32  * component 2: N2, 3
33  * Component3: N4, 5
34  */
35 
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include <grass/gis.h>
39 #include <grass/vector.h>
40 #include <grass/glocale.h>
41 #include <grass/dgl/graph.h>
42 
43 /*!
44  \brief Computes weakly connected components
45 
46  \param graph input graph
47  \param[out] component array of component ids
48 
49  \return number of components
50  \return -1 on failure
51  */
52 int NetA_weakly_connected_components(dglGraph_s *graph, int *component)
53 {
54  int nnodes, i;
55  dglInt32_t *stack;
56  int stack_size, components;
57  dglInt32_t *cur_node;
59  int have_node_costs;
60  dglInt32_t ncost;
61 
62  if (graph->Version < 2) {
63  G_warning("Directed graph must be version 2 or 3 for "
64  "NetA_weakly_connected_components()");
65  return -1;
66  }
67 
68  components = 0;
69  nnodes = dglGet_NodeCount(graph);
70  stack = (dglInt32_t *)G_calloc(nnodes + 1, sizeof(dglInt32_t));
71  if (!stack) {
72  G_fatal_error(_("Out of memory"));
73  return -1;
74  }
75 
76  for (i = 1; i <= nnodes; i++)
77  component[i] = 0;
78 
79  ncost = 0;
80  have_node_costs = dglGet_NodeAttrSize(graph);
81 
82  dglNode_T_Initialize(&nt, graph);
83 
84  for (cur_node = dglNode_T_First(&nt); cur_node;
85  cur_node = dglNode_T_Next(&nt)) {
86  dglInt32_t cur_node_id = dglNodeGet_Id(graph, cur_node);
87 
88  if (!component[cur_node_id]) {
89  stack[0] = cur_node_id;
90  stack_size = 1;
91  component[cur_node_id] = ++components;
92  while (stack_size) {
93  dglInt32_t *node, *edgeset, *edge;
95 
96  node = dglGetNode(graph, stack[--stack_size]);
97  edgeset = dglNodeGet_OutEdgeset(graph, node);
98  dglEdgeset_T_Initialize(&et, graph, edgeset);
99  for (edge = dglEdgeset_T_First(&et); edge;
100  edge = dglEdgeset_T_Next(&et)) {
101  dglInt32_t to;
102 
103  to = dglNodeGet_Id(graph, dglEdgeGet_Tail(graph, edge));
104  if (!component[to]) {
105  component[to] = components;
106  /* do not go through closed nodes */
107  if (have_node_costs) {
108  memcpy(&ncost,
110  graph, dglEdgeGet_Tail(graph, edge)),
111  sizeof(ncost));
112  }
113  if (ncost >= 0)
114  stack[stack_size++] = to;
115  }
116  }
118 
119  edgeset = dglNodeGet_InEdgeset(graph, node);
120  dglEdgeset_T_Initialize(&et, graph, edgeset);
121  for (edge = dglEdgeset_T_First(&et); edge;
122  edge = dglEdgeset_T_Next(&et)) {
123  dglInt32_t to;
124 
125  to = dglNodeGet_Id(graph, dglEdgeGet_Head(graph, edge));
126  if (!component[to]) {
127  component[to] = components;
128  /* do not go through closed nodes */
129  if (have_node_costs) {
130  memcpy(&ncost,
132  graph, dglEdgeGet_Tail(graph, edge)),
133  sizeof(ncost));
134  }
135  if (ncost >= 0)
136  stack[stack_size++] = to;
137  }
138  }
140  }
141  }
142  }
143  dglNode_T_Release(&nt);
144 
145  G_free(stack);
146  return components;
147 }
148 
149 /*!
150  \brief Computes strongly connected components with Kosaraju's
151  two-pass algorithm
152 
153  \param graph input graph
154  \param[out] component array of component ids
155 
156  \return number of components
157  \return -1 on failure
158  */
160 {
161  int nnodes, i;
162  dglInt32_t *stack, *order;
163  int *processed;
164  int stack_size, order_size, components;
165  dglInt32_t *cur_node;
167  int have_node_costs;
168  dglInt32_t ncost;
169 
170  if (graph->Version < 2) {
171  G_warning("Directed graph must be version 2 or 3 for "
172  "NetA_strongly_connected_components()");
173  return -1;
174  }
175 
176  components = 0;
177  nnodes = dglGet_NodeCount(graph);
178  stack = (dglInt32_t *)G_calloc(nnodes + 1, sizeof(dglInt32_t));
179  order = (dglInt32_t *)G_calloc(nnodes + 1, sizeof(dglInt32_t));
180  processed = (int *)G_calloc(nnodes + 1, sizeof(int));
181  if (!stack || !order || !processed) {
182  G_fatal_error(_("Out of memory"));
183  return -1;
184  }
185 
186  for (i = 1; i <= nnodes; i++) {
187  component[i] = 0;
188  }
189 
190  ncost = 0;
191  have_node_costs = dglGet_NodeAttrSize(graph);
192 
193  order_size = 0;
194  dglNode_T_Initialize(&nt, graph);
195 
196  for (cur_node = dglNode_T_First(&nt); cur_node;
197  cur_node = dglNode_T_Next(&nt)) {
198  dglInt32_t cur_node_id = dglNodeGet_Id(graph, cur_node);
199 
200  if (!component[cur_node_id]) {
201  component[cur_node_id] = --components;
202  stack[0] = cur_node_id;
203  stack_size = 1;
204  while (stack_size) {
205  dglInt32_t *node, *edgeset, *edge;
207  dglInt32_t node_id = stack[stack_size - 1];
208 
209  if (processed[node_id]) {
210  stack_size--;
211  order[order_size++] = node_id;
212  continue;
213  }
214  processed[node_id] = 1;
215 
216  node = dglGetNode(graph, node_id);
217  edgeset = dglNodeGet_OutEdgeset(graph, node);
218  dglEdgeset_T_Initialize(&et, graph, edgeset);
219  for (edge = dglEdgeset_T_First(&et); edge;
220  edge = dglEdgeset_T_Next(&et)) {
221  dglInt32_t to;
222 
223  to = dglNodeGet_Id(graph, dglEdgeGet_Tail(graph, edge));
224  if (!component[to]) {
225  component[to] = components;
226  /* do not go through closed nodes */
227  if (have_node_costs) {
228  memcpy(&ncost,
230  graph, dglEdgeGet_Tail(graph, edge)),
231  sizeof(ncost));
232  }
233  if (ncost < 0)
234  processed[to] = 1;
235 
236  stack[stack_size++] = to;
237  }
238  }
240  }
241  }
242  }
243 
244  dglNode_T_Release(&nt);
245 
246  components = 0;
247  dglNode_T_Initialize(&nt, graph);
248 
249  while (order_size) {
250  dglInt32_t cur_node_id = order[--order_size];
251  int cur_comp = component[cur_node_id];
252 
253  if (cur_comp < 1) {
254  component[cur_node_id] = ++components;
255  stack[0] = cur_node_id;
256  stack_size = 1;
257  while (stack_size) {
258  dglInt32_t *node, *edgeset, *edge;
260  dglInt32_t node_id = stack[--stack_size];
261 
262  node = dglGetNode(graph, node_id);
263  edgeset = dglNodeGet_InEdgeset(graph, node);
264  dglEdgeset_T_Initialize(&et, graph, edgeset);
265  for (edge = dglEdgeset_T_First(&et); edge;
266  edge = dglEdgeset_T_Next(&et)) {
267  dglInt32_t to;
268 
269  to = dglNodeGet_Id(graph, dglEdgeGet_Head(graph, edge));
270  if (component[to] == cur_comp) {
271  component[to] = components;
272  /* do not go through closed nodes */
273  if (have_node_costs) {
274  memcpy(&ncost,
276  graph, dglEdgeGet_Head(graph, edge)),
277  sizeof(ncost));
278  }
279  if (ncost >= 0)
280  stack[stack_size++] = to;
281  }
282  }
284  }
285  }
286  }
287  dglNode_T_Release(&nt);
288 
289  G_free(stack);
290  G_free(order);
291  G_free(processed);
292  return components;
293 }
int order(int i_x, int i_y, int yNum)
Definition: InterpSpline.c:53
int NetA_strongly_connected_components(dglGraph_s *graph, int *component)
Computes strongly connected components with Kosaraju's two-pass algorithm.
Definition: components.c:159
int NetA_weakly_connected_components(dglGraph_s *graph, int *component)
Computes weakly connected components.
Definition: components.c:52
void G_free(void *)
Free allocated memory.
Definition: gis/alloc.c:150
#define G_calloc(m, n)
Definition: defs/gis.h:95
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
void G_warning(const char *,...) __attribute__((format(printf
#define _(str)
Definition: glocale.h:10
dglByte_t Version
Definition: graph.h:140
long dglInt32_t
Definition: type.h:36
int dglGet_NodeAttrSize(dglGraph_s *pgraph)
dglInt32_t * dglNode_T_First(dglNodeTraverser_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)
int dglNode_T_Initialize(dglNodeTraverser_s *pT, dglGraph_s *pGraph)
dglInt32_t * dglEdgeset_T_Next(dglEdgesetTraverser_s *pT)
dglInt32_t * dglEdgeGet_Tail(dglGraph_s *pGraph, dglInt32_t *pnEdge)
dglInt32_t * dglEdgeGet_Head(dglGraph_s *pGraph, dglInt32_t *pnEdge)
dglInt32_t * dglNodeGet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode)
dglInt32_t * dglNode_T_Next(dglNodeTraverser_s *pT)
int dglGet_NodeCount(dglGraph_s *pgraph)
void dglEdgeset_T_Release(dglEdgesetTraverser_s *pT UNUSED)
dglInt32_t * dglNodeGet_InEdgeset(dglGraph_s *pGraph, dglInt32_t *pnNode)
dglInt32_t * dglEdgeset_T_First(dglEdgesetTraverser_s *pT)
void dglNode_T_Release(dglNodeTraverser_s *pT)
dglInt32_t dglNodeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnNode)
dglInt32_t * dglGetNode(dglGraph_s *pGraph, dglInt32_t nNodeId)