Why do I get StackOverFlowError when trying to DFS this graph?

Question

I am trying to write an algorithm that determines whether a graph is connected or not. I think my code is almost correct, although I keep getting StackOverFlowError. I personally think because there's a cycle in the graph I'm testing my algorithm with, my code doesn't understand that and comes in a loop. But I'm using an array to see if a node was already visited! So that should not happen! Anyways this is my code:

public int isConnected(String s) 
    {

        int in = nodes.indexOf(s);


        visited[in] = true;
        counter++;
        for(int i = 0; i < listOfChildren(s).size(); i++)
        {
            int ind = nodes.indexOf(listOfChildren(s).get(i));
            if(visited[ind] == false)
            {
                isConnected(listOfChildren(s).get(i));
            }

        }
        System.out.println(counter);
        if(counter == nodes.size())
            return 1;
        return 0;

    }

s is some node I begin with, nodes is an ArrayList of nodes and has the same size(5 in this case) as the array visited. In the beginning visited looks like this: [false false false false false], so none of the nodes was visited. listOfChildren() return an ArrayList of the children(not all of them, just the ones adjacent to the node) of a particular node. I am sure that listOfChildren() works, since I tested it 43545454 times.

Any help is appreciated(with minimum change of the code, if possible). Thanks.

UPDATE:

My graph is directed..

I define visited like this:

private boolean[] visited;

and I set everything in it to false in my constructor this code:

public void setUnvisited()
    {
        visited =  new boolean[nodes.size()];

        for(int i = 0; i < nodes.size(); i++)
        {
            visited[i] = false;
        }
    }

The nodes are strings! visited and nodes have the same length. That's why I can use nodes.indexOf(blabla) for the array visited.

UPDATE2:

This is how the graph looks like: enter image description here

I'm sure the problem is after N3, the algorithm goes in a loop after N3, because it doesn't understand that N1 was already visited. I really don't understand why this happens!

UPDATE3

String have different names and there are no duplicates.. so for example indexOf(nodes.get(2)) gives 2 and not 0 or anything else..

The problem is that after visiting N3 the algorithm should stop and return 0 or 1, but I don't know how to do that :)

After reading your code 10 times, I begin to suspect listOfChildren. Anyway, with a 5-nodes graph, this should take 10 minutes to track down with a debugger, a pencil and a sheet of paper... Use F5 :) — Calvin1602
You are making this really hard by using a String as a node. Why not make a Node class? — Ishtar
Is it possible that listOfChildren is clearing your array visited, maybe by calling setUnvisited()? — rlibby

rlibby rlibby · Accepted Answer · 2011-02-20T12:18:23

The reason you found this so difficult to track down is all the mutable state in your graph class. In particular you have count and visited, the latter being modified by both your methods isConnected and setUnvisited.

You depend on your array visited to tell you when to stop recursing, but accidentally reset the array on every recursive call through your call to listOfChildren.

One way around this to make it so that visited is not a class member. Here's a solution which modifies your code very little:

public boolean isConnected(String s) {
    int nVisited = isConnected(s, new boolean[nodes.size()], 0);
    return nVisited == nodes.size();
}

private int isConnected(String s, boolean[] visited, int counter) 
{

    int in = nodes.indexOf(s);


    visited[in] = true;
    counter++;
    for(int i = 0; i < listOfChildren(s).size(); i++)
    {
        int ind = nodes.indexOf(listOfChildren(s).get(i));
        if(visited[ind] == false)
        {
            counter = isConnected(listOfChildren(s).get(i), visited, counter);
        }

    }
    System.out.println(counter);
    return counter;
}

Since visited and counter are no longer shared, the bug you had is gone. This also solves another bug you had (but didn't notice yet) where only the first isConnected() call works--because in that case you weren't resetting visited or counter appropriately.

A cleaner implementation of the same idea as above:

public boolean isConnected(String s) {
    Set<String> visited = new HashSet<String>();
    isConnected(s, visited);
    return visited.size() == nodes.size();
}

private void isConnected(String s, Set<String> visited) 
{
    visited.add(s);
    for (String child : listOfChildren(s)) {
        if (!visited.contains(s)) {
            isConnected(child, visited);
        }
    }
}

I haven't actually tried to compile or run that, so there may be bugs, but you get the idea, I hope.

Why do I get StackOverFlowError when trying to DFS this graph?

3 Answers