Graph Cycle Detection with Java

Question

I'm studying cycle detection in DAGs, and I've implemented my version of the algorithm using DFS, here is the code;

public class DFS {

    public static boolean hasCycle(Graph graph) {

        for (Vertex vertex : graph.getVertices()) {
            if (detectCycle(graph, vertex)) {
                return true;
            }
        }

        return false;

    }

    private static boolean detectCycle(Graph graph, Vertex root) {

        for (Vertex vertex : graph.getVertices()) {
            vertex.setBeingVisited(false);
            vertex.setVisited(false);
        }

        return DFS.dfs(graph, root);

    }

    private static boolean dfs(Graph graph, Vertex root) {
        root.setBeingVisited(true);

        for (Edge edge : root.getNeighbors()) {
            Vertex neighborVertex = edge.getEndPoint();
            if (neighborVertex.isBeingVisited()) {
                return true;
            } else if (!neighborVertex.isVisited()) {
                DFS.dfs(graph, neighborVertex);
            }
        }

        root.setVisited(true);
        root.setBeingVisited(false);
        return false;

    }

}

And here is the testing class:

public class App {

    public static void main(String[] args) {
        Vertex a = new Vertex("A");
        Vertex b = new Vertex("B");
        Vertex c = new Vertex("C");
        Vertex d = new Vertex("D");
        Vertex e = new Vertex("E");

        Edge e1 = new Edge(a, b);
        Edge e2 = new Edge(a, c);
        a.addNeighbor(e1);
        a.addNeighbor(e2);

        Edge e3 = new Edge(b, d);
        b.addNeighbor(e3);

        Edge e4 = new Edge(c, e);
        c.addNeighbor(e4);

        Edge e5 = new Edge(d, a);
        d.addNeighbor(e5);

        List<Vertex> vertices = new ArrayList<>();
        vertices.add(a);
        vertices.add(b);
        vertices.add(c);
        vertices.add(d);
        vertices.add(e);

        Graph graph = new Graph(vertices);
        System.out.println(DFS.hasCycle(graph));
        if (DFS.hasCycle(graph)) {
            System.out.println("It does have a cycle!");
        } else {
            System.out.println("It doesn't have cycle!");
        }

    }

}

For this case in particular the result should print that the graph has a cycle since the graph we are dealing with is this one:

   >b --> d
  /       |
 a<-------
  \
   > c --> e

But my output is getting false, like there is no cycle, I just can't find the bug in my implementation. Can someone help ?

ram · Accepted Answer · 2017-06-14T14:20:38.097

1

You are missing the purpose of the line:

DFS.dfs(graph, neighborVertex);

If this call returns true, the method also should return true.

EDIT: It should be like this:

private static boolean dfs(Graph graph, Vertex root) {
    root.setBeingVisited(true);

    for (Edge edge : root.getNeighbors()) {
        Vertex neighborVertex = edge.getEndPoint();
        if (neighborVertex.isBeingVisited()) {
            return true;
        } else if (!neighborVertex.isVisited() && DFS.dfs(graph, neighborVertex)) {
            return true;
        }
    }

    root.setVisited(true);
    root.setBeingVisited(false);
    return false;
}

edited Jun 14 '17 at 14:20

answered Jun 14 '17 at 02:19

ram

1,099
1
7
22

changing to ' if (neighborVertex.isBeingVisited()) { return true; } if (!neighborVertex.isVisited()) { return DFS.dfs(graph, neighborVertex); }' made it work! thanks!! – Pj- Jun 14 '17 at 02:26
@Pj- actually this is not correct, although it might work for your particular example. If you directly return what dfs returns, then you are not updating `beingVisited` and `visited` properties of `root`, which will cause it to fail: a simple example to fail is a -> b -> c, and process in order (b, a, c): it will say it has cycle. Read my answer correctly: return `true` only if `DFS.dfs(graph, neighborVertex)` returns `true`. If `false`, continue to process other neighbours. I hope it is clear now. – ram Jun 14 '17 at 02:32
Oh im sorry, are you saying that it should be like: 'if (!neighborVertex.isVisited()) { if (DFS.dfs(graph, neighborVertex)) { return true; } else { DFS.dfs(graph, neighborVertex); } }' ? – Pj- Jun 14 '17 at 02:56

Graph Cycle Detection with Java

1 Answers1