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:

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 :)

Answer 1

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.