Topological Sort of JUNG graph in Java

Below code sorts the DAG graph in topological order. g is a directed graph object of JUNG graph.
I have used the algorithm given here

 public void topoSort()
 {
  List L =new ArrayList();
  List S =new ArrayList();
  
  String node,edge,dest;
  
  for (String nod : g.getVertices())
  {
   if (g.inDegree(nod) == 0)
   {
    S.add(nod);
   }
  }
  
  while(S.size()!=0)
  {
   node = S.get(S.size()-1);
   S.remove(node);
  // System.out.println(node);
   L.add(node);
   
   Collection outE=new ArrayList();
   outE.addAll(g.getOutEdges(node));
   
   Iterator ite = outE.iterator();
   
   while(ite.hasNext()) 
   {
    String outedge = ite.next();   
    dest = g.getDest(outedge);
    g.removeEdge(outedge);    
    if(g.inDegree(dest)==0)
     S.add(dest);    
    ite.remove();
   }   
  }
  
  if(g.getEdgeCount()!=0)
  {
   System.out.println("Error: Cycles present : "+g.getEdges().toString());
  }
  else
   System.out.println(L.toString());
 }
The input graph is shown below:
The output is :

 [6, 4, 2, 3, 1, 5]

Comments

Popular posts from this blog

Text Mining Classification Implementation in Java Using WEKA

Implementing X-means clustering in Java using WEKA API.