1 pnkfelix 1.1.2.1 // SparseGraph.java, created Wed Jan 13 16:32:04 1999 by pnkfelix
2 cananian 1.1.2.17 // Copyright (C) 1998 Felix S. Klock II <pnkfelix@mit.edu>
3 cananian 1.1.2.8 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.1 package harpoon.Analysis.GraphColoring;
5 pnkfelix 1.1.2.1
6 cananian 1.6 import net.cscott.jutil.UniqueStack;
7 cananian 1.6 import net.cscott.jutil.UnmodifiableIterator;
8 cananian 1.6 import net.cscott.jutil.Default;
9 pnkfelix 1.1.2.10 import harpoon.Util.EnumerationIterator;
10 cananian 1.5
11 pnkfelix 1.1.2.1 import java.util.Enumeration;
12 pnkfelix 1.1.2.10 import java.util.Collection;
13 pnkfelix 1.1.2.10 import java.util.Collections;
14 pnkfelix 1.1.2.10 import java.util.AbstractCollection;
15 pnkfelix 1.1.2.10 import java.util.Set;
16 pnkfelix 1.1.2.10 import java.util.List;
17 pnkfelix 1.1.2.10 import java.util.HashSet;
18 pnkfelix 1.1.2.10 import java.util.Iterator;
19 pnkfelix 1.1.2.1
20 pnkfelix 1.1.2.1 /**
21 pnkfelix 1.1.2.1 * <code>SparseGraph</code> is an implementation of a
22 pnkfelix 1.1.2.1 * <code>ColorableGraph</code> object. Nodes are represented by a
23 pnkfelix 1.1.2.1 * list <code>SparseNode</code>s, and edges are represented by the
24 pnkfelix 1.1.2.1 * references <code>SparseNode</code>s store internally.
25 pnkfelix 1.1.2.1 *
26 cananian 1.1.2.17 * @author Felix S. Klock II <pnkfelix@mit.edu>
27 cananian 1.6 * @version $Id: SparseGraph.java,v 1.6 2004/02/08 01:52:03 cananian Exp $
28 pnkfelix 1.1.2.1 */
29 pnkfelix 1.1.2.1
30 pnkfelix 1.1.2.13 public class SparseGraph extends ColorableGraphImpl implements ColorableGraph {
31 pnkfelix 1.1.2.1
32 pnkfelix 1.1.2.1 // List of hidden nodes, so that we may properly check when nodes
33 pnkfelix 1.1.2.1 // are unhid.
34 pnkfelix 1.1.2.3 UniqueStack hiddenNodes;
35 pnkfelix 1.1.2.1
36 pnkfelix 1.1.2.1 /** Creates a <code>SparseGraph</code>. */
37 pnkfelix 1.1.2.1 public SparseGraph() {
38 pnkfelix 1.1.2.1 super();
39 pnkfelix 1.1.2.3 hiddenNodes = new UniqueStack();
40 pnkfelix 1.1.2.1 }
41 pnkfelix 1.1.2.1
42 pnkfelix 1.1.2.1 /** Ensures that only <code>SparseNode</code>s are added to <code>this</code>.
43 pnkfelix 1.1.2.5 <BR> <B>requires:</B> <code>node</code> is an instance of a
44 pnkfelix 1.1.2.5 <code>SparseNode</code>
45 pnkfelix 1.1.2.5 <BR> <B>effects:</B> Does nothing.
46 pnkfelix 1.1.2.1 */
47 pnkfelix 1.1.2.5 protected void checkNode( Node node ) {
48 pnkfelix 1.1.2.1 super.checkNode( node );
49 pnkfelix 1.1.2.1 if (! (node instanceof SparseNode) ) {
50 pnkfelix 1.1.2.1 throw new WrongNodeTypeException
51 pnkfelix 1.1.2.1 ("Node " + node + " is not correct type for SparseGraph.");
52 pnkfelix 1.1.2.1 }
53 pnkfelix 1.1.2.1 }
54 pnkfelix 1.1.2.1
55 pnkfelix 1.1.2.1 private void isNodePresent( Node node )
56 pnkfelix 1.1.2.1 throws NodeNotPresentInGraphException {
57 pnkfelix 1.1.2.1 if ( ! getNodeVector().contains( node ) ) {
58 pnkfelix 1.1.2.1 throw new NodeNotPresentInGraphException
59 pnkfelix 1.1.2.1 ("Node " + node + " not present in graph.");
60 pnkfelix 1.1.2.1 }
61 pnkfelix 1.1.2.1 }
62 pnkfelix 1.1.2.1
63 pnkfelix 1.1.2.5 /** Generates an edge from <code>from</code> to <code>to</code>.
64 pnkfelix 1.1.2.5 <BR> <B>requires:</B> <code>from</code> and <code>to</code>
65 pnkfelix 1.1.2.5 are present in <code>this</code> and are
66 pnkfelix 1.1.2.5 valid targets for a new edge
67 pnkfelix 1.1.2.5 (<code>SparseGraph</code> does not allow
68 pnkfelix 1.1.2.5 multiple edges or circular edges).
69 pnkfelix 1.1.2.5 <BR> <B>modifies:</B> <code>from</code>, <code>to</code>
70 pnkfelix 1.1.2.5 <BR> <B>effects:</B> Adds an edge from <code>from</code> to
71 pnkfelix 1.1.2.5 <code>to</code>.
72 pnkfelix 1.1.2.1 */
73 pnkfelix 1.1.2.5 public void makeEdge( Node from, Node to ) {
74 pnkfelix 1.1.2.2 if (from == to) {
75 pnkfelix 1.1.2.3 throw new IllegalEdgeException
76 pnkfelix 1.1.2.3 ("SparseGraph does not allow circular edges");
77 pnkfelix 1.1.2.2 }
78 pnkfelix 1.1.2.2
79 pnkfelix 1.1.2.1 isNodePresent( from );
80 pnkfelix 1.1.2.1 isNodePresent( to );
81 pnkfelix 1.1.2.1 // if nodes are in this object, they must be SparseNodes
82 pnkfelix 1.1.2.1 // (guaranteed by representation given above)
83 pnkfelix 1.1.2.1 SparseNode sTo = (SparseNode) to;
84 pnkfelix 1.1.2.1 SparseNode sFrom = (SparseNode) from;
85 pnkfelix 1.1.2.5
86 pnkfelix 1.1.2.5 if (!this.isModifiable()) {
87 pnkfelix 1.1.2.5 throw new IllegalEdgeException
88 pnkfelix 1.1.2.5 (this + " is not allowed to be modified.");
89 pnkfelix 1.1.2.5 }
90 pnkfelix 1.1.2.3
91 pnkfelix 1.1.2.3 try {
92 pnkfelix 1.1.2.3 sTo.addEdgeFrom( sFrom );
93 pnkfelix 1.1.2.3 } catch (ObjectNotModifiableException e) {
94 pnkfelix 1.1.2.3 throw new IllegalEdgeException
95 pnkfelix 1.1.2.3 (sFrom + " is not allowed to be modified.");
96 pnkfelix 1.1.2.3 }
97 pnkfelix 1.1.2.3 try {
98 pnkfelix 1.1.2.3 sFrom.addEdgeTo( sTo );
99 pnkfelix 1.1.2.3 } catch (ObjectNotModifiableException e) {
100 pnkfelix 1.1.2.3 throw new IllegalEdgeException
101 pnkfelix 1.1.2.3 (sTo + " is not allowed to be modified.");
102 pnkfelix 1.1.2.3 }
103 pnkfelix 1.1.2.1 }
104 pnkfelix 1.1.2.2
105 pnkfelix 1.1.2.1 /** Returns the degree of <code>node</code>.
106 pnkfelix 1.1.2.5 <BR> <B>requires:</B> <code>node</code> is present in
107 pnkfelix 1.1.2.5 <code>this</code>.
108 pnkfelix 1.1.2.5 <BR> <B>effects:</B> Returns the number of other
109 pnkfelix 1.1.2.5 <code>ColorableNode</code>s that
110 pnkfelix 1.1.2.5 <code>node</code> is connected to.
111 pnkfelix 1.1.2.1 */
112 pnkfelix 1.1.2.5 public int getDegree( Node node ) {
113 pnkfelix 1.1.2.1 isNodePresent( node );
114 pnkfelix 1.1.2.1 // if its in this object, it must be a SparseNode
115 pnkfelix 1.1.2.1 // (guaranteed by representation given above)
116 pnkfelix 1.1.2.1 SparseNode snode = (SparseNode) node;
117 pnkfelix 1.1.2.1 return snode.getDegree();
118 pnkfelix 1.1.2.1 }
119 pnkfelix 1.1.2.1
120 pnkfelix 1.1.2.1 /** Constructs an enumeration for the children of a specific node.
121 pnkfelix 1.1.2.5 <BR> <B>requires:</B> <code>node</code> is present in
122 pnkfelix 1.1.2.5 <code>this</code>.
123 pnkfelix 1.1.2.5 <BR> <B>effects:</B> Returns an <code>Enumeration</code> of
124 pnkfelix 1.1.2.7 the <code>Node</code>s that have an edge
125 pnkfelix 1.1.2.5 from <code>node</code> to them that are
126 pnkfelix 1.1.2.5 not hidden.
127 pnkfelix 1.1.2.5 <BR> <B>requires:</B> <code>this</code> is not modified while
128 pnkfelix 1.1.2.5 the <code>Enumeration</code> returned is
129 pnkfelix 1.1.2.5 still in use.
130 pnkfelix 1.1.2.1 */
131 pnkfelix 1.1.2.5 public Enumeration getChildrenOf( Node node ) {
132 pnkfelix 1.1.2.5 isNodePresent( node );
133 pnkfelix 1.1.2.1 // if its in this object, it must be a SparseNode
134 pnkfelix 1.1.2.1 // (guaranteed by representation given above)
135 pnkfelix 1.1.2.1 SparseNode snode = (SparseNode) node;
136 pnkfelix 1.1.2.1
137 pnkfelix 1.1.2.9 ColorableGraphImpl.HiddenFilteringEnum filter =
138 pnkfelix 1.1.2.9 new ColorableGraphImpl.HiddenFilteringEnum(snode.getToNodes());
139 pnkfelix 1.1.2.2 return filter;
140 pnkfelix 1.1.2.1 }
141 pnkfelix 1.1.2.1
142 pnkfelix 1.1.2.1 /** Constructs an enumeration for the parents of a specific node.
143 pnkfelix 1.1.2.7 <BR> <B>effects:</B> Returns an <code>Enumeration</code> of
144 pnkfelix 1.1.2.7 the nodes that have an edge from them to
145 pnkfelix 1.1.2.7 <code>node</code>.
146 pnkfelix 1.1.2.5 <BR> <B>requires:</B> <code>this</code> is not modified while
147 pnkfelix 1.1.2.5 the <code>Enumeration</code> returned is
148 pnkfelix 1.1.2.5 still in use.
149 pnkfelix 1.1.2.1 */
150 pnkfelix 1.1.2.1 public Enumeration getParentsOf( Node node )
151 pnkfelix 1.1.2.1 throws NodeNotPresentInGraphException {
152 pnkfelix 1.1.2.1 isNodePresent( node );
153 pnkfelix 1.1.2.1 // if its in this object, it must be a SparseNode
154 pnkfelix 1.1.2.1 // (guaranteed by representation given above)
155 pnkfelix 1.1.2.1 SparseNode snode = (SparseNode) node;
156 pnkfelix 1.1.2.1
157 pnkfelix 1.1.2.9 ColorableGraphImpl.HiddenFilteringEnum filter =
158 pnkfelix 1.1.2.9 new ColorableGraphImpl.HiddenFilteringEnum( snode.getFromNodes() );
159 pnkfelix 1.1.2.2 return filter;
160 pnkfelix 1.1.2.1 }
161 pnkfelix 1.1.2.1
162 pnkfelix 1.1.2.1 /** Constructs an enumeration for the parents of a specific node.
163 pnkfelix 1.1.2.5 <BR> <B>requires:</B> <code>node</code> is present in
164 pnkfelix 1.1.2.5 <code>this</code>.
165 pnkfelix 1.1.2.7 <BR> <B>effects:</B> Returns an <code>Enumeration</code> of
166 pnkfelix 1.1.2.7 the nodes that have an edge between
167 pnkfelix 1.1.2.7 <code>node</code> and them.
168 pnkfelix 1.1.2.5 <BR> <B>requires:</B> <code>this</code> is not modified while
169 pnkfelix 1.1.2.5 the <code>Enumeration</code> returned is
170 pnkfelix 1.1.2.5 still in use.
171 pnkfelix 1.1.2.1 */
172 pnkfelix 1.1.2.1 public Enumeration getNeighborsOf( Node node )
173 pnkfelix 1.1.2.1 throws NodeNotPresentInGraphException {
174 pnkfelix 1.1.2.1 isNodePresent( node );
175 pnkfelix 1.1.2.1 // if its in this object, it must be a SparseNode
176 pnkfelix 1.1.2.1 // (guaranteed by representation given above)
177 pnkfelix 1.1.2.1 SparseNode snode = (SparseNode) node;
178 pnkfelix 1.1.2.1
179 pnkfelix 1.1.2.9 ColorableGraphImpl.HiddenFilteringEnum filter =
180 pnkfelix 1.1.2.9 new ColorableGraphImpl.HiddenFilteringEnum( snode.getNeighboringNodes());
181 pnkfelix 1.1.2.2 return filter;
182 pnkfelix 1.1.2.1 }
183 pnkfelix 1.1.2.1
184 pnkfelix 1.1.2.1
185 pnkfelix 1.1.2.1 /** Temporarily removes <code>node</code> from graph.
186 pnkfelix 1.1.2.5 <BR> <B>requires:</B> <code>node</code> is present in
187 pnkfelix 1.1.2.5 <code>this</code>.
188 pnkfelix 1.1.2.5 <BR> <B>modifies:</B> <code>this</code>, <code>node</code>
189 pnkfelix 1.1.2.5 <BR> <B>effects:</B> Removes <code>node</code> from
190 pnkfelix 1.1.2.5 <code>this</code>, placing it in storage
191 pnkfelix 1.1.2.5 for later replacement in the graph. Also
192 pnkfelix 1.1.2.5 updates all edges and nodes of
193 pnkfelix 1.1.2.5 <code>this</code> to reflect that
194 pnkfelix 1.1.2.5 <code>node</code> has been hidden.
195 pnkfelix 1.1.2.1 */
196 pnkfelix 1.1.2.5 void hideNode( ColorableNode node ) {
197 pnkfelix 1.1.2.5 // modifies: this.hiddenNodes
198 pnkfelix 1.1.2.5
199 pnkfelix 1.1.2.1 isNodePresent( node );
200 pnkfelix 1.1.2.1 // if its in this object, it must be a SparseNode
201 pnkfelix 1.1.2.1 // (guaranteed by representation given above)
202 pnkfelix 1.1.2.1 SparseNode sNode = (SparseNode) node;
203 pnkfelix 1.1.2.1
204 pnkfelix 1.1.2.3 hiddenNodes.push( sNode );
205 pnkfelix 1.1.2.1 sNode.setHidden( true );
206 pnkfelix 1.1.2.13
207 pnkfelix 1.1.2.13 // FSK: definition of nodes is loose in terms of
208 pnkfelix 1.1.2.13 // whether node is still present in nodes after being hidden
209 pnkfelix 1.1.2.13 nodes.remove( sNode );
210 pnkfelix 1.1.2.1
211 pnkfelix 1.1.2.1 Enumeration fromNodes = sNode.getFromNodes();
212 pnkfelix 1.1.2.1 while (fromNodes.hasMoreElements()) {
213 pnkfelix 1.1.2.1 SparseNode from = (SparseNode) fromNodes.nextElement();
214 pnkfelix 1.1.2.1 try {
215 pnkfelix 1.1.2.1 from.removeEdgeTo( sNode );
216 pnkfelix 1.1.2.1 } catch (EdgeNotPresentException e) {
217 pnkfelix 1.1.2.1 // should never be thrown for this rep...
218 pnkfelix 1.1.2.3 e.printStackTrace();
219 pnkfelix 1.1.2.3 throw new RuntimeException(e.getMessage());
220 pnkfelix 1.1.2.3 } catch (ObjectNotModifiableException e) {
221 pnkfelix 1.1.2.3 e.printStackTrace();
222 pnkfelix 1.1.2.3 throw new RuntimeException
223 pnkfelix 1.1.2.3 (sNode + " is not allowed to be modified");
224 pnkfelix 1.1.2.1 }
225 pnkfelix 1.1.2.1 }
226 pnkfelix 1.1.2.1 Enumeration toNodes = sNode.getToNodes();
227 pnkfelix 1.1.2.1 while (toNodes.hasMoreElements()) {
228 pnkfelix 1.1.2.1 SparseNode to = (SparseNode) toNodes.nextElement();
229 pnkfelix 1.1.2.1 try {
230 pnkfelix 1.1.2.1 to.removeEdgeFrom( sNode );
231 pnkfelix 1.1.2.1 } catch (EdgeNotPresentException e) {
232 pnkfelix 1.1.2.1 // should never be thrown for this rep...
233 pnkfelix 1.1.2.3 e.printStackTrace();
234 pnkfelix 1.1.2.3 throw new RuntimeException(e.getMessage());
235 pnkfelix 1.1.2.3 } catch (ObjectNotModifiableException e) {
236 pnkfelix 1.1.2.3 e.printStackTrace();
237 pnkfelix 1.1.2.3 throw new RuntimeException(e.getMessage());
238 pnkfelix 1.1.2.1 }
239 pnkfelix 1.1.2.1 }
240 pnkfelix 1.1.2.1 }
241 pnkfelix 1.1.2.1
242 pnkfelix 1.1.2.1 /** Replaces a hidden <code>node</code> in graph.
243 pnkfelix 1.1.2.5 <BR> <B>requires:</B> <code>node</code> was previously hidden
244 pnkfelix 1.1.2.5 in <code>this</code> and has not been
245 pnkfelix 1.1.2.5 replaced since its last removal.
246 pnkfelix 1.1.2.5 <BR> <B>modifies:</B> <code>this</code>, <code>node</code>
247 pnkfelix 1.1.2.5 <BR> <B>effects:</B> If <code>node</code> was previously
248 pnkfelix 1.1.2.5 removed from <code>this</code>, and has
249 pnkfelix 1.1.2.5 not been replaced since its last
250 pnkfelix 1.1.2.5 removal), then moves <code>node</code>
251 pnkfelix 1.1.2.5 from temporary storage back into the
252 pnkfelix 1.1.2.5 graph. It also updates all edges and
253 pnkfelix 1.1.2.5 nodes of <code>this</code> to reflect
254 pnkfelix 1.1.2.5 that <code>node</code> has been replaced.
255 pnkfelix 1.1.2.1 */
256 pnkfelix 1.1.2.5 void unhideNode( ColorableNode node ) {
257 pnkfelix 1.1.2.5 // modifies: this.hiddenNodes
258 pnkfelix 1.1.2.1 if ( ! hiddenNodes.contains( node ) ) {
259 pnkfelix 1.1.2.1 throw new NodeNotRemovedException
260 pnkfelix 1.1.2.1 ("Node " + node +
261 pnkfelix 1.1.2.1 " was never hidden in graph " + this);
262 pnkfelix 1.1.2.1 }
263 pnkfelix 1.1.2.1 // if node WAS hidden at some point, it must be a SparseNode.
264 pnkfelix 1.1.2.1 SparseNode sNode = (SparseNode) node;
265 pnkfelix 1.1.2.1
266 pnkfelix 1.1.2.1 hiddenNodes.removeElement( sNode );
267 pnkfelix 1.1.2.1 sNode.setHidden( false );
268 pnkfelix 1.1.2.1
269 pnkfelix 1.1.2.13 // FSK: added to match corresponding "remove" in hideNode
270 pnkfelix 1.1.2.13 nodes.add( sNode );
271 pnkfelix 1.1.2.13
272 pnkfelix 1.1.2.1 Enumeration fromNodes = sNode.getFromNodes();
273 pnkfelix 1.1.2.2
274 pnkfelix 1.1.2.2 try {
275 pnkfelix 1.1.2.2 while (fromNodes.hasMoreElements()) {
276 pnkfelix 1.1.2.2 SparseNode from = (SparseNode) fromNodes.nextElement();
277 pnkfelix 1.1.2.2 from.addEdgeTo( sNode );
278 pnkfelix 1.1.2.2 }
279 pnkfelix 1.1.2.2 Enumeration toNodes = sNode.getToNodes();
280 pnkfelix 1.1.2.2 while (toNodes.hasMoreElements()) {
281 pnkfelix 1.1.2.2 SparseNode to = (SparseNode) toNodes.nextElement();
282 pnkfelix 1.1.2.2 to.addEdgeFrom( sNode );
283 pnkfelix 1.1.2.2 }
284 pnkfelix 1.1.2.2 } catch (IllegalEdgeException e) {
285 pnkfelix 1.1.2.2 // should not happen...
286 pnkfelix 1.1.2.2 e.printStackTrace();
287 pnkfelix 1.1.2.2 throw new RuntimeException(e.getMessage());
288 pnkfelix 1.1.2.3 } catch (ObjectNotModifiableException e) {
289 pnkfelix 1.1.2.3 e.printStackTrace();
290 pnkfelix 1.1.2.3 throw new RuntimeException(sNode + " could not be unhid");
291 pnkfelix 1.1.2.1 }
292 pnkfelix 1.1.2.1 }
293 pnkfelix 1.1.2.1
294 pnkfelix 1.1.2.2 /** Replaces all hidden nodes in graph.
295 pnkfelix 1.1.2.5 <BR> <B>modifies:</B> <code>this</code>
296 pnkfelix 1.1.2.5 <BR> <B>effects:</B> If a node was previously removed from
297 pnkfelix 1.1.2.5 <code>this</code>, and has not been
298 pnkfelix 1.1.2.5 replaced since its last removal, then
299 pnkfelix 1.1.2.5 moves node (and all other hidden ones)
300 pnkfelix 1.1.2.5 back into the graph. It also updates all
301 pnkfelix 1.1.2.5 edges and nodes of <code>this</code> to
302 pnkfelix 1.1.2.5 reflect that the nodes have been
303 pnkfelix 1.1.2.5 replaced.
304 pnkfelix 1.1.2.2 */
305 pnkfelix 1.1.2.1 void unhideAllNodes() {
306 pnkfelix 1.1.2.1 try {
307 pnkfelix 1.1.2.3 // need to unhide nodes in reverse order.
308 pnkfelix 1.1.2.3 while(! hiddenNodes.empty()) {
309 pnkfelix 1.1.2.3 unhideNode( (ColorableNode) hiddenNodes.peek() );
310 pnkfelix 1.1.2.1 }
311 pnkfelix 1.1.2.1 } catch ( NodeNotRemovedException e ) {
312 pnkfelix 1.1.2.1 // should never be thrown, as the internal representation
313 pnkfelix 1.1.2.1 // requires that all nodes in hiddenNode vector are in
314 pnkfelix 1.1.2.1 // fact hidden.
315 pnkfelix 1.1.2.1 throw new RuntimeException(e.getMessage());
316 pnkfelix 1.1.2.1 }
317 pnkfelix 1.1.2.2 }
318 pnkfelix 1.1.2.2
319 pnkfelix 1.1.2.2 /** Modifiability check.
320 pnkfelix 1.1.2.2 Subclasses should override this method to incorporate
321 pnkfelix 1.1.2.2 consistency checks, and should ensure that they call
322 pnkfelix 1.1.2.2 super.isModifiable in their check.
323 pnkfelix 1.1.2.5 <BR> <B>effects:</B> If <code>this</code> is allowed to be modified,
324 pnkfelix 1.1.2.5 returns true. Else returns false.
325 pnkfelix 1.1.2.2 */
326 pnkfelix 1.1.2.2 public boolean isModifiable() {
327 pnkfelix 1.1.2.2 return hiddenNodes.size() == 0 && super.isModifiable();
328 pnkfelix 1.1.2.1 }
329 pnkfelix 1.1.2.1
330 pnkfelix 1.1.2.10
331 pnkfelix 1.1.2.11 /***** ColorableGraph Support methods *****/
332 pnkfelix 1.1.2.12
333 pnkfelix 1.1.2.12 private class NsnEx extends IllegalArgumentException {
334 pnkfelix 1.1.2.12 NsnEx(Object n) { super(n+"not SparseNode"); }
335 pnkfelix 1.1.2.12 }
336 pnkfelix 1.1.2.12
337 pnkfelix 1.1.2.12 private class NmEx extends UnsupportedOperationException {
338 pnkfelix 1.1.2.12 NmEx() { super("not modifiable"); }
339 pnkfelix 1.1.2.12 }
340 pnkfelix 1.1.2.12
341 pnkfelix 1.1.2.11 /** Wrapper method that calls <code>super.addNode(n)</code>.
342 pnkfelix 1.1.2.11 Needed to resolve ambiguity in method resolution at
343 pnkfelix 1.1.2.11 compile-time.
344 pnkfelix 1.1.2.11 */
345 pnkfelix 1.1.2.10 public void addNode( Node n ) {
346 pnkfelix 1.1.2.10 super.addNode(n);
347 pnkfelix 1.1.2.10 }
348 pnkfelix 1.1.2.10
349 pnkfelix 1.1.2.10 /** Returns all nodes in graph to their original state.
350 pnkfelix 1.1.2.10 <BR> <B>modifies:</B> <code>this</code>
351 pnkfelix 1.1.2.10 <BR> <B>effects:</B> the Node -> Color mapping
352 pnkfelix 1.1.2.10 is cleared and each hidden node is restored;
353 pnkfelix 1.1.2.10 <code>this</code> is otherwise unchanged.
354 pnkfelix 1.1.2.10 */
355 pnkfelix 1.1.2.10 public void resetGraph() {
356 pnkfelix 1.1.2.11 super.resetGraph();
357 pnkfelix 1.1.2.10 }
358 pnkfelix 1.1.2.10
359 pnkfelix 1.1.2.10 /** Reverts the graph to an uncolored state.
360 pnkfelix 1.1.2.10 <BR> <B>modifies:</B> <code>this</code>
361 pnkfelix 1.1.2.10 <BR> <B>effects:</B> clears the Node -> Color mapping.
362 pnkfelix 1.1.2.10 */
363 pnkfelix 1.1.2.10 public void resetColors() {
364 pnkfelix 1.1.2.11 super.resetColors();
365 pnkfelix 1.1.2.10 }
366 pnkfelix 1.1.2.10
367 pnkfelix 1.1.2.10 /** Sets the color of <code>n</code>.
368 pnkfelix 1.1.2.10 <BR> <B>effects:</B> If <code>c</code> is null, then
369 pnkfelix 1.1.2.10 removes <code>n</code> from the Node -> Color mapping.
370 pnkfelix 1.1.2.10 Else puts (n, c) in the Node -> Color mapping.
371 pnkfelix 1.1.2.10 @throws IllegalArgumentException If <code>n</code> is not
372 pnkfelix 1.1.2.10 present in the node set for <code>this</code> or
373 pnkfelix 1.1.2.10 <code>n</code> has already been colored.
374 pnkfelix 1.1.2.10 */
375 pnkfelix 1.1.2.10 public void setColor(Object n, Color c) {
376 pnkfelix 1.1.2.12 try {
377 pnkfelix 1.1.2.12 SparseNode sn = (SparseNode) n;
378 pnkfelix 1.1.2.12 sn.setColor(c);
379 pnkfelix 1.1.2.13 } catch (ClassCastException e) {
380 pnkfelix 1.1.2.13 throw new NsnEx(n);
381 pnkfelix 1.1.2.13 } catch (NodeAlreadyColoredException e) {
382 pnkfelix 1.1.2.13 throw new ColorableGraph.AlreadyColoredException(n);
383 pnkfelix 1.1.2.16 }
384 pnkfelix 1.1.2.16 }
385 pnkfelix 1.1.2.16
386 pnkfelix 1.1.2.16 public void unsetColor(Object n) {
387 pnkfelix 1.1.2.16 try {
388 pnkfelix 1.1.2.16 SparseNode sn = (SparseNode) n;
389 pnkfelix 1.1.2.16 sn.setColor(null);
390 pnkfelix 1.1.2.16 } catch (ClassCastException e) {
391 pnkfelix 1.1.2.16 throw new NsnEx(n);
392 pnkfelix 1.1.2.16 } catch (NodeAlreadyColoredException e) {
393 cananian 1.3.2.1 assert false;
394 pnkfelix 1.1.2.13 }
395 pnkfelix 1.1.2.12 }
396 pnkfelix 1.1.2.10
397 pnkfelix 1.1.2.10 /** Returns the color of <code>node</code>.
398 pnkfelix 1.1.2.10 <BR> <B>effects:</B> Returns the color associated with
399 pnkfelix 1.1.2.10 <code>node</code> in the Node -> Color mapping, or null
400 pnkfelix 1.1.2.10 if there is no entry in the mapping for
401 pnkfelix 1.1.2.10 <code>node</code>.
402 pnkfelix 1.1.2.10 @throws IllegalArgumentException If <code>node</code> is not
403 pnkfelix 1.1.2.10 present in the node set for <code>this</code>.
404 pnkfelix 1.1.2.10 */
405 pnkfelix 1.1.2.10 public Color getColor(Object node) {
406 pnkfelix 1.1.2.12 try {
407 pnkfelix 1.1.2.12 SparseNode sn = (SparseNode) node;
408 pnkfelix 1.1.2.12 return sn.getColor();
409 pnkfelix 1.1.2.15 } catch (NodeNotColoredException e) { return null;
410 pnkfelix 1.1.2.15 } catch (ClassCastException e) { throw new NsnEx(node);
411 pnkfelix 1.1.2.15 }
412 pnkfelix 1.1.2.10 }
413 pnkfelix 1.1.2.10
414 pnkfelix 1.1.2.10 /** Temporarily removes <code>node</code> from graph.
415 pnkfelix 1.1.2.10 <BR> <B>modifies:</B> <code>this</code>, <code>node</code>
416 pnkfelix 1.1.2.10 <BR> <B>effects:</B> Removes <code>node</code> and
417 pnkfelix 1.1.2.10 <code>node</code>'s associated edges from
418 pnkfelix 1.1.2.10 <code>this</code>, pushing it onto hidden-nodes stack
419 pnkfelix 1.1.2.10 for later replacement in the graph. Also updates all
420 pnkfelix 1.1.2.10 edges and nodes of <code>this</code> to reflect that
421 pnkfelix 1.1.2.10 <code>node</code> has been hidden.
422 pnkfelix 1.1.2.10 @throws IllegalArgumentException If <code>node</code> is not
423 pnkfelix 1.1.2.10 present in the node set for <code>this</code>.
424 pnkfelix 1.1.2.10 */
425 pnkfelix 1.1.2.10 public void hide( Object node ) {
426 pnkfelix 1.1.2.12 try {
427 pnkfelix 1.1.2.12 SparseNode sn = (SparseNode) node;
428 pnkfelix 1.1.2.12 hideNode(sn);
429 pnkfelix 1.1.2.12 } catch (ClassCastException e) { throw new NsnEx(node); }
430 pnkfelix 1.1.2.10 }
431 pnkfelix 1.1.2.12
432 pnkfelix 1.1.2.10 /** Replaces the last hidden node</code> into the graph.
433 pnkfelix 1.1.2.10 <BR> <B>modifies:</B> <code>this</code>
434 pnkfelix 1.1.2.10 <BR> <B>effects:</B>
435 pnkfelix 1.1.2.10 if hidden-nodes stack is empty,
436 pnkfelix 1.1.2.10 then returns null
437 pnkfelix 1.1.2.10 else let n = Pop(hidden-nodes stack).
438 pnkfelix 1.1.2.10 puts `n' and its associated edges back in the
439 pnkfelix 1.1.2.10 graph, updating all edges and nodes of
440 pnkfelix 1.1.2.10 <code>this</code> to reflect that n has been
441 pnkfelix 1.1.2.10 replaced.
442 pnkfelix 1.1.2.10 Returns n.
443 pnkfelix 1.1.2.10 */
444 pnkfelix 1.1.2.10 public Object replace() {
445 pnkfelix 1.1.2.13 if (hiddenNodes.isEmpty()) {
446 pnkfelix 1.1.2.13 return null;
447 pnkfelix 1.1.2.13 } else {
448 pnkfelix 1.1.2.13 ColorableNode n = (ColorableNode) hiddenNodes.peek();
449 pnkfelix 1.1.2.13 unhideNode(n);
450 pnkfelix 1.1.2.13 return n;
451 pnkfelix 1.1.2.13 }
452 pnkfelix 1.1.2.10 }
453 pnkfelix 1.1.2.10
454 pnkfelix 1.1.2.10 /** Replaces all hidden nodes in graph.
455 pnkfelix 1.1.2.10 <BR> <B>modifies:</B> <code>this</code>
456 pnkfelix 1.1.2.10 <BR> <B>effects:</B>
457 pnkfelix 1.1.2.10 until hidden-nodes stack is empty,
458 pnkfelix 1.1.2.10 let n = Pop(hidden-nodes stack).
459 pnkfelix 1.1.2.10 puts `n' and its associated edges back in the
460 pnkfelix 1.1.2.10 graph, updating all edges and nodes of
461 pnkfelix 1.1.2.10 <code>this</code> to reflect that n has been
462 pnkfelix 1.1.2.10 replaced.
463 pnkfelix 1.1.2.10 */
464 pnkfelix 1.1.2.10 public void replaceAll() {
465 pnkfelix 1.1.2.12 unhideAllNodes();
466 pnkfelix 1.1.2.10 }
467 pnkfelix 1.1.2.10
468 pnkfelix 1.1.2.10 /** Returns a set view of the nodes in <code>this</code>.
469 pnkfelix 1.1.2.10 <BR> <B>effects:</B> Returns an <code>Set</code> of
470 pnkfelix 1.1.2.10 the <code>Object</code>s that have been successfully
471 pnkfelix 1.1.2.10 added to <code>this</code>.
472 pnkfelix 1.1.2.10 */
473 pnkfelix 1.1.2.10 public Set nodeSet() {
474 pnkfelix 1.1.2.10 return Collections.unmodifiableSet(nodes);
475 pnkfelix 1.1.2.10 }
476 pnkfelix 1.1.2.10
477 pnkfelix 1.1.2.10 /** Returns a collection view for the neighbors of a specific node.
478 pnkfelix 1.1.2.10 <BR> <B>effects:</B> Returns an <code>Collection</code> of
479 pnkfelix 1.1.2.10 <code>Object</code>s that have an edge between
480 pnkfelix 1.1.2.10 <code>node</code> and them.
481 pnkfelix 1.1.2.10 <BR> <B>mandates:</B> <code>node</code> is not removed from
482 pnkfelix 1.1.2.10 <code>this</code> while the returned
483 pnkfelix 1.1.2.10 <code>Collection</code> is in use.
484 pnkfelix 1.1.2.10 @throws IllegalArgumentException <code>node</code> is not
485 pnkfelix 1.1.2.10 present in the node set for <code>this</code>.
486 pnkfelix 1.1.2.10 */
487 pnkfelix 1.1.2.10 public Collection neighborsOf( Object node ) {
488 pnkfelix 1.1.2.10 final SparseNode sn;
489 pnkfelix 1.1.2.10 try {
490 pnkfelix 1.1.2.10 sn = (SparseNode) node;
491 pnkfelix 1.1.2.10 } catch (ClassCastException e) {
492 pnkfelix 1.1.2.10 throw new IllegalArgumentException();
493 pnkfelix 1.1.2.10 }
494 pnkfelix 1.1.2.10 return new AbstractCollection() {
495 pnkfelix 1.1.2.10 public int size() {
496 pnkfelix 1.1.2.10 return sn.getDegree();
497 pnkfelix 1.1.2.10 }
498 pnkfelix 1.1.2.10 public Iterator iterator() {
499 pnkfelix 1.1.2.10 Enumeration e = sn.getNeighboringNodes();
500 pnkfelix 1.1.2.10 return new EnumerationIterator(e);
501 pnkfelix 1.1.2.10 }
502 pnkfelix 1.1.2.10 };
503 pnkfelix 1.1.2.10 }
504 pnkfelix 1.1.2.10
505 cananian 1.2 }