Skip to main content

Find given sequence is a valid topological sort or not

Detecting a valid topological sequence

Here given code implementation process.

//C program
//Find given sequence is a valid topological sort or not
#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;
};

const int size=7; //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("Vertices 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);
  }
}
//Find indegree of each nodes of a given graph
//Find the  incoming edges of each node
void findIndegree(int indegree[],struct Graph*node)
{

  if(node==NULL) return;

  struct AjlistNode *temp=NULL;

  for (int i = 0; i < size; ++i)
  {
    temp=node[i].next;

    while(temp!=NULL)
    {
      indegree[temp->vId]++;
      temp=temp->next;
    }
  }
}

//check the given  topological sequence is valid or not
void topological_find(struct Graph*node,int sequence[],int capacity)
{

  if(capacity!=size)
  {
    printf("Not Valid Topological Sequence\n" );
    return;
  }
  //store indegree of node edges
  int indegree[size];

  for(int i=0;i<size;i++)
  {
    //set initial zero
    indegree[i]=0;
  }

  //Find indegree of each node in graph
  findIndegree(indegree,node);

  printf("\n");
  
  int status=1;

  struct AjlistNode *edges=NULL;
  for (int i = 0; i < size; ++i)
  {
    //Compare to given sequence  into of indegree
    if(indegree[sequence[i]]==0 )
    {

      edges=node[sequence[i]].next;

      while(edges!=NULL)
      {
        indegree[edges->vId]--;
        edges=edges->next;
      }
    }
    else
    {
      status=0;
      break;
    }
  }
  //This is useful to compare given sequence are contain all elements or not, 
  //Assume that given sequence is a valid number of size
  for (int i = 0; i < size; ++i)
  {

    if(indegree[i]!=0)
    {
      status=0;
      break;
    }
  }
  for (int i = 0; i < size; ++i)
  {
    printf("%3d",sequence[i] );
  }
  printf("\n");
  if(status==0)
  {
    printf(" This is not a Valid Topological Sequence\n" );
    
  }
  else
  {
    printf(" Is a Valid Topological Sequence\n" );
  }

}

//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");
  }
}
int main()
{

  struct Graph*node=NULL;
  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, 3);
    addEdge(node,0, 6);
    addEdge(node,2, 1);
    addEdge(node,2, 4);
    addEdge(node,3, 2); 
    addEdge(node,4, 1);
    addEdge(node,5, 2); 
    addEdge(node,5, 4); 
    addEdge(node,5, 6); 
    addEdge(node,6, 2);

    printGraph(node);

    
    int seq1[] = {0,3,5,6,2,4,1};
    int capacity=sizeof(seq1)/sizeof(seq1[0]);
    topological_find(node,seq1,capacity);

    int seq2[] = {5,0,6,3,2,1,4};
    capacity=sizeof(seq2)/sizeof(seq2[0]);
    topological_find(node,seq2,capacity);

    int seq3[] = {5,0,6,3,2,4,1};
    capacity=sizeof(seq3)/sizeof(seq3[0]);
    topological_find(node,seq3,capacity);
  }  
  return 0;
}

Output

 Adjacency list of vertex 0  :  3  6
 Adjacency list of vertex 1  :
 Adjacency list of vertex 2  :  1  4
 Adjacency list of vertex 3  :  2
 Adjacency list of vertex 4  :  1
 Adjacency list of vertex 5  :  2  4  6
 Adjacency list of vertex 6  :  2
  0  3  5  6  2  4  1
 Is a Valid Topological Sequence

  5  0  6  3  2  1  4
 This is not a Valid Topological Sequence

  5  0  6  3  2  4  1
 Is a Valid Topological Sequence


//C++ program
//Find given sequence is a valid topological sort or not

#include <iostream>
using namespace std;

struct AjlistNode
{
  int id;//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 set_data();
  void add_edge(int,int);
  void print_graph();
  void connect(int ,int );
  void topological_find(int sequence[],int capacity);
  void  find_indegree(int indegree[]);
};
Graph::Graph(int size)
{
  this->size = size;
  //set number of nodes
  node = new Vertices[size];
}
//set node key value
void Graph:: set_data()
{
  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:: connect(int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
    //first create Adjacency node
  AjlistNode *newEdge=new AjlistNode;

  if(newEdge!=NULL)
  {

    newEdge->next=NULL;
    newEdge->id=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;          
    }
  }

}

void Graph:: add_edge(int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
  if(V<size && E <size)
  {
    connect(V,E);

  }else
  {
        //not valid Vertices
    cout<<"Invalid Node Vertices "<< V<<" "<<E;
  }
}
//Display Adjacency list of vertex
void Graph:: print_graph()
{
  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->id is graph node vertices
        //in this case temp->id is same as 
        //node[temp->id].data

        cout<<" "<<node[temp->id].data;
        temp=temp->next;
      }
    }
  }else
  {
    cout<<"Empty Graph"<<endl;
  }
}
//Find indegree of each nodes of a given graph
//Find the  incoming edges of each node
void Graph:: find_indegree(int indegree[])
{
  if (node==NULL) return ;
   AjlistNode *temp=NULL;
  for (int i = 0; i < size; ++i)
  {
    temp=node[i].next;
    while (temp!=NULL)
    {
      indegree[temp->id]++;
      temp=temp->next;
    }
  }
}


//check the given  topological sequence is valid or not
void Graph:: topological_find(int sequence[],int capacity)
{
  if(capacity!=size)
  {
    cout<<("Not Valid Topological Sequence\n" );
    return ;
  }
  //store indegree of node edges
  int indegree[size];
  for (int i=0;i<size;i++)
  {
    //set initial zero
    indegree[i]=0;
  }
  //Find indegree of each node in graph
  find_indegree(indegree);
  cout<<("\n");
  
  int status=1;
   AjlistNode *edges=NULL;
  for (int i = 0; i < size; ++i)
  {
    //Compare to given sequence  into of indegree
    if (indegree[sequence[i]]==0 )
    {
      edges=node[sequence[i]].next;
      while (edges!=NULL)
      {
        indegree[edges->id]--;
        edges=edges->next;
      }
    }
    else
    {
      status=0;
      break ;
    }
  }
  //This is useful to compare given sequence are contain all elements or not, 
  //Assume that given sequence is a valid number of size
  for (int i = 0; i < size; ++i)
  {
    if (indegree[i]!=0)
    {
      status=0;
      break ;
    }
  }
  for (int i = 0; i < size; ++i)
  {
    cout<<"  "<<sequence[i];
  }
  cout<<"\n";
  if (status==0)
  {
    cout<<(" This is not a Valid Topological Sequence\n" );
    
  }
  else
  {
    cout<<(" Is a Valid Topological Sequence\n" );
  }
}



int main()
{
  //Create Object
  Graph g = Graph(7);
  //First set node keys
  g.set_data();



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

  g.print_graph();

  
  int seq1[] = {0,3,5,6,2,4,1};
  int capacity=sizeof(seq1)/sizeof(seq1[0]);
  g.topological_find(seq1,capacity);

  int seq2[] = {5,0,6,3,2,1,4};
  capacity=sizeof(seq2)/sizeof(seq2[0]);
  g.topological_find(seq2,capacity);

  int seq3[] = {5,0,6,3,2,4,1};
  capacity=sizeof(seq3)/sizeof(seq3[0]);
  g.topological_find(seq3,capacity);



  return 0;
}

Output

 Adjacency list of vertex 0 : 3 6
 Adjacency list of vertex 1 :
 Adjacency list of vertex 2 : 1 4
 Adjacency list of vertex 3 : 2
 Adjacency list of vertex 4 : 1
 Adjacency list of vertex 5 : 2 4 6
 Adjacency list of vertex 6 : 2
  0  3  5  6  2  4  1
 Is a Valid Topological Sequence

  5  0  6  3  2  1  4
 This is not a Valid Topological Sequence

  5  0  6  3  2  4  1
 Is a Valid Topological Sequence

//Java program
//Find given sequence is a valid topological sort or not
public class MyGraph
{

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

  //number of Vertices
  public  int size;
  public Vertices []node;

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

  }

    //set initial node value
  public void set_data()
  {
    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;
      }
    }
  }
    //connect two nodes
  public void connect(int start,int end)
  {
    AjlistNode newEdge=new AjlistNode();
    newEdge.id=end;//end node
    newEdge.next=null;
    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;
    }
  }
    //Add edge at the end
  public void add_edge(int start,int end)
  {
    if(start < size && end < size && node != null)
    {
      connect(start,end);

    }
    else{
      System.out.println("\nInvalid nodes "+start+" "+end);
    }
  }

  public void print_graph()
  {

    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;
        }
      }
    }
  }

//Find indegree of each nodes of a given graph
//Find the  incoming edges of each node
public void  find_indegree(int indegree[])
{
  if (node==null) return ;
   AjlistNode  temp=null;
  for (int i = 0; i < size; ++i)
  {
    temp=node[i].next;
    while (temp!=null)
    {
      indegree[temp.id]++;
      temp=temp.next;
    }
  }
}


//check the given  topological sequence is valid or not
public void topological_find(int []sequence,int capacity)
{
  if(capacity!=size)
  {
    System.out.print("Not Valid Topological Sequence\n");
    return ;
  }
  //store indegree of node edges
  int []indegree=new int[size];
  for (int i=0;i<size;i++)
  {
    //set initial zero
    indegree[i]=0;
  }
  //Find indegree of each node in graph
  find_indegree(indegree);
  System.out.print("\n");
  
  int status=1;
  AjlistNode  edges=null;
  for (int i = 0; i < size; ++i)
  {
    //Compare to given sequence  into of indegree
    if (indegree[sequence[i]]==0 )
    {
      edges=node[sequence[i]].next;
      while (edges!=null)
      {
        indegree[edges.id]--;
        edges=edges.next;
      }
    }
    else
    {
      status=0;
      break ;
    }
  }
  //This is useful to compare given sequence are contain all elements or not, 
  //Assume that given sequence is a valid number of size
  for (int i = 0; i < size; ++i)
  {
    if (indegree[i]!=0)
    {
      status=0;
      break ;
    }
  }
  for (int i = 0; i < size; ++i)
  {
    System.out.print("  "+sequence[i]);
  }
  System.out.print("\n");
  if (status==0)
  {
    System.out.print(" This is not a Valid Topological Sequence\n" );
    
  }
  else
  {
    System.out.print(" Is a Valid Topological Sequence\n" );
  }
}

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

    MyGraph g=new MyGraph(totalNode);
    g.set_data();
     //Connected two node with Edges
    g.add_edge(0, 3);
    g.add_edge(0, 6);
    g.add_edge(2, 1);
    g.add_edge(2, 4);
    g.add_edge(3, 2); 
    g.add_edge(4, 1);
    g.add_edge(5, 2); 
    g.add_edge(5, 4); 
    g.add_edge(5, 6); 
    g.add_edge(6, 2);

    g.print_graph();


    int []seq1 = new int[]{0,3,5,6,2,4,1};
    int capacity=seq1.length;
    g.topological_find(seq1,capacity);

    int []seq2 = new int[]{5,0,6,3,2,1,4};
    capacity=seq2.length;
    g.topological_find(seq2,capacity);

    int []seq3 = new int[]{5,0,6,3,2,4,1};
    capacity=seq3.length;
    g.topological_find(seq3,capacity);
  }
}

Output

