Re: Is There a Java Class for this Kind of Data Structure?

Oliver Wong wrote:


Oliver,
  Thanks for eye-opening(for me) explanation.
After reading your post I have been able to overcome a stumbling block
in one of my own back-burner projects, a Java impl of rmutt.

Googling on dag produced for me a package buried deep in Apache
Excalibur project with just the right dag impl for my purpose.

Very appreciative,
Jeff Higgins

public class DependancyTest
{
  public static void main(String[] args)
  {
    DependancyModel model = new DependancyModel();

    // ,-<-B<-.
    // E<-\ / \
    // *-<-*---<-C<---*-<-A
    // F<-/ \ /
    // `-<-D<-'

    model.addDependant(new Dependant("A"), "root");
    model.addDependant(new Dependant("B"), "A");
    model.addDependant(new Dependant("C"), "A");
    model.addDependant(new Dependant("D"), "A");
    model.addDependant(new Dependant("E"),
        new String[]{"A","B","C","D"});
    model.addDependant(new Dependant("F"),
        new String[] {"A","B","C","D"});
    for(Dependant t : model.getDependancies("D"))
    {
      System.out.print(t.getName() + " ");
    }
  }
}

class Dependant
{
  private String name;

  public Dependant(String name)
  {
    this.name = name;
  }

  public String getName()
  {
    return name;
  }
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.apache.avalon.fortress.util.dag.Vertex;

public class DependancyModel
{
  Map<String, Vertex> nameMap;
  Vertex root;

  public DependancyModel()
  {
    nameMap = new HashMap<String, Vertex>();
    root = new Vertex(null, "root");
    nameMap.put("root", root);
  }

  public void addDependant(Dependant dept, String anc)
  {
    Vertex vertex = new Vertex(dept.getName(), dept);
    nameMap.get(anc).addDependency(vertex);
    nameMap.put(dept.getName(), vertex);
  }

  public void addDependant(Dependant dept, String[] anc)
  {
    Vertex vertex = new Vertex(dept.getName(), dept);
    for (String s : anc)
    {
      nameMap.get(s).addDependency(vertex);
      nameMap.put(dept.getName(), vertex);
    }
  }

  public List<Dependant> getDependancies(String deptName)
  {
    List<Vertex> vertices =
      nameMap.get(deptName).getDependencies();
    List<Dependant> tables = new ArrayList<Dependant>();
    for (Vertex v : vertices)
    {
      tables.add((Dependant) v.getNode());
    }
    return tables;
  }
}