harpoon.Analysis.GraphColoring
Class SimpleGraphColorer

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

public class SimpleGraphColorer
extends GraphColorer

SimpleGraphColorer uses the simple but effective graph coloring strategy of progressively removing nodes with degree less than K, (where K is the number of colors provided). This is a conservative heuristic, as it guarantees that if the graph post-removal is K-colorable, then the graph post-replacement will also K-colorable; several improvements on this heuristic are available. Inspired by a 6.035 lecture.

Version:

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

Author:

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

Constructor Summary

SimpleGraphColorer()

Method Summary

void	color(ColorableGraph graph, List colors) Colors graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

SimpleGraphColorer

public SimpleGraphColorer()

Method Detail

color

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

Colors graph.

Specified by:

color in class GraphColorer

Throws:

UnableToColorGraph