41 #include <grass/dgl/graph.h> 56 int stack_size, components;
63 G_warning(
"Directed graph must be version 2 or 3 for NetA_weakly_connected_components()");
75 for (i = 1; i <= nnodes; i++)
87 if (!component[cur_node_id]) {
88 stack[0] = cur_node_id;
90 component[cur_node_id] = ++components;
103 if (!component[to]) {
104 component[to] = components;
106 if (have_node_costs) {
111 stack[stack_size++] = to;
123 if (!component[to]) {
124 component[to] = components;
126 if (have_node_costs) {
131 stack[stack_size++] = to;
159 int stack_size, order_size, components;
166 G_warning(
"Directed graph must be version 2 or 3 for NetA_strongly_connected_components()");
174 processed = (
int *)
G_calloc(nnodes + 1,
sizeof(
int));
175 if (!stack || !order || !processed) {
180 for (i = 1; i <= nnodes; i++) {
194 if (!component[cur_node_id]) {
195 component[cur_node_id] = --components;
196 stack[0] = cur_node_id;
203 if (processed[node_id]) {
205 order[order_size++] = node_id;
208 processed[node_id] = 1;
218 if (!component[to]) {
219 component[to] = components;
221 if (have_node_costs) {
228 stack[stack_size++] = to;
243 int cur_comp = component[cur_node_id];
246 component[cur_node_id] = ++components;
247 stack[0] = cur_node_id;
262 if (component[to] == cur_comp) {
263 component[to] = components;
265 if (have_node_costs) {
270 stack[stack_size++] = to;
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
int NetA_weakly_connected_components(dglGraph_s *graph, int *component)
Computes weakly connected components.
dglInt32_t * dglGetNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
int NetA_strongly_connected_components(dglGraph_s *graph, int *component)
Computes strongly connected components with Kosaraju's two-pass algorithm.
dglInt32_t dglNodeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnNode)
void dglNode_T_Release(dglNodeTraverser_s *pT)
void G_free(void *)
Free allocated memory.
dglInt32_t * dglEdgeGet_Head(dglGraph_s *pGraph, dglInt32_t *pnEdge)
int dglGet_NodeCount(dglGraph_s *pgraph)
dglInt32_t * dglEdgeGet_Tail(dglGraph_s *pGraph, dglInt32_t *pnEdge)
dglInt32_t * dglNode_T_First(dglNodeTraverser_s *pT)
dglInt32_t * dglEdgeset_T_First(dglEdgesetTraverser_s *pT)
void dglEdgeset_T_Release(dglEdgesetTraverser_s *pT)
void G_warning(const char *,...) __attribute__((format(printf
dglInt32_t * dglNodeGet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode)
int order(int i_x, int i_y, int yNum)
dglInt32_t * dglNodeGet_InEdgeset(dglGraph_s *pGraph, dglInt32_t *pnNode)
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)
int dglGet_NodeAttrSize(dglGraph_s *pgraph)