Non recursive depth first search on graphs for Delphi

I am searching for a non-recursive depth first search algorithm on graphs in Pascal (Delphi).

I need DFS for computing strongly or bi-connected components of large graphs. Currently I am using a recursive variant of the algorithm: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

The problem is that for such algorithm I must define a large amount of memory to be used for a stack and that m开发者_高级运维akes later problems in Windows 7, where Open and Save Dialogs do not work because of several threads generated....

So again: I do not see how to rewrite the Tarjan DFS algorithm to work without recursion. Do you have any suggestion - or point to a non recursice algorithm for depth first search on graphs?

Thanks.

The algorithm as described on Wikipedia looks to reasonably easily be made non-recursive with an explicit stack. Starting out with that (included here for reference, in case Wikipedia changes):

Input: Graph G = (V, E)

index = 0                                         // DFS node number counter 
S = empty                                         // An empty stack of node
for all v in V do
  if (v.index is undefined)                       // Start a DFS at each node
    tarjan(v)                                     // we haven't visited yet

procedure tarjan(v)
  v.index = index                                 // Set the depth index for v
  v.lowlink = index                               // SHOULD BE v.lowlink = MAX_INT?
  index = index + 1
  S.push(v)                                       // Push v on the stack
  for all (v, v') in E do                         // Consider successors of v
    if (v'.index is undefined)                    // Was successor v' visited?
        tarjan(v')                                // Recurse
        v.lowlink = min(v.lowlink, v'.lowlink)
    else if (v' is in S)                          // Was successor v' in stack S? 
        v.lowlink = min(v.lowlink, v'.index )     // v' is in stack but it isn't in the dfs tree
  if (v.lowlink == v.index)                       // Is v the root of an SCC?
    print "SCC:"
    repeat
      v' = S.pop                                  
      print v'
    until (v' == v)

Step 1: Remove loops containing recursion, adding labels and gotos. This is necessary to make loop variables explicit, savable and restorable (needed during recursion-simulation with stacks). A label needs to be added after tarjan()'s return, as we'll jump to it in a moment.

procedure tarjan(v)
  v.index = index                                 // Set the depth index for v
  v.lowlink = index                               // SHOULD BE v.lowlink = MAX_INT?
  index = index + 1
  S.push(v)                                       // Push v on the stack
  succ = all (v, v') in E      // Consider successors of v
  succIndex = 0                // presume succ is 0-based
loop_top:
  if succIndex >= Length(succ) goto skip_loop
  v' = succ[succIndex]
  if (v'.index is undefined)                    // Was successor v' visited?
      tarjan(v')                                // Recurse
recursion_returned:
      v.lowlink = min(v.lowlink, v'.lowlink)
  else if (v' is in S)                          // Was successor v' in stack S? 
      v.lowlink = min(v.lowlink, v'.index )     // v' is in stack but it isn't in the dfs tree
  succIndex = succIndex + 1
  goto loop_top
skip_loop:
  if (v.lowlink == v.index)                       // Is v the root of an SCC?
    print "SCC:"
    repeat
      v' = S.pop                                  
      print v'
    until (v' == v)

Step 2: Introduce a stack which contains all the relevant state for storing our position and computation in the loop at any point where we may be returning from recursion, or starting out at the top of the loop.

The stack:

T = empty // T will be our stack, storing (v, v', succ, succIndex, state)

state is an enumeration (TopState, ReturnedState) encoding the location in the procedure. Here's the procedure rewritten to use this stack and state rather than recursion:

procedure tarjan(v)
  while (T is not empty) do
    (v, v', succ, succIndex, state) = T.pop
    case state of
      TopState: goto top
      ReturnedState: goto recursion_returned
    end case
top:
    v.index = index                                 // Set the depth index for v
    v.lowlink = index                               // SHOULD BE v.lowlink = MAX_INT?
    index = index + 1
    S.push(v)                                       // Push v on the stack
    succ = all (v, v') in E      // Consider successors of v
    succIndex = 0                // presume succ is 0-based
loop_top:
    if succIndex >= Length(succ) goto skip_loop
    v' = succ[succIndex]
    if (v'.index is undefined)                    // Was successor v' visited?
      // instead of recursing, set up state for return and top and iterate
      T.push(v, v', succ, succIndex, ReturnedState) // this is where we return to
      T.push(v', empty, empty, empty, TopState) // but this is where we go first
      continue // continue the while loop at top
recursion_returned:
      v.lowlink = min(v.lowlink, v'.lowlink)
    else if (v' is in S)                          // Was successor v' in stack S? 
      v.lowlink = min(v.lowlink, v'.index )     // v' is in stack but it isn't in the dfs tree
    succIndex = succIndex + 1
    goto loop_top
skip_loop:
    if (v.lowlink == v.index)                       // Is v the root of an SCC?
    print "SCC:"
    repeat
      v' = S.pop                                  
      print v'
    until (v' == v)

Step 3: Finally, we need to make sure the entry conditions are correct, for the top-level code which calls tarjan. That can easily be done by an initial push:

procedure tarjan(v)
  T.push(v, empty, empty, empty, TopState)
  while (T is not empty) do
    (v, v', succ, succIndex, state) = T.pop
    case state of
      TopState: goto top
      ReturnedState: goto recursion_returned
    end case
top:
    v.index = index                                 // Set the depth index for v
    v.lowlink = index                               // SHOULD BE v.lowlink = MAX_INT?
    index = index + 1
    S.push(v)                                       // Push v on the stack
    succ = all (v, v') in E      // Consider successors of v
    succIndex = 0                // presume succ is 0-based
loop_top:
    if succIndex >= Length(succ) goto skip_loop
    v' = succ[succIndex]
    if (v'.index is undefined)                    // Was successor v' visited?
      // instead of recursing, set up state for return and top and iterate
      T.push(v, v', succ, succIndex, ReturnedState) // this is where we return to
      T.push(v', empty, empty, empty, TopState) // but this is where we go first
      continue // continue the while loop at top
recursion_returned:
      v.lowlink = min(v.lowlink, v'.lowlink)
    else if (v' is in S)                          // Was successor v' in stack S? 
      v.lowlink = min(v.lowlink, v'.index )     // v' is in stack but it isn't in the dfs tree
    succIndex = succIndex + 1
    goto loop_top
skip_loop:
    if (v.lowlink == v.index)                       // Is v the root of an SCC?
    print "SCC:"
    repeat
      v' = S.pop                                  
      print v'
    until (v' == v)

It could also be done by a jump, jumping immediately to top. The code can be further cleaned up, perhaps converted to use a while or repeat loop to eliminate some of the gotos, etc., but the above should be at least functionally equivalent, eliminating the explicit recursion.

Eliminating recursion in Tarjan's algorithm is difficult. Certainly, it requires a complex code. Kosaraju's algorithm is an alternative solution. I believe that eliminating recursion in Kosaraju's algorithm is much easier.

You can try yourself with Kosaraju's algorithm described in Wikipedia or follow the following instructions.

1. List nodes in the order of DFS.

Let G1 be a directed graph, and List be an empty stack.

For each nodes v not in List, perform DFS starting at v. Each time that DFS finishes at node u, push u onto List.

To DFS without recursion, create a stack named st. Each elements in st represent a command.

• A positive element x means "visit node x if x is not visited".
  • Each time visiting node x, push -x into stack, then push nodes y adjacent with x.
• A negative element -x means "finish visiting x".
  • Each time finishing visiting x, push x onto List.

Consider the following code:

const int N = 100005;
bool Dfs[N];                // check if a node u is visited
vector<int> List;

void dfs(int U) {
    stack<int> st; st.push(U);
    while (st.size()) {
        int u=st.top(); st.pop();
        if (u<0) {
            List.push_back(-u);
        } else if (!Dfs[u]) {
            Dfs[u] = true;
            st.push(-u);
            // for each node v adjacent with u in G1
            for (int i=0; int v=a1[u][i]; i++)
            if (!Dfs[v]) st.push(v);
        }
    }
}

for (int i=1; i<=n; i++)
    if (!Dfs[i]) dfs(i);

Now, List is created.

2. BFS according to List

Let G2 be the transpose graph of G1 (Reverse the directions of all arcs in G1 to obtain the transpose graph G2).

While List is not empty, pop the top node v from List. Perform a BFS in G2 starting at v, the visited nodes merges into a new SCC. Remove such nodes from both G2 and List.

Consider following code:

bool Bfs[N];
int Group[N]; // the result

void bfs(int U) {
    queue<int> qu; 
    qu.push(U); Bfs[U]=true;
    while (qu.size()) {
        int u=qu.front(); qu.pop();
        Group[u]=U;
        // for each node v adjacent with u in G2
        for (int i=0; int v=a2[u][i]; i++)
        if (!Bfs[v]) { qu.push(v); Bfs[v]=true; }
    }
}

for (int i=List.size()-1; i>=0; i--)
    if (!Bfs[List[i]]) bfs(List[i]);

The result is located in array Group.

While I don't have access to your data set, it's rather common to have accidental incorrect recursion that doesn't find the base case in all the correct circumstances, or else there may be a cycle in your graph. I would check these two things before moving on. For instance, are there more function descents than you have nodes in the tree?

Barring that, your data set might just be so large as to be overflowing the process stack. If this is the case, I would recommend writing an iterative version of the algorithm that uses the stack that you provide to it. The stack should live in heap-space, not stack space. You'll need to keep the context of the search on your own rather than letting the algorithm do it.

This algorithm is a recursive algorithm. Period. You don't need to write a function that calls itself, but in the end you'll still need to keep track of where you've been, and the order your visited nodes.