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
The output is :
[6, 4, 2, 3, 1, 5]
I have used the algorithm given here
public void topoSort() { ListThe input graph is shown below: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 output is :
[6, 4, 2, 3, 1, 5]
Comments
Post a Comment