harpoon.Analysis.GraphColoring
Class UnboundedGraphColorer

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

public class UnboundedGraphColorer
extends GraphColorer

UnboundedGraphColorer uses the graph coloring strategy provided by another GraphColorer to search for a near minimum number of colors required. It generates colors dynamically using a ColorFactory.

Version:

$Id: UnboundedGraphColorer.java,v 1.2 2002/02/25 20:57:17 cananian Exp $

Author:

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

Constructor Summary

UnboundedGraphColorer(GraphColorer colorer, ColorFactory cf)
Creates a UnboundedGraphColorer.

Method Summary

void	color(ColorableGraph graph, List colors) Attempts to color graph.
void	findColoring(ColorableGraph graph) Finds a coloring for graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

UnboundedGraphColorer

public UnboundedGraphColorer(GraphColorer colorer,
                             ColorFactory cf)

Creates a UnboundedGraphColorer.
effects: Constructs an UnboundedGraphColorer that will use colorer for its coloring strategy and cf to produce the set of colors used in the coloring.

Method Detail

findColoring

public void findColoring(ColorableGraph graph)

Finds a coloring for graph.
modifies: graph, this
effects: Performs a search for a near-minimum number of colors needed to color graph, producing Colors as needed from the ColorFactory associated with this. Once an appopriate set is found, colors graph accordingly.

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