All Topological Sort in Directed Acyclic Graph

Print all possible topological sort in graph

Here given code implementation process.

//C program
//All Topological Sort in Directed Acyclic 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=6;

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

void path_sequence(struct Graph*node,
  int indegree[],
  int visit[],
  int index,
  int result[])
{
  if(index>=size) return;

  struct AjlistNode *edges=NULL;

  for (int i = 0; i < size; ++i)
  {
    if(indegree[i]==0 && visit[i]==0)
    {
      
      visit[i]=1;
      result[index]=i;
     

      edges=node[i].next;

      while(edges!=NULL)
      {
        indegree[edges->vId]--;
        edges=edges->next;
      }
      path_sequence(node,indegree,visit,index+1,result);

      //Reset changes

      visit[i]=0;

      edges=node[i].next;
    
      while(edges!=NULL)
      {
        indegree[edges->vId]++;
        edges=edges->next;
      }

    }
  }
  
  if(index+1==size)
  {
    for (int i = 0; i < size; ++i)
    {
       printf("%3d",result[i]);
    }
    printf("\n");
  }
  
}
void topologicalSort(struct Graph*node)
{
  int indegree[size],visit[size],result[size];

  for(int i=0;i<size;i++)
  {
    indegree[i]=0;
    visit[i]=0;
  }
  int status=-1;
  
  //Find indegree of each node in graph
  findIndegree(indegree,node);

  printf("\n");
  for (int i = 0; i < size; i++)
  {

    if(indegree[i]==0)
    {
      status=i;
      break;
    }
  }
  if(status!=-1)
  {
    path_sequence(node,indegree,visit,0,result);

  }else
  {
    printf("No topological Sort in this graph");
  }
}

//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,1, 0);
    addEdge(node,1, 4);
    addEdge(node,1, 5);
    addEdge(node,2, 0);
    addEdge(node,2, 4); 
    addEdge(node,2, 5);
    addEdge(node,3, 4); 
    addEdge(node,3, 5); 
    addEdge(node,5, 4); 
   
    printGraph(node);
    topologicalSort(node);
  }  
  return 0;
}

   

Output

 Adjacency list of vertex 0  :
 Adjacency list of vertex 1  :  0  4  5
 Adjacency list of vertex 2  :  0  4  5
 Adjacency list of vertex 3  :  4  5
 Adjacency list of vertex 4  :
 Adjacency list of vertex 5  :  4
  1  2  0  3  5  4
  1  2  3  0  5  4
  1  2  3  5  0  4
  1  2  3  5  4  0
  1  3  2  0  5  4
  1  3  2  5  0  4
  1  3  2  5  4  0
  2  1  0  3  5  4
  2  1  3  0  5  4
  2  1  3  5  0  4
  2  1  3  5  4  0
  2  3  1  0  5  4
  2  3  1  5  0  4
  2  3  1  5  4  0
  3  1  2  0  5  4
  3  1  2  5  0  4
  3  1  2  5  4  0
  3  2  1  0  5  4
  3  2  1  5  0  4
  3  2  1  5  4  0
/*
 C++ Program
 All Topological Sort in Directed Acyclic Graph
*/

#include<iostream>

using namespace std;
class AjlistNode {
  public:
    int id;
  AjlistNode *next;
  AjlistNode(int value) {
    this->id = value;
    this->next = NULL;
  }
};
class Vertices {
  public:

  int data;
  AjlistNode *next;
  Vertices()
  {
    this->data = 0;
    this->next = NULL;
  }
  Vertices(int value) {
    this->data = value;
    this->next = NULL;
  }
};
class MyGraph {
  public:

  int size;
  Vertices *node;
  MyGraph(int value) {
    this->size = value;
    this->node = new Vertices[value];
    ///this->setData();
  }
  void setData() {
    if (this->node == NULL) {
      cout << "\nEmpty Graph";
    } else {
      int index = 0;
      while (index < this->size) {
        this->node[index] = index;
        index++;
      }
    }
  }
  void addEdge(int start, int end) {
    AjlistNode *newEdge = new AjlistNode(end);
    if (this->node[start].next == NULL) {
      this->node[start].next = newEdge;
    } else {
      AjlistNode *temp = this->node[start].next;
      while (temp->next != NULL) {
        temp = temp->next;
      }
      temp->next = newEdge;
    }
  }
  void findIndegree(int *indegree) {
    if (this->node == NULL) {
      return;
    }
    AjlistNode *temp = NULL;
    int i = 0;
    while (i < this->size) {
      temp = this->node[i].next;
      while (temp != NULL) {
        indegree[temp->id]++;
        temp = temp->next;
      }
      i++;
    }
  }
  void path_sequence(int *indegree, bool *visit, int index, int *result) {
    if (index >= this->size) {
      return;
    }
    AjlistNode *edges = NULL;
    int i = 0;
    while (i < this->size) {
      if (indegree[i] == 0 && visit[i] == false) {
        visit[i] = true;
        result[index] = i;
        edges = this->node[i].next;
        while (edges != NULL) {
          indegree[edges->id]--;
          edges = edges->next;
        }
        this->path_sequence(indegree, visit, index + 1, result);
        visit[i] = false;
        edges = this->node[i].next;
        while (edges != NULL) {
          indegree[edges->id]++;
          edges = edges->next;
        }
      }
      i++;
    }
    if (index + 1 == this->size) {
      i = 0;
      while (i < this->size) {
        cout << "  " << result[i];
        i++;
      }
      cout << "\n";
    }
  }
  void topologicalSort() {
    int *indegree = new int[this->size];
    bool *visit = new bool[this->size];
    int *result = new int[this->size];
    int i = 0;
    while (i < this->size) {
      indegree[i] = 0;
      visit[i] = false;
      i++;
    }
    int status = -1;
    this->findIndegree(indegree);
    cout << "\n Topological Sort \n";
    i = 0;
    while (i < this->size) {
      if (indegree[i] == 0) {
        status = i;
        break;
      }
      i++;
    }
    if (status != -1) {
      this->path_sequence(indegree, visit, 0, result);
    } else {
      cout << "No topological Sort in this graph";
    }
  }
  void printGraph() {
    if (this->size > 0 && this->node != NULL) {
      int index = 0;
      while (index < this->size) {
        cout << "\nAdjacency list of vertex " << index << " :";
        AjlistNode *temp = this->node[index].next;
        while (temp != NULL) {
          cout << " " << this->node[temp->id].data;
          temp = temp->next;
        }
        index++;
      }
    }
  }
};
int main() {
  int totalNode = 6;
  MyGraph g(totalNode);
  g.addEdge(1, 0);
  g.addEdge(1, 4);
  g.addEdge(1, 5);
  g.addEdge(2, 0);
  g.addEdge(2, 4);
  g.addEdge(2, 5);
  g.addEdge(3, 4);
  g.addEdge(3, 5);
  g.addEdge(5, 4);
  g.printGraph();
  g.topologicalSort();
  return 0;
}

Output

 Adjacency list of vertex 0  :
 Adjacency list of vertex 1  :  0  4  5
 Adjacency list of vertex 2  :  0  4  5
 Adjacency list of vertex 3  :  4  5
 Adjacency list of vertex 4  :
 Adjacency list of vertex 5  :  4
  1  2  0  3  5  4
  1  2  3  0  5  4
  1  2  3  5  0  4
  1  2  3  5  4  0
  1  3  2  0  5  4
  1  3  2  5  0  4
  1  3  2  5  4  0
  2  1  0  3  5  4
  2  1  3  0  5  4
  2  1  3  5  0  4
  2  1  3  5  4  0
  2  3  1  0  5  4
  2  3  1  5  0  4
  2  3  1  5  4  0
  3  1  2  0  5  4
  3  1  2  5  0  4
  3  1  2  5  4  0
  3  2  1  0  5  4
  3  2  1  5  0  4
  3  2  1  5  4  0
// Java program
// All Topological Sort in Directed Acyclic Graph

class AjlistNode {

  public int id; //Vertices node key
  public AjlistNode next;
  public AjlistNode(int value) {
    id = value;
    next = null;
  }
}
class Vertices {

  public int data;
  public AjlistNode next;

  public Vertices(int value) {
    data = value;
    next = null;
  }
}
public class MyGraph {


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

  public MyGraph(int value) {
    //set value
    size = value;

    node = new Vertices[size];
    //set initial values of graph node
    this.setData();
  }

  //set initial node value
  public void setData() {
    if (node == null) {
      System.out.println("\nEmpty Graph");
    } else {

      int index = 0; 

      while (index < size) {
        // avoid java.lang.NullPointerException
        node[index] = new Vertices(index);

         index++;
      }
    }
  }


  //connect two node
  public void addEdge(int start, int last) {
    AjlistNode newEdge = new AjlistNode(last);

    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;
    }
  }
  void findIndegree(int[] indegree) {

    if (node == null) {
      return;
    }
    AjlistNode temp = null;
    int i = 0;
    while (i < size) {
      temp = node[i].next;

      while (temp != null) {
        indegree[temp.id]++;
        temp = temp.next;
      }
      i++;
    }
  }
  void path_sequence(int[] indegree, boolean[] visit, int index, int[] result) {

    if (index >= size) {
      return;
    }
    AjlistNode edges = null;

    int i = 0;

    while (i < size) {

      if (indegree[i] == 0 && visit[i] == false) {
        visit[i] = true;
        result[index] = i;
        edges = node[i].next;

        while (edges != null) {
          indegree[edges.id]--;
          edges = edges.next;
        }
        path_sequence(indegree, visit, index + 1, result);
        visit[i] = false;
        edges = node[i].next;

        while (edges != null) {
          indegree[edges.id]++;
          edges = edges.next;
        }
      }
      i++;
    }

    if (index + 1 == size) {
      i = 0;

      while (i < size) {

        System.out.print("  " + result[i]);

        i++;
      }

      System.out.print("\n");
    }
  }
  void topologicalSort() {
    int[] indegree = new int[size];
    boolean[] visit = new boolean[size];
    int[] result = new int[size];
    int i = 0;
    while (i < size) {
      indegree[i] = 0;
      visit[i] = false;
      i++;
    }
    int status = -1;
    findIndegree(indegree);

    System.out.print("\n Topological Sort \n");
    i = 0;
    while (i < size) {

      if (indegree[i] == 0) {
        status = i;
        break;
      }
      i++;
    }

    if (status != -1) {
      path_sequence(indegree, visit, 0, result);
    } else {

      System.out.print("No topological Sort in this graph");
    }
  }

  public void printGraph() {

    if (size > 0 && node != null) {
      int index = 0;
      while (index < size) {
        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;
        }
        index++;
      }
    }
  }

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

    MyGraph g = new MyGraph(totalNode);

    //Connected two node with Edges

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

    g.printGraph();
    g.topologicalSort();

  }
}