Adjacency list of vertex 0 : 3 6
Adjacency list of vertex 1 :
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 2
Adjacency list of vertex 4 : 1
Adjacency list of vertex 5 : 2 4 6
Adjacency list of vertex 6 : 2
  0  3  5  6  2  4  1
 Is a Valid Topological Sequence

  5  0  6  3  2  1  4
 This is not a Valid Topological Sequence

  5  0  6  3  2  4  1
 Is a Valid Topological Sequence

#Python program
#Find given sequence is a valid topological sort or not

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

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

class Graph:

  def __init__(self,size):
    self.size=size
    self.node=[]
    

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


  #connect two node with  edge
  def connect(self,start,end):
    new_edge=AjLinkeNode(end)
    if(self.node[start].next==None):
      self.node[start].next=new_edge
    else:
      temp=self.node[start].next
      while(temp.next!=None):
        temp=temp.next
      temp.next=new_edge  

  #add edge
  def add_edge(self,start,end):

    #start,end is two nodes
    if(self.size>start and self.size>start):
      
      self.connect(start,end)
  
    else:
      print("Invalid nodes")


  def print_graph(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.key),end=" ")

          temp=temp.next

        index+=1

  

  
  #Find indegree of each nodes of a given graph
  #Find the  incoming edges of each node
  def find_indegree(self,indegree) :

    if (self.node==None) :

      return 
    temp=None
    i = 0
    while ( i < self.size ) :

      temp=self.node[i].next
      while (temp!=None) :

        indegree[temp.key] += 1
        temp=temp.next
      i+=1
  #check the given  topological sequence is valkey or not
  def  topological_find(self,sequence, capacity) :

    if(capacity!=self.size) :

      print("Not Valid Topological Sequence\n")

      return 
    #store indegree of node edges
    indegree=[False]*self.size
    #Find indegree of each node in graph
    self.find_indegree(indegree)
    print("\n")

    status=1
    edges=None
    i = 0
    while (  i < self.size ) :

      #Compare to given sequence  into of indegree
      if (indegree[sequence[i]]==False ) :

        edges=self.node[sequence[i]].next
        while (edges!=None) :

          indegree[edges.key] -=1 
          edges=edges.next
      else :

        status=0
        break 
      i+=1
    

    i = 0  
    #This is useful to compare given sequence are contain all elements or not,
    #Assume that given sequence is a valkey number of size
    while ( i < self.size ) :

      if (indegree[i]!=False) :
        status=0
        break 

      i+=1

    i = 0
    while ( i < self.size) :

      print(sequence[i],end=" ")
      i+=1
    

    if(status==0) :

      print("\n This is not a Valid Topological Sequence")

    else :

      print("\n Is a Valid Topological Sequence")


def main():
  g=Graph(7)

  g.set_data();
  #Connected two node with Edges
  g.add_edge(0, 3)
  g.add_edge(0, 6)
  g.add_edge(2, 1)
  g.add_edge(2, 4)
  g.add_edge(3, 2) 
  g.add_edge(4, 1)
  g.add_edge(5, 2) 
  g.add_edge(5, 4) 
  g.add_edge(5, 6) 
  g.add_edge(6, 2)
  g.print_graph()
  seq1 =[0,3,5,6,2,4,1]
  capacity=len(seq1)
  g.topological_find(seq1,capacity)
  seq2 = [5,0,6,3,2,1,4]
  capacity=len(seq2)
  g.topological_find(seq2,capacity)
  seq3 = [5,0,6,3,2,4,1]
  capacity=len(seq3)
  g.topological_find(seq3,capacity)

if __name__=="__main__":
    main()

Output

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

0 3 5 6 2 4 1 
 Is a Valid Topological Sequence


5 0 6 3 2 1 4 
 This is not a Valid Topological Sequence


5 0 6 3 2 4 1 
 Is a Valid Topological Sequence

