GRASS Programmer's Manual
6.4.2(2012)
|
00001 00016 #include <stdio.h> 00017 #include <stdlib.h> 00018 #include <grass/gis.h> 00019 #include <grass/Vect.h> 00020 #include <grass/glocale.h> 00021 #include <grass/dgl/graph.h> 00022 00034 int NetA_compute_bridges(dglGraph_s * graph, struct ilist *bridge_list) 00035 { 00036 int nnodes; 00037 int bridges = 0; 00038 00039 dglEdgesetTraverser_s *current; /*edge to be processed when the node is visited */ 00040 int *tin, *min_tin; /*time in, and smallest tin over all successors. 0 if not yet visited */ 00041 dglInt32_t *parent; /*edge from parent to the node */ 00042 dglInt32_t **stack; /*stack of nodes */ 00043 dglInt32_t **current_edge; /*current edge for each node */ 00044 dglNodeTraverser_s nt; 00045 dglInt32_t *current_node; 00046 int stack_size; 00047 int i, time; 00048 00049 nnodes = dglGet_NodeCount(graph); 00050 current = 00051 (dglEdgesetTraverser_s *) G_calloc(nnodes + 1, 00052 sizeof(dglEdgesetTraverser_s)); 00053 tin = (int *)G_calloc(nnodes + 1, sizeof(int)); 00054 min_tin = (int *)G_calloc(nnodes + 1, sizeof(int)); 00055 parent = (dglInt32_t *) G_calloc(nnodes + 1, sizeof(dglInt32_t)); 00056 stack = (dglInt32_t **) G_calloc(nnodes + 1, sizeof(dglInt32_t *)); 00057 current_edge = (dglInt32_t **) G_calloc(nnodes + 1, sizeof(dglInt32_t *)); 00058 if (!tin || !min_tin || !parent || !stack || !current) { 00059 G_fatal_error(_("Out of memory")); 00060 return -1; 00061 } 00062 00063 for (i = 1; i <= nnodes; i++) { 00064 dglEdgeset_T_Initialize(¤t[i], graph, 00065 dglNodeGet_OutEdgeset(graph, 00066 dglGetNode(graph, i))); 00067 current_edge[i] = dglEdgeset_T_First(¤t[i]); 00068 tin[i] = 0; 00069 } 00070 00071 dglNode_T_Initialize(&nt, graph); 00072 00073 time = 0; 00074 for (current_node = dglNode_T_First(&nt); current_node; 00075 current_node = dglNode_T_Next(&nt)) { 00076 dglInt32_t current_id = dglNodeGet_Id(graph, current_node); 00077 00078 if (tin[current_id] == 0) { 00079 stack[0] = current_node; 00080 stack_size = 1; 00081 parent[current_id] = 0; 00082 while (stack_size) { 00083 dglInt32_t *node = stack[stack_size - 1]; 00084 dglInt32_t node_id = dglNodeGet_Id(graph, node); 00085 00086 if (tin[node_id] == 0) /*vertex visited for the first time */ 00087 min_tin[node_id] = tin[node_id] = ++time; 00088 else { /*return from the recursion */ 00089 dglInt32_t to = dglNodeGet_Id(graph, 00090 dglEdgeGet_Tail(graph, 00091 current_edge 00092 [node_id])); 00093 if (min_tin[to] > tin[node_id]) { /*no path from the subtree above the current node */ 00094 Vect_list_append(bridge_list, dglEdgeGet_Id(graph, current_edge[node_id])); /*so it must be a bridge */ 00095 bridges++; 00096 } 00097 if (min_tin[to] < min_tin[node_id]) 00098 min_tin[node_id] = min_tin[to]; 00099 current_edge[node_id] = dglEdgeset_T_Next(¤t[node_id]); /*proceed to the next edge */ 00100 } 00101 for (; current_edge[node_id]; current_edge[node_id] = dglEdgeset_T_Next(¤t[node_id])) { //try next edges 00102 dglInt32_t *to = 00103 dglEdgeGet_Tail(graph, current_edge[node_id]); 00104 dglInt32_t edge_id = 00105 dglEdgeGet_Id(graph, current_edge[node_id]); 00106 if (abs(edge_id) == parent[node_id]) 00107 continue; /*skip edge we used to travel to this node */ 00108 int to_id = dglNodeGet_Id(graph, to); 00109 00110 if (tin[to_id]) { /*back edge, cannot be a bridge/articualtion point */ 00111 if (tin[to_id] < min_tin[node_id]) 00112 min_tin[node_id] = tin[to_id]; 00113 } 00114 else { /*forward edge */ 00115 parent[to_id] = abs(edge_id); 00116 stack[stack_size++] = to; 00117 break; 00118 } 00119 } 00120 if (!current_edge[node_id]) 00121 stack_size--; /*current node completely processed */ 00122 } 00123 } 00124 } 00125 00126 dglNode_T_Release(&nt); 00127 for (i = 1; i <= nnodes; i++) 00128 dglEdgeset_T_Release(¤t[i]); 00129 00130 G_free(current); 00131 G_free(tin); 00132 G_free(min_tin); 00133 G_free(parent); 00134 G_free(stack); 00135 G_free(current_edge); 00136 return bridges; 00137 }