CODEWITHSUNDEEP
recursiongraphcomponents
user1321324
user1321324

Reputation: 131

Finding strongly connected components - no recursion

I need to find strongly connected components of a directed graph. I've decided to use Tarjan's algorithm. So far so good. However, the dataset I need my program to operate on is huge and I get stackoverflow exception. I can't increase the stack size so I need to find another solution.

I could change the recursive algorithm to iterative but I was wondering if there's "a cleaner solution".

I guess not but I'd like to be sure before I start implementing the iterative version.

Thanks for any suggestions!

Upvotes: 3

Views: 2386

Answers (2)

Erfan
Erfan

Reputation: 21

I had this problem too and I found out the best way two solve this problem is to transfer all your code to a new Thread Like this :

public class Class implements Runnable {
    @Override
    public void run() {
        ...
    }
}

and in your Main Class you do this:

public class Main {
    public static void main(String[] args) {
        Thread th = new Thread(null, new Class(), "solution", 32 << 20);
        th.start();
    }
} 

Thread(ThreadGroup group, Runnable target, String name, long stackSize)

The first parameter is null, second parameter is your class you want to run on this thread, third parameter is just a name its not very important, and the last parameter is the stack size you want to assign to this thread and I think in this example stack size is 2^32 bytes (I'm not sure!)

Here you can find out more about Thread in Java: https://docs.oracle.com/javase/7/docs/api/java/lang/Thread.html

These examples are in Java; you can do the same in any other object oriented language.

Upvotes: 0

voidengine
voidengine

Reputation: 2579

Known algorithms for finding SCC are all based on DFS, which is recursive in nature, so you've basically got these options:

  • live with the recursion. Not really an option, recursion for every node will fill the stack quickly
  • rewrite recursion with iteration, provide your own stack for the DFS. Not that hard, I'd recommend this one
  • invent a non-recursive algorithm. Good luck in that case

Upvotes: 2

Related Questions