GRASS GIS 8 Programmer's Manual  8.5.0dev(2024)-e07a2894ef
bridge.c
Go to the documentation of this file.
1 /*!
2  \file lib/vector/neta/bridge.c
3 
4  \brief Network Analysis library - bridges
5 
6  Computes number of bridges in the graph.
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 bridges in the graph.
25 
26  Bridge is an array containing the indices of the bridges.
27 
28  \param graph input graph
29  \param[out] bridge_list list of bridges
30 
31  \return number of bridges, -1 on error
32  */
33 int NetA_compute_bridges(dglGraph_s *graph, struct ilist *bridge_list)
34 {
35  int nnodes;
36  int bridges = 0;
37 
39  *current; /*edge to be processed when the node is visited */
40  int *tin, *min_tin; /*time in, and smallest tin over all successors. 0 if
41  not yet visited */
42  dglInt32_t *parent; /*edge from parent to the node */
43  dglInt32_t **stack; /*stack of nodes */
44  dglInt32_t **current_edge; /*current edge for each node */
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  if (!tin || !min_tin || !parent || !stack || !current) {
59  G_fatal_error(_("Out of memory"));
60  return -1;
61  }
62 
63  for (i = 1; i <= nnodes; i++) {
65  &current[i], graph,
66  dglNodeGet_OutEdgeset(graph, dglGetNode(graph, i)));
67  current_edge[i] = dglEdgeset_T_First(&current[i]);
68  tin[i] = 0;
69  }
70 
71  dglNode_T_Initialize(&nt, graph);
72 
73  time = 0;
74  for (current_node = dglNode_T_First(&nt); current_node;
75  current_node = dglNode_T_Next(&nt)) {
76  dglInt32_t current_id = dglNodeGet_Id(graph, current_node);
77 
78  if (tin[current_id] == 0) {
79  stack[0] = current_node;
80  stack_size = 1;
81  parent[current_id] = 0;
82  while (stack_size) {
83  dglInt32_t *node = stack[stack_size - 1];
84  dglInt32_t node_id = dglNodeGet_Id(graph, node);
85 
86  if (tin[node_id] == 0) /*vertex visited for the first time */
87  min_tin[node_id] = tin[node_id] = ++time;
88  else { /*return from the recursion */
90  graph, dglEdgeGet_Tail(graph, current_edge[node_id]));
91  if (min_tin[to] >
92  tin[node_id]) { /*no path from the subtree above the
93  current node */
95  bridge_list,
97  graph, current_edge[node_id])); /*so it must be
98  a bridge */
99  bridges++;
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  for (; current_edge[node_id];
107  current_edge[node_id] = dglEdgeset_T_Next(
108  &current[node_id])) { /*try next edges */
109  dglInt32_t *to =
110  dglEdgeGet_Tail(graph, current_edge[node_id]);
111  dglInt32_t edge_id =
112  dglEdgeGet_Id(graph, current_edge[node_id]);
113  if (labs(edge_id) == parent[node_id])
114  continue; /*skip edge we used to travel to this node */
115  int to_id = dglNodeGet_Id(graph, to);
116 
117  if (tin[to_id]) { /*back edge, cannot be a
118  bridge/articualtion point */
119  if (tin[to_id] < min_tin[node_id])
120  min_tin[node_id] = tin[to_id];
121  }
122  else { /*forward edge */
123  parent[to_id] = labs(edge_id);
124  stack[stack_size++] = to;
125  break;
126  }
127  }
128  if (!current_edge[node_id])
129  stack_size--; /*current node completely processed */
130  }
131  }
132  }
133 
134  dglNode_T_Release(&nt);
135  for (i = 1; i <= nnodes; i++)
136  dglEdgeset_T_Release(&current[i]);
137 
138  G_free(current);
139  G_free(tin);
140  G_free(min_tin);
141  G_free(parent);
142  G_free(stack);
143  G_free(current_edge);
144  return bridges;
145 }
int NetA_compute_bridges(dglGraph_s *graph, struct ilist *bridge_list)
Get number of bridges in the graph.
Definition: bridge.c:33
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 dglEdgeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnEdge)
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)