Non-recursive depth of first chart search for Delphi

Question

I am looking for a search algorithm without recursive depth on graphs in Pascal (Delphi).

I need DFS to compute strongly or doubly connected components of large graphs. I am currently using a recursive version of the algorithm: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

The problem is that for such an algorithm I have to determine the large amount of memory that will be used for the stack, and which will continue to work in Windows 7, where Open and Save Dialogs do not work due to several threads generated ....

So again: I don’t see how to rewrite the Tarjan DFS algorithm to work without recursion. Do you have any suggestions - or point to an algorithm without recursion for the first depth search on graphs?

Thanks.

Answer 1

The algorithm described on Wikipedia looks easy enough to make non-recursive with an explicit stack. Starting from this (included here for reference, in case of a change in Wikipedia):

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 by adding labels and gotos. This is necessary in order to make loop variables clear, convenient, and recoverable (necessary during recursion-modeling with stacks). The label must be added after tarjan() returns, since we will get 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: Imagine a stack that contains all the appropriate state to store our position and calculate in a loop at any point where we can return from recursion, or start at the top of the loop.

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 the procedure is rewritten to use this stack and state, not 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 that the input conditions are correct for the top-level code that calls tarjan. This is easy to do with an initial click:

 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) 

You can also do this with a jump, immediately jumping to top . The code can be further cleaned up, possibly converted to use a while or repeat loop to eliminate some of gotos, etc., but the above should be at least functionally equivalent, excluding explicit recursion.

Answer 2

The elimination of recursion in the Tarjan algorithm is difficult. Of course, this requires complex code. Kosaraju algorithm is an alternative solution. I find that eliminating recursion in the Kosaraju algorithm is much easier.

You can try yourself using the Kosaraju algorithm described on Wikipedia, or follow the following instructions.

1. The list of nodes in DFS order.

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

For each node v not in List run DFS starting with v . Each time DFS ends with node u , click u on List .

In DFS without recursion, create a stack called st . Each element in st is a command.

• A positive x means "visit node x if x is not visited."
  • Each time visiting node x, push -x onto the stack, then push the nodes y adjacent to x.
• The negative element -x means "end visit x".
  • Each time you finish visiting x, click x on 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); 

List is now created.

2. BFS as per List

Let G2 be the transposed graph G1 (Let's reverse the directions of all arcs in G1 to get the transposition graph G2 ).

Until List is empty, put the top node v from List . Run BFS on G2 starting at v , visited nodes merge into a new SCC. Remove such nodes from G2 and List .

Consider the 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 in the Group array.

Answer 3

As long as I don’t have access to your dataset, quite often there is a random incorrect recursion that does not find the base case in all the right circumstances, otherwise there might be a cycle on your chart. I would check out these two things before moving on. For example, is there more descent functions than you have nodes in the tree?

Preventing your data set from being so large as to overflow the process stack. If so, I would recommend writing an iterative version of an algorithm that uses the stack that you provide it. The stack must be in the heap space, not in the stack. You will need to save the search context yourself, and not let the algorithm do this.

This algorithm is a recursive algorithm. Period. You do not need to write a function that calls itself, but in the end you will still need to keep track of where you were and the order of your visited nodes.