GRASS GIS 7 Programmer's Manual  7.9.dev(2021)-e5379bbd7
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  */
33  struct ilist *articulation_list)
34 {
35  int nnodes;
36  int points = 0;
37 
38  dglEdgesetTraverser_s *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 not yet visited */
40  dglInt32_t **parent; /*parents of the nodes */
41  dglInt32_t **stack; /*stack of nodes */
42  dglInt32_t **current_edge; /*current edge for each node */
43  int *mark; /*marked articulation points */
45  dglInt32_t *current_node;
46  int stack_size;
47  int i, time;
48 
49  nnodes = dglGet_NodeCount(graph);
50  current =
51  (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++) {
65  dglEdgeset_T_Initialize(&current[i], graph,
67  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 = 0; /*number of subtrees rooted at the root/current_node */
81 
82  stack[0] = current_node;
83  stack_size = 1;
84  parent[current_id] = NULL;
85  while (stack_size) {
86  dglInt32_t *node = stack[stack_size - 1];
87  dglInt32_t node_id = dglNodeGet_Id(graph, node);
88 
89  if (tin[node_id] == 0) /*vertex visited for the first time */
90  min_tin[node_id] = tin[node_id] = ++time;
91  else { /*return from the recursion */
92  dglInt32_t to = dglNodeGet_Id(graph,
93  dglEdgeGet_Tail(graph,
94  current_edge
95  [node_id]));
96  if (min_tin[to] >= tin[node_id]) /*no path from the subtree above the current node */
97  mark[node_id] = 1; /*so the current node must be an articulation point */
98 
99  if (min_tin[to] < min_tin[node_id])
100  min_tin[node_id] = min_tin[to];
101  current_edge[node_id] = dglEdgeset_T_Next(&current[node_id]); /*proceed to the next edge */
102  }
103  /*try next edges */
104  for (; current_edge[node_id]; current_edge[node_id] = dglEdgeset_T_Next(&current[node_id])) {
105  dglInt32_t *to =
106  dglEdgeGet_Tail(graph, current_edge[node_id]);
107  if (to == parent[node_id])
108  continue; /*skip parent */
109  int to_id = dglNodeGet_Id(graph, to);
110 
111  if (tin[to_id]) { /*back edge, cannot be a bridge/articualtion point */
112  if (tin[to_id] < min_tin[node_id])
113  min_tin[node_id] = tin[to_id];
114  }
115  else { /*forward edge */
116  if (node_id == current_id)
117  children++; /*if root, increase number of children */
118  parent[to_id] = node;
119  stack[stack_size++] = to;
120  break;
121  }
122  }
123  if (!current_edge[node_id])
124  stack_size--; /*current node completely processed */
125  }
126  if (children > 1)
127  mark[current_id] = 1; /*if the root has more than 1 subtrees rooted at it, then it is an
128  * articulation point */
129  }
130  }
131 
132  for (i = 1; i <= nnodes; i++)
133  if (mark[i]) {
134  points++;
135  Vect_list_append(articulation_list, i);
136  }
137 
138  dglNode_T_Release(&nt);
139  for (i = 1; i <= nnodes; i++)
140  dglEdgeset_T_Release(&current[i]);
141 
142  G_free(current);
143  G_free(tin);
144  G_free(min_tin);
145  G_free(parent);
146  G_free(stack);
147  G_free(current_edge);
148  return points;
149 }
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
dglInt32_t * dglGetNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
dglInt32_t dglNodeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnNode)
void dglNode_T_Release(dglNodeTraverser_s *pT)
void G_free(void *)
Free allocated memory.
Definition: gis/alloc.c:149
int dglGet_NodeCount(dglGraph_s *pgraph)
dglInt32_t * dglEdgeGet_Tail(dglGraph_s *pGraph, dglInt32_t *pnEdge)
#define NULL
Definition: ccmath.h:32
#define G_calloc(m, n)
Definition: defs/gis.h:113
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)
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:689
int NetA_articulation_points(dglGraph_s *graph, struct ilist *articulation_list)
Get number of articulation points in the graph.
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)