harpoon.Analysis.GraphColoring
Class OptimisticGraphColorer

java.lang.Object
  harpoon.Analysis.GraphColoring.GraphColorer
      harpoon.Analysis.GraphColoring.OptimisticGraphColorer

public class OptimisticGraphColorer
extends GraphColorer

OptimisticGraphColorer uses a strategy similar to that of SimpleGraphColorer, except after removing all nodes with degree < K (where K is the number of colors provided), it begins optimistically removing nodes in the hopes that they will not actually need to be spilled. By default it selects the nodes with the largest degree for removal in this second stage, but this is parameterizable.

Version:

$Id: OptimisticGraphColorer.java,v 1.6 2004/02/08 03:19:33 cananian Exp $

Author:

Felix S. Klock II <pnkfelix@mit.edu>

Nested Class Summary

static class	OptimisticGraphColorer.NodeSelector
static class	OptimisticGraphColorer.SimpleSelector

Field Summary

static boolean

MONITOR

Constructor Summary

OptimisticGraphColorer()
Creates a OptimisticGraphColorer with the default second stage selection strategy.

OptimisticGraphColorer(OptimisticGraphColorer.NodeSelector selector)
Creates a OptimisticGraphColorer with selector as its second stage selection strategy.

Method Summary

void	color(ColorableGraph graph, List colors) Attempts to color graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

MONITOR

public static boolean MONITOR

Constructor Detail

OptimisticGraphColorer

public OptimisticGraphColorer()

Creates a OptimisticGraphColorer with the default second stage selection strategy.

OptimisticGraphColorer

public OptimisticGraphColorer(OptimisticGraphColorer.NodeSelector selector)

Creates a OptimisticGraphColorer with selector as its second stage selection strategy.

Method Detail

color

public final void color(ColorableGraph graph,
                        List colors)
                 throws UnableToColorGraph

Description copied from class: GraphColorer

Attempts to color graph.
requires:

1. colors is a List of Colors.
2. graph does not have any hidden nodes.

modifies: graph
effects: Attempts to color graph using the set of Colors given in colors. If successful, every node in graph will be present in graph's Node -> Color mapping, with no two interfering nodes sharing the same color.

Specified by:

color in class GraphColorer

Throws:

UnableToColorGraph