Tools/Source/Prototype/DAG.java

   1 import java.util.*;
   2
   3 // A directed Acyclic Graph class. The main purpose is to provide a set of nodes
   4 // and the dependency relations between them.  Then ask for a topological sort of
   5 // the nodes.
   6
   7 public class DAG<Node>
   8 {
   9   // Constructor.
  10   DAG()
  11   {
  12     children = new HashMap<Node,Set<Node>>();
  13   }
  14
  15   public Set<Node> nodes() { return children.keySet(); }
  16   public Set<Node> children(Node parent) { return children.get(parent); }
  17
  18   // Add the relations from a compatible DAG to this one.
  19   public void add(DAG<Node> newDag)
  20   {
  21     for(Node parent : newDag.children.keySet())
  22     {
  23       children.put(parent, newDag.children(parent));
  24     }
  25   }
  26
  27   // The central data structure is a one-to-many map. Each node is
  28   // treated as a parent. It is mapped to a list of its children. Leaf
  29   // nodes are also treated as parents and map to an empty list of
  30   // children.
  31   Map<Node,Set<Node>> children;
  32
  33   public void remove(Collection<Node> nodes)
  34   {
  35     // Remove it as a parent
  36     for(Node node : nodes)
  37     {
  38       children.remove(node);
  39     }
  40
  41     for(Set<Node> childlist : children.values())
  42     {
  43       // Remove it as a child
  44       childlist.removeAll(nodes);
  45     }
  46   }
  47
  48   // Remove every occurrence of node from the DAG.
  49   public void remove(Node node)
  50   {
  51     // Remove it as a parent
  52     children.remove(node);
  53
  54     for(Set<Node> childlist : children.values())
  55     {
  56       // Remove it as a child
  57       childlist.remove(node);
  58     }
  59   }
  60
  61   // Return true iff parent is a direct parent of child.
  62   public boolean directDepends(Node parent, Node child)
  63   {
  64     return children.containsKey(parent) ?
  65            children(parent).contains(child) :
  66            false;
  67   }
  68
  69   // Return true iff parent is a direct or indirect parent of child.
  70   // This is the transitive closure of the dependency relation.
  71   public boolean depends(Node parent, Node child)
  72   {
  73     if(!children.containsKey(parent))
  74     {
  75       return false;
  76     }
  77     if( directDepends(parent, child) )
  78     {
  79       return true;
  80     }
  81     else
  82     {
  83       for(Node descendent : children(parent) )
  84       {
  85         // Recursively call depends() to compute the transitive closure of
  86         // the relation.
  87         if(depends(descendent, child))
  88         {
  89           return true;
  90         }
  91       }
  92       return false;
  93     }
  94   }
  95
  96   // Add a parent child relation to the dag. Fail if there is already
  97   // a dependency from the child to the parent. This implies a cycle.
  98   // Our invariant is that the DAG must never contain a cycle. That
  99   // way it lives up to its name.
 100   public void add(Node parent, Node child)
 101   {
 102     if(depends(child, parent))
 103     {
 104       System.out.format("Error: There is a cycle from %s to %s.\n", parent, child);
 105       return;
 106     }
 107     if(children.containsKey(parent))
 108     {
 109       children(parent).add(child);
 110     }
 111     else
 112     {
 113       Set<Node> cs = new HashSet<Node>();
 114       cs.add(child);
 115       children.put(parent, cs);
 116     }
 117     if(!children.containsKey(child))
 118     {
 119       children.put(child,new HashSet<Node>());
 120     }
 121   }
 122
 123   // Perform a topological sort on the DAG.
 124   public List<Node> sort()
 125   {
 126     // Make an ordered list to hold the topo sort.
 127     List<Node> sorted = new LinkedList<Node>();
 128
 129     // We add the leaves to the beginning of the list until
 130     // the sorted list contains all the nodes in the DAG.
 131     while(!sorted.containsAll(nodes()))
 132     {
 133       // Ignoring the ones we have found, what are the leaves of this
 134       // DAG?
 135       Set<Node> leaves = leaves(sorted);
 136       // Put the new leaves at the beginning of the list.
 137       sorted.addAll(0, leaves);
 138     }
 139     return sorted;
 140   }
 141
 142   // Return the set of nodes that have no children. Pretend
 143   // the nodes in the exclude list are not present.
 144   public Set<Node> leaves(Collection<Node> exclude)
 145   {
 146     Set<Node> leaves=new HashSet<Node>();
 147     for(Node parent : children.keySet())
 148     {
 149       if(exclude.contains(parent))
 150       {
 151         continue;
 152       }
 153       // If the children of parent are a subset of the exclude set,
 154       // then parent is a leaf.
 155       if(exclude.containsAll(children(parent)))
 156       {
 157         leaves.add(parent);
 158       }
 159     }
 160     return leaves;
 161   }
 162
 163   // Return the set of nodes that have no children.
 164   public Set<Node> leaves()
 165   {
 166     Set<Node> leaves=new HashSet<Node>();
 167     for(Node parent : children.keySet())
 168     {
 169       if( children(parent).isEmpty())
 170       {
 171         leaves.add(parent);
 172       }
 173     }
 174     return leaves;
 175   }
 176 }