GRASS Programmer's Manual  6.4.2(2012)
neta/components.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 
00032 int NetA_weakly_connected_components(dglGraph_s * graph, int *component)
00033 {
00034     int nnodes;
00035     dglInt32_t *stack;
00036     int *visited;
00037     int stack_size, components;
00038     dglInt32_t *cur_node;
00039     dglNodeTraverser_s nt;
00040 
00041     components = 0;
00042     nnodes = dglGet_NodeCount(graph);
00043     stack = (dglInt32_t *) G_calloc(nnodes + 1, sizeof(dglInt32_t));
00044     visited = (int *)G_calloc(nnodes + 1, sizeof(int));
00045     if (!stack || !visited) {
00046         G_fatal_error(_("Out of memory"));
00047         return -1;
00048     }
00049 
00050     dglNode_T_Initialize(&nt, graph);
00051 
00052     for (cur_node = dglNode_T_First(&nt); cur_node;
00053          cur_node = dglNode_T_Next(&nt)) {
00054         dglInt32_t node_id = dglNodeGet_Id(graph, cur_node);
00055 
00056         if (!visited[node_id]) {
00057             visited[node_id] = 1;
00058             stack[0] = node_id;
00059             stack_size = 1;
00060             component[node_id] = ++components;
00061             while (stack_size) {
00062                 dglInt32_t *node, *edgeset, *edge;
00063                 dglEdgesetTraverser_s et;
00064 
00065                 node = dglGetNode(graph, stack[--stack_size]);
00066                 edgeset = dglNodeGet_OutEdgeset(graph, node);
00067                 dglEdgeset_T_Initialize(&et, graph, edgeset);
00068                 for (edge = dglEdgeset_T_First(&et); edge;
00069                      edge = dglEdgeset_T_Next(&et)) {
00070                     dglInt32_t to;
00071 
00072                     to = dglNodeGet_Id(graph, dglEdgeGet_Tail(graph, edge));
00073                     if (!visited[to]) {
00074                         visited[to] = 1;
00075                         component[to] = components;
00076                         stack[stack_size++] = to;
00077                     }
00078                 }
00079                 dglEdgeset_T_Release(&et);
00080             }
00081         }
00082     }
00083     dglNode_T_Release(&nt);
00084     G_free(visited);
00085     return components;
00086 }
00087 
00097 int NetA_strongly_connected_components(dglGraph_s * graph, int *component)
00098 {
00099     int nnodes;
00100     dglInt32_t *stack, *order;
00101     int *visited, *processed;
00102     int stack_size, order_size, components;
00103     dglInt32_t *node;
00104     dglNodeTraverser_s nt;
00105 
00106     components = 0;
00107     nnodes = dglGet_NodeCount(graph);
00108     stack = (dglInt32_t *) G_calloc(nnodes + 1, sizeof(dglInt32_t));
00109     order = (dglInt32_t *) G_calloc(nnodes + 1, sizeof(dglInt32_t));
00110     visited = (int *)G_calloc(nnodes + 1, sizeof(int));
00111     processed = (int *)G_calloc(nnodes + 1, sizeof(int));
00112     if (!stack || !visited || !order || !processed) {
00113         G_fatal_error(_("Out of memory"));
00114         return -1;
00115     }
00116 
00117     order_size = 0;
00118     dglNode_T_Initialize(&nt, graph);
00119 
00120     for (node = dglNode_T_First(&nt); node; node = dglNode_T_Next(&nt)) {
00121         dglInt32_t node_id = dglNodeGet_Id(graph, node);
00122 
00123         component[node_id] = 0;
00124         if (!visited[node_id]) {
00125             visited[node_id] = 1;
00126             stack[0] = node_id;
00127             stack_size = 1;
00128             while (stack_size) {
00129                 dglInt32_t *node, *edgeset, *edge;
00130                 dglEdgesetTraverser_s et;
00131                 dglInt32_t cur_node_id = stack[stack_size - 1];
00132 
00133                 if (processed[cur_node_id]) {
00134                     stack_size--;
00135                     order[order_size++] = cur_node_id;
00136                     continue;
00137                 }
00138                 processed[cur_node_id] = 1;
00139                 node = dglGetNode(graph, cur_node_id);
00140                 edgeset = dglNodeGet_OutEdgeset(graph, node);
00141                 dglEdgeset_T_Initialize(&et, graph, edgeset);
00142                 for (edge = dglEdgeset_T_First(&et); edge;
00143                      edge = dglEdgeset_T_Next(&et)) {
00144                     dglInt32_t to;
00145 
00146                     if (dglEdgeGet_Id(graph, edge) < 0)
00147                         continue;       /*ignore backward edges */
00148                     to = dglNodeGet_Id(graph, dglEdgeGet_Tail(graph, edge));
00149                     if (!visited[to]) {
00150                         visited[to] = 1;
00151                         stack[stack_size++] = to;
00152                     }
00153                 }
00154                 dglEdgeset_T_Release(&et);
00155             }
00156         }
00157     }
00158 
00159     dglNode_T_Release(&nt);
00160 
00161     while (order_size) {
00162         dglInt32_t node_id = order[--order_size];
00163 
00164         if (component[node_id])
00165             continue;
00166         components++;
00167         component[node_id] = components;
00168         stack[0] = node_id;
00169         stack_size = 1;
00170         while (stack_size) {
00171             dglInt32_t *node, *edgeset, *edge;
00172             dglEdgesetTraverser_s et;
00173             dglInt32_t cur_node_id = stack[--stack_size];
00174 
00175             node = dglGetNode(graph, cur_node_id);
00176             edgeset = dglNodeGet_OutEdgeset(graph, node);
00177             dglEdgeset_T_Initialize(&et, graph, edgeset);
00178             for (edge = dglEdgeset_T_First(&et); edge;
00179                  edge = dglEdgeset_T_Next(&et)) {
00180                 dglInt32_t to;
00181 
00182                 if (dglEdgeGet_Id(graph, edge) > 0)
00183                     continue;   /*ignore forward edges */
00184                 to = dglNodeGet_Id(graph, dglEdgeGet_Tail(graph, edge));
00185                 if (!component[to]) {
00186                     component[to] = components;
00187                     stack[stack_size++] = to;
00188                 }
00189             }
00190             dglEdgeset_T_Release(&et);
00191         }
00192     }
00193 
00194     G_free(stack);
00195     G_free(visited);
00196     G_free(order);
00197     G_free(processed);
00198     return components;
00199 }
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines