Print a Topological Sort in Directed Acyclic Graph

Here given code implementation process.

``````//C program
//Print a 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)
{
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
{
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 topologicalSort(struct Graph*node)
{
int indegree[size],visit[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)
{

printf("\n");
struct AjlistNode *edges=NULL;
for (int i = 0; i < size; ++i)
{
if(indegree[i]==0 && visit[i]==0)
{
visit[i]=1;

printf("%3d",i);

edges=node[i].next;

while(edges!=NULL)
{
indegree[edges->vId]--;
edges=edges->next;
}
i=-1; //reset loop execution
}
}

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

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

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``````
``````//C++ program
//Print a Topological Sort in Directed Acyclic Graph

#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 print_graph();
void connect(int ,int );
void topological_sort();
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
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
{
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;
}
}
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;
}
}
}

//find a sequence of topological sort
void Graph:: topological_sort()
{

int indegree[size],visit[size];
for (int i=0;i<size;i++)
{
indegree[i]=0;
visit[i]=0;
}
int status=-1;

//Find indegree of each node in graph
find_indegree(indegree);
cout<<("\n");
for (int i = 0; i < size; i++)
{
if (indegree[i]==0)
{
status=i;
break ;
}
}
if (status!=-1)
{
cout<<"\n";
AjlistNode *edges=NULL;
for (int i = 0; i < size; ++i)
{
if (indegree[i]==0 && visit[i]==0)
{
visit[i]=1;
cout<<"  "<<i;
edges=node[i].next;
while (edges!=NULL)
{
indegree[edges->id]--;
edges=edges->next;
}
i=-1; //reset loop execution
}
}
}
else
{
cout<<"No topological Sort in this graph";
}
}

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

//Connected two node with Edges

g.print_graph();
g.topological_sort();

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``````
``````//Java program
//Print a Topological Sort in Directed Acyclic Graph
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].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;
}
}
{
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;
}
}
}

//find a sequence of topological sort
public void topological_sort()
{
int []indegree=new int[size];
boolean []visit=new boolean[size];
for (int i=0;i<size;i++)
{
indegree[i]=0;
visit[i]=false;
}
int status=-1;

//Find indegree of each node in graph
find_indegree(indegree);
System.out.print("\n");
for (int i = 0; i < size; i++)
{
if (indegree[i]==0)
{
status=i;
break ;
}
}
if (status!=-1)
{
System.out.println();
AjlistNode  edges=null;
for (int i = 0; i < size; ++i)
{
if (indegree[i]==0 && visit[i]==false)
{
visit[i]=true;
System.out.print("  "+i);
edges=node[i].next;
while (edges!=null)
{
indegree[edges.id]--;
edges=edges.next;
}
i=-1; //reset loop execution
}
}
}
else
{
System.out.println("No topological Sort in this graph");
}
}

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

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

g.print_graph();
g.topological_sort();
}
}``````

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``````
``````#Python program
#Print a Topological Sort in Directed Acyclic Graph

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):
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

#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

#find a sequence of topological sort
def  topological_sort(self) :

indegree=[0]*self.size
visit=[False]*self.size
status=-1
#Find indegree of each node in graph
self.find_indegree(indegree)
print()
i = 0
while (i < self.size ) :

if (indegree[i]==0) :

status=i
break
i+=1

if (status!=-1) :

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

if (indegree[i]==0  and  visit[i]==False) :

visit[i]=True
print(i,end="  ")

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

indegree[edges.key]-=1
edges=edges.next
i=-1 #reset loop execution
i+=1
else :

print("No topological Sort in this graph")

def main():
g=Graph(6)

g.set_data();
#Connected two node with Edges
g.print_graph();
g.topological_sort();

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
1  2  0  3  5  4``````
``````//C# program
//Print a Topological Sort in Directed Acyclic Graph
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].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;
}
}
{
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;
}
}
}

//find a sequence of topological sort
public void topological_sort()
{
int []indegree=new int[size];
Boolean []visit=new Boolean[size];
for (int i=0;i<size;i++)
{
indegree[i]=0;
visit[i]=false;
}
int status=-1;

//Find indegree of each node in graph
find_indegree(indegree);
Console.Write("\n");
for (int i = 0; i < size; i++)
{
if (indegree[i]==0)
{
status=i;
break ;
}
}
if (status!=-1)
{
Console.WriteLine();
AjlistNode  edges=null;
for (int i = 0; i < size; ++i)
{
if (indegree[i]==0 && visit[i]==false)
{
visit[i]=true;
Console.Write("  "+i);
edges=node[i].next;
while (edges!=null)
{
indegree[edges.id]--;
edges=edges.next;
}
i=-1; //reset loop execution
}
}
}
else
{
Console.WriteLine("No topological Sort in this graph");
}
}

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

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

g.print_graph();
g.topological_sort();
}
}``````

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
``````
``````<?php
/*
* PHP Program
* Print a Topological Sort in Directed Acyclic Graph
*/

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

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

}
}
class MyGraph
{

public \$node;
public \$size;
function __construct(\$size)
{
\$this->size=\$size;
\$this->node=[];  //empty array

}
public function 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;
}
}
{
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;
}
}
}

//find a sequence of topological sort
public function topological_sort()
{

\$indegree=array_fill(0, \$this->size, 0);
\$visit=array_fill(0, \$this->size, false);

\$status=-1;

//Find indegree of each node in graph
\$this->find_indegree(\$indegree);
echo ("\n");
for ( \$i = 0; \$i < \$this->size; \$i++)
{
if (\$indegree[\$i]==0)
{
\$status=\$i;
break ;
}
}
if (\$status!=-1)
{
echo ("\n");
\$edges=NULL;
for ( \$i = 0; \$i < \$this->size; ++\$i)
{
if (\$indegree[\$i]==0 && \$visit[\$i]==false)
{
\$visit[\$i]=true;
echo "   ".\$i;
\$edges=\$this->node[\$i]->next;
while (\$edges!=NULL)
{
\$indegree[\$edges->key]--;
\$edges=\$edges->next;
}
\$i=-1; //reset loop execution
}
}
}
else
{
echo "No topological Sort in this graph";
}
}
}

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

//Connected two node with Edges

\$g->print_graph();
\$g->topological_sort();

}
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

1   2   0   3   5   4``````

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.