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