GRASS GIS 7 Programmer's Manual  7.5.svn(2017)-r71942
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
components.c
Go to the documentation of this file.
1 /*!
2  \file vector/neta/components.c
3 
4  \brief Network Analysis library - graph componets
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 NetA_weakly_connected_components()");
64  return -1;
65  }
66 
67  components = 0;
68  nnodes = dglGet_NodeCount(graph);
69  stack = (dglInt32_t *) G_calloc(nnodes + 1, sizeof(dglInt32_t));
70  if (!stack) {
71  G_fatal_error(_("Out of memory"));
72  return -1;
73  }
74 
75  for (i = 1; i <= nnodes; i++)
76  component[i] = 0;
77 
78  ncost = 0;
79  have_node_costs = dglGet_NodeAttrSize(graph);
80 
81  dglNode_T_Initialize(&nt, graph);
82 
83  for (cur_node = dglNode_T_First(&nt); cur_node;
84  cur_node = dglNode_T_Next(&nt)) {
85  dglInt32_t cur_node_id = dglNodeGet_Id(graph, cur_node);
86 
87  if (!component[cur_node_id]) {
88  stack[0] = cur_node_id;
89  stack_size = 1;
90  component[cur_node_id] = ++components;
91  while (stack_size) {
92  dglInt32_t *node, *edgeset, *edge;
94 
95  node = dglGetNode(graph, stack[--stack_size]);
96  edgeset = dglNodeGet_OutEdgeset(graph, node);
97  dglEdgeset_T_Initialize(&et, graph, edgeset);
98  for (edge = dglEdgeset_T_First(&et); edge;
99  edge = dglEdgeset_T_Next(&et)) {
100  dglInt32_t to;
101 
102  to = dglNodeGet_Id(graph, dglEdgeGet_Tail(graph, edge));
103  if (!component[to]) {
104  component[to] = components;
105  /* do not go through closed nodes */
106  if (have_node_costs) {
107  memcpy(&ncost, dglNodeGet_Attr(graph, dglEdgeGet_Tail(graph, edge)),
108  sizeof(ncost));
109  }
110  if (ncost >= 0)
111  stack[stack_size++] = to;
112  }
113  }
115 
116  edgeset = dglNodeGet_InEdgeset(graph, node);
117  dglEdgeset_T_Initialize(&et, graph, edgeset);
118  for (edge = dglEdgeset_T_First(&et); edge;
119  edge = dglEdgeset_T_Next(&et)) {
120  dglInt32_t to;
121 
122  to = dglNodeGet_Id(graph, dglEdgeGet_Head(graph, edge));
123  if (!component[to]) {
124  component[to] = components;
125  /* do not go through closed nodes */
126  if (have_node_costs) {
127  memcpy(&ncost, dglNodeGet_Attr(graph, dglEdgeGet_Tail(graph, edge)),
128  sizeof(ncost));
129  }
130  if (ncost >= 0)
131  stack[stack_size++] = to;
132  }
133  }
135  }
136  }
137  }
138  dglNode_T_Release(&nt);
139 
140  G_free(stack);
141  return components;
142 }
143 
144 /*!
145  \brief Computes strongly connected components with Kosaraju's
146  two-pass algorithm
147 
148  \param graph input graph
149  \param[out] component array of component ids
150 
151  \return number of components
152  \return -1 on failure
153  */
154 int NetA_strongly_connected_components(dglGraph_s * graph, int *component)
155 {
156  int nnodes, i;
157  dglInt32_t *stack, *order;
158  int *processed;
159  int stack_size, order_size, components;
160  dglInt32_t *cur_node;
162  int have_node_costs;
163  dglInt32_t ncost;
164 
165  if (graph->Version < 2) {
166  G_warning("Directed graph must be version 2 or 3 for NetA_strongly_connected_components()");
167  return -1;
168  }
169 
170  components = 0;
171  nnodes = dglGet_NodeCount(graph);
172  stack = (dglInt32_t *) G_calloc(nnodes + 1, sizeof(dglInt32_t));
173  order = (dglInt32_t *) G_calloc(nnodes + 1, sizeof(dglInt32_t));
174  processed = (int *)G_calloc(nnodes + 1, sizeof(int));
175  if (!stack || !order || !processed) {
176  G_fatal_error(_("Out of memory"));
177  return -1;
178  }
179 
180  for (i = 1; i <= nnodes; i++) {
181  component[i] = 0;
182  }
183 
184  ncost = 0;
185  have_node_costs = dglGet_NodeAttrSize(graph);
186 
187  order_size = 0;
188  dglNode_T_Initialize(&nt, graph);
189 
190  for (cur_node = dglNode_T_First(&nt); cur_node;
191  cur_node = dglNode_T_Next(&nt)) {
192  dglInt32_t cur_node_id = dglNodeGet_Id(graph, cur_node);
193 
194  if (!component[cur_node_id]) {
195  component[cur_node_id] = --components;
196  stack[0] = cur_node_id;
197  stack_size = 1;
198  while (stack_size) {
199  dglInt32_t *node, *edgeset, *edge;
201  dglInt32_t node_id = stack[stack_size - 1];
202 
203  if (processed[node_id]) {
204  stack_size--;
205  order[order_size++] = node_id;
206  continue;
207  }
208  processed[node_id] = 1;
209 
210  node = dglGetNode(graph, node_id);
211  edgeset = dglNodeGet_OutEdgeset(graph, node);
212  dglEdgeset_T_Initialize(&et, graph, edgeset);
213  for (edge = dglEdgeset_T_First(&et); edge;
214  edge = dglEdgeset_T_Next(&et)) {
215  dglInt32_t to;
216 
217  to = dglNodeGet_Id(graph, dglEdgeGet_Tail(graph, edge));
218  if (!component[to]) {
219  component[to] = components;
220  /* do not go through closed nodes */
221  if (have_node_costs) {
222  memcpy(&ncost, dglNodeGet_Attr(graph, dglEdgeGet_Tail(graph, edge)),
223  sizeof(ncost));
224  }
225  if (ncost < 0)
226  processed[to] = 1;
227 
228  stack[stack_size++] = to;
229  }
230  }
232  }
233  }
234  }
235 
236  dglNode_T_Release(&nt);
237 
238  components = 0;
239  dglNode_T_Initialize(&nt, graph);
240 
241  while (order_size) {
242  dglInt32_t cur_node_id = order[--order_size];
243  int cur_comp = component[cur_node_id];
244 
245  if (cur_comp < 1) {
246  component[cur_node_id] = ++components;
247  stack[0] = cur_node_id;
248  stack_size = 1;
249  while (stack_size) {
250  dglInt32_t *node, *edgeset, *edge;
252  dglInt32_t node_id = stack[--stack_size];
253 
254  node = dglGetNode(graph, node_id);
255  edgeset = dglNodeGet_InEdgeset(graph, node);
256  dglEdgeset_T_Initialize(&et, graph, edgeset);
257  for (edge = dglEdgeset_T_First(&et); edge;
258  edge = dglEdgeset_T_Next(&et)) {
259  dglInt32_t to;
260 
261  to = dglNodeGet_Id(graph, dglEdgeGet_Head(graph, edge));
262  if (component[to] == cur_comp) {
263  component[to] = components;
264  /* do not go through closed nodes */
265  if (have_node_costs) {
266  memcpy(&ncost, dglNodeGet_Attr(graph, dglEdgeGet_Head(graph, edge)),
267  sizeof(ncost));
268  }
269  if (ncost >= 0)
270  stack[stack_size++] = to;
271  }
272  }
274  }
275  }
276  }
277  dglNode_T_Release(&nt);
278 
279  G_free(stack);
280  G_free(order);
281  G_free(processed);
282  return components;
283 }
void G_free(void *buf)
Free allocated memory.
Definition: gis/alloc.c:149
int NetA_weakly_connected_components(dglGraph_s *graph, int *component)
Computes weakly connected components.
Definition: components.c:52
dglInt32_t * dglGetNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
int NetA_strongly_connected_components(dglGraph_s *graph, int *component)
Computes strongly connected components with Kosaraju&#39;s two-pass algorithm.
Definition: components.c:154
dglInt32_t dglNodeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnNode)
void dglNode_T_Release(dglNodeTraverser_s *pT)
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_fatal_error(const char *msg,...)
Print a fatal error message to stderr.
Definition: gis/error.c:159
dglInt32_t * dglNode_T_First(dglNodeTraverser_s *pT)
dglInt32_t * dglEdgeset_T_First(dglEdgesetTraverser_s *pT)
long dglInt32_t
Definition: type.h:37
void dglEdgeset_T_Release(dglEdgesetTraverser_s *pT)
dglInt32_t * dglNodeGet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode)
dglByte_t Version
Definition: graph.h:156
#define _(str)
Definition: glocale.h:13
int order(int i_x, int i_y, int yNum)
Definition: InterpSpline.c:54
dglInt32_t * dglNodeGet_InEdgeset(dglGraph_s *pGraph, dglInt32_t *pnNode)
int dglNode_T_Initialize(dglNodeTraverser_s *pT, 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 * dglNode_T_Next(dglNodeTraverser_s *pT)
void G_warning(const char *msg,...)
Print a warning message to stderr.
Definition: gis/error.c:203
int dglGet_NodeAttrSize(dglGraph_s *pgraph)