Geek Answers Handbook

C ++ - How to increase stack size to provide greater recursion for the Kosaraju algorithm to calculate tightly coupled components

I use a Mac, 4 GB of RAM and a CLion IDE. The compiler is Clang. I need to enable big recursion in this recursive implementation of Depth First Search (currently a crash on the 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 to implement the Kosaraju algorithm for calculating tightly coupled components in a graph. https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm I know that it is possible to implement DFS as iterative, but the last step is important and I cannot find a way to enable it using iteration. This is because this step is performed when DFS is down and backtracking occurs, and recursion provides a very natural way to do this.

Currently, I have only two options:

  • Increase stack size to allow greater recursion.
  • Or find an iterative solution

Any ideas how to do this?

+6
source share
4 answers

As pointed out in a comment, you can push each call to DFS on a stack allocated on the heap, made from a list of DFS options, and then iterate through the stack. Each entry on the stack is essentially a task.

Pseudo-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 about your algorithm, but it may be important which order you push your tasks to the stack, that is, the order is "for everyone ...".

I took the liberty of rethinking the meaning of "end time" to its opposite. To get the original definition, align the new end time with the total number of recursions.

+3
source

I don’t know if this is the best solution, but you can create a list of ready times using only the stack and the visited array of states, having more than one visit state.

The following code is for illustrative purposes only. I didn’t actually test it (just a small {{0, {1}}, {1, <>}, {2, <>}} small test), but I already used this technique the same way as before, for large graphs, and I know this works.

The idea is to keep the visited node on the stack after it is visited until everyone is visited before it pops, thus emulating a recursive call, but with less data being pushed on the stack as well.

 #include <iostream> #include <vector> #include <stack> #include <cassert> #include <unordered_map> using namespace std; typedef enum { vssClean, vssPushed, vssVisited } VerticeStackState; typedef unordered_map <int, vector<int>> graph; void kosarajuBuildFinishOrder(const int inital, graph &G, vector<int> &finish, vector<VerticeStackState> &state, int &lastFinished) { assert(vssClean == state[inital]); std::stack<int> stack; stack.push(inital); state[inital] = vssPushed; int current; while (!stack.empty()) { current = stack.top(); if (vssPushed == state[current]) { state[current] = vssVisited; for (const auto to: G[current]) { if (state[to]==vssClean) { state[to] = vssPushed; stack.push(to); } } } else { assert(vssVisited == state[current]); stack.pop(); finish[--lastFinished] = current; } } } int main() { graph G; G.insert({0, vector<int>(1, 1)}); G.insert({1, vector<int>()}); G.insert({2, vector<int>()}); vector<int> finish(G.size(), 0); vector <VerticeStackState> state(G.size(), vssClean); int lastFinished = G.size(); for (int i=0; i < G.size(); ++i) { if (vssClean == state[i]){ kosarajuBuildFinishOrder(i, G, finish, state, lastFinished); } } for (auto i: finish) { cout << i << " "; } return 0; }
0
source

For one of your options for increasing the size of the stack, you can do this:

 g++ -Wl,--stack,16777216 -o kosaraju.exe kosaraju_stl.cpp

This increases the stack size to 16 MB. Although, as mentioned in previous answers, this just postpones the problem.

0
source 
 typedef unordered_map <int, vector<int>> graph; void DFS (graph &G, vector <bool> &visited) { std::stack<int> stack; stack.push(0); // root int i, j; while(!stack.empty()) { i = stack.pop_back(); visited[i] = true; for (j= (int) G[i].size() -1; j >= 0; j--) { if (!visited[G[i][j]]) { stack.push_back(G[i][j]); } } t++; finishingTime[t] = i; //important step } // end while. }

Anyone can make a programming error, and since I don’t have test data, I can’t verify this, but the same is output?

-one
source

More articles:


All Articles