title: couting back edges to get the number of cylces in a directed graph
body: <p>I have been writing code to get all the possible cycles in a directed graph. <a href="http://www.geeksforgeeks.org/detect-cycle-in-a-graph/" rel="nofollow noreferrer">Here</a> 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 <code>count</code> 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 <code>edgeMap</code> that stores all the back edges seems to give the correct number of cycles in some graphs but not all.</p>
  
  <p>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 helpful<img src="https://i.stack.imgur.com/qqRAq.png" alt="enter image description here"></p>
  
  <pre><code>public int allCyclesDirectedmain(){
          clearAll();
          int count=0;
          Map&lt;Vertex, Vertex&gt; edgeMap = new HashMap&lt;&gt;();
  
  
          for (Vertex v : vertexMap.values()) {
              if (!v.isVisited &amp;&amp; allCyclesDirected(v,edgeMap))
                  count++;
          }
          System.out.println(edgeMap);
          return count;
  
      }
  public boolean allCyclesDirected(Vertex v, Map&lt;Vertex, Vertex&gt; edgeMap ){
          if (!v.isVisited){
              v.setVisited(true);
              Iterator&lt;Edge&gt; e = v.adj.iterator();
              while (e.hasNext()){
                      Vertex t = e.next().target;
                      if (!t.isVisited &amp;&amp; allCyclesDirected(t,edgeMap)){
                          edgeMap.put(v, t);
                              return true;
                      }
                      else 
                              return true;
                      }
                  }
          return false;
      }
  </code></pre>