Hi,

I am trying to compute the strongly connected components of a graph. I have my recursive program, but due to stack overflow problem, I want to turn it into an iterative one. However, I am running into some problems with the iterative one.

I'd appreciate some help. Here is my code of the recursive one, and my attempt to make into a loop, which is not working.

thanks

Code:/* Recursive one*/ typedef unsigned int vType #define REPEAT do{ #define UNTIL( condition ) }while(!(condition)); enum cases {finished, live, unexplored}; unsigned int component; void scc_djikstra(Graph &g, vType &v, vType &c, std::stack<vType> &S, std::stack<vType> &C, std::vector<vType> &number, std::vector<cases> &status){ vType c_prime, w; c++; status[v] = live; number[v] = c; S.push(v); C.push(c); std::list< E >::const_iterator itr; // iterate through out-edges (v,w) of v for(itr = g[v].second.begin(); itr != g[v].second.end(); ++itr) { w = (*itr).first; if (status[w] == unexplored) scc_djikstra(g, w, c, S, C, number, status); else { if (status[w] == live){ REPEAT c_prime = C.top(); C.pop(); UNTIL (c_prime <= number[w]) C.push(c_prime); } }// else }// for c_prime = C.top(); C.pop(); if (number[v] == c_prime){ REPEAT w = S.top(); S.pop(); status[w] = finished; number[w] = v; UNTIL (w == v) } else C.push(c_prime); } //...... /* g is the graph in adjacency list representation. g is a vector, where each element is std::pair<unsigned int, std::list> .... <node, out-edges-list> and each element in the list is of type std::pair< vertexType, weightType > */ // call function std::stack<vType> *S = new std::stack<vType>(); std::stack<vType> *C = new std::stack<vType>(); std::vector<vType> *number = new std::vector<vType>(g.nV(), 0); std::vector<cases> *status = new std::vector<cases>(g.nV(), unexplored); for (vType i = 0; i < g.nV(); ++i){ if ( (*status)[i] == unexplored ) scc_djikstra(g, i, h, components); } number->clear(); delete number; status->clear(); delete status; delete S; delete C;

Code:/* iterative one*/ void scc_djikstra_iterative(Graph &g){ vType c = 0; vType v, w, c_prime; std::stack<vType> S; std::stack<vType> C; std::vector<vType> number(g.nV(), 0); std::vector<cases> status(g.nV(), unexplored); EdgeList::const_iterator start, end; std::stack<vType, std::vector<vType> > verticesStack; // vertices to be visited // visit all vertices for (vType i = 0; i < g.nV(); ++i){ if ( status[i] == unexplored ) verticesStack.push(i); // store on stack for further processing // process stack while(!verticesStack.empty()) { v = verticesStack.top(); verticesStack.pop(); c++; status[v] = live; number[v] = c; S.push(v); C.push(c); // iterate through the out-edges of v start = g[v].second.begin(); end = g[v].second.end(); while(start != end) { --end; w = (*end).first; if (status[w] == unexplored) verticesStack.push(w); // store on stack for further processing else { if (status[w] == live){ REPEAT c_prime = C.top(); C.pop(); UNTIL (c_prime <= number[w]) C.push(c_prime); } c_prime = C.top(); C.pop(); if (number[v] == c_prime){ REPEAT w = S.top(); S.pop(); status[w] = finished; number[w] = v; UNTIL (w == v) } else C.push(c_prime); } // else } // while (start!=end) } // while !verticesStack.empty() } // for i std::cerr<<"\nNumbers: \n"; std::copy(number.begin(), number.end(), std::ostream_iterator<unsigned int> (std::cerr, " ")); }