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, " "));
}