1 pnkfelix 1.1.2.1 // SimpleGraphColorer.java, created Wed Jan 13 14:17:43 1999 by pnkfelix
2 cananian 1.1.2.18 // Copyright (C) 1998 Felix S. Klock II <pnkfelix@mit.edu>
3 cananian 1.1.2.7 // 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.8 import java.util.List;
7 pnkfelix 1.1.2.10 import java.util.Iterator;
8 pnkfelix 1.1.2.10 import java.util.Collection;
9 pnkfelix 1.1.2.10 import java.util.ArrayList;
10 pnkfelix 1.1.2.10 import java.util.HashSet;
11 pnkfelix 1.1.2.6 import java.util.Vector;
12 pnkfelix 1.1.2.6 import java.util.Stack;
13 pnkfelix 1.1.2.6 import java.util.Enumeration;
14 pnkfelix 1.1.2.1
15 pnkfelix 1.1.2.10 import harpoon.Util.Util;
16 cananian 1.3 import net.cscott.jutil.LinearSet;
17 pnkfelix 1.1.2.10
18 pnkfelix 1.1.2.1 /**
19 pnkfelix 1.1.2.16 * <code>SimpleGraphColorer</code> uses the simple but effective graph
20 pnkfelix 1.1.2.16 * coloring strategy of progressively removing nodes with degree less
21 pnkfelix 1.1.2.16 * than K, (where K is the number of colors provided). This is a
22 pnkfelix 1.1.2.16 * conservative heuristic, as it guarantees that if the graph
23 pnkfelix 1.1.2.16 * post-removal is K-colorable, then the graph post-replacement will
24 pnkfelix 1.1.2.16 * also K-colorable; several improvements on this heuristic are
25 pnkfelix 1.1.2.16 * available.
26 pnkfelix 1.1.2.16 * Inspired by a 6.035
27 pnkfelix 1.1.2.16 * <A href="http://ceylon.lcs.mit.edu/6035/lecture18/sld064.htm">lecture</A>.
28 pnkfelix 1.1.2.1 *
29 cananian 1.1.2.18 * @author Felix S. Klock II <pnkfelix@mit.edu>
30 cananian 1.4 * @version $Id: SimpleGraphColorer.java,v 1.4 2004/02/08 03:19:33 cananian Exp $
31 pnkfelix 1.1.2.1 */
32 pnkfelix 1.1.2.1
33 pnkfelix 1.1.2.4 public class SimpleGraphColorer extends GraphColorer {
34 pnkfelix 1.1.2.2
35 pnkfelix 1.1.2.3 private static final boolean DEBUG = false;
36 pnkfelix 1.1.2.5
37 pnkfelix 1.1.2.10 public SimpleGraphColorer() { }
38 pnkfelix 1.1.2.1
39 pnkfelix 1.1.2.16 /** Colors <code>graph</code>.
40 pnkfelix 1.1.2.16 */
41 pnkfelix 1.1.2.10 public final void color(ColorableGraph graph, List colors)
42 pnkfelix 1.1.2.11 throws UnableToColorGraph {
43 pnkfelix 1.1.2.10 // System.out.println("entered color("+graph+", "+colors+")");
44 pnkfelix 1.1.2.10
45 pnkfelix 1.1.2.10 boolean moreNodesToHide = false;
46 pnkfelix 1.1.2.10 do {
47 pnkfelix 1.1.2.10 moreNodesToHide = false;
48 pnkfelix 1.1.2.10
49 pnkfelix 1.1.2.10 // make new copy of nodeSet (can't modify graph and
50 pnkfelix 1.1.2.10 // iterate over it at same time)
51 pnkfelix 1.1.2.10 HashSet nodeSet = new HashSet(graph.nodeSet());
52 pnkfelix 1.1.2.10 Iterator nodes = nodeSet.iterator();
53 pnkfelix 1.1.2.10 while(nodes.hasNext()) {
54 pnkfelix 1.1.2.10 Object n = nodes.next();
55 pnkfelix 1.1.2.10 if (graph.getDegree( n ) < colors.size() ) {
56 pnkfelix 1.1.2.10 graph.hide(n);
57 pnkfelix 1.1.2.10
58 pnkfelix 1.1.2.10 // removing n may have made previous nodes in
59 pnkfelix 1.1.2.10 // the enumeration available to be hidden
60 pnkfelix 1.1.2.10 moreNodesToHide = true;
61 pnkfelix 1.1.2.10 }
62 pnkfelix 1.1.2.10 }
63 pnkfelix 1.1.2.10 } while(moreNodesToHide);
64 pnkfelix 1.1.2.10
65 pnkfelix 1.1.2.10 // at this point, we are assured that there are no more
66 pnkfelix 1.1.2.10 // nodes to hide. Either the graph is finished (no nodes
67 pnkfelix 1.1.2.10 // remain) or all nodes present have degree >=
68 pnkfelix 1.1.2.10 // colors.size(), in which case this algorithm can't color
69 pnkfelix 1.1.2.10 // it without more colors.
70 pnkfelix 1.1.2.10 if (!graph.nodeSet().isEmpty()) {
71 pnkfelix 1.1.2.17 UnableToColorGraph u = new UnableToColorGraph();
72 pnkfelix 1.1.2.17 u.rmvSuggs = new LinearSet(graph.nodeSet());
73 pnkfelix 1.1.2.17 throw u;
74 pnkfelix 1.1.2.10 }
75 pnkfelix 1.1.2.10
76 pnkfelix 1.1.2.17 nextNode:
77 pnkfelix 1.1.2.10 for(Object n=graph.replace(); n!=null; n=graph.replace()){
78 pnkfelix 1.1.2.10 // find color that none of n's neighbors is set to
79 pnkfelix 1.1.2.12
80 pnkfelix 1.1.2.14 if (graph.getColor(n) != null) {
81 pnkfelix 1.1.2.14 // precolored, skip
82 pnkfelix 1.1.2.15 if (false)
83 pnkfelix 1.1.2.15 System.out.println("skipping "+n+
84 pnkfelix 1.1.2.15 "b/c its precolored to "+
85 pnkfelix 1.1.2.15 graph.getColor(n));
86 pnkfelix 1.1.2.17 continue nextNode;
87 pnkfelix 1.1.2.14 }
88 pnkfelix 1.1.2.14
89 pnkfelix 1.1.2.12 Collection nborsC = graph.neighborsOf(n);
90 pnkfelix 1.1.2.12 HashSet nColors = new HashSet(nborsC.size());
91 pnkfelix 1.1.2.12 for(Iterator nbors = nborsC.iterator(); nbors.hasNext();){
92 pnkfelix 1.1.2.12 Object nb = nbors.next();
93 pnkfelix 1.1.2.10 nColors.add(graph.getColor(nb));
94 pnkfelix 1.1.2.10 }
95 pnkfelix 1.1.2.10
96 cananian 1.4 for(Object colO : colors){
97 cananian 1.4 Color col = (Color) colO;
98 pnkfelix 1.1.2.10 if (!nColors.contains(col)) {
99 pnkfelix 1.1.2.17 try {
100 pnkfelix 1.1.2.17 graph.setColor(n, col);
101 pnkfelix 1.1.2.17 continue nextNode;
102 pnkfelix 1.1.2.17 } catch (ColorableGraph.IllegalColor ic) {
103 pnkfelix 1.1.2.17 // col was not legal for n
104 pnkfelix 1.1.2.17 // try another color...
105 pnkfelix 1.1.2.17 }
106 pnkfelix 1.1.2.10 }
107 pnkfelix 1.1.2.10 }
108 pnkfelix 1.1.2.10
109 pnkfelix 1.1.2.17 // if we ever reach this point, we failed to color n
110 pnkfelix 1.1.2.17 UnableToColorGraph u = new UnableToColorGraph();
111 pnkfelix 1.1.2.17 u.rmvSuggs = new LinearSet(graph.nodeSet());
112 pnkfelix 1.1.2.17 throw u;
113 pnkfelix 1.1.2.10 }
114 pnkfelix 1.1.2.10 }
115 pnkfelix 1.1.2.10
116 cananian 1.2 }