//C# program
//Find given sequence is a valid topological sort or not
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;

  MyGraph(int size)
  {
    //set value
    this.size = size;

    node = new Vertices[size];

  }

  //set initial node value
  public void set_data()
  {
    if(node == null)
    {
      Console.WriteLine("\nEmpty Graph");
    }else
    {
      for(int index = 0; index < size; index++)
      {
        // avoid C#.lang.nullPointerException
        node[index]=new Vertices(); 
        node[index].data=index;//set your data
        node[index].next=null;
      }
    }
  }
  //connect two nodes
  public void connect(int start,int end)
  {
    AjlistNode newEdge=new AjlistNode();
    newEdge.id=end;//end node
    newEdge.next=null;
    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;
    }
  }
  //Add edge at the end
  public void add_edge(int start,int end)
  {
    if(start < size && end < size && node != null)
    {
      connect(start,end);

    }
    else{
      Console.WriteLine("\nInvalid nodes "+start+" "+end);
    }
  }

  public void print_graph()
  {

    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(" "+node[temp.id].data);

          temp=temp.next;
        }
      }
    }
  }

  //Find indegree of each nodes of a given graph
  //Find the  incoming edges of each node
  public void  find_indegree(int []indegree)
  {
    if (node==null) return ;
    AjlistNode  temp=null;
    for (int i = 0; i < size; ++i)
    {
      temp=node[i].next;
      while (temp!=null)
      {
        indegree[temp.id]++;
        temp=temp.next;
      }
    }
  }


  //check the given  topological sequence is valid or not
  public void topological_find(int []sequence,int capacity)
  {
    if(capacity!=size)
    {
      Console.Write("Not Valid Topological Sequence\n");
      return ;
    }
    //store indegree of node edges
    int []indegree=new int[size];
    for (int i=0;i<size;i++)
    {
      //set initial zero
      indegree[i]=0;
    }
    //Find indegree of each node in graph
    find_indegree(indegree);
    Console.Write("\n");

    int status=1;
    AjlistNode  edges=null;
    for (int i = 0; i < size; ++i)
    {
      //Compare to given sequence  into of indegree
      if (indegree[sequence[i]]==0 )
      {
        edges=node[sequence[i]].next;
        while (edges!=null)
        {
          indegree[edges.id]--;
          edges=edges.next;
        }
      }
      else
      {
        status=0;
        break ;
      }
    }
    //This is useful to compare given sequence are contain all elements or not, 
    //Assume that given sequence is a valid number of size
    for (int i = 0; i < size; ++i)
    {
      if (indegree[i]!=0)
      {
        status=0;
        break ;
      }
    }
    for (int i = 0; i < size; ++i)
    {
      Console.Write("  "+sequence[i]);
    }
    Console.Write("\n");
    if (status==0)
    {
      Console.Write(" This is not a Valid Topological Sequence\n" );

    }
    else
    {
      Console.Write(" Is a Valid Topological Sequence\n" );
    }
  }

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

    MyGraph g=new MyGraph(totalNode);
    g.set_data();
    //Connected two node with Edges
    g.add_edge(0, 3);
    g.add_edge(0, 6);
    g.add_edge(2, 1);
    g.add_edge(2, 4);
    g.add_edge(3, 2); 
    g.add_edge(4, 1);
    g.add_edge(5, 2); 
    g.add_edge(5, 4); 
    g.add_edge(5, 6); 
    g.add_edge(6, 2);

    g.print_graph();


    int []seq1 = new int[]{0,3,5,6,2,4,1};
    int capacity=seq1.Length;
    g.topological_find(seq1,capacity);

    int []seq2 = new int[]{5,0,6,3,2,1,4};
    capacity=seq2.Length;
    g.topological_find(seq2,capacity);

    int []seq3 = new int[]{5,0,6,3,2,4,1};
    capacity=seq3.Length;
    g.topological_find(seq3,capacity);
  }
}

Output

