1 pnkfelix 1.1.2.1 // UnboundedGraphColorer.java, created Mon Jul 24 10:56:07 2000 by pnkfelix
2 cananian 1.1.2.6 // 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.1 import java.util.List;
7 pnkfelix 1.1.2.1
8 pnkfelix 1.1.2.1 /**
9 pnkfelix 1.1.2.1 * <code>UnboundedGraphColorer</code> uses the graph coloring strategy
10 pnkfelix 1.1.2.1 * provided by another <code>GraphColorer</code> to search for a near
11 pnkfelix 1.1.2.1 * minimum number of colors required. It generates colors dynamically
12 pnkfelix 1.1.2.1 * using a <code>ColorFactory</code>.
13 pnkfelix 1.1.2.1 *
14 cananian 1.1.2.6 * @author Felix S. Klock II <pnkfelix@mit.edu>
15 cananian 1.2 * @version $Id: UnboundedGraphColorer.java,v 1.2 2002/02/25 20:57:17 cananian Exp $
16 pnkfelix 1.1.2.1 */
17 pnkfelix 1.1.2.1 public class UnboundedGraphColorer extends GraphColorer {
18 pnkfelix 1.1.2.1
19 pnkfelix 1.1.2.1 private ColorFactory factory;
20 pnkfelix 1.1.2.1 private GraphColorer colorer;
21 pnkfelix 1.1.2.1
22 pnkfelix 1.1.2.1 /** Creates a <code>UnboundedGraphColorer</code>.
23 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Constructs an UnboundedGraphColorer that
24 pnkfelix 1.1.2.1 will use <code>colorer</code> for its coloring strategy
25 pnkfelix 1.1.2.1 and <code>cf</code> to produce the set of colors used in
26 pnkfelix 1.1.2.1 the coloring.
27 pnkfelix 1.1.2.1 */
28 pnkfelix 1.1.2.1 public UnboundedGraphColorer(GraphColorer colorer, ColorFactory cf) {
29 pnkfelix 1.1.2.1 super();
30 pnkfelix 1.1.2.1 this.factory = cf;
31 pnkfelix 1.1.2.1 this.colorer = colorer;
32 pnkfelix 1.1.2.1 }
33 pnkfelix 1.1.2.1
34 pnkfelix 1.1.2.1 /** Finds a coloring for <code>graph</code>.
35 pnkfelix 1.1.2.1 <BR> <B>modifies:</B> <code>graph</code>, <code>this</code>
36 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Performs a search for a near-minimum
37 pnkfelix 1.1.2.1 number of colors needed to color <code>graph</code>,
38 pnkfelix 1.1.2.1 producing <code>Color</code>s as needed from the
39 pnkfelix 1.1.2.1 <code>ColorFactory</code> associated with
40 pnkfelix 1.1.2.1 <code>this</code>. Once an appopriate set is found,
41 pnkfelix 1.1.2.1 colors <code>graph</code> accordingly.
42 pnkfelix 1.1.2.1 */
43 pnkfelix 1.1.2.1 public void findColoring( ColorableGraph graph ) {
44 pnkfelix 1.1.2.1 // modifies: this.factory
45 pnkfelix 1.1.2.1 int upperBound = 1; // upperBound is inclusive
46 pnkfelix 1.1.2.1
47 pnkfelix 1.1.2.1 while (! ableToColor( graph, upperBound ) ) {
48 pnkfelix 1.1.2.1 upperBound *= 2;
49 pnkfelix 1.1.2.1 }
50 pnkfelix 1.1.2.1
51 pnkfelix 1.1.2.1 // managed to color the graph; now find minimum colors
52 pnkfelix 1.1.2.1 // required.
53 pnkfelix 1.1.2.1 int lowerBound = upperBound / 2; // lowerBound is noninclusive
54 pnkfelix 1.1.2.1
55 pnkfelix 1.1.2.1 while (upperBound - lowerBound > 1) {
56 pnkfelix 1.1.2.1 int trial = lowerBound + (upperBound - lowerBound)/2;
57 pnkfelix 1.1.2.1 if (ableToColor( graph, trial)) {
58 pnkfelix 1.1.2.1 upperBound = trial;
59 pnkfelix 1.1.2.1 } else {
60 pnkfelix 1.1.2.1 lowerBound = trial;
61 pnkfelix 1.1.2.1 }
62 pnkfelix 1.1.2.1 }
63 pnkfelix 1.1.2.5
64 pnkfelix 1.1.2.5 // final call to ableToColor to properly set factory size.
65 pnkfelix 1.1.2.5 ableToColor(graph, upperBound);
66 pnkfelix 1.1.2.1
67 pnkfelix 1.1.2.4 try {
68 pnkfelix 1.1.2.4 color( graph, factory.getColors() );
69 pnkfelix 1.1.2.4 } catch ( UnableToColorGraph u ) {
70 pnkfelix 1.1.2.1 throw new RuntimeException
71 pnkfelix 1.1.2.1 ("Something went horribly wrong with the color search");
72 pnkfelix 1.1.2.1 }
73 pnkfelix 1.1.2.1 }
74 pnkfelix 1.1.2.1
75 pnkfelix 1.1.2.1 /** Attempts to color <code>graph</code> using only
76 pnkfelix 1.1.2.1 <code>numCols</code> colors.
77 pnkfelix 1.1.2.1 <BR> <B>modifies:</B> <code>graph</code>, <code>this</code>
78 pnkfelix 1.1.2.1 <BR> <B>effects:</B> First expands or reduces the inventory of
79 pnkfelix 1.1.2.1 the <code>ColorFactory</code> associated with
80 pnkfelix 1.1.2.1 <code>this</code> to make it have the number of colors
81 pnkfelix 1.1.2.1 indicated by <code>numCols</code>. Then attempts to
82 pnkfelix 1.1.2.1 color <code>graph</code> with that number of colors,
83 pnkfelix 1.1.2.1 returning true if successful and false otherwise.
84 pnkfelix 1.1.2.1 */
85 pnkfelix 1.1.2.1 private boolean ableToColor( ColorableGraph graph, int numCols ) {
86 pnkfelix 1.1.2.1 // modifies: this.factory
87 pnkfelix 1.1.2.1 if (numCols < factory.getColors().size()) {
88 pnkfelix 1.1.2.1 while (numCols < factory.getColors().size()) {
89 pnkfelix 1.1.2.1 factory.removeColor();
90 pnkfelix 1.1.2.1 }
91 pnkfelix 1.1.2.1 } else if (numCols > factory.getColors().size()) {
92 pnkfelix 1.1.2.1 while (numCols > factory.getColors().size()) {
93 pnkfelix 1.1.2.1 factory.makeColor();
94 pnkfelix 1.1.2.1 }
95 pnkfelix 1.1.2.1 }
96 pnkfelix 1.1.2.1
97 pnkfelix 1.1.2.1 try {
98 pnkfelix 1.1.2.1 color( graph, factory.getColors() );
99 pnkfelix 1.1.2.4 graph.resetColors();
100 pnkfelix 1.1.2.1 return true;
101 pnkfelix 1.1.2.2 } catch ( UnableToColorGraph e ) {
102 pnkfelix 1.1.2.4 graph.replaceAll();
103 pnkfelix 1.1.2.4 graph.resetColors();
104 pnkfelix 1.1.2.1 return false;
105 pnkfelix 1.1.2.1 }
106 pnkfelix 1.1.2.1 }
107 pnkfelix 1.1.2.1
108 pnkfelix 1.1.2.1 public final void color(ColorableGraph graph, List colors)
109 pnkfelix 1.1.2.2 throws UnableToColorGraph {
110 pnkfelix 1.1.2.1 colorer.color(graph, colors);
111 pnkfelix 1.1.2.1 }
112 cananian 1.2 }