C++- How to increase stack size to allow more recursion for Kosaraju's Algorithm to compute Strongly Connected Components

Question

I am using a mac, 4GB of RAM and CLion IDE. Compiler is Clang. I need to allow more recursion in this recursive implementation of Depth First Search (currently fails on a graph with 80k nodes).

typedef unordered_map <int, vector<int>> graph;
void DFS (graph &G, int i, vector <bool> &visited) {

    visited[i] = true;
    for (int j = 0; i < G[i].size(); j++) {
        if (!visited[G[i][j]]) {
            DFS(G, G[i][j], visited);
        }
    }
    t++;
    finishingTime[t] = i; //important step
}

This is for an implementation of Kosaraju's algorithm to compute strongly connected components in a graph. https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm I know it is possible to implement DFS as iterative instead but the last step is important, and I can't find a way to include it using iteration. This is because that step is done when DFS fails and backtracking occurs, and recursion provides a very natural way to do this.

So currently I have only two options:

• Increase the stack size to allow more recursion
• Or find an iterative solution

Any ideas how to do either?

Answer 1

As suggested by a comment you can put each call to DFS on a stack allocated on heap made from the parameter list of DFS and then iterate through the stack. Each entry in the stack is essentially a task.

Pseudo-like code:

Start and run "recursion":
nr_of_recursions = 0;
dfs_task_stack.push(first_task_params)
while dfs_task_stack not empty
  DFS(dfs_task_stack.pop)
  nr_of_recursions += 1
end while;
true_finishingtime[] = nr_of_recursions - finishingtime[];

DFS:
for each recursion found
  dfs_task_stack.push(task_params)
end for;
t++; finishingtime...

Not sure of your algorithm but it may be significant which order you push your tasks to the stack, i.e. the order of "for each ...".

I took the liberty of redefining the meaning of "finishingtime" to its inverse. To get the original definition substract the new finishingtime with the total number of recursions made.