Count number of cycles in a Directed graph

Question:

Write a program which gives us the number of cycles in a Directed graph.

Approach 1:

I know that we can detect cycles in graph using Depth First Search and return the answer in terms of a simple boolean value. I have written a code for this below. However, I am trying to implement a counter in this code which increments every time a cycle is detected. But I don't seem to get the right answer no matter where I implement the counter! (I've written the increment statements in comments)

I am also worried that DFS is not the right approach to chose for this question because there might be some common edges between the cycles.

The cycle detection algorithm is taken from: https://www.geeksforgeeks.org/detect-cycle-in-a-graph/

The code given below, produces an output:

for the graph:

(Here it says 0 cycles, because of the commented count is incremented)

Code:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Graph 
{   
    static int count = 0; //counter initialised
    private final int V;
    private final List<List<Integer>> adj;

    public Graph(int V)
    {
        this.V = V;
        adj = new ArrayList<>(V);
        
        for (int i = 0; i < V; i++)
            adj.add(new LinkedList<>());
    }
    
    private boolean isCyclicUtil(int i, boolean[] visited,boolean[] recStack)
    {
        if (recStack[i])
            return true; //count++;

        if (visited[i])
            return false;
            
        visited[i] = true;

        recStack[i] = true;
        List<Integer> children = adj.get(i);
        
        for (Integer c: children)
            if (isCyclicUtil(c, visited, recStack))
                return true; 
                
        recStack[i] = false;

        return false;
    }

    private void addEdge(int source, int dest) {
        adj.get(source).add(dest);
    }
    
    private boolean isCyclic()
    {
        boolean[] visited = new boolean[V];
        boolean[] recStack = new boolean[V];
        for (int i = 0; i < V; i++)
            if (isCyclicUtil(i, visited, recStack))
                return true; //count++;
        return false;
    }
    
    public static void main(String[] args)
    {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);
        
        if(graph.isCyclic())
            System.out.println("Graph contains cycles");
        else
            System.out.println("Graph doesn't contains "+count+" cycles");
    }
}

I also wondered whether I can find the solution using graph coloring method, and this is what I was able to dig up code from: https://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

APPROACH 2:

Algorithm:

• Create a recursive function that takes the edge and color array (this can be also kept as a global variable)

• Mark the current node as GREY.

• Traverse all the adjacent nodes and if any node is marked GREY then
  return true as a loop is bound to exist.

• If any adjacent vertex is WHITE then call the recursive function for that node.

• If the function returns true. Return true.

• If no adjacent node is grey or has not returned true then mark the current Node as BLACK and return false.

Code:

import java.io.*;
import java.util.*;

class GFG
{

    // A DFS based approach to find if there is a cycle
    // in a directed graph. This approach strictly follows
    // the algorithm given in CLRS book.
    static int WHITE = 0, GRAY = 1, BLACK = 2;

    // Graph class represents a directed graph using
    // adjacency list representation
    static class Graph
    {
            int V;
            LinkedList<Integer>[] adjList;
            
            // Constructor
            Graph(int ver)
            {
                V = ver;
                adjList = new LinkedList[V];
                for (int i = 0; i < V; i++)
                    adjList[i] = new LinkedList<>();
            }
    }

    // Utility function to add an edge
    static void addEdge(Graph g, int u, int v)
    {
            g.adjList[u].add(v); // Add v to u's list.
    }

    // Recursive function to find if there is back edge
    // in DFS subtree tree rooted with 'u'
    static boolean DFSUtil(Graph g, int u, int[] color)
    {
            // GRAY : This vertex is being processed (DFS
            // for this vertex has started, but not
            // ended (or this vertex is in function
            // call stack)
            color[u] = GRAY;
            
            // Iterate through all adjacent vertices
            for (Integer in : g.adjList[u])
            {
                // If there is
                if (color[in] == GRAY)
                    return true;

                // If v is not processed and there is a back
                // edge in subtree rooted with v
                if (color[in] == WHITE && DFSUtil(g, in, color) == true)
                    return true;
            }

            // Mark this vertex as processed
            color[u] = BLACK;
            return false;
    }

    // Returns true if there is a cycle in graph
    static boolean isCyclic(Graph g)
    {
            // Initialize color of all vertices as WHITE
            int[] color = new int[g.V];
            for (int i = 0; i < g.V; i++)
            {
                color[i] = WHITE;
            }

            // Do a DFS traversal beginning with all
            // vertices
            for (int i = 0; i < g.V; i++)
            {
                if (color[i] == WHITE)
                {
                    if(DFSUtil(g, i, color) == true)
                        return true;
                }
            }
            return false;

    }

    // Driver code to test above
    public static void main(String args[])
    {
            // Create a graph given in the above diagram
            Graph g = new Graph(4);
            addEdge(g, 0, 1);
            addEdge(g, 0, 2);
            addEdge(g, 1, 2);
            addEdge(g, 2, 0);
            addEdge(g, 2, 3);
            addEdge(g, 3, 3);
            if (isCyclic(g))
                System.out.println("Graph contains cycle");
            else
                System.out.println("Graph doesn't contain cycle");
    }
}

It took me a while, but I finally found a solution to this problem using DFS and Graph colouring method. I'm still working on ways to simplify it, but this code works!

//Program to count the number of cycles in a Directed Graph.

import java.util.*;
class dir
{

    public static int WHITE = 0, GRAY = 1, BLACK = 2;
    public static int count=0;
    // Graph class represents a directed graph using
    // adjacency list representation
    public static class Graph
    {
            int V;
            LinkedList<Integer>[] adjList;
            @SuppressWarnings("unchecked")
            Graph(int ver)
            {
                V = ver;
                adjList = new LinkedList[V];
                for (int i = 0; i < V; i++)
                    adjList[i] = new LinkedList<>();
            }
    }
    
    //function to add an edge
    public static void addEdge(Graph g, int u, int v)
    {
            g.adjList[u].add(v); 
    }

    // Recursive function to find if there is back edge
    // in DFS subtree tree rooted with 'u'
    public static boolean DFSUtil(Graph g, int u, int[] color)
    {
            color[u] = GRAY;
            // Iterate through all adjacent vertices
            for (Integer in : g.adjList[u])
            {
                // If there is
                if (color[in] == GRAY)
                    return true;
                //If v is not processed and there is a back
                // edge in subtree rooted with v
                if (color[in] == WHITE && DFSUtil(g, in, color) == true)
                    return true;
            }
            // Mark this vertex as processed
            color[u] = BLACK;
            return false;
    }

    // Returns number of cycles.
    public static int isCyclic(Graph g)
    {
            // Initialize color of all vertices as WHITE
            int[] color = new int[g.V];
            for (int i = 0; i < g.V; i++)
            {
                color[i] = WHITE;
            }
            
            // Do a traversal beginning with all vertices
            for (int i = 0; i < g.V; i++)
            {
                if (color[i] == WHITE)
                {
                    if(DFSUtil(g, i, color) == true)
                        count++; 
                }
            }
            return count;

    }

    //Driver Code
    public static void main(String args[])
    {
            //Modify edges accordingly
            Graph g = new Graph(7);
            addEdge(g, 0, 1);
            addEdge(g, 4, 0);
            addEdge(g, 4, 1);
            addEdge(g, 4, 3);
            addEdge(g, 3, 4);
            addEdge(g, 1, 3);
            addEdge(g, 2, 1);
            addEdge(g, 3, 2);
            if (isCyclic(g)>0)
            {
                System.out.println("Cycle detected");
                System.out.println("Graph contains "+count+" cycles");
            }
            else
                {
                System.out.println("Graph doesn't contain cycle");
                }
    }
}