-import java.util.*;\r
-\r
-// A directed Acyclic Graph class. The main purpose is to provide a set of nodes\r
-// and the dependency relations between them. Then ask for a topological sort of\r
-// the nodes.\r
-\r
-public class DAG<Node>\r
-{\r
- // Constructor.\r
- DAG()\r
- {\r
- children = new HashMap<Node,Set<Node>>();\r
- }\r
-\r
- public Set<Node> nodes() { return children.keySet(); }\r
- public Set<Node> children(Node parent) { return children.get(parent); }\r
-\r
- // Add the relations from a compatible DAG to this one.\r
- public void add(DAG<Node> newDag)\r
- {\r
- for(Node parent : newDag.children.keySet())\r
- {\r
- children.put(parent, newDag.children(parent));\r
- }\r
- }\r
-\r
- // The central data structure is a one-to-many map. Each node is \r
- // treated as a parent. It is mapped to a list of its children. Leaf\r
- // nodes are also treated as parents and map to an empty list of\r
- // children.\r
- Map<Node,Set<Node>> children;\r
-\r
- public void remove(Collection<Node> nodes)\r
- {\r
- // Remove it as a parent\r
- for(Node node : nodes)\r
- {\r
- children.remove(node);\r
- }\r
-\r
- for(Set<Node> childlist : children.values())\r
- {\r
- // Remove it as a child\r
- childlist.removeAll(nodes);\r
- }\r
- }\r
-\r
- // Remove every occurrence of node from the DAG.\r
- public void remove(Node node)\r
- {\r
- // Remove it as a parent\r
- children.remove(node);\r
-\r
- for(Set<Node> childlist : children.values())\r
- {\r
- // Remove it as a child\r
- childlist.remove(node);\r
- }\r
- }\r
-\r
- // Return true iff parent is a direct parent of child.\r
- public boolean directDepends(Node parent, Node child)\r
- {\r
- return children.containsKey(parent) ? \r
- children(parent).contains(child) :\r
- false;\r
- }\r
-\r
- // Return true iff parent is a direct or indirect parent of child.\r
- // This is the transitive closure of the dependency relation.\r
- public boolean depends(Node parent, Node child)\r
- {\r
- if(!children.containsKey(parent))\r
- {\r
- return false;\r
- }\r
- if( directDepends(parent, child) )\r
- {\r
- return true;\r
- }\r
- else\r
- {\r
- for(Node descendent : children(parent) )\r
- {\r
- // Recursively call depends() to compute the transitive closure of\r
- // the relation.\r
- if(depends(descendent, child))\r
- {\r
- return true;\r
- }\r
- }\r
- return false;\r
- } \r
- }\r
-\r
- // Add a parent child relation to the dag. Fail if there is already\r
- // a dependency from the child to the parent. This implies a cycle.\r
- // Our invariant is that the DAG must never contain a cycle. That\r
- // way it lives up to its name.\r
- public void add(Node parent, Node child)\r
- {\r
- if(depends(child, parent))\r
- {\r
- System.out.format("Error: There is a cycle from %s to %s.\n", parent, child);\r
- return;\r
- }\r
- if(children.containsKey(parent))\r
- {\r
- children(parent).add(child);\r
- }\r
- else\r
- {\r
- Set<Node> cs = new HashSet<Node>();\r
- cs.add(child);\r
- children.put(parent, cs);\r
- }\r
- if(!children.containsKey(child))\r
- {\r
- children.put(child,new HashSet<Node>());\r
- }\r
- }\r
-\r
- // Perform a topological sort on the DAG.\r
- public List<Node> sort()\r
- {\r
- // Make an ordered list to hold the topo sort.\r
- List<Node> sorted = new LinkedList<Node>();\r
-\r
- // We add the leaves to the beginning of the list until\r
- // the sorted list contains all the nodes in the DAG.\r
- while(!sorted.containsAll(nodes()))\r
- {\r
- // Ignoring the ones we have found, what are the leaves of this\r
- // DAG?\r
- Set<Node> leaves = leaves(sorted);\r
- // Put the new leaves at the beginning of the list.\r
- sorted.addAll(0, leaves);\r
- }\r
- return sorted;\r
- }\r
-\r
- // Return the set of nodes that have no children. Pretend\r
- // the nodes in the exclude list are not present.\r
- public Set<Node> leaves(Collection<Node> exclude)\r
- {\r
- Set<Node> leaves=new HashSet<Node>();\r
- for(Node parent : children.keySet())\r
- {\r
- if(exclude.contains(parent))\r
- {\r
- continue;\r
- }\r
- // If the children of parent are a subset of the exclude set,\r
- // then parent is a leaf.\r
- if(exclude.containsAll(children(parent)))\r
- {\r
- leaves.add(parent);\r
- }\r
- }\r
- return leaves;\r
- }\r
-\r
- // Return the set of nodes that have no children.\r
- public Set<Node> leaves()\r
- {\r
- Set<Node> leaves=new HashSet<Node>();\r
- for(Node parent : children.keySet())\r
- {\r
- if( children(parent).isEmpty())\r
- {\r
- leaves.add(parent);\r
- }\r
- }\r
- return leaves;\r
- }\r
-}\r