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 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 }