harpoon.Analysis.GraphColoring
Class SparseGraph

java.lang.Object
  harpoon.Analysis.GraphColoring.AbstractGraph
      harpoon.Analysis.GraphColoring.SparseGraph

All Implemented Interfaces:

ColorableGraph, Graph

public class SparseGraph
extends AbstractGraph
implements ColorableGraph

SparseGraph is an implementation of a ColorableGraph object. Nodes are represented by a list SparseNodes, and edges are represented by the references SparseNodes store internally.

Version:

$Id: SparseGraph.java,v 1.6 2004/02/08 01:52:03 cananian Exp $

Author:

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

Nested Class Summary

protected static class

ColorableGraphImpl.HiddenFilteringEnum Deprecated. Wrapper class for Enumeration that filters out hidden nodes.

Nested classes/interfaces inherited from interface harpoon.Analysis.GraphColoring.ColorableGraph

ColorableGraph.AlreadyColoredException, ColorableGraph.AlreadyHiddenException, ColorableGraph.IllegalColor

Field Summary

protected UniqueVector

nodes Deprecated.

Constructor Summary

SparseGraph()
Creates a SparseGraph.

Method Summary

void	addEdge(Node from, Node to) Deprecated. Adds an edge from from to to.
void	addNode(Node n) Wrapper method that calls super.addNode(n).
protected void	checkNode(Node node) Ensures that only SparseNodes are added to this.
Enumeration	getChildrenOf(Node node) Constructs an enumeration for the children of a specific node.
Color	getColor(Object node) Returns the color of node.
int	getDegree(Node node) Returns the degree of node.
Enumeration	getNeighborsOf(Node node) Constructs an enumeration for the parents of a specific node.
Enumeration	getNodes() Deprecated. Constructs an enumeration for all the nodes.
protected UniqueVector	getNodeVector() Deprecated. Nodes accessor method for subclass use.
Enumeration	getParentsOf(Node node) Constructs an enumeration for the parents of a specific node.
void	hide(Object node) Temporarily removes node from graph.
boolean	isModifiable() Modifiability check.
void	makeEdge(Node from, Node to) Generates an edge from from to to.
Collection	neighborsOf(Object node) Returns a collection view for the neighbors of a specific node.
Set	nodeSet() Returns a set view of the nodes in this.
Object	replace() Replaces the last hidden node into the graph.
void	replaceAll() Replaces all hidden nodes in graph.
void	resetColors() Reverts the graph to an uncolored state.
void	resetGraph() Returns all nodes in graph to their original 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 class harpoon.Analysis.GraphColoring.AbstractGraph

addEdge, addNode, edges, edgesFor, getDegree

Methods inherited from class java.lang.Object

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

Methods inherited from interface harpoon.Analysis.GraphColoring.ColorableGraph

addNode

Methods inherited from interface harpoon.Analysis.GraphColoring.Graph

addEdge, edges, edgesFor, getDegree

Field Detail

nodes

protected UniqueVector nodes

Deprecated.

Constructor Detail

SparseGraph

public SparseGraph()

Creates a SparseGraph.

Method Detail

checkNode

protected void checkNode(Node node)

Ensures that only SparseNodes are added to this.
requires: node is an instance of a SparseNode
effects: Does nothing.

makeEdge

public void makeEdge(Node from,
                     Node to)

Generates an edge from from to to.
requires: from and to are present in this and are valid targets for a new edge (SparseGraph does not allow multiple edges or circular edges).
modifies: from, to
effects: Adds an edge from from to to.

getDegree

public int getDegree(Node node)

Returns the degree of node.
requires: node is present in this.
effects: Returns the number of other ColorableNodes that node is connected to.

getChildrenOf

public Enumeration getChildrenOf(Node node)

Constructs an enumeration for the children of a specific node.
requires: node is present in this.
effects: Returns an Enumeration of the Nodes that have an edge from node to them that are not hidden.
requires: this is not modified while the Enumeration returned is still in use.

getParentsOf

public Enumeration getParentsOf(Node node)
                         throws NodeNotPresentInGraphException

Constructs an enumeration for the parents of a specific node.
effects: Returns an Enumeration of the nodes that have an edge from them to node.
requires: this is not modified while the Enumeration returned is still in use.

Throws:

NodeNotPresentInGraphException

getNeighborsOf

public Enumeration getNeighborsOf(Node node)
                           throws NodeNotPresentInGraphException

Constructs an enumeration for the parents of a specific node.
requires: node is present in this.
effects: Returns an Enumeration of the nodes that have an edge between node and them.
requires: this is not modified while the Enumeration returned is still in use.

Throws:

NodeNotPresentInGraphException

isModifiable

public boolean isModifiable()

Modifiability check. Subclasses should override this method to incorporate consistency checks, and should ensure that they call super.isModifiable in their check.
effects: If this is allowed to be modified, returns true. Else returns false.

addNode

public void addNode(Node n)

Wrapper method that calls super.addNode(n). Needed to resolve ambiguity in method resolution at compile-time.

resetGraph

public void resetGraph()

Returns all nodes in graph to their original state.
modifies: this
effects: the Node -> Color mapping is cleared and each hidden node is restored; this is otherwise unchanged.

resetColors

public void resetColors()

Reverts the graph to an uncolored state.
modifies: this
effects: clears the Node -> Color mapping.

Specified by:

resetColors in interface ColorableGraph

setColor

public void setColor(Object n,
                     Color c)

Sets the color of n.
effects: If c is null, then removes n from the Node -> Color mapping. Else puts (n, c) in the Node -> Color mapping.

Specified by:

setColor in interface ColorableGraph

Throws:

IllegalArgumentException - If n is not present in the node set for this or n has already been colored.

unsetColor

public void unsetColor(Object n)

Description copied from interface: ColorableGraph

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.

Specified by:

unsetColor in interface ColorableGraph

getColor

public 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.

Specified by:

getColor in interface ColorableGraph

Throws:

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

hide

public 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.

Specified by:

hide in interface ColorableGraph

Throws:

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

replace

public 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.

Specified by:

replace in interface ColorableGraph

replaceAll

public 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.

Specified by:

replaceAll in interface ColorableGraph

nodeSet

public Set nodeSet()

Returns a set view of the nodes in this.
effects: Returns an Set of the Objects that have been successfully added to this.

Specified by:

nodeSet in interface Graph

Specified by:

nodeSet in class AbstractGraph

neighborsOf

public Collection neighborsOf(Object node)

Returns a collection view for the neighbors of a specific node.
effects: Returns an Collection of Objects that have an edge between node and them.
mandates: node is not removed from this while the returned Collection is in use.

Specified by:

neighborsOf in interface Graph

Specified by:

neighborsOf in class AbstractGraph

Throws:

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

getNodes

public Enumeration getNodes()

Deprecated.

Constructs an enumeration for all the nodes.
effects: Returns an Enumeration of the ColorableNodes that have been successfully added to this that are not currently hidden.
requires: this is not modified while the Enumeration returned is in use.

addEdge

public void addEdge(Node from,
                    Node to)

Deprecated.

Adds an edge from from to to.
requires: from and to are present in this and are valid targets for a new edge.
modifies: this.

getNodeVector

protected UniqueVector getNodeVector()

Deprecated.

Nodes accessor method for subclass use.
effects: Returns the UniqueVector of the Nodes that have been successfully added to this.