Detect Cycle in a Directed Graph

Detect Cycle in a Directed Graph

Here given code implementation process.

//C Program 
//Detect Cycle in a Directed Graph
#include<stdio.h>
#include<stdlib.h>

struct AjlistNode
{
  int vId;//Vertices id
  struct AjlistNode*next;
};

struct Graph
{
  int data; //node key value
  struct AjlistNode*next;
};

int size; //number of nodes

//set node key value
void setData(struct Graph*node)
{
  if(node!=NULL && size>0)
  {
    int index=0;
    for(index;index<size;index++)
    {
      //set vertic node data
      node[index].data=index;//set node key
      //Initial no AjlistNode
      //set NULL Value
      node[index].next=NULL;
    }
  }else
  {
    printf("Vertic Node is Empty");
  }
}
//Add Edge from Two given Nodes
void addEdge(struct Graph*node, int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
  if(V<size && E <size)
  {
      //first create Adjacency node
    struct AjlistNode *newEdge=(struct AjlistNode*)malloc(
      sizeof(struct AjlistNode)
      );
    if(newEdge!=NULL)
    {

      newEdge->next=NULL;
      newEdge->vId=E;

      struct AjlistNode *temp=node[V].next;

      if(temp==NULL)
      {
        node[V].next=newEdge;
      }else
      {
                //Add node at last
        while(temp->next!=NULL)
        {
          temp=temp->next;
        }      
        temp->next=newEdge;          
      }
    }else
    {
      printf("\n Memory overflow");
    }
  }else
  {
        //not valid Vertices
    printf("Invalid Node Vertices %d  %d", V,E);
  }
}
//Display Adjacency list of vertex
void printGraph(struct Graph*node)
{
  if(node!=NULL)
  {
    struct AjlistNode *temp=NULL;
    for(int index=0;index<size;index++)
    {
      printf("\n Adjacency list of vertex %d  :",index);
      temp=node[index].next;
      while(temp!=NULL)
      {
      //temp->vId is graph node vertices
      //in this case temp->vId is same as 
      //node[temp->vId].data

        printf("  %d",node[temp->vId].data);
        temp=temp->next;
      }
    }
  }else
  {
    printf("Empty Graph");
  }
}

void detect_cycle(int point,int *visit,struct Graph*node,int *status)
{

  if(*status!=-1)
  {
    if(visit[*status]==1 && point == *status)
    {
      *status=-1;
    }else if(visit[point]==1)
    {
      return;
    }
    visit[point]=1;
    struct AjlistNode *temp=node[point].next;
    while(temp!=NULL)
    {
     if(*status!=-1)
     {
       detect_cycle(temp->vId,visit,node,status); 
     }else
     {
      break;
    } 

    temp=temp->next;
  }
}
}
void check_cycle(struct Graph*node)
{

  if(node==NULL)
  {
    printf("Empty Graph\n");
    return;
  }
  printGraph(node);
  int *visit=(int*)calloc(size,sizeof(int));
  int test=0,status=0;
  while(test<size)
  {
    status=test;
    detect_cycle(test,visit,node,&status);
    if(status==-1)
    {
      break;
    }
    for(int index=0;index<size;index++)
    {
     visit[index]=0;
   }
   test++; 
 }
 if(status==-1)
 {

  printf("\n Detect Cycle\n");
}else
{
  printf("\n No Cycle\n");
}
}
int main()
{

  size=6;
  struct Graph*node=node=(struct Graph*)malloc(
    sizeof(struct Graph)*size
    );

  if(node==NULL)
  {
    printf("\n Memory overflow");
  }else
  {
        //First set node keys
    setData(node); 
        //Connected two node with Edges
    addEdge(node,0,1);
    addEdge(node,0,3);
    addEdge(node,1,2);
    addEdge(node,2,5);
    addEdge(node,3,4);
    addEdge(node,4,2);

    check_cycle(node);
    addEdge(node,5,1);
    
    //Case two
    check_cycle(node);
  }  
  return 0;
}

Output

 Adjacency list of vertex 0  :  1  3
 Adjacency list of vertex 1  :  2
 Adjacency list of vertex 2  :  5
 Adjacency list of vertex 3  :  4
 Adjacency list of vertex 4  :  2
 Adjacency list of vertex 5  :
 No Cycle

 Adjacency list of vertex 0  :  1  3
 Adjacency list of vertex 1  :  2
 Adjacency list of vertex 2  :  5
 Adjacency list of vertex 3  :  4
 Adjacency list of vertex 4  :  2
 Adjacency list of vertex 5  :  1
 Detect Cycle
//C++ program
//Detect Cycle in a Directed Graph
#include<iostream>
using namespace std;

struct AjlistNode
{
    int vId;//Vertices id
    struct AjlistNode*next;
};

struct Vertices
{
    int data; //node key value
    struct AjlistNode*next;
};

class Graph
{
	Vertices *node;
    int size;//number of 
public:
	Graph(int);
	void setData();
	void addEdge(int,int);
	void printGraph();
	void check_cycle();
	void detect_cycle(int ,int [],int *);
};
Graph::Graph(int size)
{
	this->size = size;
    //set number of nodes
	node = new Vertices[size];
}
//set node key value
void Graph:: setData()
{
	if(node!=NULL)
	{
		int index=0;

		for(index;index<size;index++)
		{
			//set vertic node data
			node[index].data=index;//set node key
			//Initial no AjlistNode
			//set NULL Value
			node[index].next=NULL;
		}
	}
	else
	{
		cout<<"Vertic Node is Empty"<<endl;
	}
}
//Add Edge from Two given Nodes
void Graph ::addEdge(int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
    if(V<size && E <size)
    {
      //first create Adjacency node
        AjlistNode *newEdge=new AjlistNode;
        
        if(newEdge!=NULL)
        {
            
            newEdge->next=NULL;
            newEdge->vId=E;

            AjlistNode *temp=node[V].next;

            if(temp==NULL)
            {
                node[V].next=newEdge;
            }else{
                //Add node at last
                while(temp->next!=NULL)
                {
                    temp=temp->next;
                }      
                temp->next=newEdge;          
            }
        }
    }else{
        //not valid Vertices
        cout<<"Invalid Node Vertices "<< V<<" "<<E;
    }
}
//Display Adjacency list of vertex
void Graph::printGraph()
{
	if(node!=NULL)
	{
		AjlistNode *temp=NULL;
		for(int index=0; index < size; index++)
		{
			cout<<"\n Adjacency list of vertex "<<index<<" :";
			temp=node[index].next;
			while(temp!=NULL)
			{
                //temp->vId is graph node vertices
                //in this case temp->vId is same as 
                //node[temp->vId].data

				cout<<" "<<node[temp->vId].data;
				temp=temp->next;
			}
		}
	}else
	{
		cout<<"Empty Graph"<<endl;
	}
}
//Detect cycle using DFS
void Graph:: detect_cycle(int point,int visit[],int *status)
{

	if(*status!=-1)
	{
		if(visit[*status]==1 && point == *status)
		{   
			//when visits a node are more than one
			//contain cycle
			*status=-1;
		}
		else if(visit[point]==1)
		{
			//when start and end node are not same then 
			//allow to visit same node more than once
			return;
		}
        //Set visited status 1
		visit[point]=1;

		//Get the address of first edge of  current node
		struct AjlistNode *temp=node[point].next;

		while(temp!=NULL)
		{
			if(*status!=-1)
			{   
				detect_cycle(temp->vId,visit,status); 

			}else
			{
				break;
			} 
            //visit next edge
			temp=temp->next;
		}
	}
}
//method which are manage finding and detecting cycle operation
void Graph:: check_cycle()
{

	if(node==NULL)
	{
		cout<<"Empty Graph\n";
		return;
	}

	printGraph();

    //This are storing the information about visiting node status
	int *visit=new int[size];

	int test=0,status=0;

	while(test < size)
	{
		//Set all visit node as zero
		for(int index=0;index<size;index++)
		{
			visit[index]=0;
		}

		status=test;

		detect_cycle(test,visit,&status);

		if(status==-1)
		{
			break;
		}

		test++; 
	}
	if(status==-1)
	{
		cout<<"\n Detect Cycle\n";
	}else
	{
		cout<<"\n No Cycle\n";
	}
}

int main()
{
    //Create Object
	Graph g(6);
     //First set node keys
	g.setData();



	g.addEdge(0,1);
    g.addEdge(0,3);
    g.addEdge(1,2);
    g.addEdge(2,5);
    g.addEdge(3,4);
    g.addEdge(4,2);

    g.check_cycle();
    
    g.addEdge(5,1);
    
    //Case two
    g.check_cycle();

	return 0;
}

Output

 Adjacency list of vertex 0 : 1 3
 Adjacency list of vertex 1 : 2
 Adjacency list of vertex 2 : 5
 Adjacency list of vertex 3 : 4
 Adjacency list of vertex 4 : 2
 Adjacency list of vertex 5 :
 No Cycle

 Adjacency list of vertex 0 : 1 3
 Adjacency list of vertex 1 : 2
 Adjacency list of vertex 2 : 5
 Adjacency list of vertex 3 : 4
 Adjacency list of vertex 4 : 2
 Adjacency list of vertex 5 : 1
 Detect Cycle
//Java program
//Detect Cycle in a Directed Graph
public class MyGraph
{

    static class AjlistNode
    {
        int id;//Vertices node key
        AjlistNode next;
    }
    static class Vertices
    {
        int data;
        AjlistNode next;
    }

    //number of Vertices
    static int size;
    Vertices node[];
    int status;
    MyGraph(int size)
    {
        //set value
        this.size = size;
        node = new Vertices[size];
        status=0;
    }

    //set initial node value
    public void setData()
    {
        if(node == null)
        {
            System.out.println("\nEmpty Graph");
        }else
        {
            for(int index = 0; index < size; index++)
            {
                // avoid java.lang.nullPointerException
                node[index]=new Vertices(); 
                node[index].data=index;//set your data
                node[index].next=null;
            }
        }
    }
    //Add edge at the end
    public void addEdge(int S,int E)
    {
        if(S < size && E < size && node != null)
        {
            AjlistNode newEdge=new AjlistNode();
            newEdge.id=E;//end node
            newEdge.next=null;
            if(node[S].next==null)
            {
                node[S].next=newEdge;
            }else
            {
                AjlistNode temp=node[S].next;
                
                while(temp.next!=null)
                {
                    temp=temp.next;
                }
                temp.next=newEdge;
            }

        }else{
            System.out.println("\nEmpty Graph");
        }
    }

    public void printGraph()
    {

        if(size>0 && node!=null)
        {
            for(int index=0;index<size;index++)
            {
                System.out.print("\nAdjacency list of vertex "+index+" :");
                
                AjlistNode temp=node[index].next;

                while(temp!=null)
                {
                    System.out.print(" "+node[temp.id].data);

                    temp=temp.next;
                }
            }
        }
    }
    //Detect cycle using DFS
    public void detectCycle(int point,int visit[])
    {

        if( status != -1)
        {
            if(visit[status] == 1 && point ==  status)
            {   
                //when visits a node are more than one
                //contain cycle
                status = -1;
               
            }
            else if(visit[point] == 1)
            {
                //when start and end node are not same then 
                //allow to visit same node more than once
                return;
            }
            //Set visited status 1
            visit[point]=1;

            //Get the address of first edge of  current node
            AjlistNode  temp=node[point].next;

            while(temp!=null)
            {
                if( status != -1)
                {   
                    detectCycle(temp.id,visit); 

                }else
                {
                    break;
                } 
                //visit next edge
                temp=temp.next;
            }
        }
    }
    //method which are manage finding and detecting cycle operation
    public void checkCycle()
    {

        if(node==null)
        {
            System.out.println("Empty Graph");
            return;
        }

        printGraph();

        //This are storing the information about visiting node status
        int []visit=new int[size];

        int test=0;

        while(test < size)
        {
            //Set all visit node as zero
            for(int index=0;index<size;index++)
            {
                visit[index]=0;
            }
            //set instance status
            status = test;

            detectCycle(test,visit);

            if(status==-1)
            {
                break;
            }

            test++; 
        }
        if(status==-1)
        {
            System.out.println("\n Detect Cycle");
        }else
        {
            System.out.println("\n No Cycle");
        }
    }

    public static void main(String[] args) 
    {
        int totalNode=6;
        
        MyGraph g=new MyGraph(totalNode);
        g.setData();
        //Connected two node with Edges

        g.addEdge(0,1);
        g.addEdge(0,3);
        g.addEdge(1,2);
        g.addEdge(2,5);
        g.addEdge(3,4);
        g.addEdge(4,2);

        g.checkCycle();
        
        g.addEdge(5,1);
        
        //Case two
        g.checkCycle();


    }
}

Output

Adjacency list of vertex 0 : 1 3
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 5
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 2
Adjacency list of vertex 5 :
 No Cycle

Adjacency list of vertex 0 : 1 3
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 5
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 2
Adjacency list of vertex 5 : 1
 Detect Cycle
#Python program
# Detect Cycle in a Directed Graph
class AjLinkeNode:
  def __init__(self,data):
    self.id=data
    self.next=None

class Vertices:
  def __init__(self,data):
    self.data=data
    self.next=None

class Graph:
  """Constructor for Graph"""
  def __init__(self, size):
    self.size=size
    self.node=[]
    self.status=0

  def setData(self):
    if(self.size>0 and self.node!=None):
      index=0
      while(index<self.size):
        self.node.append(Vertices(index))
        index+=1
  #add edge
  def addEdge(self,S,E):

    #S and E is two nodes
    if(self.size>S and self.size>E):
      
      new_edge=AjLinkeNode(E)
      
      if(self.node[S].next==None):
        self.node[S].next=new_edge
      else:
        temp=self.node[S].next
        while(temp.next!=None):
          temp=temp.next
        temp.next=new_edge
    else:
      print("Invalid nodes")


  def printGraph(self):

    if(self.size>0 and self.node!=None):

      index=0

      while(index<self.size):

        print("\nAdjacency list of vertex  {0} :".format(index),end=" ")
        
        temp=self.node[index].next
        
        while temp!=None:

          print("  {0}".format(temp.id),end=" ")

          temp=temp.next

        index+=1

  #Detect cycle using DFS
  def detectCycle(self, point, visit):

    if( self.status != -1):
        if(visit[self.status] == 1 and point ==  self.status):   
            #when visits a node are more than one
            #contain cycle
            self.status = -1
           
        
        elif(visit[point] == 1):
            #when start and end node are not same then 
            #allow to visit same node more than once
            return
        
        #Set visited status 1
        visit[point]=1

        #Get the address of first edge of  current node
        temp=self.node[point].next

        while(temp!=None):
            if( self.status != -1):   
                self.detectCycle(temp.id,visit) 

            else:
                break
             
            #visit next edge
            temp=temp.next
        
        
    
    #method which are manage finding and detecting cycle operation
  def checkCycle(self):

      if(self.node==None):
        print("Empty Graph")
        return
      

      self.printGraph()

      #This are storing the information about visiting node status
      visit=[0]*self.size

      test=0

      while(test < self.size):
        index=0
        while (index<self.size):
          visit[index]=0
          index+=1

        
        #set instance status
        self.status = test

        self.detectCycle(test,visit)

        if(self.status==-1):
          break
        
        test+=1
      
      if(self.status==-1):

        print("\n Detect Cycle")
      else:
        print("\n No Cycle")
      
    
        
    
def main():
  g=Graph(6)
  g.setData() 
  #Connected two node with Edges

  g.addEdge(0,1)
  g.addEdge(0,3)
  g.addEdge(1,2)
  g.addEdge(2,5)
  g.addEdge(3,4)
  g.addEdge(4,2)

  g.checkCycle()
  
  g.addEdge(5,1)
  
  #Case two
  g.checkCycle()
if __name__=="__main__":
    main()

Output

Adjacency list of vertex  0 :   1   3 
Adjacency list of vertex  1 :   2 
Adjacency list of vertex  2 :   5 
Adjacency list of vertex  3 :   4 
Adjacency list of vertex  4 :   2 
Adjacency list of vertex  5 : 
 No Cycle

Adjacency list of vertex  0 :   1   3 
Adjacency list of vertex  1 :   2 
Adjacency list of vertex  2 :   5 
Adjacency list of vertex  3 :   4 
Adjacency list of vertex  4 :   2 
Adjacency list of vertex  5 :   1 
 Detect Cycle
//C# Graph 
//Detect Cycle in a Directed Graph
using System;
class AjlistNode
{
	public int key;
	public AjlistNode next;
	public AjlistNode(int key)
	{
		this.key=key;
		this.next=null;
	}
}
class Node
{
	public int data;
	public AjlistNode next;
	public Node(int data)
	{
		this.data=data;
		this.next=null;

	}
}
class MyGraph
{
	//empty array
	public Node[]node= new Node[] {};
	public int size;
	public MyGraph(int size)
	{
		this.size=size;
		node=new Node[size];
	}
	public void setData()
	{
		if(size>0 && this.node!=null)
		{
			for(int index=0;index<size;index++)
			{
				node[index]=new Node(index);
			}

		}
	}
	public void addEdge(int start,int end)
	{
		if(this.size>start && this.size>end)
		{
			AjlistNode newEdge=new AjlistNode(end);

			if(node[start].next==null)
			{
				node[start].next=newEdge;
			}else
			{
				AjlistNode temp=node[start].next;
				while(temp.next!=null)
				{
					temp=temp.next;
				}
				temp.next=newEdge;
			}

		}
	}
	public void printGraph()
	{
		if(size>0 && node.Length>0 && node!=null)
		{
			for(int index=0;index<size;index++)
			{
				Console.Write("\nAdjacency list of vertex {0} :",index);
				AjlistNode temp=node[index].next;
				while(temp!=null)
				{
					Console.Write(" "+node[temp.key].data);
						temp=temp.next;
			    }
			}
		}
	}
	//Detect cycle using DFS
	public void detectCycle(int point,int []visit,ref int status)
	{

		if( status != -1)
		{
			if(visit[status] == 1 && point ==  status)
			{   
				//when visits a node are more than one
				//contain cycle
				status = -1;

			}
			else if(visit[point] == 1)
			{
				//when start and end node are not same then 
				//allow to visit same node more than once
				return;
			}
			//Set visited status 1
			visit[point]=1;

			//Get the address of first edge of  current node
			AjlistNode  temp=node[point].next;

			while(temp!=null)
			{
				if( status != -1)
				{   
					detectCycle(temp.key,visit,ref status); 

				}else
				{
					break;
				} 
				//visit next edge
				temp=temp.next;
			}
		}
	}
	//method which are manage finding and detecting cycle operation
	public void checkCycle()
	{

		if(node==null)
		{
			Console.WriteLine("Empty Graph");
			return;
		}

		printGraph();

		//This are storing the information about visiting node status
		int []visit=new int[size];

		int test=0,status=0;

		while(test < size)
		{
			//Set all visit node as zero
			for(int index=0;index<size;index++)
			{
				visit[index]=0;
			}
			//set instance status
			status = test;

			detectCycle(test,visit,ref status);

			if(status==-1)
			{
				break;
			}

			test++; 
		}
		if(status==-1)
		{
			Console.WriteLine("\n Detect Cycle");
		}else
		{
			Console.WriteLine("\n No Cycle");
		}
	}


}
class Program
{

	static void Main(string[] args)
	{
		//create object
		MyGraph g=new MyGraph(6);
		g.setData();
		//Connected two node with Edges


		g.addEdge(0,1);
		g.addEdge(0,3);
		g.addEdge(1,2);
		g.addEdge(2,5);
		g.addEdge(3,4);
		g.addEdge(4,2);

		g.checkCycle();

		g.addEdge(5,1);

		//Case two
		g.checkCycle();
	}
}

Output

Adjacency list of vertex 0 : 1 3
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 5
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 2
Adjacency list of vertex 5 :
 No Cycle

Adjacency list of vertex 0 : 1 3
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 5
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 2
Adjacency list of vertex 5 : 1
 Detect Cycle
<?php 
/*
* PHP Program 
* Detect Cycle in a Directed Graph
*/

class AjlistNode
{
  public $key;
  public $next;
  function __construct($key)
  {
    $this->key=$key;
    $this->next=NULL;
}
}
class Node
{
  public $data;
  public $next;
  function __construct($data)
  {
    $this->data=$data;
    $this->next=NULL;

}
}
class MyGraph
{

    public $node;
    public $size;
    function __construct($size)
    {
        $this->size=$size;
        $this->node=[];  //empty array
    }
    public function setData()
    {
        if($this->size>0)
        {
            for($index=0;$index<$this->size;$index++)
            {
                $this->node[$index]=new Node($index);
            }

        }
    }
    public function addEdge($start,$end)
    {
        if($this->size > $start && $this->size>$end)
        {
            $newEdge=new AjlistNode($end);
            if($this->node[$start]->next==NULL)
            {
                $this->node[$start]->next=$newEdge;
            }
            else
            {

                $temp=$this->node[$start]->next;
                while($temp->next!=NULL)
                {
                    $temp=$temp->next;
                }
                $temp->next= $newEdge;
            }
        }
    }
    public function printGraph()
    {
        if($this->size>0 && count($this->node)>0 && $this->node!=NULL)
        {
            for($index=0;$index<$this->size;$index++)
            {
                echo ("\nAdjacency list of vertex ".$index." : ");
                $temp=$this->node[$index]->next;
                while($temp!=NULL)
                {
                    echo (" ".$this->node[$temp->key]->data);
                    $temp=$temp->next;
                }
            }
        }
    }

    public function detect_cycle($point,$visit,& $status)
    {

        if($status!=-1)
        {
            if($visit[$status]==1 && $point == $status)
            {
                $status=-1;
            }else if($visit[$point]==1)
            {
                return;
            }
            $visit[$point]=1;
            $temp=$this->node[$point]->next;
            while($temp!=NULL)
            {
                if($status!=-1)
                {
                    $this->detect_cycle($temp->key,$visit,$status);

                }else
                {
                    break;
                } 

                $temp=$temp->next;
            }
        }
    }
    public function check_cycle()
    {

        if($this->node==NULL)
        {
            echo ("Empty Graph\n");
            return;
        }
        $this->printGraph();
        $visit=[];
        $test=0;
        $status=0;
        while($test < $this->size)
        {
            $status=$test;
            for($index=0;$index<$this->size;$index++)
            {
                $visit[$index]=0;
            }
            $this->detect_cycle($test,$visit,$status);
            if($status==-1)
            {
                break;
            }
            $test++; 
        }
        if($status==-1)
        {

            echo ("\n Detect Cycle\n");
        }else
        {
            echo ("\n No Cycle\n");
        }
    }

}


function main()
{
    //create object
    $g=new MyGraph(6);
    $g->setData();

    //Connected two node with Edges
    $g->addEdge(0,1);
    $g->addEdge(0,3);
    $g->addEdge(1,2);
    $g->addEdge(2,5);
    $g->addEdge(3,4);
    $g->addEdge(4,2);

    $g->check_cycle();
    
    $g->addEdge(5,1);
    
    //Case two
    $g->check_cycle();

}
main();
?>

Output

Adjacency list of vertex 0 :  1 3
Adjacency list of vertex 1 :  2
Adjacency list of vertex 2 :  5
Adjacency list of vertex 3 :  4
Adjacency list of vertex 4 :  2
Adjacency list of vertex 5 : 
 No Cycle

Adjacency list of vertex 0 :  1 3
Adjacency list of vertex 1 :  2
Adjacency list of vertex 2 :  5
Adjacency list of vertex 3 :  4
Adjacency list of vertex 4 :  2
Adjacency list of vertex 5 :  1
 Detect Cycle


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved