Graph DFS in Java giving stack overflow error on large input

Question

This is for a homework problem- for a given undirected graph, if it is 2-colorable, color it, and if not, output some odd-length loop within it. This method goes through, coloring as it goes, and if it finds a loop it pops back up the stack and outputs the loop. It works fine for a small input, but on a large input gives a stack overflow error. Is there anything I can do to get it to not overflow with a large input?

P.S. I know I should be using getter and setter methods for the variables in Node. Children is a list of all nodes with an edge to the given node.

public static boolean isOddLoop(Node current){
    for(int x=0; x<current.children.size(); x++){
        Node next = current.children.get(x);
        if(next.color==0){ //i.e. is unvisited
            next.color=3-current.color; //colors are 1 and 2, so this sets it to the opposite
            if(isOddLoop(next)){
                System.out.println(current.number + ": " + current.color);
                return true;
            }   
        }
        if(next.color==current.color){
            System.out.println(next.number + ": " + next.color);
            System.out.println(current.number + ": " + current.color);
            return true;
        }
    }
    return false;
}

You could still increase memory for JVM -Xss4m, but that doesn't solve a algorithm problems. — Lukino, Apr 22 '15 at 18:40
Yep, that worked. Thanks! TBH, under time pressure I don't 100% care what the issue is, so long as I can get it to function — Patrick N, Apr 22 '15 at 18:45
This: **next.color=3-current.color; //colors are 1 and 2, so this sets it to the opposite** is not true, because at this point next.color is equal 0 (see if) — Lukino, Apr 22 '15 at 18:46
Sorry, that's unclear. So if the next node's color is 0, that means it's unvisited. The current node has a color of either 1 or 2, so doing 3-current.color gives 2 or 1, the opposite color. — Patrick N, Apr 22 '15 at 18:49

score 1 · Answer 1 · edited May 23 '17 at 12:14

As a comment above says, increasing the memory allocated to your JVM stack will definitely alleviate the problem. See this post here for help on that Java stack overflow error - how to increase the stack size in Eclipse?

A better solution in my opinion is to switch to BFS instead of DFS. Using BFS is also a valid solution for the 2-coloring problem. Furthermore, BFS can be done with a queue and no recursion. Then, you'd have a far smaller stack and be limited by your heap size instead. Note that since you no longer have a stack to keep track of the parent node, you'll need to add a pointer for the parent node in the node class and update it as you go.

Graph DFS in Java giving stack overflow error on large input

1 Answers1