Output

 Adjacency list of vertex 0  :
 Adjacency list of vertex 1  :  0  4  5
 Adjacency list of vertex 2  :  0  4  5
 Adjacency list of vertex 3  :  4  5
 Adjacency list of vertex 4  :
 Adjacency list of vertex 5  :  4
  1  2  0  3  5  4
  1  2  3  0  5  4
  1  2  3  5  0  4
  1  2  3  5  4  0
  1  3  2  0  5  4
  1  3  2  5  0  4
  1  3  2  5  4  0
  2  1  0  3  5  4
  2  1  3  0  5  4
  2  1  3  5  0  4
  2  1  3  5  4  0
  2  3  1  0  5  4
  2  3  1  5  0  4
  2  3  1  5  4  0
  3  1  2  0  5  4
  3  1  2  5  0  4
  3  1  2  5  4  0
  3  2  1  0  5  4
  3  2  1  5  0  4
  3  2  1  5  4  0
// C# program
// All Topological Sort in Directed Acyclic Graph
using System;
public class AjlistNode {

  public int id; //Vertices node key
  public AjlistNode next;
  public AjlistNode(int value) {
    id = value;
    next = null;
  }
}
public class Vertices {

  public int data;
  public AjlistNode next;

  public Vertices(int value) {
    data = value;
    next = null;
  }
}
public class MyGraph {


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

  public MyGraph(int value) {
    //set value
    size = value;

    node = new Vertices[size];
    //set initial values of graph node
    this.setData();
  }

  //set initial node value
  public void setData() {
    if (node == null) {
      Console.WriteLine("\nEmpty Graph");
    } else {

      int index = 0; 

      while (index < size) {
        // avoid C#.lang.NullPointerException
        node[index] = new Vertices(index);

        index++;
      }
    }
  }


  //connect two node
  public void addEdge(int start, int last) {
    AjlistNode newEdge = new AjlistNode(last);

    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;
    }
  }
  void findIndegree(int[] indegree) {

    if (node == null) {
      return;
    }
    AjlistNode temp = null;
    int i = 0;
    while (i < size) {
      temp = node[i].next;

      while (temp != null) {
        indegree[temp.id]++;
        temp = temp.next;
      }
      i++;
    }
  }
  void path_sequence(int[] indegree, Boolean[] visit, int index, int[] result) {

    if (index >= size) {
      return;
    }
    AjlistNode edges = null;

    int i = 0;

    while (i < size) {

      if (indegree[i] == 0 && visit[i] == false) {
        visit[i] = true;
        result[index] = i;
        edges = node[i].next;

        while (edges != null) {
          indegree[edges.id]--;
          edges = edges.next;
        }
        path_sequence(indegree, visit, index + 1, result);
        visit[i] = false;
        edges = node[i].next;

        while (edges != null) {
          indegree[edges.id]++;
          edges = edges.next;
        }
      }
      i++;
    }

    if (index + 1 == size) {
      i = 0;

      while (i < size) {

        Console.Write("  " + result[i]);

        i++;
      }

      Console.Write("\n");
    }
  }
  void topologicalSort() {
    int[] indegree = new int[size];
    Boolean[] visit = new Boolean[size];
    int[] result = new int[size];
    int i = 0;
    while (i < size) {
      indegree[i] = 0;
      visit[i] = false;
      i++;
    }
    int status = -1;
    findIndegree(indegree);

    Console.Write("\n Topological Sort \n");
    i = 0;
    while (i < size) {

      if (indegree[i] == 0) {
        status = i;
        break;
      }
      i++;
    }

    if (status != -1) {
      path_sequence(indegree, visit, 0, result);
    } else {

      Console.Write("No topological Sort in this graph");
    }
  }

  public void printGraph() {

    if (size > 0 && node != null) {
      int index = 0;
      while (index < size) {
        Console.Write("\nAdjacency list of vertex " + index + " :");
        AjlistNode temp = node[index].next;
        while (temp != null) {
          Console.Write(" " + node[temp.id].data);
          temp = temp.next;
        }
        index++;
      }
    }
  }

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

    MyGraph g = new MyGraph(totalNode);

    //Connected two node with Edges

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

    g.printGraph();
    g.topologicalSort();

  }
}

Output

Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
 Topological Sort 
  1  2  0  3  5  4
  1  2  3  0  5  4
  1  2  3  5  0  4
  1  2  3  5  4  0
  1  3  2  0  5  4
  1  3  2  5  0  4
  1  3  2  5  4  0
  2  1  0  3  5  4
  2  1  3  0  5  4
  2  1  3  5  0  4
  2  1  3  5  4  0
  2  3  1  0  5  4
  2  3  1  5  0  4
  2  3  1  5  4  0
  3  1  2  0  5  4
  3  1  2  5  0  4
  3  1  2  5  4  0
  3  2  1  0  5  4
  3  2  1  5  0  4
  3  2  1  5  4  0
# Python 3 Program
# All Topological Sort in Directed Acyclic Graph

class AjlistNode :
  
  def __init__(self, value) :
    self.id = value
    self.next = None
  

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

class MyGraph :

  def __init__(self, value) :
    self.size = value
    self.node = [0]*self.size
    self.setData()
  
  def setData(self) :
    if (self.node == None) :
      print("\nEmpty Graph")
    else :
      index = 0
      while (index < self.size) :
        self.node[index] = Vertices(index)
        index += 1
      
    
  
  def addEdge(self, start, last) :
    newEdge = AjlistNode(last)
    if (self.node[start].next == None) :
      self.node[start].next = newEdge
    else :
      temp = self.node[start].next
      while (temp.next != None) :
        temp = temp.next
      
      temp.next = newEdge
    
  
  def findIndegree(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.id] += 1
        temp = temp.next
      
      i += 1
    
  
  def path_sequence(self, indegree, visit, index, result) :
    if (index >= self.size) :
      return
    
    edges = None
    i = 0
    while (i < self.size) :
      if (indegree[i] == 0 and visit[i] == False) :
        visit[i] = True
        result[index] = i
        edges = self.node[i].next
        while (edges != None) :
          indegree[edges.id] -= 1
          edges = edges.next
        
        self.path_sequence(indegree, visit, index + 1, result)
        visit[i] = False
        edges = self.node[i].next
        while (edges != None) :
          indegree[edges.id] += 1
          edges = edges.next
        
      
      i += 1
    
    if (index + 1 == self.size) :
      i = 0
      while (i < self.size) :
        print(" ", result[i],end=" ")
        i += 1
      
      print(end="\n")
    
  
  def topologicalSort(self) :
    indegree = [0]*self.size
    visit = [False]*self.size
    result = [0]*self.size
    i = 0
    while (i < self.size) :
      indegree[i] = 0
      visit[i] = False
      i += 1
    
    status = -1
    self.findIndegree(indegree)
    print("\n Topological Sort ")
    i = 0
    while (i < self.size) :
      if (indegree[i] == 0) :
        status = i
        break
      
      i += 1
    
    if (status != -1) :
      self.path_sequence(indegree, visit, 0, result)
    else :
      print("No topological Sort in this graph")
    
  
  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(self.node[temp.id].data,end="  ")
          temp = temp.next
        
        index += 1
      
    
  

def main() :
  totalNode = 6
  g = MyGraph(totalNode)
  g.addEdge(1, 0)
  g.addEdge(1, 4)
  g.addEdge(1, 5)
  g.addEdge(2, 0)
  g.addEdge(2, 4)
  g.addEdge(2, 5)
  g.addEdge(3, 4)
  g.addEdge(3, 5)
  g.addEdge(5, 4)
  g.printGraph()
  g.topologicalSort()

if __name__ == "__main__":
  main()

Output

Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
 Topological Sort 
  1  2  0  3  5  4
  1  2  3  0  5  4
  1  2  3  5  0  4
  1  2  3  5  4  0
  1  3  2  0  5  4
  1  3  2  5  0  4
  1  3  2  5  4  0
  2  1  0  3  5  4
  2  1  3  0  5  4
  2  1  3  5  0  4
  2  1  3  5  4  0
  2  3  1  0  5  4
  2  3  1  5  0  4
  2  3  1  5  4  0
  3  1  2  0  5  4
  3  1  2  5  0  4
  3  1  2  5  4  0
  3  2  1  0  5  4
  3  2  1  5  0  4
  3  2  1  5  4  0
# Ruby Program
# All Topological Sort in Directed Acyclic Graph

class AjlistNode 
  attr_reader :id, :next
  attr_accessor :id, :next
  def initialize(value) 
    @id = value
    @next = nil
  end
end

class Vertices 
  attr_reader :data, :next
  attr_accessor :data, :next
  def initialize(value) 
    @data = value
    @next = nil
  end
end

class MyGraph 
  attr_reader :size, :node
  attr_accessor :size, :node
  def initialize(value) 
    @size = value
    @node = Array.new(@size,0)
    self.setData()
  end
  def setData() 
    if (@node == nil) 
      print("\nEmpty Graph")
    else 
      index = 0
      while (index < @size) 
        @node[index] = Vertices.new(index)
        index += 1
      end
    end
  end
  def addEdge(start, last) 
    newEdge = AjlistNode.new(last)
    if (@node[start].next == nil) 
      @node[start].next = newEdge
    else 
      temp = @node[start].next
      while (temp.next != nil) 
        temp = temp.next
      end
      temp.next = newEdge
    end
  end
  def findIndegree(indegree) 
    if (@node == nil) 
      return
    end
    temp = nil
    i = 0
    while (i < @size) 
      temp = @node[i].next
      while (temp != nil) 
        indegree[temp.id] += 1
        temp = temp.next
      end
      i += 1
    end
  end
  def path_sequence(indegree, visit, index, result) 
    if (index >= @size) 
      return
    end
    edges = nil
    i = 0
    while (i < @size) 
      if (indegree[i] == 0 and visit[i] == false) 
        visit[i] = true
        result[index] = i
        edges = @node[i].next
        while (edges != nil) 
          indegree[edges.id] -= 1
          edges = edges.next
        end
        self.path_sequence(indegree, visit, index + 1, result)
        visit[i] = false
        edges = @node[i].next
        while (edges != nil) 
          indegree[edges.id] += 1
          edges = edges.next
        end
      end
      i += 1
    end
    if (index + 1 == @size) 
      i = 0
      while (i < @size) 
        print("  ", result[i])
        i += 1
      end
      print("\n")
    end
  end
  def topologicalSort() 
    indegree =  Array.new(@size,0)
    visit =  Array.new(@size,false)
    result =  Array.new(@size,0)
    i = 0
    while (i < @size) 
      indegree[i] = 0
      visit[i] = false
      i += 1
    end
    status = -1
    self.findIndegree(indegree)
    print("\n Topological Sort \n")
    i = 0
    while (i < @size) 
      if (indegree[i] == 0) 
        status = i
        break
      end
      i += 1
    end
    if (status != -1) 
      self.path_sequence(indegree, visit, 0, result)
    else 
      print("No topological Sort in this graph")
    end
  end
  def printGraph() 
    if (@size > 0 and @node != nil) 
      index = 0
      while (index < @size) 
        print("\nAdjacency list of vertex ", index ,"  :")
        temp = @node[index].next
        while (temp != nil) 
          print(" ", @node[temp.id].data)
          temp = temp.next
        end
        index += 1
      end
    end
  end
end
def main() 
  totalNode = 6
  g = MyGraph.new(totalNode)
  g.addEdge(1, 0)
  g.addEdge(1, 4)
  g.addEdge(1, 5)
  g.addEdge(2, 0)
  g.addEdge(2, 4)
  g.addEdge(2, 5)
  g.addEdge(3, 4)
  g.addEdge(3, 5)
  g.addEdge(5, 4)
  g.printGraph()
  g.topologicalSort()
end


main()

Output

Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
 Topological Sort 
  1  2  0  3  5  4
  1  2  3  0  5  4
  1  2  3  5  0  4
  1  2  3  5  4  0
  1  3  2  0  5  4
  1  3  2  5  0  4
  1  3  2  5  4  0
  2  1  0  3  5  4
  2  1  3  0  5  4
  2  1  3  5  0  4
  2  1  3  5  4  0
  2  3  1  0  5  4
  2  3  1  5  0  4
  2  3  1  5  4  0
  3  1  2  0  5  4
  3  1  2  5  0  4
  3  1  2  5  4  0
  3  2  1  0  5  4
  3  2  1  5  0  4
  3  2  1  5  4  0
<?php
/*
 Php Program
 All Topological Sort in Directed Acyclic Graph
*/

class AjlistNode {
  public $id;
  public $next;

  function __construct($value) {
    $this->id = $value;
    $this->next = null;
  }
}
class Vertices {
  public $data;
  public $next;

  function __construct($value) {
    $this->data = $value;
    $this->next = null;
  }
}
class MyGraph {
  private $size;
  private $node;

  function __construct($value) {
    $this->size = $value;
    $this->node = array_fill(0, $this->size, 0);
    $this->setData();
  }
  public  function setData() {
    if ($this->node == null) {
      echo("\nEmpty Graph");
    } else {
      $index = 0;
      while ($index < $this->size) {
        $this->node[$index] = new Vertices($index);
        $index++;
      }
    }
  }
  public  function addEdge($start, $last) {
    $newEdge = new AjlistNode($last);
    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;
    }
  }

  function findIndegree(&$indegree) {
    if ($this->node == null) {
      return;
    }
    $temp = null;
    $i = 0;
    while ($i < $this->size) {
      $temp = $this->node[$i]->next;
      while ($temp != null) {
        $indegree[$temp->id]++;
        $temp = $temp->next;
      }
      $i++;
    }
  }

  function path_sequence(&$indegree, &$visit, $index, &$result) {
    if ($index >= $this->size) {
      return;
    }
    $edges = null;
    $i = 0;
    while ($i < $this->size) {
      if ($indegree[$i] == 0 && $visit[$i] == false) {
        $visit[$i] = true;
        $result[$index] = $i;
        $edges = $this->node[$i]->next;
        while ($edges != null) {
          $indegree[$edges->id]--;
          $edges = $edges->next;
        }
        $this->path_sequence($indegree, $visit, $index + 1, $result);
        $visit[$i] = false;
        $edges = $this->node[$i]->next;
        while ($edges != null) {
          $indegree[$edges->id]++;
          $edges = $edges->next;
        }
      }
      $i++;
    }
    if ($index + 1 == $this->size) {
      $i = 0;
      while ($i < $this->size) {
        echo("  ". $result[$i]);
        $i++;
      }
      echo("\n");
    }
  }

  function topologicalSort() {
    $indegree = array_fill(0, $this->size, 0);;
    $visit = array_fill(0, $this->size, false);;
    $result = array_fill(0, $this->size, 0);;
    $i = 0;
    while ($i < $this->size) {
      $indegree[$i] = 0;
      $visit[$i] = false;
      $i++;
    }
    $status = -1;
    $this->findIndegree($indegree);
    echo("\n Topological Sort \n");
    $i = 0;
    while ($i < $this->size) {
      if ($indegree[$i] == 0) {
        $status = $i;
        break;
      }
      $i++;
    }
    if ($status != -1) {
      $this->path_sequence($indegree, $visit, 0, $result);
    } else {
      echo("No topological Sort in this graph");
    }
  }
  public  function printGraph() {
    if ($this->size > 0 && $this->node != null) {
      $index = 0;
      while ($index < $this->size) {
        echo("\nAdjacency list of vertex ". $index ." :");
        $temp = $this->node[$index]->next;
        while ($temp != null) {
          echo(" ". $this->node[$temp->id]->data);
          $temp = $temp->next;
        }
        $index++;
      }
    }
  }
}

function main() {
  $totalNode = 6;
  $g = new MyGraph($totalNode);
  $g->addEdge(1, 0);
  $g->addEdge(1, 4);
  $g->addEdge(1, 5);
  $g->addEdge(2, 0);
  $g->addEdge(2, 4);
  $g->addEdge(2, 5);
  $g->addEdge(3, 4);
  $g->addEdge(3, 5);
  $g->addEdge(5, 4);
  $g->printGraph();
  $g->topologicalSort();
}
main();

Output

Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
 Topological Sort 
  1  2  0  3  5  4
  1  2  3  0  5  4
  1  2  3  5  0  4
  1  2  3  5  4  0
  1  3  2  0  5  4
  1  3  2  5  0  4
  1  3  2  5  4  0
  2  1  0  3  5  4
  2  1  3  0  5  4
  2  1  3  5  0  4
  2  1  3  5  4  0
  2  3  1  0  5  4
  2  3  1  5  0  4
  2  3  1  5  4  0
  3  1  2  0  5  4
  3  1  2  5  0  4
  3  1  2  5  4  0
  3  2  1  0  5  4
  3  2  1  5  0  4
  3  2  1  5  4  0
/*
 Node Js Program
 All Topological Sort in Directed Acyclic Graph
*/

class AjlistNode {
  
  constructor(value) {
    this.id = value;
    this.next = null;
  }
}
class Vertices {

  constructor(value) {
    this.data = value;
    this.next = null;
  }
}
class MyGraph {

  constructor(value) {
    this.size = value;
    this.node = Array(value).fill(0);
    this.setData();
  }
  setData() {
    if (this.node == null) {
      process.stdout.write("\nEmpty Graph");
    } else {
      var index = 0;
      while (index < this.size) {
        this.node[index] = new Vertices(index);
        index++;
      }
    }
  }
  addEdge(start, last) {
    var newEdge = new AjlistNode(last);
    if (this.node[start].next == null) {
      this.node[start].next = newEdge;
    } else {
      var temp = this.node[start].next;
      while (temp.next != null) {
        temp = temp.next;
      }
      temp.next = newEdge;
    }
  }
  findIndegree(indegree) {
    if (this.node == null) {
      return;
    }
    var temp = null;
    var i = 0;
    while (i < this.size) {
      temp = this.node[i].next;
      while (temp != null) {
        indegree[temp.id]++;
        temp = temp.next;
      }
      i++;
    }
  }
  path_sequence(indegree, visit, index, result) {
    if (index >= this.size) {
      return;
    }
    var edges = null;
    var i = 0;
    while (i < this.size) {
      if (indegree[i] == 0 && visit[i] == false) {
        visit[i] = true;
        result[index] = i;
        edges = this.node[i].next;
        while (edges != null) {
          indegree[edges.id]--;
          edges = edges.next;
        }
        this.path_sequence(indegree, visit, index + 1, result);
        visit[i] = false;
        edges = this.node[i].next;
        while (edges != null) {
          indegree[edges.id]++;
          edges = edges.next;
        }
      }
      i++;
    }
    if (index + 1 == this.size) {
      i = 0;
      while (i < this.size) {
        process.stdout.write("  " + result[i]);
        i++;
      }
      process.stdout.write("\n");
    }
  }
  topologicalSort() {
    var indegree = Array(this.size).fill(0);;
    var visit = Array(this.size).fill(false);;
    var result = Array(this.size).fill(0);;
    var i = 0;
    while (i < this.size) {
      indegree[i] = 0;
      visit[i] = false;
      i++;
    }
    var status = -1;
    this.findIndegree(indegree);
    process.stdout.write("\n Topological Sort \n");
    i = 0;
    while (i < this.size) {
      if (indegree[i] == 0) {
        status = i;
        break;
      }
      i++;
    }
    if (status != -1) {
      this.path_sequence(indegree, visit, 0, result);
    } else {
      process.stdout.write("No topological Sort in this graph");
    }
  }
  printGraph() {
    if (this.size > 0 && this.node != null) {
      var index = 0;
      while (index < this.size) {
        process.stdout.write("\nAdjacency list of vertex " + index + " :");
        var temp = this.node[index].next;
        while (temp != null) {
          process.stdout.write(" " + this.node[temp.id].data);
          temp = temp.next;
        }
        index++;
      }
    }
  }
}

function main() {
  var totalNode = 6;
  var g = new MyGraph(totalNode);
  g.addEdge(1, 0);
  g.addEdge(1, 4);
  g.addEdge(1, 5);
  g.addEdge(2, 0);
  g.addEdge(2, 4);
  g.addEdge(2, 5);
  g.addEdge(3, 4);
  g.addEdge(3, 5);
  g.addEdge(5, 4);
  g.printGraph();
  g.topologicalSort();
}

main();

Output

Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
 Topological Sort 
  1  2  0  3  5  4
  1  2  3  0  5  4
  1  2  3  5  0  4
  1  2  3  5  4  0
  1  3  2  0  5  4
  1  3  2  5  0  4
  1  3  2  5  4  0
  2  1  0  3  5  4
  2  1  3  0  5  4
  2  1  3  5  0  4
  2  1  3  5  4  0
  2  3  1  0  5  4
  2  3  1  5  0  4
  2  3  1  5  4  0
  3  1  2  0  5  4
  3  1  2  5  0  4
  3  1  2  5  4  0
  3  2  1  0  5  4
  3  2  1  5  0  4
  3  2  1  5  4  0
/*
 Swift 4 Program
 All Topological Sort in Directed Acyclic Graph
*/

class AjlistNode {
  var id: Int;
  var next: AjlistNode? ;
  init(_ value: Int) {
    self.id = value;
    self.next = nil;
  }
}
class Vertices {
  var data: Int;
  var next: AjlistNode? ;
  init(_ value: Int) {
    self.data = value;
    self.next = nil;
  }
}
class MyGraph {
  var size : Int;
  var node : [Vertices]? = [Vertices]() ;
  init(_ value: Int) {
    self.size = value;

    var i : Int = 0;
    while (i<value) {
      self.node!.append(Vertices(i));
      i+=1;
    }
   
  }

  func addEdge(_ start: Int, _ last: Int) {
    let newEdge: AjlistNode? = AjlistNode(last);
    if (self.node![start].next == nil) {
      self.node![start].next = newEdge;
    } else {
      var temp: AjlistNode? = self.node![start].next;
      while (temp!.next != nil) {
        temp = temp!.next;
      }
      temp!.next = newEdge;
    }
  }
  func findIndegree(_ indegree: inout [Int] ) {
    if (self.node == nil) {
      return;
    }
    var temp: AjlistNode? = nil;
    var i: Int = 0;
    while (i < self.size) {
      temp = self.node![i].next;
      while (temp != nil) {
        indegree[temp!.id] += 1;
        temp = temp!.next;
      }
      i += 1;
    }
  }
  func path_sequence(_ indegree: inout [Int] , _ visit : inout [Bool] , _ index : Int, _ result: inout [Int] ) {
    if (index >= self.size) {
      return;
    }
    var edges: AjlistNode? = nil;
    var i: Int = 0;
    while (i < self.size) {
      if (indegree[i] == 0 && visit[i] == false) {
        visit[i] = true;
        result[index] = i;
        edges = self.node![i].next;
        while (edges != nil) {
          indegree[edges!.id] -= 1;
          edges = edges!.next;
        }
        self.path_sequence(&indegree, &visit, index + 1, &result);
        visit[i] = false;
        edges = self.node![i].next;
        while (edges != nil) {
          indegree[edges!.id] += 1;
          edges = edges!.next;
        }
      }
      i += 1;
    }
    if (index + 1 == self.size) {
      i = 0;
      while (i < self.size) {
        print(" ", result[i],terminator:" ");
        i += 1;
      }
      print(terminator:"\n");
    }
  }
  func topologicalSort() {
    var indegree: [Int] = Array(repeating:0,count:self.size);
    var visit: [Bool] = Array(repeating:false,count:self.size);
    var result: [Int] = Array(repeating:0,count:self.size);
    var i: Int = 0;
    while (i < self.size) {
      indegree[i] = 0;
      visit[i] = false;
      i += 1;
    }
    var status: Int = -1;
    self.findIndegree(&indegree);
    print("\n Topological Sort ");
    i = 0;
    while (i < self.size) {
      if (indegree[i] == 0) {
        status = i;
        break;
      }
      i += 1;
    }
    if (status != -1) {
      self.path_sequence(&indegree, &visit, 0, &result);
    } else {
      print("No topological Sort in this graph");
    }
  }
  func printGraph() {
    if (self.size > 0 && self.node != nil) {
      var index: Int = 0;
      while (index < self.size) {
        print("\nAdjacency list of vertex ", index ," :",terminator:" ");
        var temp: AjlistNode? = self.node![index].next;
        while (temp != nil) {
          print(" ", self.node![temp!.id].data,terminator:" ");
          temp = temp!.next;
        }
        index += 1;
      }
    }
  }
}
func main() {
  let totalNode: Int = 6;
  let g: MyGraph? = MyGraph(totalNode);
  g!.addEdge(1, 0);
  g!.addEdge(1, 4);
  g!.addEdge(1, 5);
  g!.addEdge(2, 0);
  g!.addEdge(2, 4);
  g!.addEdge(2, 5);
  g!.addEdge(3, 4);
  g!.addEdge(3, 5);
  g!.addEdge(5, 4);
  g!.printGraph();
  g!.topologicalSort();
}
main();

Output

Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
 Topological Sort 
  1  2  0  3  5  4
  1  2  3  0  5  4
  1  2  3  5  0  4
  1  2  3  5  4  0
  1  3  2  0  5  4
  1  3  2  5  0  4
  1  3  2  5  4  0
  2  1  0  3  5  4
  2  1  3  0  5  4
  2  1  3  5  0  4
  2  1  3  5  4  0
  2  3  1  0  5  4
  2  3  1  5  0  4
  2  3  1  5  4  0
  3  1  2  0  5  4
  3  1  2  5  0  4
  3  1  2  5  4  0
  3  2  1  0  5  4
  3  2  1  5  0  4
  3  2  1  5  4  0
// Scala program
// All Topological Sort in Directed Acyclic Graph
class AjlistNode(var next: AjlistNode,
  var id: Int) {

  //Vertices node key
  def this(id: Int) {
    this(null, id);
  }
}
class Vertices(var next: AjlistNode,
  var data: Int) {
  def this(value: Int) {
    this(null, value);
  }
}
class MyGraph(var node: Array[Vertices],
  var size: Int) {
  //number of Vertices
  def this(size: Int) {
    //set value
    this(Array.fill[Vertices](size)(null), size);

    //set initial values of graph node
    this.setData();
  }
  //set initial node value
  def setData(): Unit = {
    if (this.node == null) {
      print("\nEmpty Graph");
    } else {
      var index: Int = 0;
      while (index < this.size) {
        // avoid Scala.lang.NullPointerException
        this.node(index) = new Vertices(index);
        index += 1;
      }
    }
  }
  //connect two node
  def addEdge(start: Int, last: Int): Unit = {
    val newEdge: AjlistNode = new AjlistNode(last);

    if (this.node(start).next == null) {
      this.node(start).next = newEdge;
    } else {
      var temp: AjlistNode = this.node(start).next;
      while (temp.next != null) {
        temp = temp.next;
      }
      temp.next = newEdge;
    }
  }
  def findIndegree(indegree: Array[Int]): Unit = {
    if (this.node == null) {
      return;
    }
    var temp: AjlistNode = null;
    var i: Int = 0;
    while (i < this.size) {
      temp = this.node(i).next;
      while (temp != null) {
        indegree(temp.id) += 1;
        temp = temp.next;
      }
      i += 1;
    }
  }
  def path_sequence(indegree: Array[Int], visit : 
Array[Boolean], index: Int, result: Array[Int]): Unit = {
    if (index >= this.size) {
      return;
    }
    var edges: AjlistNode = null;
    var i: Int = 0;
    while (i < this.size) {
      if (indegree(i) == 0 && visit(i) == false) {
        visit(i) = true;
        result(index) = i;
        edges = this.node(i).next;
        while (edges != null) {
          indegree(edges.id) -= 1;
          edges = edges.next;
        }
        this.path_sequence(indegree, visit, index + 1, result);
        visit(i) = false;
        edges = this.node(i).next;
        while (edges != null) {
          indegree(edges.id) += 1;
          edges = edges.next;
        }
      }
      i += 1;
    }
    if (index + 1 == this.size) {
      i = 0;
      while (i < this.size) {
        print(" " + result(i));
        i += 1;
      }
      print("\n");
    }
  }
  def topologicalSort(): Unit = {
    var indegree: Array[Int] = Array.fill[Int](size)(0);
    var visit: Array[Boolean] = Array.fill[Boolean](size)(false);
    val result: Array[Int] = Array.fill[Int](size)(0);
    var i: Int = 0;
    while (i < this.size) {
      indegree(i) = 0;
      visit(i) = false;
      i += 1;
    }
    var status: Int = -1;
    this.findIndegree(indegree);
    print("\n Topological Sort \n");
    i = 0;
    while (i < this.size && status == -1) {
      if (indegree(i) == 0) {
        status = i;
      }
      i += 1;
    }
    if (status != -1) {
      this.path_sequence(indegree, visit, 0, result);
    } else {
      print("No topological Sort in this graph");
    }
  }
  def printGraph(): Unit = {
    if (this.size > 0 && this.node != null) {
      var index: Int = 0;
      while (index < this.size) {
        print("\nAdjacency list of vertex " + index + " :");
        var temp: AjlistNode = this.node(index).next;
        while (temp != null) {
          print(" " + this.node(temp.id).data);
          temp = temp.next;
        }
        index += 1;
      }
    }
  }
}
object Main {
  def main(args: Array[String]): Unit = {
    val totalNode: Int = 6;
    val g: MyGraph = new MyGraph(totalNode);

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

Output

Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
 Topological Sort
 1 2 0 3 5 4
 1 2 3 0 5 4
 1 2 3 5 0 4
 1 2 3 5 4 0
 1 3 2 0 5 4
 1 3 2 5 0 4
 1 3 2 5 4 0
 2 1 0 3 5 4
 2 1 3 0 5 4
 2 1 3 5 0 4
 2 1 3 5 4 0
 2 3 1 0 5 4
 2 3 1 5 0 4
 2 3 1 5 4 0
 3 1 2 0 5 4
 3 1 2 5 0 4
 3 1 2 5 4 0
 3 2 1 0 5 4
 3 2 1 5 0 4
 3 2 1 5 4 0

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