Adjacency list of vertex 0 : 3 6
Adjacency list of vertex 1 :
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 2
Adjacency list of vertex 4 : 1
Adjacency list of vertex 5 : 2 4 6
Adjacency list of vertex 6 : 2
  0  3  5  6  2  4  1
 Is a Valid Topological Sequence

  5  0  6  3  2  1  4
 This is not a Valid Topological Sequence

  5  0  6  3  2  4  1
 Is a Valid Topological Sequence

<?php 
/*
* PHP Program 
* Find given sequence is a valkey topological sort or not
*/

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 set_data()
  {
    if($this->size>0)
    {
      for($index=0;$index<$this->size;$index++)
      {
        $this->node[$index]=new Node($index);
      }

    }
  }
  public function connect($start,$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 add_edge($start,$end)
  {
    if($this->size > $start && $this->size>$end)
    {
      $this->connect($start,$end);
    }
    else
    {
      echo "\n Invalkey node";
    }
  }
  public function print_graph()
  {
    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;
        }
      }
    }
  }
  //Find indegree of each nodes of a given graph
  //Find the  incoming edges of each node
  public function  find_indegree( &$indegree=array())
  {
    if ($this->node==NULL)
    {
      return ;
    }
    $temp=NULL;
    for ( $i = 0; $i < $this->size; ++$i)
    {
      $temp=$this->node[$i]->next;
      while ($temp!=NULL)
      {
        $indegree[$temp->key]++;
        $temp=$temp->next;
      }
    }
  }


  //check the given  topological sequence is valkey or not
  public function topological_find( &$sequence, $capacity)
  {
    if($capacity!=$this->size)
    {
      echo "Not Valkey Topological Sequence\n";
      return ;
    }
    //store indegree of node edges
    $indegree=array_fill(0, $this->size, False);

    //Find indegree of each node in graph
    $this->find_indegree($indegree);
    echo "\n";
    
    $status=1;
    $edges=NULL;
    for ( $i = 0; $i < $this->size; ++$i)
    {
      //Compare to given sequence  into of indegree
      if ($indegree[$sequence[$i]]==False )
      {
        $edges=$this->node[$sequence[$i]]->next;
        while ($edges!=NULL)
        {
          $indegree[$edges->key]--;
          $edges=$edges->next;
        }
      }
      else
      {
        $status=0;
        break ;
      }
    }
    //This is useful to compare given sequence are contain all elements or not, 
    //Assume that given sequence is a valkey number of size
    for ( $i = 0; $i < $this->size; ++$i)
    {
      if ($indegree[$i]!=False)
      {
        $status=0;
        break ;
      }
    }
    for ($i = 0; $i < $this->size; ++$i)
    {
      echo "  ".$sequence[$i];
    }
    echo "\n";
    if($status==0)
    {
      echo " This is not a Valkey Topological Sequence\n";
      
    }
    else
    {
      echo " Is a Valkey Topological Sequence\n";
    }
  }
}


function main()
{
  //create object
  $g=new MyGraph(7);
  //First set node keys
  $g->set_data();

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

  $g->print_graph();

  
  $seq1 = array(0,3,5,6,2,4,1);
  $capacity=count($seq1);
  $g->topological_find($seq1,$capacity);

  $seq2 = array(5,0,6,3,2,1,4);
  $capacity=count($seq2);
  $g->topological_find($seq2,$capacity);

  $seq3 = array(5,0,6,3,2,4,1);
  $capacity=count($seq3);
  $g->topological_find($seq3,$capacity);


}
main();
?>

Output

Adjacency list of vertex 0 :   3  6
Adjacency list of vertex 1 : 
Adjacency list of vertex 2 :   1  4
Adjacency list of vertex 3 :   2
Adjacency list of vertex 4 :   1
Adjacency list of vertex 5 :   2  4  6
Adjacency list of vertex 6 :   2
  0  3  5  6  2  4  1
 Is a Valkey Topological Sequence

  5  0  6  3  2  1  4
 Is a Valkey Topological Sequence

  5  0  6  3  2  4  1
 Is a Valkey Topological Sequence
Last updated on by Kalkicode




Comment

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