1 pnkfelix 1.1.2.1 // ColorableGraph.java, created Wed Jan 13 14:13:21 1999 by pnkfelix
2 cananian 1.1.2.4 // Copyright (C) 1998 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.1 // 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 pnkfelix 1.1.2.1 import java.util.Enumeration;
7 pnkfelix 1.1.2.1 import java.util.NoSuchElementException;
8 pnkfelix 1.1.2.1
9 pnkfelix 1.1.2.1 /**
10 pnkfelix 1.1.2.2 * <code>ColorableGraphImpl</code> defines a set of methods that graphs to
11 pnkfelix 1.1.2.1 * be colored should implement. They are meant to be called by the
12 pnkfelix 1.1.2.1 * graph colorers defined in this package.
13 pnkfelix 1.1.2.2 *
14 pnkfelix 1.1.2.2 * @deprecated replaced by <code>ColorableGraph</code> interface.
15 cananian 1.1.2.4 * @author Felix S. Klock II <pnkfelix@mit.edu>
16 cananian 1.2 * @version $Id: ColorableGraphImpl.java,v 1.2 2002/02/25 20:57:16 cananian Exp $ */
17 pnkfelix 1.1.2.1
18 pnkfelix 1.1.2.3 abstract class ColorableGraphImpl extends GraphImpl {
19 pnkfelix 1.1.2.1
20 pnkfelix 1.1.2.1 private boolean mutable;
21 pnkfelix 1.1.2.1
22 pnkfelix 1.1.2.1 /** Creates a <code>ColorableGraph</code>. */
23 pnkfelix 1.1.2.1 public ColorableGraphImpl() {
24 pnkfelix 1.1.2.1 super();
25 pnkfelix 1.1.2.1 mutable = true;
26 pnkfelix 1.1.2.1 }
27 pnkfelix 1.1.2.1
28 pnkfelix 1.1.2.1 /** Returns the graph to a modifiable state.
29 pnkfelix 1.1.2.1 <BR> <B>modifies:</B> all colored and hidden nodes in
30 pnkfelix 1.1.2.1 <code>this</code>.
31 pnkfelix 1.1.2.1 <BR> <B>effects:</B> each colored node is given an 'uncolored'
32 pnkfelix 1.1.2.1 state and each hidden node is unhid.
33 pnkfelix 1.1.2.1 */
34 pnkfelix 1.1.2.1 public void resetGraph() {
35 pnkfelix 1.1.2.1 unhideAllNodes();
36 pnkfelix 1.1.2.1 resetColors();
37 pnkfelix 1.1.2.1 }
38 pnkfelix 1.1.2.1
39 pnkfelix 1.1.2.1 /** Reverts the graph to an uncolored state.
40 pnkfelix 1.1.2.1 <BR> <B>modifies:</B> all colored nodes in <code>this</code>
41 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Each colored node is given an 'uncolored'
42 pnkfelix 1.1.2.1 state.
43 pnkfelix 1.1.2.1 */
44 pnkfelix 1.1.2.1 void resetColors() {
45 pnkfelix 1.1.2.1 Enumeration nodes = super.getNodes();
46 pnkfelix 1.1.2.1 while(nodes.hasMoreElements()) {
47 pnkfelix 1.1.2.1 ColorableNode node = (ColorableNode) nodes.nextElement();
48 pnkfelix 1.1.2.1 try {
49 pnkfelix 1.1.2.1 node.setColor(null);
50 pnkfelix 1.1.2.1 } catch (NodeAlreadyColoredException e) {
51 pnkfelix 1.1.2.1 // this should not be thrown, because we are not
52 pnkfelix 1.1.2.1 // coloring the node.
53 pnkfelix 1.1.2.1 throw new RuntimeException
54 pnkfelix 1.1.2.1 (e.getMessage());
55 pnkfelix 1.1.2.1 }
56 pnkfelix 1.1.2.1 }
57 pnkfelix 1.1.2.1 mutable = true;
58 pnkfelix 1.1.2.1 }
59 pnkfelix 1.1.2.1
60 pnkfelix 1.1.2.1 /** Sets the color of <code>node</code>.
61 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <code>node</code> is present in graph
62 pnkfelix 1.1.2.1 and has not been colored.
63 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Sets the color of <code>node</code> to
64 pnkfelix 1.1.2.1 <code>color</code>. If
65 pnkfelix 1.1.2.1 <code>color</code> is <code>null</code>
66 pnkfelix 1.1.2.1 then <code>node</code> is given an
67 pnkfelix 1.1.2.1 'uncolored' state. Marks
68 pnkfelix 1.1.2.1 <code>this</code> as unmodifiable.
69 pnkfelix 1.1.2.1 */
70 pnkfelix 1.1.2.1 void setColor(ColorableNode node, Color color) {
71 pnkfelix 1.1.2.1 // modifies: this.mutable
72 pnkfelix 1.1.2.1 mutable = false;
73 pnkfelix 1.1.2.1 node.setColor( color );
74 pnkfelix 1.1.2.1 }
75 pnkfelix 1.1.2.1
76 pnkfelix 1.1.2.1
77 pnkfelix 1.1.2.1 /** Temporarily removes <code>node</code> from graph.
78 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <code>node</code> is present in
79 pnkfelix 1.1.2.1 <code>this</code>.
80 pnkfelix 1.1.2.1 <BR> <B>modifies:</B> <code>this</code>, <code>node</code>
81 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Removes <code>node</code> from
82 pnkfelix 1.1.2.1 <code>this</code>, placing it in storage
83 pnkfelix 1.1.2.1 for later replacement in the graph. Also
84 pnkfelix 1.1.2.1 updates all edges and nodes of
85 pnkfelix 1.1.2.1 <code>this</code> to reflect that
86 pnkfelix 1.1.2.1 <code>node</code> has been hidden.
87 pnkfelix 1.1.2.1 */
88 pnkfelix 1.1.2.1 abstract void hideNode( ColorableNode node );
89 pnkfelix 1.1.2.1
90 pnkfelix 1.1.2.1 /** Replaces a hidden <code>node</code> in graph.
91 pnkfelix 1.1.2.1 <BR> <B>NOTE:</B> This method may be replaced by a "unhide
92 pnkfelix 1.1.2.1 last node" or equivalent method, like
93 pnkfelix 1.1.2.1 popping a stack, because the current
94 pnkfelix 1.1.2.1 implementation does not support unhiding
95 pnkfelix 1.1.2.1 nodes out-of-reverse-order. (I will look
96 pnkfelix 1.1.2.1 into the difficulty of implementing this
97 pnkfelix 1.1.2.1 correctly).
98 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <code>node</code> was previously hidden
99 pnkfelix 1.1.2.1 in <code>this</code> and has not been
100 pnkfelix 1.1.2.1 replaced since its last removal.
101 pnkfelix 1.1.2.1 <BR> <B>modifies:</B> <code>this</code>, <code>node</code>
102 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Moves <code>node</code> back into
103 pnkfelix 1.1.2.1 the graph. It also updates all edges and
104 pnkfelix 1.1.2.1 nodes of <code>this</code> to reflect
105 pnkfelix 1.1.2.1 that <code>node</code> has been replaced.
106 pnkfelix 1.1.2.1 */
107 pnkfelix 1.1.2.1 abstract void unhideNode( ColorableNode node );
108 pnkfelix 1.1.2.1
109 pnkfelix 1.1.2.1 /** Replaces all hidden nodes in graph.
110 pnkfelix 1.1.2.1 <BR> <B>modifies:</B> <code>this</code>, all
111 pnkfelix 1.1.2.1 <code>Node</code>s in <code>this</code>
112 pnkfelix 1.1.2.1 <BR> <B>effects:</B> If a node was previously removed from
113 pnkfelix 1.1.2.1 <code>this</code>, and has not been
114 pnkfelix 1.1.2.1 replaced since its last removal, then
115 pnkfelix 1.1.2.1 moves node (and all other hidden ones)
116 pnkfelix 1.1.2.1 back into the graph. It also updates all
117 pnkfelix 1.1.2.1 edges and nodes of <code>this</code> to
118 pnkfelix 1.1.2.1 reflect that the nodes have been
119 pnkfelix 1.1.2.1 replaced.
120 pnkfelix 1.1.2.1 */
121 pnkfelix 1.1.2.1 abstract void unhideAllNodes();
122 pnkfelix 1.1.2.1
123 pnkfelix 1.1.2.1 /** Ensures that only <code>ColorableNode</code>s are added to <code>this</code>.
124 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <code>node</code> is an instance of a
125 pnkfelix 1.1.2.1 <code>ColorableNode</code>.
126 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Does nothing.
127 pnkfelix 1.1.2.1 */
128 pnkfelix 1.1.2.1 protected void checkNode( Node node ) {
129 pnkfelix 1.1.2.1 if (! (node instanceof ColorableNode) ) {
130 pnkfelix 1.1.2.1 throw new WrongNodeTypeException(node + " is not a ColorableNode.");
131 pnkfelix 1.1.2.1 }
132 pnkfelix 1.1.2.1 }
133 pnkfelix 1.1.2.1
134 pnkfelix 1.1.2.1 /** Wrapper class for Enumeration that filters out hidden nodes. */
135 pnkfelix 1.1.2.1 protected static class HiddenFilteringEnum implements Enumeration {
136 pnkfelix 1.1.2.1 Enumeration nodes;
137 pnkfelix 1.1.2.1 ColorableNode next = null;
138 pnkfelix 1.1.2.1
139 pnkfelix 1.1.2.1 HiddenFilteringEnum(Enumeration e) {
140 pnkfelix 1.1.2.1 nodes = e;
141 pnkfelix 1.1.2.1 }
142 pnkfelix 1.1.2.1
143 pnkfelix 1.1.2.1 public boolean hasMoreElements() {
144 pnkfelix 1.1.2.1 while(next == null && nodes.hasMoreElements()) {
145 pnkfelix 1.1.2.1 ColorableNode n = (ColorableNode)
146 pnkfelix 1.1.2.1 nodes.nextElement();
147 pnkfelix 1.1.2.1 if (! n.isHidden()) {
148 pnkfelix 1.1.2.1 next = n;
149 pnkfelix 1.1.2.1 }
150 pnkfelix 1.1.2.1 }
151 pnkfelix 1.1.2.1 return (next != null);
152 pnkfelix 1.1.2.1 }
153 pnkfelix 1.1.2.1
154 pnkfelix 1.1.2.1 public Object nextElement() {
155 pnkfelix 1.1.2.1 Object rtrn;
156 pnkfelix 1.1.2.1 if (hasMoreElements()) {
157 pnkfelix 1.1.2.1 rtrn = next;
158 pnkfelix 1.1.2.1 next = null;
159 pnkfelix 1.1.2.1 } else {
160 pnkfelix 1.1.2.1 throw new NoSuchElementException();
161 pnkfelix 1.1.2.1 }
162 pnkfelix 1.1.2.1 return rtrn;
163 pnkfelix 1.1.2.1 }
164 pnkfelix 1.1.2.1 }
165 pnkfelix 1.1.2.1
166 pnkfelix 1.1.2.1
167 pnkfelix 1.1.2.1 /** Constructs an enumeration for all the nodes.
168 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Returns an <code>Enumeration</code> of
169 pnkfelix 1.1.2.1 the <code>ColorableNode</code>s that have
170 pnkfelix 1.1.2.1 been successfully added to
171 pnkfelix 1.1.2.1 <code>this</code> that are not currently
172 pnkfelix 1.1.2.1 hidden.
173 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <code>this</code> is not modified while
174 pnkfelix 1.1.2.1 the <code>Enumeration</code> returned is
175 pnkfelix 1.1.2.1 in use.
176 pnkfelix 1.1.2.1 */
177 pnkfelix 1.1.2.1 public Enumeration getNodes() {
178 pnkfelix 1.1.2.1 HiddenFilteringEnum hf = new HiddenFilteringEnum(super.getNodes());
179 pnkfelix 1.1.2.1 return hf;
180 pnkfelix 1.1.2.1 }
181 pnkfelix 1.1.2.1
182 pnkfelix 1.1.2.1 /** Modifiability check.
183 pnkfelix 1.1.2.1 Subclasses should override this method to incorporate
184 pnkfelix 1.1.2.1 consistency checks, and should ensure that they call
185 pnkfelix 1.1.2.1 <code>super.isModifiable</code> in their check.
186 pnkfelix 1.1.2.1 <BR> <B>effects:</B> if <code>this</code> is allowed to be
187 pnkfelix 1.1.2.1 modified, returns true. Else returns
188 pnkfelix 1.1.2.1 false.
189 pnkfelix 1.1.2.1 */
190 pnkfelix 1.1.2.1 public boolean isModifiable() {
191 pnkfelix 1.1.2.1 return mutable && super.isModifiable();
192 pnkfelix 1.1.2.1 }
193 pnkfelix 1.1.2.1
194 pnkfelix 1.1.2.1
195 pnkfelix 1.1.2.1 }
196 cananian 1.2