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

algorithm, c++, recursion

Solution

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.

Problem

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?

Original source