Topological Sorting

 

#include<iostream>

using namespace std;

int queue[10];

class digraph

{

  private:

int adj[10][10],indegree[10],n;

 

public:

digraph();

~digraph();

void constructdigraph(int n);

void findindegree();

int vertexwithminindegree();

  void modifyindegree(int i);

  void displaygraph();

  void topologicalsort();

};

digraph::digraph()

{n=0;

for(int i=0;i<10;i++)

{

  for(int j=0;j<10;j++){

  adj[i][j]=0;

  indegree[i]=0;}

}

}

digraph::~digraph()

{

  delete &n;

  for(int i=0;i<10;i++)

{

  for(int j=0;j<10;j++){

  delete &adj[i][j];

  delete &indegree[i];}

}

}

void digraph::constructdigraph(int m)

{n=m;

int c,edge=0;

do

{cout<<"\n enter vertices of graph between which you want to design edge\n";

cout<<"\n enter first vertex \t";

int a;

cin>>a;

cout<<"\n enter second vertex\t";

int b;

cin>>b;

adj[a-1][b-1]=1;

cout<<"\n do you want to continue if yes press 1 ";

 

cin>>c;

edge++;

 

}while(c==1);

  cout<<"\n-----------------------------------------------------------------------------------\nno of edge in this graph is\t\t"<<edge<<"\n------------------------------------------------------------------------------\n";

 

}

void digraph::displaygraph()

{

  for(int i=0;i<n;i++)

{for(int  j=0;j<n;j++)

{if(adj[i][j]==1)

cout<<"\t "<<i+1<<"is connected to"<<" "<<j+1<<"\n";

}}

}

void digraph::findindegree()

{for(int i=0;i<n;i++)

indegree[i]=0;

  for(int i=0;i<n;i++)

{for(int  j=0;j<n;j++){

//if(adjacency[i][j]==1)

//outdegree[i]++;

if(adj[j][i]==1)

indegree[i]++;

}}

for(int i=0;i<n;i++)

cout<<"\n\t\t"<<"in degree of \t"<<i+1<<"vertex is:\t"<<indegree[i]<<"\n--------------------------------------------------------\n";

cout<<"\n";

}

void digraph::modifyindegree(int i)

{

  for(int j=0;j<n;j++)

  {if(adj[i][j]!=0){

    adj[i][j]=0;

    indegree[j]=indegree[j]-1;}

 

  }

indegree[i]=1000;

}

int digraph::vertexwithminindegree()

{int j;

for(int i=0;i<n;i++){

if(indegree[i]==0){

 

  j=i;

 //out<<"\n"<<j+1;

  break;

}}

//ut<<"\n vertex with minimum indegree is:\t"<<j+1;

//degree[j]=1000;

return j;

}

void digraph::topologicalsort()

{int vertexindex;int k=0;

findindegree();

  for(int counter=0;counter<n;counter++)

{vertexindex=vertexwithminindegree();

if(vertexindex>=n){

cout<<"\n loop  present is the graph";

break;

}

 

cout<<vertexindex+1<<"\t"<<">----->";

  modifyindegree(vertexindex);

}

 

}

int main()

{

  digraph dg;

  int a;

cout<<"\n\thello belcome to graph construction\n-----------------------------------------------------------------------";

cout<<"\n\t enter the no of vertix you want to have is graph:\t";

cin>>a;

dg.constructdigraph(a);

dg.displaygraph();

dg.topologicalsort();

}