harpoon.Analysis.GraphColoring
Interface ColorableGraph

All Superinterfaces:

Graph

All Known Implementing Classes:

SparseGraph

public interface ColorableGraph
extends Graph

ColorableGraph extends GraphColoring.Graph with methods that are useful for a graph-coloring system. Two main pieces of state are added:

1. A Node -> Color mapping
2. A stack of "hidden" nodes.

The first component is inherent in the nature of a colorable graph. The second component of state is to allow optimization of a common routine required by graph-coloring algorithms: the ability to temporarily remove a node and its associated edges from a graph but retaining the information for later replacement into the graph again. When a node is hidden, all methods on the graph will operate as if it has been removed from the graph, except for addNode(Object).

Version:

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

Author:

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

Nested Class Summary

static class	ColorableGraph.AlreadyColoredException AlreadyColoredException will be thrown on attempt to call g.setColor(node,color) when n is present in the node -> color mapping.
static class	ColorableGraph.AlreadyHiddenException AlreadyHiddenException will be thrown on attempt to call g.addNode(n) while n is a member of the set of hidden nodes in g.
static class	ColorableGraph.IllegalColor IllegalColor will be thrown on an attempt to color a node with a color that for some reason is not legal for that node in this graph.

Method Summary

boolean	addNode(Object node) Ensures that this graph contains node (optional operation).
Color	getColor(Object node) Returns the color of node.
void	hide(Object node) Temporarily removes node from graph.
Object	replace() Replaces the last hidden node into the graph.
void	replaceAll() Replaces all hidden nodes in graph.
void	resetColors() Reverts the graph's color mapping to its initial state.
void	setColor(Object n, Color c) Sets the color of n.
void	unsetColor(Object n) Removes n from the Node -> Color mapping.

Methods inherited from interface harpoon.Analysis.GraphColoring.Graph

addEdge, edges, edgesFor, getDegree, neighborsOf, nodeSet

Method Detail

addNode

boolean addNode(Object node)

Ensures that this graph contains node (optional operation).
modifies: this
effects: If this method returns normally, node will be present in the node-set for this. Returns true if this graph changed as a result of the call, false otherwise.

Specified by:

addNode in interface Graph

Throws:

UnsupportedOperationException - addNode is not supported by this graph.

ClassCastException - class of specified element prevents it from being added to this graph.

ColorableGraph.AlreadyHiddenException - node is part of the set of hidden nodes in this

IllegalArgumentException - some aspect of node prevents it from being added to the node-set for this graph.

resetColors

void resetColors()

Reverts the graph's color mapping to its initial state.
modifies: this
effects: undoes any modifications made to the graph's Node -> Color mapping. Note that if a colorable graph is to support node precoloring, where elements of the graph are assigned a color prior to an attempt to color the remainder of the graph, then it is not sufficient to implement this method by completely clearing the Node -> Color mapping.

setColor

void setColor(Object n,
              Color c)
              throws ColorableGraph.IllegalColor

Sets the color of n.
requires: c != null
modifies: this
effects: If no exception is thrown, puts (n, c) in the Node -> Color mapping

Throws:

IllegalArgumentException - n is not present in the node set for this. No modification to this.

ColorableGraph.AlreadyColoredException - n is already present in the Node -> Color mapping. No modification to this.

ColorableGraph.IllegalColor - c is not an appropriate Color for n in this graph. No modification to this.

unsetColor

void unsetColor(Object n)

Removes n from the Node -> Color mapping.
modifies: this
effects If the pair (n, c) is present in the Node -> Color mapping, removes the pair. Else does nothing.

Throws:

IllegalArgumentException - n is not present in the node set for this. No modification to this.

getColor

Color getColor(Object node)

Returns the color of node.
effects: Returns the color associated with node in the Node -> Color mapping, or null if there is no entry in the mapping for node.

Throws:

IllegalArgumentException - If node is not present in the node set for this.

hide

void hide(Object node)

Temporarily removes node from graph.
modifies: this, node
effects: Removes node and node's associated edges from this, pushing it onto hidden-nodes stack for later replacement in the graph. Also updates all edges and nodes of this to reflect that node has been hidden.

Throws:

IllegalArgumentException - If node is not present in the node set for this.

replace

Object replace()

Replaces the last hidden node into the graph.
modifies: this
effects: if hidden-nodes stack is empty, then returns null else let n = Pop(hidden-nodes stack). puts `n' and its associated edges back in the graph, updating all edges and nodes of this to reflect that n has been replaced. Returns n.

replaceAll

void replaceAll()

Replaces all hidden nodes in graph.
modifies: this
effects: until hidden-nodes stack is empty, let n = Pop(hidden-nodes stack). puts `n' and its associated edges back in the graph, updating all edges and nodes of this to reflect that n has been replaced.