GRASS GIS 7 Programmer's Manual  7.9.dev(2021)-e5379bbd7
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 
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; /*edge from parent to the node */
41  dglInt32_t **stack; /*stack of nodes */
42  dglInt32_t **current_edge; /*current edge for each node */
44  dglInt32_t *current_node;
45  int stack_size;
46  int i, time;
47 
48  nnodes = dglGet_NodeCount(graph);
49  current =
50  (dglEdgesetTraverser_s *) G_calloc(nnodes + 1,
51  sizeof(dglEdgesetTraverser_s));
52  tin = (int *)G_calloc(nnodes + 1, sizeof(int));
53  min_tin = (int *)G_calloc(nnodes + 1, sizeof(int));
54  parent = (dglInt32_t *) G_calloc(nnodes + 1, sizeof(dglInt32_t));
55  stack = (dglInt32_t **) G_calloc(nnodes + 1, sizeof(dglInt32_t *));
56  current_edge = (dglInt32_t **) G_calloc(nnodes + 1, sizeof(dglInt32_t *));
57  if (!tin || !min_tin || !parent || !stack || !current) {
58  G_fatal_error(_("Out of memory"));
59  return -1;
60  }
61 
62  for (i = 1; i <= nnodes; i++) {
63  dglEdgeset_T_Initialize(&current[i], graph,
65  dglGetNode(graph, i)));
66  current_edge[i] = dglEdgeset_T_First(&current[i]);
67  tin[i] = 0;
68  }
69 
70  dglNode_T_Initialize(&nt, graph);
71 
72  time = 0;
73  for (current_node = dglNode_T_First(&nt); current_node;
74  current_node = dglNode_T_Next(&nt)) {
75  dglInt32_t current_id = dglNodeGet_Id(graph, current_node);
76 
77  if (tin[current_id] == 0) {
78  stack[0] = current_node;
79  stack_size = 1;
80  parent[current_id] = 0;
81  while (stack_size) {
82  dglInt32_t *node = stack[stack_size - 1];
83  dglInt32_t node_id = dglNodeGet_Id(graph, node);
84 
85  if (tin[node_id] == 0) /*vertex visited for the first time */
86  min_tin[node_id] = tin[node_id] = ++time;
87  else { /*return from the recursion */
88  dglInt32_t to = dglNodeGet_Id(graph,
89  dglEdgeGet_Tail(graph,
90  current_edge
91  [node_id]));
92  if (min_tin[to] > tin[node_id]) { /*no path from the subtree above the current node */
93  Vect_list_append(bridge_list, dglEdgeGet_Id(graph, current_edge[node_id])); /*so it must be a bridge */
94  bridges++;
95  }
96  if (min_tin[to] < min_tin[node_id])
97  min_tin[node_id] = min_tin[to];
98  current_edge[node_id] = dglEdgeset_T_Next(&current[node_id]); /*proceed to the next edge */
99  }
100  for (; current_edge[node_id]; current_edge[node_id] = dglEdgeset_T_Next(&current[node_id])) { /*try next edges */
101  dglInt32_t *to =
102  dglEdgeGet_Tail(graph, current_edge[node_id]);
103  dglInt32_t edge_id =
104  dglEdgeGet_Id(graph, current_edge[node_id]);
105  if (labs(edge_id) == parent[node_id])
106  continue; /*skip edge we used to travel to this node */
107  int to_id = dglNodeGet_Id(graph, to);
108 
109  if (tin[to_id]) { /*back edge, cannot be a bridge/articualtion point */
110  if (tin[to_id] < min_tin[node_id])
111  min_tin[node_id] = tin[to_id];
112  }
113  else { /*forward edge */
114  parent[to_id] = labs(edge_id);
115  stack[stack_size++] = to;
116  break;
117  }
118  }
119  if (!current_edge[node_id])
120  stack_size--; /*current node completely processed */
121  }
122  }
123  }
124 
125  dglNode_T_Release(&nt);
126  for (i = 1; i <= nnodes; i++)
127  dglEdgeset_T_Release(&current[i]);
128 
129  G_free(current);
130  G_free(tin);
131  G_free(min_tin);
132  G_free(parent);
133  G_free(stack);
134  G_free(current_edge);
135  return bridges;
136 }
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 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)
int NetA_compute_bridges(dglGraph_s *graph, struct ilist *bridge_list)
Get number of bridges in the graph.
Definition: bridge.c:33
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 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)
dglInt32_t dglEdgeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnEdge)