DAG Classes for Java

It's a little surprising that even after more than a dozen years worth of bloat, Java still doesn't have a standard set of classes to handle standard graphs like DAGs and their associated operations.

I needed this recently and decided against writing from scratch. With a little Googling, I decided to use the Plexus Utilities. See the JavaDocs at http://plexus.codehaus.org/plexus-utils/apidocs/index.html

The Plexus-Utils overview is here: http://plexus.codehaus.org/plexus-utils/. The best way to get going is to grab the jars with Maven. Below is a dumb little example code:

import org.codehaus.plexus.util.dag.DAG;
import org.codehaus.plexus.util.dag.Vertex;
import org.codehaus.plexus.util.dag.CycleDetectedException;

import java.util.*;

public class DAGFun {
DAG dag;
Vertex from1, to1;
Vertex from2, to2;
public DAGFun() {
dag=new DAG();
from1=new Vertex("from");
to1=new Vertex("to");
}

public DAGFun(DAG dag) {
this.dag=dag;
}

public void addEdge(DAG dag, Vertex from, Vertex to) throws CycleDetectedException {
dag.addEdge(from,to);
}

public void processDag(){
List vertices=dag.getVerticies();
List roots=new ArrayList();
//Find all the roots. There may be more than one
for(int i=0;i<vertices.size();i++){
Vertex test=(Vertex)vertices.get(i);
if(test.isRoot()) roots.add(test);
}

//Now walk through all the DAGs
for(int i=0;i<roots.size();i++){
Vertex v=(Vertex)roots.get(i);
List children=v.getChildren();
for(int j=0;j<children.size();j++) {
processChild((Vertex)children.get(j));
}
}
}

public void processChild(Vertex vertex) {
if(vertex.isLeaf()) {
return;
}
List children=vertex.getChildren();
for(int j=0;j<children.size();j++) {
processChild((Vertex)children.get(j));
}
}

public static void main(String[] args) throws Exception{
Vertex from1, to1;
Vertex from2, to2;
from1=new Vertex("from1");
to1=new Vertex("to1");

from2=new Vertex("from2");
to2=new Vertex("to2");

DAG dag=new DAG();
DAGFun df=new DAGFun(dag);
df.addEdge(dag,from1,to1);
df.addEdge(dag,from2,to2);

df.processDag();
}
}