3

I have been writing code to get all the possible cycles in a directed graph. Here is an implementation that keeps track of back edges and whenever one back edge is found, it return true that one cycle is detected. I extended this to the following: calculate all the possible back edges in a tree, the number of back edges should give the number of cycles. Not sure if this correct. using this, I implemented the following: The count variable below is not useful. Initially I had it to give the count of each cycles. but that does not give the correct answer. but the size of edgeMap that stores all the back edges seems to give the correct number of cycles in some graphs but not all.

The code works for G2 an G3 in the picture, but fails for G1. (G1 has only two cycles, but I get three back edges). any suggestions of where I could be going wrong will be helpfulenter image description here

public int allCyclesDirectedmain(){
        clearAll();
        int count=0;
        Map<Vertex, Vertex> edgeMap = new HashMap<>();


        for (Vertex v : vertexMap.values()) {
            if (!v.isVisited && allCyclesDirected(v,edgeMap))
                count++;
        }
        System.out.println(edgeMap);
        return count;

    }
public boolean allCyclesDirected(Vertex v, Map<Vertex, Vertex> edgeMap ){
        if (!v.isVisited){
            v.setVisited(true);
            Iterator<Edge> e = v.adj.iterator();
            while (e.hasNext()){
                    Vertex t = e.next().target;
                    if (!t.isVisited && allCyclesDirected(t,edgeMap)){
                        edgeMap.put(v, t);
                            return true;
                    }
                    else 
                            return true;
                    }
                }
        return false;
    }
eagertoLearn
  • 9,772
  • 23
  • 80
  • 122
  • I think you are looking at a non-trivial problem with some known solutions already. Have you looked at previous answers here at SO? For example this: http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph One of the answers there mention an algorithm in Java for counting the cycles: http://normalisiert.de/code/java/elementaryCycles.zip – Ricardo Nov 27 '13 at 22:04
  • @Ricardo: I looked at it. It is not trivial, I agree. There was a post there on the link you provided by Himadri Choudhury. That solution seems elegant, but it is not clear, I left a note there, but no one replied. – brain storm Nov 27 '13 at 22:15

2 Answers2

3

The number of backedges is not the number of cycles, because a single backedge can participate in more than one cycle.

In your graph G1, let's trace the progression of the depth-first search from A: it visits A->B->C, and then has a choice between D and E. Let's suppose it takes D. Then it visits E, and finds one backedge going to B. Thing is, the EB edge participates in both the BCE cycle and the BCDE cycle!

Here's another example: consider the complete directed graph on four nodes. There are 12 edges, but

  • 6 two-vertex cycles
  • 8 three-vertex cycles
  • 6 four-vertex cycles

for a total of 20 cycles - more than there are edges in the graph! In fact, there can be an exponential number of cycles in a graph, and the problem of counting them, called #CYCLE, is not computable in polynomial time if P != NP.

Andy Jones
  • 4,723
  • 2
  • 19
  • 24
  • Suppose each time we encounter a back edge, we record the back edge and all the edges going back to the adjacent ancestor node from the current node (the predecessor path to the adjacent node). Does that at least mean we have all the edges participating in all the cycles? – Kun May 31 '21 at 22:46
1

As previously mentioned , a single backedge could contribute in more than one cycle so number of backedges are not same as number of cycle. One could use Johnson's algorithm to find all simple cycles in a graph.

Shreyas SIngh
  • 21
  • 1