1 pnkfelix 1.1.2.1 // OptimisticGraphColorer.java, created Fri Jul 28 18:45:20 2000 by pnkfelix
2 cananian 1.1.2.11 // Copyright (C) 2000 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.10 import harpoon.Analysis.GraphColoring.ColorableGraph.IllegalColor;
7 pnkfelix 1.1.2.10
8 pnkfelix 1.1.2.1 import java.util.List;
9 pnkfelix 1.1.2.1 import java.util.Iterator;
10 pnkfelix 1.1.2.1 import java.util.Collection;
11 pnkfelix 1.1.2.1 import java.util.ArrayList;
12 pnkfelix 1.1.2.1 import java.util.Set;
13 pnkfelix 1.1.2.1 import java.util.HashSet;
14 pnkfelix 1.1.2.1 import java.util.Vector;
15 pnkfelix 1.1.2.1 import java.util.Stack;
16 pnkfelix 1.1.2.1 import java.util.Enumeration;
17 pnkfelix 1.1.2.1
18 pnkfelix 1.1.2.1 import harpoon.Util.Util;
19 cananian 1.5 import net.cscott.jutil.LinearSet;
20 pnkfelix 1.1.2.1
21 pnkfelix 1.1.2.1 /**
22 pnkfelix 1.1.2.1 * <code>OptimisticGraphColorer</code> uses a strategy similar to that
23 pnkfelix 1.1.2.1 * of <code>SimpleGraphColorer</code>, except after removing
24 pnkfelix 1.1.2.1 * all nodes with degree < K (where K is the number of colors
25 pnkfelix 1.1.2.2 * provided), it begins optimistically removing nodes in the hopes
26 pnkfelix 1.1.2.2 * that they will not actually need to be spilled. By default it
27 pnkfelix 1.1.2.2 * selects the nodes with the largest degree for removal in this
28 pnkfelix 1.1.2.2 * second stage, but this is parameterizable.
29 pnkfelix 1.1.2.1 *
30 cananian 1.1.2.11 * @author Felix S. Klock II <pnkfelix@mit.edu>
31 cananian 1.6 * @version $Id: OptimisticGraphColorer.java,v 1.6 2004/02/08 03:19:33 cananian Exp $
32 pnkfelix 1.1.2.1 */
33 pnkfelix 1.1.2.1 public class OptimisticGraphColorer extends GraphColorer {
34 pnkfelix 1.1.2.2
35 pnkfelix 1.1.2.8 public static boolean MONITOR = false;
36 pnkfelix 1.1.2.7 private static void MONITOR(String s) {
37 pnkfelix 1.1.2.7 if (MONITOR) System.out.print(s);
38 pnkfelix 1.1.2.7 }
39 pnkfelix 1.1.2.7
40 pnkfelix 1.1.2.2 private final NodeSelector selector;
41 pnkfelix 1.1.2.1
42 pnkfelix 1.1.2.2 public static abstract class NodeSelector {
43 pnkfelix 1.1.2.2 /** Returns a element of <code>g.nodeSet()</code>, in the
44 pnkfelix 1.1.2.2 intent that it be removed from <code>g</code>.
45 pnkfelix 1.1.2.2 <BR> <B>requires:</B> g.nodeSet() is not empty.
46 pnkfelix 1.1.2.2 <BR> <B>effects:</B> returns some element of g.nodeSet().
47 pnkfelix 1.1.2.6 */
48 pnkfelix 1.1.2.8 public abstract Object chooseNodeForRemoval(ColorableGraph g);
49 pnkfelix 1.1.2.8
50 pnkfelix 1.1.2.8 /** Returns a element of <code>g.nodeSet()</code>, in the
51 pnkfelix 1.1.2.9 intent that it be hidden in <code>g</code>.
52 pnkfelix 1.1.2.8 <BR> <B>requires:</B> g.nodeSet() is not empty.
53 pnkfelix 1.1.2.9 <BR> <B>effects:</B>
54 pnkfelix 1.1.2.9 returns some uncolored element of g.nodeSet(), or
55 pnkfelix 1.1.2.9 null if all the elements of g.nodeSet() are colored.
56 pnkfelix 1.1.2.8 */
57 pnkfelix 1.1.2.8 public abstract Object chooseNodeForHiding(ColorableGraph g);
58 pnkfelix 1.1.2.8
59 pnkfelix 1.1.2.10 /** Checks if node can be removed from graph to improve
60 pnkfelix 1.1.2.10 colorability.
61 pnkfelix 1.1.2.10 <BR> <B>requires:</B> n is in g
62 pnkfelix 1.1.2.10 <BR> <B>effects:</B> returns True if n could ever be
63 pnkfelix 1.1.2.10 returned from chooseNodeForRemoval(g), False
64 pnkfelix 1.1.2.10 otherwise.
65 pnkfelix 1.1.2.10 */
66 pnkfelix 1.1.2.10 public abstract boolean allowedToRemove(Object n,ColorableGraph g);
67 pnkfelix 1.1.2.10
68 pnkfelix 1.1.2.2 }
69 pnkfelix 1.1.2.2
70 pnkfelix 1.1.2.8 private static NodeSelector DEFAULT_SELECTOR = new SimpleSelector();
71 pnkfelix 1.1.2.8
72 pnkfelix 1.1.2.8 public static class SimpleSelector extends NodeSelector {
73 pnkfelix 1.1.2.8 protected SimpleSelector() { }
74 pnkfelix 1.1.2.10 public boolean allowedToRemove(Object n, ColorableGraph g) {
75 pnkfelix 1.1.2.10 return true;
76 pnkfelix 1.1.2.10 }
77 pnkfelix 1.1.2.8 public Object chooseNodeForRemoval(ColorableGraph g) {
78 pnkfelix 1.1.2.9 Object o = chooseNode(g);
79 cananian 1.3.2.1 assert o != null;
80 pnkfelix 1.1.2.9 return o;
81 pnkfelix 1.1.2.8 }
82 pnkfelix 1.1.2.8 public Object chooseNodeForHiding(ColorableGraph g) {
83 pnkfelix 1.1.2.9 Object o = chooseNode(g);
84 pnkfelix 1.1.2.9 return o;
85 pnkfelix 1.1.2.8 }
86 pnkfelix 1.1.2.8 private Object chooseNode(ColorableGraph g) {
87 pnkfelix 1.1.2.8 Object spillChoice = null;
88 pnkfelix 1.1.2.8 Set nset = g.nodeSet();
89 pnkfelix 1.1.2.8 int maxDegree = -1;
90 pnkfelix 1.1.2.8 for(Iterator ns = nset.iterator(); ns.hasNext();){
91 pnkfelix 1.1.2.8 Object n = ns.next();
92 pnkfelix 1.1.2.8 if (g.getColor(n) == null &&
93 pnkfelix 1.1.2.8 g.getDegree(n) > maxDegree) {
94 pnkfelix 1.1.2.8 spillChoice = n;
95 pnkfelix 1.1.2.8 maxDegree = g.getDegree(n);
96 pnkfelix 1.1.2.2 }
97 pnkfelix 1.1.2.2 }
98 pnkfelix 1.1.2.8 return spillChoice;
99 pnkfelix 1.1.2.8 }
100 pnkfelix 1.1.2.8 }
101 pnkfelix 1.1.2.8
102 pnkfelix 1.1.2.2 /** Creates a <code>OptimisticGraphColorer</code> with the default
103 pnkfelix 1.1.2.2 second stage selection strategy. */
104 pnkfelix 1.1.2.2 public OptimisticGraphColorer() {
105 pnkfelix 1.1.2.2 this.selector = DEFAULT_SELECTOR;
106 pnkfelix 1.1.2.2 }
107 pnkfelix 1.1.2.2
108 pnkfelix 1.1.2.2 /** Creates a <code>OptimisticGraphColorer</code> with
109 pnkfelix 1.1.2.2 <code>selector</code> as its second stage selection
110 pnkfelix 1.1.2.2 strategy. */
111 pnkfelix 1.1.2.2 public OptimisticGraphColorer(NodeSelector selector) {
112 pnkfelix 1.1.2.2 this.selector = selector;
113 pnkfelix 1.1.2.2 }
114 pnkfelix 1.1.2.1
115 pnkfelix 1.1.2.5 private boolean uncoloredNodesRemain(ColorableGraph g) {
116 pnkfelix 1.1.2.5 Iterator nodes = g.nodeSet().iterator();
117 pnkfelix 1.1.2.5 while(nodes.hasNext()) {
118 pnkfelix 1.1.2.5 if (g.getColor(nodes.next()) == null)
119 pnkfelix 1.1.2.5 return true;
120 pnkfelix 1.1.2.5 }
121 pnkfelix 1.1.2.5 return false;
122 pnkfelix 1.1.2.5 }
123 pnkfelix 1.1.2.5
124 pnkfelix 1.1.2.1 public final void color(ColorableGraph graph, List colors)
125 pnkfelix 1.1.2.1 throws UnableToColorGraph {
126 pnkfelix 1.1.2.1 boolean moreNodesToHide;
127 pnkfelix 1.1.2.1
128 pnkfelix 1.1.2.1 HashSet spills = new HashSet();
129 pnkfelix 1.1.2.1 for(;;) {
130 pnkfelix 1.1.2.1 do {
131 pnkfelix 1.1.2.1 moreNodesToHide = false;
132 pnkfelix 1.1.2.5 LinearSet nodeSet = new LinearSet(graph.nodeSet());
133 pnkfelix 1.1.2.1 for(Iterator ns = nodeSet.iterator(); ns.hasNext();){
134 pnkfelix 1.1.2.1 Object n = ns.next();
135 pnkfelix 1.1.2.5 if (graph.getDegree(n) < colors.size() &&
136 pnkfelix 1.1.2.5 graph.getColor(n) == null) {
137 pnkfelix 1.1.2.1 graph.hide(n);
138 pnkfelix 1.1.2.1 moreNodesToHide = true;
139 pnkfelix 1.1.2.7
140 pnkfelix 1.1.2.7 // MONITOR("conservative hide: "+n+"\n");
141 pnkfelix 1.1.2.1 }
142 pnkfelix 1.1.2.1 }
143 pnkfelix 1.1.2.1 } while (moreNodesToHide);
144 pnkfelix 1.1.2.5
145 pnkfelix 1.1.2.5 // Either the graph is finished (no uncolored nodes
146 pnkfelix 1.1.2.5 // remain) or all nodes present have degree >= K, in which
147 pnkfelix 1.1.2.5 // case we optimistically remove the node chosen by
148 pnkfelix 1.1.2.5 // this.selector.
149 pnkfelix 1.1.2.1
150 pnkfelix 1.1.2.5 if (!uncoloredNodesRemain(graph)) {
151 pnkfelix 1.1.2.1 break;
152 pnkfelix 1.1.2.1 } else {
153 pnkfelix 1.1.2.8 Object choice = this.selector.chooseNodeForHiding(graph);
154 pnkfelix 1.1.2.2 graph.hide(choice);
155 pnkfelix 1.1.2.2 spills.add(choice);
156 pnkfelix 1.1.2.7
157 pnkfelix 1.1.2.7 MONITOR("optimistic hide: "+choice+"\n");
158 pnkfelix 1.1.2.1 continue;
159 pnkfelix 1.1.2.1 }
160 pnkfelix 1.1.2.1 }
161 pnkfelix 1.1.2.5
162 pnkfelix 1.1.2.8 HashSet allSpills = new HashSet(spills);
163 pnkfelix 1.1.2.6 boolean unableToColor = false;
164 pnkfelix 1.1.2.8
165 pnkfelix 1.1.2.3 nextNode:
166 pnkfelix 1.1.2.1 for(Object n=graph.replace(); n!=null; n=graph.replace()){
167 pnkfelix 1.1.2.1 // find color that none of n's neighbors is set to
168 pnkfelix 1.1.2.1
169 pnkfelix 1.1.2.1 if (graph.getColor(n) != null) {
170 pnkfelix 1.1.2.5 // precolored, die
171 cananian 1.3.2.1 assert false;
172 pnkfelix 1.1.2.1 }
173 pnkfelix 1.1.2.1
174 pnkfelix 1.1.2.1 Collection nborsC = graph.neighborsOf(n);
175 pnkfelix 1.1.2.1 HashSet nColors = new HashSet(nborsC.size());
176 pnkfelix 1.1.2.1 for(Iterator nbors = nborsC.iterator(); nbors.hasNext();){
177 pnkfelix 1.1.2.1 Object nb = nbors.next();
178 pnkfelix 1.1.2.9 if (spills.contains(nb)) continue;
179 pnkfelix 1.1.2.9
180 pnkfelix 1.1.2.3 Color col = graph.getColor(nb);
181 pnkfelix 1.1.2.6
182 pnkfelix 1.1.2.6 // nb can have no color, if it was a failed optimistic
183 pnkfelix 1.1.2.6 // spill. treat it as not needing a color.
184 pnkfelix 1.1.2.6 if (col != null) nColors.add(col);
185 pnkfelix 1.1.2.1 }
186 pnkfelix 1.1.2.1
187 pnkfelix 1.1.2.6 nextColor:
188 cananian 1.6 for(Object colO : colors){
189 cananian 1.6 Color col = (Color) colO;
190 pnkfelix 1.1.2.1 if (!nColors.contains(col)) {
191 pnkfelix 1.1.2.3 try {
192 pnkfelix 1.1.2.8 // MONITOR("trying "+col+" with "+n+"\n");
193 pnkfelix 1.1.2.3 graph.setColor(n, col);
194 pnkfelix 1.1.2.6 spills.remove(n);
195 pnkfelix 1.1.2.7
196 pnkfelix 1.1.2.7 // MONITOR("set color of "+n+ " to "+col+"\n");
197 pnkfelix 1.1.2.3 continue nextNode;
198 pnkfelix 1.1.2.10 } catch (IllegalColor ic) {
199 pnkfelix 1.1.2.3 // col was not legal for n
200 pnkfelix 1.1.2.3 // try another color...
201 pnkfelix 1.1.2.9 if (false) MONITOR(col + " not legal for " + n +
202 pnkfelix 1.1.2.8 "b/c of conflict between "+
203 pnkfelix 1.1.2.8 ic.color + " and " + ic.node+"\n");
204 pnkfelix 1.1.2.6 continue nextColor;
205 pnkfelix 1.1.2.3 }
206 pnkfelix 1.1.2.1 }
207 pnkfelix 1.1.2.1 }
208 pnkfelix 1.1.2.3
209 pnkfelix 1.1.2.3 // if we ever reach this point, we failed to color n
210 pnkfelix 1.1.2.7 MONITOR("failed to color "+n+"\n");
211 pnkfelix 1.1.2.9 // MONITOR("nbors(n): "+graph.neighborsOf(n));
212 pnkfelix 1.1.2.10
213 pnkfelix 1.1.2.10 Object choice = null; int max = -1;
214 pnkfelix 1.1.2.10 for(Iterator ns=graph.neighborsOf(n).iterator();ns.hasNext();){
215 pnkfelix 1.1.2.10 Object nde = ns.next();
216 pnkfelix 1.1.2.10 if (graph.getDegree(nde) > max &&
217 pnkfelix 1.1.2.10 selector.allowedToRemove(nde,graph)) {
218 pnkfelix 1.1.2.10 choice = nde;
219 pnkfelix 1.1.2.10 max = graph.getDegree(nde);
220 pnkfelix 1.1.2.10 }
221 pnkfelix 1.1.2.10 }
222 pnkfelix 1.1.2.10 if (choice == null)
223 pnkfelix 1.1.2.10 choice = this.selector.chooseNodeForRemoval(graph);
224 pnkfelix 1.1.2.9 if (choice != null) {
225 pnkfelix 1.1.2.9 spills.add(choice);
226 pnkfelix 1.1.2.9 allSpills.add(choice);
227 pnkfelix 1.1.2.10 graph.unsetColor(choice);
228 pnkfelix 1.1.2.9 }
229 pnkfelix 1.1.2.6 unableToColor = true;
230 pnkfelix 1.1.2.6 }
231 pnkfelix 1.1.2.6
232 pnkfelix 1.1.2.6 if (unableToColor) {
233 pnkfelix 1.1.2.3 UnableToColorGraph u = new UnableToColorGraph();
234 pnkfelix 1.1.2.3 u.rmvSuggs = spills;
235 pnkfelix 1.1.2.8 u.rmvSuggsLarge = allSpills;
236 pnkfelix 1.1.2.3 throw u;
237 pnkfelix 1.1.2.1 }
238 pnkfelix 1.1.2.1 }
239 pnkfelix 1.1.2.1
240 cananian 1.2 }