GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-2653d7b383
articulation_point.c
Go to the documentation of this file.
1 /*!
2  \file vector/neta/articulation_point.c
3 
4  \brief Network Analysis library - connected components
5 
6  Computes network articulation points.
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 /*!
24  \brief Get number of articulation points in the graph
25 
26  \param graph input graph
27  \param[out] articulation_list list of articulation points
28 
29  \return number of points
30  \return -1 on error
31  */
32 int NetA_articulation_points(dglGraph_s *graph, struct ilist *articulation_list)
33 {
34  int nnodes;
35  int points = 0;
36 
38  *current; /*edge to be processed when the node is visited */
39  int *tin, *min_tin; /*time in, and smallest tin over all successors. 0 if
40  not yet visited */
41  dglInt32_t **parent; /*parents of the nodes */
42  dglInt32_t **stack; /*stack of nodes */
43  dglInt32_t **current_edge; /*current edge for each node */
44  int *mark; /*marked articulation points */
46  dglInt32_t *current_node;
47  int stack_size;
48  int i, time;
49 
50  nnodes = dglGet_NodeCount(graph);
51  current = (dglEdgesetTraverser_s *)G_calloc(nnodes + 1,
52  sizeof(dglEdgesetTraverser_s));
53  tin = (int *)G_calloc(nnodes + 1, sizeof(int));
54  min_tin = (int *)G_calloc(nnodes + 1, sizeof(int));
55  parent = (dglInt32_t **)G_calloc(nnodes + 1, sizeof(dglInt32_t *));
56  stack = (dglInt32_t **)G_calloc(nnodes + 1, sizeof(dglInt32_t *));
57  current_edge = (dglInt32_t **)G_calloc(nnodes + 1, sizeof(dglInt32_t *));
58  mark = (int *)G_calloc(nnodes + 1, sizeof(int));
59  if (!tin || !min_tin || !parent || !stack || !current || !mark) {
60  G_fatal_error(_("Out of memory"));
61  return -1;
62  }
63 
64  for (i = 1; i <= nnodes; i++) {
66  &current[i], graph,
67  dglNodeGet_OutEdgeset(graph, dglGetNode(graph, i)));
68  current_edge[i] = dglEdgeset_T_First(&current[i]);
69  tin[i] = mark[i] = 0;
70  }
71 
72  dglNode_T_Initialize(&nt, graph);
73 
74  time = 0;
75  for (current_node = dglNode_T_First(&nt); current_node;
76  current_node = dglNode_T_Next(&nt)) {
77  dglInt32_t current_id = dglNodeGet_Id(graph, current_node);
78 
79  if (tin[current_id] == 0) {
80  int children =
81  0; /*number of subtrees rooted at the root/current_node */
82 
83  stack[0] = current_node;
84  stack_size = 1;
85  parent[current_id] = NULL;
86  while (stack_size) {
87  dglInt32_t *node = stack[stack_size - 1];
88  dglInt32_t node_id = dglNodeGet_Id(graph, node);
89 
90  if (tin[node_id] == 0) /*vertex visited for the first time */
91  min_tin[node_id] = tin[node_id] = ++time;
92  else { /*return from the recursion */
94  graph, dglEdgeGet_Tail(graph, current_edge[node_id]));
95  if (min_tin[to] >=
96  tin[node_id]) /*no path from the subtree above the
97  current node */
98  mark[node_id] = 1; /*so the current node must be an
99  articulation point */
100 
101  if (min_tin[to] < min_tin[node_id])
102  min_tin[node_id] = min_tin[to];
103  current_edge[node_id] = dglEdgeset_T_Next(
104  &current[node_id]); /*proceed to the next edge */
105  }
106  /*try next edges */
107  for (; current_edge[node_id];
108  current_edge[node_id] =
109  dglEdgeset_T_Next(&current[node_id])) {
110  dglInt32_t *to =
111  dglEdgeGet_Tail(graph, current_edge[node_id]);
112  if (to == parent[node_id])
113  continue; /*skip parent */
114  int to_id = dglNodeGet_Id(graph, to);
115 
116  if (tin[to_id]) { /*back edge, cannot be a
117  bridge/articualtion point */
118  if (tin[to_id] < min_tin[node_id])
119  min_tin[node_id] = tin[to_id];
120  }
121  else { /*forward edge */
122  if (node_id == current_id)
123  children++; /*if root, increase number of children
124  */
125  parent[to_id] = node;
126  stack[stack_size++] = to;
127  break;
128  }
129  }
130  if (!current_edge[node_id])
131  stack_size--; /*current node completely processed */
132  }
133  if (children > 1)
134  mark[current_id] =
135  1; /*if the root has more than 1 subtrees rooted at it, then
136  * it is an articulation point */
137  }
138  }
139 
140  for (i = 1; i <= nnodes; i++)
141  if (mark[i]) {
142  points++;
143  Vect_list_append(articulation_list, i);
144  }
145 
146  dglNode_T_Release(&nt);
147  for (i = 1; i <= nnodes; i++)
148  dglEdgeset_T_Release(&current[i]);
149 
150  G_free(current);
151  G_free(tin);
152  G_free(min_tin);
153  G_free(parent);
154  G_free(stack);
155  G_free(current_edge);
156  return points;
157 }
int NetA_articulation_points(dglGraph_s *graph, struct ilist *articulation_list)
Get number of articulation points in the graph.
#define NULL
Definition: ccmath.h:32
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
int Vect_list_append(struct ilist *, int)
Append new item to the end of list if not yet present.
#define _(str)
Definition: glocale.h:10
List of integers.
Definition: gis.h:708
long dglInt32_t
Definition: type.h:36
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 * dglNode_T_Next(dglNodeTraverser_s *pT)
int dglGet_NodeCount(dglGraph_s *pgraph)
void dglEdgeset_T_Release(dglEdgesetTraverser_s *pT UNUSED)
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)