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()
{
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
Post a Comment