GRASS Programmer's Manual  6.4.2(2012)
bridge.c
Go to the documentation of this file.
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(&current[i], graph,
00065                                 dglNodeGet_OutEdgeset(graph,
00066                                                       dglGetNode(graph, i)));
00067         current_edge[i] = dglEdgeset_T_First(&current[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(&current[node_id]);       /*proceed to the next edge */
00100                 }
00101                 for (; current_edge[node_id]; current_edge[node_id] = dglEdgeset_T_Next(&current[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(&current[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 }
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines