Transitive Closure of a Graph using DFS

Transitive Closure of a Graph

Here given code implementation process.

//C Program Transitive Closure of a Graph using DFS
#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;
};
void setData(struct Graph *);
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 fill_path(int point,int *visit,struct Graph*node){

    if(visit[point]==1){
        return;
    }else{
        visit[point]=1;
        struct AjlistNode *temp=node[point].next;
        while(temp!=NULL){
           fill_path(temp->vId,visit,node); 
           temp=temp->next;
        }
    }
}
int main(){
    
    size=7;
    struct Graph*node=NULL;


    int *visit=(int*)calloc(size,sizeof(int));

    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,6);
        addEdge(node,1,0);
        addEdge(node,1,4);
        addEdge(node,2,5);
        addEdge(node,3,1);
        addEdge(node,3,2);
        addEdge(node,3,6);
        addEdge(node,4,3);
        addEdge(node,5,0);
        
        printGraph(node);
     
        
        int test=0,status=1;
        printf("\n Transitive Closure");
        while(test<size){
             printf("\n");
            status=1;
            fill_path(test,visit,node);
        
            for(int index=0;index<size;index++){
                
               printf("  %d",visit[index]);
               visit[index]=0;
            }
            test++; 
        }
    }  
    return 0;
}

Output

 Adjacency list of vertex 0  :  6
 Adjacency list of vertex 1  :  0  4
 Adjacency list of vertex 2  :  5
 Adjacency list of vertex 3  :  1  2  6
 Adjacency list of vertex 4  :  3
 Adjacency list of vertex 5  :  0
 Adjacency list of vertex 6  :
 Transitive Closure
  1  0  0  0  0  0  1
  1  1  1  1  1  1  1
  1  0  1  0  0  1  1
  1  1  1  1  1  1  1
  1  1  1  1  1  1  1
  1  0  0  0  0  1  1
  0  0  0  0  0  0  1
//C++ Program,Transitive Closure of a Graph using DFS
#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;

public:
    int size;//number of node
    Graph(int);
    void setData();
    void addEdge(int,int);
    void printGraph();
    void check_vertex(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;
    }
}
//Check Path of given vertex
void Graph:: check_vertex(int point,int *visit){

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

int main()
{   

    int size = 7;
    //Create Object
    Graph g(size);
    //First set node keys
    g.setData(); 

   //Connected two node with Edges
    g.addEdge(0,6);
    g.addEdge(1,0);
    g.addEdge(1,4);
    g.addEdge(2,5);
    g.addEdge(3,1);
    g.addEdge(3,2);
    g.addEdge(3,6);
    g.addEdge(4,3);
    g.addEdge(5,0);

    g.printGraph();

    //Create array
    int visit[size]={0};

    cout<<"\n  Transitive Closure :"<<endl;
    int test=0;
    
    while(test<size)
    {
        g.check_vertex(test,visit);
        
        //When current node are visit other nodes
        //Then that is a Mother Vertex
        for(int index=0;index<size;index++)
        {

            cout<<"  "<<visit[index];
            visit[index]=0;
        }
        cout<<"\n";
        test++;
    }
    return 0;
}

Output

 Adjacency list of vertex 0 : 6
 Adjacency list of vertex 1 : 0 4
 Adjacency list of vertex 2 : 5
 Adjacency list of vertex 3 : 1 2 6
 Adjacency list of vertex 4 : 3
 Adjacency list of vertex 5 : 0
 Adjacency list of vertex 6 :
  Transitive Closure :
  1  0  0  0  0  0  1
  1  1  1  1  1  1  1
  1  0  1  0  0  1  1
  1  1  1  1  1  1  1
  1  1  1  1  1  1  1
  1  0  0  0  0  1  1
  0  0  0  0  0  0  1
//Java Program, Transitive Closure of a Graph using DFS
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;
    public Vertices node[];
    MyGraph(int size)
    {
        //set value
        this.size=size;

        node=new Vertices[size];
        
    }

    //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.null PointerException
                node[index]=new Vertices(); 
                node[index].data=index;//set your data
                node[index].next=null ;
            }
        }
    }

    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;
                }
            }
        }
    }
    //Check Path of given vertex
    public void  checkVertex(int point,int  []visit){

        if(visit[point]==1){
            return;
        }else{
            visit[point]=1;
            AjlistNode  temp=node[point].next;
            while(temp!=null ){
             checkVertex(temp.id,visit); 
             temp=temp.next;
         }
     }
 }


 public static void main(String[] args) {
    int totalNode=7;

    MyGraph g=new MyGraph(totalNode);
    g.setData();
        //Connected two node with Edges


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

    g.printGraph();

    //Create array
    int []visit=new int[totalNode];
    for(int index=0;index<totalNode;index++)
    {
        visit[index]=0;
     }

    System.out.println("\n  Transitive Closure :");
    int test=0;
    
    while(test<totalNode)
    {
        
        g.checkVertex(test,visit);
        
        //When current node are visit other nodes
        //Then that is a Mother Vertex
        for(int index=0;index<totalNode;index++)
        {

            System.out.print("  "+visit[index]);
            //reset element value
            visit[index]=0;
        }
       
        System.out.println();
        
        test++;
    }

}
}

Output

Adjacency list of vertex 0 : 6
Adjacency list of vertex 1 : 0 4
Adjacency list of vertex 2 : 5
Adjacency list of vertex 3 : 1 2 6
Adjacency list of vertex 4 : 3
Adjacency list of vertex 5 : 0
Adjacency list of vertex 6 :
  Transitive Closure :
  1  0  0  0  0  0  1
  1  1  1  1  1  1  1
  1  0  1  0  0  1  1
  1  1  1  1  1  1  1
  1  1  1  1  1  1  1
  1  0  0  0  0  1  1
  0  0  0  0  0  0  1
#Python Program , Transitive Closure of a Graph using DFS
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=[]


  def setData(self):
    if(self.size>0 and self.node!=None):
      index=0
      while(index<self.size):
        self.node.append(Vertices(index))
        index+=1

  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 ",index,end=" : ")
        temp=self.node[index].next
        while temp!=None:
          print(temp.id,end=" ")
          temp=temp.next
        index+=1
  def checkVertex(self,point,visit):

        if(visit[point]==1):
            return 
        else:
            visit[point]=1 
            temp=self.node[point].next 
            while(temp!=None ):
              self.checkVertex(temp.id,visit)  
              temp=temp.next 

def main():
    totalNode=7
    g=Graph(totalNode)
    g.setData() 
    #Connected two node with Edges
    g.addEdge(0,6) 
    g.addEdge(1,0) 
    g.addEdge(1,4) 
    g.addEdge(2,5) 
    g.addEdge(3,1) 
    g.addEdge(3,2) 
    g.addEdge(3,6) 
    g.addEdge(4,3) 
    g.addEdge(5,0) 
    
    g.printGraph() 
    #Create list
    visit=[0]*totalNode 

    print(" \n Mother Vertex :",end=" ") 
    test=0
    
    while(test<totalNode):
       
        g.checkVertex(test,visit) 
        
        #When current node are visit other nodes
        #Then that is a Mother Vertex
        index=0
        while(index<totalNode):

          print(visit[index],end=" ")

          #reset element value
          visit[index]=0 
          index+=1 
        

        print("") 
        test+=1 

if __name__=="__main__":
    main()

Output

Adjacency list of vertex  0 : 6 
Adjacency list of vertex  1 : 0 4 
Adjacency list of vertex  2 : 5 
Adjacency list of vertex  3 : 1 2 6 
Adjacency list of vertex  4 : 3 
Adjacency list of vertex  5 : 0 
Adjacency list of vertex  6 :  
 Mother Vertex : 1 0 0 0 0 0 1 
1 1 1 1 1 1 1 
1 0 1 0 0 1 1 
1 1 1 1 1 1 1 
1 1 1 1 1 1 1 
1 0 0 0 0 1 1 
0 0 0 0 0 0 1 
//C# Program, Transitive Closure of a Graph using DFS

using System;
public class AjlistNode
{
  public int id;//Vertices node key
  public AjlistNode next;
}
public class Vertices
{
  public int data;
  public AjlistNode next;
}
public class MyGraph
{



  //number of Vertices
  public int size;

  public Vertices[]node= new Vertices[] {};
  MyGraph(int size)
  {
    //set value
    this.size=size;

    node=new Vertices[size];

  }

  //set initial node value
  public void setData(){
    if(node==null )
    {
      Console.WriteLine("\nEmpty Graph");
    }else
    {
      for(int index=0;index<size;index++)
      {
        // avoid java.lang.null PointerException
        node[index]=new Vertices(); 
        node[index].data=index;//set your data
        node[index].next=null ;
      }
    }
  }

  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{
      Console.WriteLine("\nEmpty Graph");
    }
  }

  public void printGraph()
  {
    if(size>0&&node!=null )
    {
      for(int index=0;index<size;index++)
      {
        Console.Write("\nAdjacency list of vertex "+index+" :");
        AjlistNode temp=node[index].next;
        while(temp!=null )
        {
          Console.Write(" {0}",node[temp.id].data);
          temp=temp.next;
        }
      }
    }
  }
  //Check Path of given vertex
  public void  checkVertex(int point,int  []visit){

    if(visit[point]==1){
      return;
    }else{
      visit[point]=1;
      AjlistNode  temp=node[point].next;
      while(temp!=null ){
        checkVertex(temp.id,visit); 
        temp=temp.next;
      }
    }
  }


  static void Main(string[] args)
  {
    int totalNode=7;

    MyGraph g=new MyGraph(totalNode);
    g.setData();
    //Connected two node with Edges


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


    g.printGraph();

    //Create array
    int []visit=new int[totalNode];

    Console.WriteLine(" \n Mother Vertex :");
    int test=0;

    while(test<totalNode)
    {
      
      g.checkVertex(test,visit);

      //When current node are visit other nodes
      //Then that is a Mother Vertex
      for(int index=0;index<totalNode;index++)
      {

        Console.Write("  {0}",visit[index]);
        //reset element value
        visit[index]=0;
      }

        Console.WriteLine();

      test++;
    }

  }
}

Output

Adjacency list of vertex 0 : 6
Adjacency list of vertex 1 : 0 4
Adjacency list of vertex 2 : 5
Adjacency list of vertex 3 : 1 2 6
Adjacency list of vertex 4 : 3
Adjacency list of vertex 5 : 0
Adjacency list of vertex 6 : 
 Mother Vertex :
  1  0  0  0  0  0  1
  1  1  1  1  1  1  1
  1  0  1  0  0  1  1
  1  1  1  1  1  1  1
  1  1  1  1  1  1  1
  1  0  0  0  0  1  1
  0  0  0  0  0  0  1
<?php 
/*
* PHP Program,Transitive Closure of a Graph using DFS

*/

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;
        }
      }
    }
  }
    //Check Path of given vertex
    public function checkVertex($point,& $visit){

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


}


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

   //Connected two node with Edges


    $g->addEdge(0,6);
    $g->addEdge(1,0);
    $g->addEdge(1,4);
    $g->addEdge(2,5);
    $g->addEdge(3,1);
    $g->addEdge(3,2);
    $g->addEdge(3,6);
    $g->addEdge(4,3);
    $g->addEdge(5,0);
    

    $g->printGraph();

    //Create array
    $visit=array_fill(0, $totalNode, 0);;

    echo (" \n Transitive Closure : \n");
    $test=0;
 
    
    while($test<$totalNode)
    {
      
       
        $g->checkVertex($test, $visit);
        
        //When current node are visit other nodes
        //Then that is a Mother Vertex
        for($index=0;$index<$totalNode;$index++)
        {

            echo("  ".$visit[$index]);
            //reset element value
            $visit[$index]=0;
        }
       
          echo "\n";
        
        $test++;
    }

 
}
main();
?>

Output

Adjacency list of vertex 0 :  6
Adjacency list of vertex 1 :  0 4
Adjacency list of vertex 2 :  5
Adjacency list of vertex 3 :  1 2 6
Adjacency list of vertex 4 :  3
Adjacency list of vertex 5 :  0
Adjacency list of vertex 6 :  
 Transitive Closure : 
  1  0  0  0  0  0  1
  1  1  1  1  1  1  1
  1  0  1  0  0  1  1
  1  1  1  1  1  1  1
  1  1  1  1  1  1  1
  1  0  0  0  0  1  1
  0  0  0  0  0  0  1


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