Thread: recursion into loop

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

I am not really going to delve too much into your actual code, rather I will offer a suggestion that would allow you to keep your code recursive (or even alter it into a loop... whatever you like better).

Why not have your "unexplored" data be stored in its own vector, and then process your entire memory block, then process your "unexplored" data, then merge all your data into one vector (or binary tree or whatever).

thanks for the reply,

however, I'd really like to learn how to translate the recursive code into an iterative one in a more traditional way. Is something that is bugging me

I'd appreciate the help with this.

thanks

Recursion can be transformed cleanly to iteration if the recursion is not multiple. In other words, this:

Code:

void recur()
{
    ...
    recur();
    ...
}

Is easy to convert, whereas this is harder:

Code:

void recur()
{
    ...
    recur();
    ...
    recur();
    ...
}

The reason being, you can convert singular recursion to iteration by packing all local variables into a struct, putting these on a stack, and replacing the recursive call by a loop. But if the recursion is multiple, you have to have a way of saving where the "recursion" came from, so that on each iteration you can restart the loop from the right place, and so you end up with either a bunch of goto statements or a very weird looking switch. At that point it's probably better to use real recursion.