|
1 package com.quadcap.util.collections;
2
3
40
41 import java.util.ArrayList  ;
51 import java.util.HashMap ;
52 import java.util.HashSet ;
53 import java.util.Iterator ;
54 import java.util.Map ;
55 import java.util.Set ;
56
58 import com.quadcap.util.Debug;
59
60
66 public class DiGraph {
67 final HashMap nodes = new HashMap ();
69
70 public DiGraph() {}
71
72 public void addNode(Object obj) {
73 mapNode(obj);
74 }
75
76 public final Iterator getNodes() {
77 return new NodeIterator(nodes.values().iterator());
78 }
79
80 public void addArc(Object from, Object to) {
81 Node f = mapNode(from);
82 Node t = mapNode(to);
83 f.addTo(t);
84 t.addFrom(f);
85 }
86
87 public final boolean hasChildren(Object obj) {
88 return mapNode(obj).toSize() > 0;
89 }
90
91 public final boolean hasParents(Object obj) {
92 return mapNode(obj).fromSize() > 0;
93 }
94
95 public boolean hasNode(Object obj) {
96 Node node = (Node)nodes.get(obj);
97 return node != null;
98 }
99
100 public final Iterator getParents(Object to) {
101 return new NodeIterator(mapNode(to).iterateFrom());
102 }
103
104 public final Iterator getChildren(Object from) {
105 return new NodeIterator(mapNode(from).iterateTo());
106 }
107
108 public void removeNode(Object obj, boolean force) {
109 Node node = mapNode(obj);
110 if (!force) {
111 if (node.toSize() != 0 || node.fromSize() != 0) {
112 throw new RuntimeException ("node has links");
113 }
114 } else {
115 Iterator iter = node.iterateTo();
116 while (iter.hasNext()) {
117 Node to = (Node)iter.next();
118 node.removeTo(to);
119 to.removeFrom(node);
120 }
121 iter = node.iterateFrom();
122 while (iter.hasNext()) {
123 Node from = (Node)iter.next();
124 node.removeFrom(from);
125 from.removeTo(node);
126 }
127 }
128 nodes.remove(obj);
129 }
130
131 public void removeArc(Object from, Object to) {
132 Node f = mapNode(from);
133 Node t = mapNode(to);
134 f.removeTo(t);
135 t.removeFrom(f);
136 }
137
138 public Iterator levelize() {
139 return levelize(false);
140 }
141
142 public Iterator levelize(boolean cyclesOK) {
143 ArrayList v = new ArrayList ();
144 Iterator iter = nodes.values().iterator();
145 while (iter.hasNext()) {
146 Node node = (Node)iter.next();
147 node.level = -1;
148 node.visitCnt = 0;
149 if (node.fromSize() == 0) {
150 node.level = 0;
151 v.add(node);
152 }
153 }
154 for (int i = 0; i < v.size(); i++) {
155 Node node = (Node)v.get(i);
156 Iterator t = node.iterateTo();
157 while (t.hasNext()) {
158 Node to = (Node)t.next();
159 if (++to.visitCnt == to.fromSize()) {
160 to.level = node.level + 1;
161 v.add(to);
162 }
163 }
164 }
165 if (!cyclesOK && v.size() != nodes.size()) {
166 throw new RuntimeException ("can't levelize, contains cycles");
167 }
168 return new NodeIterator(v.iterator());
169 }
170
171 public String toString() {
172 StringBuffer sb = new StringBuffer ();
173 Iterator iter = getNodes();
174 String ldelim = "";
175 while (iter.hasNext()) {
176 sb.append(ldelim);
177 ldelim = "\n";
178 Object obj = iter.next();
179 Iterator i2 = getParents(obj);
180 String delim = "";
181 sb.append("(");
182 while (i2.hasNext()) {
183 sb.append(delim);
184 delim = " ";
185 sb.append(i2.next().toString());
186 }
187 sb.append(") ");
188 sb.append(obj.toString());
189 sb.append(" (");
190 i2 = getChildren(obj);
191 delim = "";
192 while (i2.hasNext()) {
193 sb.append(delim);
194 delim = " ";
195 sb.append(i2.next().toString());
196 }
197 sb.append(") ");
198 }
199 return sb.toString();
200 }
201
202 final Node mapNode(Object obj) {
203 Node node = (Node)nodes.get(obj);
204 if (node == null) {
205 node = new Node(obj);
206 nodes.put(obj, node);
207 }
208 return node;
209 }
210
211 class Node implements Comparable {
212 Object obj;
213
214 final HashSet to = new HashSet ();
215 final HashSet from = new HashSet ();
216 int level = 0;
217 int visitCnt = 0;
218
219 Node(Object obj) { this.obj = obj; }
220 void addTo(Node node) {
221 to.add(node);
222 }
223 void addFrom(Node node) {
224 from.add(node);
225 }
226 void removeTo(Node obj) { to.remove(obj); }
227 void removeFrom(Node obj) { from.remove(obj); }
228
229 int toSize() { return to.size(); }
230 int fromSize() { return from.size(); }
231
232 Iterator iterateTo() { return to.iterator(); }
233 Iterator iterateFrom() { return from.iterator(); }
234
235 public int compareTo(Object other) {
236 Node no = (Node)other;
237 return ((Comparable )obj).compareTo(no.obj);
238 }
239
240 public int hashCode() { return obj.hashCode(); }
241
242 public boolean equals(Object obj) {
243 return 0 == compareTo(obj);
244 }
245 public String toString() {
246 return obj.toString();
247 }
248 }
249
250 class NodeIterator implements Iterator {
251 Iterator iter;
252 NodeIterator(Iterator iter) { this.iter = iter; }
253 public boolean hasNext() { return iter.hasNext(); }
254 public Object next() {
255 Node node = (Node)iter.next();
256 return node.obj;
257 }
258 public void remove() {}
259 }
260 }
261
262 |
Popular Tags |
Java API By Example, From Geeks To Geeks.