1 pnkfelix 1.1.2.1 // ColorableGraph.java, created Wed Jan 13 14:13:21 1999 by pnkfelix
2 cananian 1.1.2.17 // Copyright (C) 1998 Felix S. Klock II <pnkfelix@mit.edu>
3 cananian 1.1.2.9 // 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.5 import java.util.Enumeration;
7 pnkfelix 1.1.2.5 import java.util.NoSuchElementException;
8 pnkfelix 1.1.2.1
9 pnkfelix 1.1.2.1 /**
10 pnkfelix 1.1.2.13 * <code>ColorableGraph</code> extends
11 pnkfelix 1.1.2.13 * <code>GraphColoring.Graph</code> with methods
12 pnkfelix 1.1.2.12 * that are useful for a graph-coloring system. Two main pieces of
13 pnkfelix 1.1.2.12 * state are added:
14 pnkfelix 1.1.2.11 * <OL>
15 pnkfelix 1.1.2.11 * <LI> A Node -> Color mapping
16 pnkfelix 1.1.2.11 * <LI> A stack of "hidden" nodes.
17 pnkfelix 1.1.2.11 * </OL>
18 pnkfelix 1.1.2.11 * The first component is inherent in the nature of a colorable
19 pnkfelix 1.1.2.11 * graph.
20 pnkfelix 1.1.2.11 * The second component of state is to allow optimization of a common
21 pnkfelix 1.1.2.11 * routine required by graph-coloring algorithms: the ability to
22 pnkfelix 1.1.2.11 * temporarily remove a node and its associated edges from a graph but
23 pnkfelix 1.1.2.11 * retaining the information for later replacement into the graph
24 pnkfelix 1.1.2.11 * again. When a node is hidden, all methods on the graph will
25 pnkfelix 1.1.2.11 * operate as if it has been removed from the graph, except for
26 pnkfelix 1.1.2.11 * <code>addNode(Object)</code>.
27 pnkfelix 1.1.2.1 *
28 cananian 1.1.2.17 * @author Felix S. Klock II <pnkfelix@mit.edu>
29 cananian 1.2 * @version $Id: ColorableGraph.java,v 1.2 2002/02/25 20:57:15 cananian Exp $ */
30 pnkfelix 1.1.2.1
31 pnkfelix 1.1.2.11 public interface ColorableGraph extends Graph {
32 pnkfelix 1.1.2.2
33 pnkfelix 1.1.2.11 /** Ensures that this graph contains <code>node</code> (optional operation).
34 pnkfelix 1.1.2.11 <BR> <B>modifies:</B> <code>this</code>
35 pnkfelix 1.1.2.11 <BR> <B>effects:</B> If this method returns normally,
36 pnkfelix 1.1.2.11 <code>node</code> will be present in the node-set for
37 pnkfelix 1.1.2.11 <code>this</code>. Returns <tt>true</tt> if this graph
38 pnkfelix 1.1.2.11 changed as a result of the call, <tt>false</tt>
39 pnkfelix 1.1.2.11 otherwise.
40 pnkfelix 1.1.2.11 @throws UnsupportedOperationException addNode is not supported
41 pnkfelix 1.1.2.11 by this graph.
42 pnkfelix 1.1.2.11 @throws ClassCastException class of specified element prevents
43 pnkfelix 1.1.2.11 it from being added to this graph.
44 pnkfelix 1.1.2.11 @throws AlreadyHiddenException node is part of the set of
45 pnkfelix 1.1.2.11 hidden nodes in <code>this</code>
46 pnkfelix 1.1.2.11 @throws IllegalArgumentException some aspect of
47 pnkfelix 1.1.2.11 <code>node</code> prevents it from being added to the
48 pnkfelix 1.1.2.11 node-set for this graph.
49 pnkfelix 1.1.2.11 */
50 pnkfelix 1.1.2.11 boolean addNode( Object node );
51 pnkfelix 1.1.2.11
52 pnkfelix 1.1.2.11 /** AlreadyHiddenException will be thrown on attempt to call
53 pnkfelix 1.1.2.11 <code>g.addNode(n)</code> while n is a member of the set of
54 pnkfelix 1.1.2.11 hidden nodes in <code>g</code>.
55 pnkfelix 1.1.2.11 */
56 pnkfelix 1.1.2.11 public static class AlreadyHiddenException
57 pnkfelix 1.1.2.11 extends IllegalArgumentException {
58 pnkfelix 1.1.2.11 public AlreadyHiddenException() { super(); }
59 pnkfelix 1.1.2.11 public AlreadyHiddenException(String s) { super(s); }
60 pnkfelix 1.1.2.1 }
61 pnkfelix 1.1.2.11
62 pnkfelix 1.1.2.12 /** AlreadyColoredException will be thrown on attempt to call
63 pnkfelix 1.1.2.12 <code>g.setColor(node,color)</code> when n is present in the
64 pnkfelix 1.1.2.12 node -> color mapping.
65 pnkfelix 1.1.2.12 */
66 pnkfelix 1.1.2.12 public static class AlreadyColoredException
67 pnkfelix 1.1.2.12 extends IllegalArgumentException {
68 pnkfelix 1.1.2.12 /** The node that was targetted for coloring. */
69 pnkfelix 1.1.2.12 public final Object node;
70 pnkfelix 1.1.2.12
71 pnkfelix 1.1.2.12 public AlreadyColoredException(Object n) {
72 pnkfelix 1.1.2.12 super();
73 pnkfelix 1.1.2.12 node = n;
74 pnkfelix 1.1.2.12 }
75 pnkfelix 1.1.2.12 public AlreadyColoredException(String s, Object n) {
76 pnkfelix 1.1.2.12 super(s);
77 pnkfelix 1.1.2.12 node = n;
78 pnkfelix 1.1.2.12 }
79 pnkfelix 1.1.2.12 }
80 pnkfelix 1.1.2.12
81 pnkfelix 1.1.2.15 /** IllegalColor will be thrown on an attempt to color a
82 pnkfelix 1.1.2.15 node with a color that for some reason is not legal for that
83 pnkfelix 1.1.2.15 node in this graph.
84 pnkfelix 1.1.2.15 */
85 pnkfelix 1.1.2.15 public static class IllegalColor extends Throwable {
86 pnkfelix 1.1.2.15 /** Color intended for assignment. */
87 pnkfelix 1.1.2.15 public final Color color;
88 pnkfelix 1.1.2.15 /** Node intended to be assigned to <code>color</code>. */
89 pnkfelix 1.1.2.15 public final Object node;
90 pnkfelix 1.1.2.15
91 pnkfelix 1.1.2.15 /** Constructs an IllegalColor with <code>node = n</code> and
92 pnkfelix 1.1.2.15 <code>color = c</code>.
93 pnkfelix 1.1.2.15 */
94 pnkfelix 1.1.2.15 public IllegalColor(Object n, Color c) {
95 pnkfelix 1.1.2.15 super();
96 pnkfelix 1.1.2.15 node = n;
97 pnkfelix 1.1.2.15 color = c;
98 pnkfelix 1.1.2.15 }
99 pnkfelix 1.1.2.15 }
100 pnkfelix 1.1.2.15
101 pnkfelix 1.1.2.14 /** Reverts the graph's color mapping to its initial state.
102 pnkfelix 1.1.2.11 <BR> <B>modifies:</B> <code>this</code>
103 pnkfelix 1.1.2.14 <BR> <B>effects:</B> undoes any modifications made to the
104 pnkfelix 1.1.2.14 graph's Node -> Color mapping. Note that if a colorable
105 pnkfelix 1.1.2.14 graph is to support <i>node precoloring</i>, where
106 pnkfelix 1.1.2.14 elements of the graph are assigned a color prior to an
107 pnkfelix 1.1.2.14 attempt to color the remainder of the graph, then it
108 pnkfelix 1.1.2.14 is not sufficient to implement this method by completely
109 pnkfelix 1.1.2.14 clearing the Node -> Color mapping.
110 pnkfelix 1.1.2.11 */
111 pnkfelix 1.1.2.11 void resetColors();
112 pnkfelix 1.1.2.1
113 pnkfelix 1.1.2.11 /** Sets the color of <code>n</code>.
114 pnkfelix 1.1.2.16 <BR> <B>requires:</B> <code>c</code> != null
115 pnkfelix 1.1.2.15 <BR> <B>modifies:</B> <code>this</code>
116 pnkfelix 1.1.2.16 <BR> <B>effects:</B> If no exception is thrown,
117 pnkfelix 1.1.2.16 puts (n, c) in the Node -> Color mapping
118 pnkfelix 1.1.2.12 @throws IllegalArgumentException <code>n</code> is not
119 pnkfelix 1.1.2.15 present in the node set for <code>this</code>. No
120 pnkfelix 1.1.2.15 modification to <code>this</code>.
121 pnkfelix 1.1.2.12 @throws AlreadyColoredException <code>n</code> is already
122 pnkfelix 1.1.2.15 present in the Node -> Color mapping. No modification to
123 pnkfelix 1.1.2.15 <code>this</code>.
124 pnkfelix 1.1.2.15 @throws IllegalColor <code>c</code> is not an appropriate
125 pnkfelix 1.1.2.15 <code>Color</code> for <code>n</code> in this graph. No
126 pnkfelix 1.1.2.15 modification to <code>this</code>.
127 pnkfelix 1.1.2.11 */
128 pnkfelix 1.1.2.15 void setColor(Object n, Color c) throws IllegalColor;
129 pnkfelix 1.1.2.16
130 pnkfelix 1.1.2.16 /** Removes <code>n</code> from the Node -> Color mapping.
131 pnkfelix 1.1.2.16 <BR> <B>modifies:</B> <code>this</code>
132 pnkfelix 1.1.2.16 <BR> <B>effects</B> If the pair (n, c) is present in
133 pnkfelix 1.1.2.16 the Node -> Color mapping, removes the pair. Else does
134 pnkfelix 1.1.2.16 nothing.
135 pnkfelix 1.1.2.16 @throws IllegalArgumentException <code>n</code> is not present
136 pnkfelix 1.1.2.16 in the node set for <code>this</code>. No modification
137 pnkfelix 1.1.2.16 to <code>this</code>.
138 pnkfelix 1.1.2.16 */
139 pnkfelix 1.1.2.16 void unsetColor(Object n);
140 pnkfelix 1.1.2.11
141 pnkfelix 1.1.2.11 /** Returns the color of <code>node</code>.
142 pnkfelix 1.1.2.11 <BR> <B>effects:</B> Returns the color associated with
143 pnkfelix 1.1.2.11 <code>node</code> in the Node -> Color mapping, or null
144 pnkfelix 1.1.2.11 if there is no entry in the mapping for
145 pnkfelix 1.1.2.11 <code>node</code>.
146 pnkfelix 1.1.2.11 @throws IllegalArgumentException If <code>node</code> is not
147 pnkfelix 1.1.2.11 present in the node set for <code>this</code>.
148 pnkfelix 1.1.2.11 */
149 pnkfelix 1.1.2.11 Color getColor(Object node);
150 pnkfelix 1.1.2.2
151 pnkfelix 1.1.2.1 /** Temporarily removes <code>node</code> from graph.
152 pnkfelix 1.1.2.6 <BR> <B>modifies:</B> <code>this</code>, <code>node</code>
153 pnkfelix 1.1.2.11 <BR> <B>effects:</B> Removes <code>node</code> and
154 pnkfelix 1.1.2.11 <code>node</code>'s associated edges from
155 pnkfelix 1.1.2.11 <code>this</code>, pushing it onto hidden-nodes stack
156 pnkfelix 1.1.2.11 for later replacement in the graph. Also updates all
157 pnkfelix 1.1.2.11 edges and nodes of <code>this</code> to reflect that
158 pnkfelix 1.1.2.11 <code>node</code> has been hidden.
159 pnkfelix 1.1.2.11 @throws IllegalArgumentException If <code>node</code> is not
160 pnkfelix 1.1.2.11 present in the node set for <code>this</code>.
161 pnkfelix 1.1.2.1 */
162 pnkfelix 1.1.2.11 void hide( Object node );
163 pnkfelix 1.1.2.1
164 pnkfelix 1.1.2.11 /** Replaces the last hidden node</code> into the graph.
165 pnkfelix 1.1.2.11 <BR> <B>modifies:</B> <code>this</code>
166 pnkfelix 1.1.2.11 <BR> <B>effects:</B>
167 pnkfelix 1.1.2.11 if hidden-nodes stack is empty,
168 pnkfelix 1.1.2.11 then returns null
169 pnkfelix 1.1.2.11 else let n = Pop(hidden-nodes stack).
170 pnkfelix 1.1.2.11 puts `n' and its associated edges back in the
171 pnkfelix 1.1.2.11 graph, updating all edges and nodes of
172 pnkfelix 1.1.2.11 <code>this</code> to reflect that n has been
173 pnkfelix 1.1.2.11 replaced.
174 pnkfelix 1.1.2.11 Returns n.
175 pnkfelix 1.1.2.1 */
176 pnkfelix 1.1.2.11 Object replace();
177 pnkfelix 1.1.2.1
178 pnkfelix 1.1.2.1 /** Replaces all hidden nodes in graph.
179 pnkfelix 1.1.2.11 <BR> <B>modifies:</B> <code>this</code>
180 pnkfelix 1.1.2.11 <BR> <B>effects:</B>
181 pnkfelix 1.1.2.11 until hidden-nodes stack is empty,
182 pnkfelix 1.1.2.11 let n = Pop(hidden-nodes stack).
183 pnkfelix 1.1.2.11 puts `n' and its associated edges back in the
184 pnkfelix 1.1.2.11 graph, updating all edges and nodes of
185 pnkfelix 1.1.2.11 <code>this</code> to reflect that n has been
186 pnkfelix 1.1.2.11 replaced.
187 pnkfelix 1.1.2.1 */
188 pnkfelix 1.1.2.11 void replaceAll();
189 pnkfelix 1.1.2.1
190 pnkfelix 1.1.2.1 }
191 cananian 1.2