code for cycle detection is not finding returning the right number of cycles in directed graph in Java?

Question

I have code written for calculating the no of cycles in a directed graph using DFS. The method to check if a cycle exists or not works fine. I now iterate through all the vertices (which I have in a HashMap) and check if a vertex is unvisited, then check if a cycle exists, if so increment the counter by 1. Now the code breaks, it does not give the right number of cycles eg: for the graph with following edges:

(A B),(B C),(C E),(E A),(B E)

Here is my code;

public int getTotalCyclesinDir(){
    clearAll();
    int count=0;
    for (Vertex v : vertexMap.values()) {
        if (!v.isVisited && isCyclicDirected(v))
            count++;
    }
    return count;
}

public boolean isCyclicDirected(Vertex v){
    if (!v.isVisited){
        v.setVisited(true);
        Iterator<Edge> e = v.adj.iterator();
        while (e.hasNext()){
            Vertex t = e.next().target;
            if (!t.isVisited) {
                if (isCyclicDirected(t))
                    return true;
            }
            else return true;
        }
        return false;
    }
    else return true;
}

Which number do you expect and what does the algorithm return? — Stefan Haustein, Nov 26 '13 at 21:38
I expect 2 because there are two cycles, but it returns only one — brain storm, Nov 26 '13 at 21:50
Also, I see there are too many return statements in my `isCyclicDirected` method. is there a way to simplify it? — brain storm, Nov 26 '13 at 21:51
In if / else, I'd put the short case first, in particular if this can avoid a not. Also, if you return conditionally, you don't really need an explicit else after that. — Stefan Haustein, Nov 26 '13 at 23:01
what you mean by return conditionally? or which line of code you mean? — brain storm, Nov 26 '13 at 23:23
First lines of isCycleDirected could be `if (v.visited) { return true }`. After that, no else or indent. Weed out the simple cases quickly while you progress through the method -- at the end it's harder to remember or look up what a lonely else actually belongs to... — Stefan Haustein, Nov 27 '13 at 01:21
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/42071/discussion-between-user1988876-and-stefan-haustein) — brain storm, Nov 27 '13 at 21:18

score 1 · Accepted Answer · answered Nov 26 '13 at 22:27

1

There are at least two problems with your algorithm:

isCyclicDirected just detects whether there is any cycle in the graph. You can't use it directly to count cycles. For instance, your algorithm will count two cycles in (A B) (B A) (C A) because (C A) connects to a visited node.
If you want to detect two cycles in your example, your detection needs to be edge based instead of vertex based. (B E) forms a cycle but both B and E are marked visited from previous runs.

answered Nov 26 '13 at 22:27

Stefan Haustein

18,427
3
36
51

I see your point. 1) what you mean by edge based, can you elaborate a little 2) in `isCyclicDirected` method, I have too many returns, is that all necessary or any room for simplification..Thanks – brain storm Nov 26 '13 at 22:34
Assume there is a river and you want to count bridges. You start on one side of the bridge and mark the shore as visited. Then you cross the bridge and mark the other side as visited. Then you conclude that there is only one bridge because you have visited both sides. – Stefan Haustein Nov 26 '13 at 23:06
I made changes to code and implemented differently to keep track of edges. Still I have some issues, which I posted here..http://stackoverflow.com/questions/20253255/couting-back-edges-to-get-the-number-of-cylces-in-a-directed-graph – brain storm Nov 27 '13 at 21:19

code for cycle detection is not finding returning the right number of cycles in directed graph in Java?

1 Answers1

Linked