harpoon.Analysis.GraphColoring
Interface Graph

All Known Subinterfaces:

ColorableGraph, DirectedGraph

All Known Implementing Classes:

AbstractGraph, SparseGraph

public interface Graph

Abstractly, a Graph is a pair (V, E), where V is a set of nodes and E is collection of edges between those nodes. (E is a collection instead of a set to allow for multigraphs which allow multiple edges to exist between the same two nodes) The Graph interface provides a number of collection views of the data maintained by a graph. In addition to being able to view the nodes and their neighbors, one can also view the edges between the nodes themselves. Note that since some graphs may not concretely maintain edge objects in their internal representation, the edges may have to be constructed on demand (a performance drain).

Version:

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

Author:

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

Method Summary

boolean	addEdge(Object m, Object n) Ensures that this graph contains an edge between m and n (optional operation).
boolean	addNode(Object node) Ensures that this graph contains node (optional operation).
Collection	edges() Returns a collection view of the edges contained in this graph.
Collection	edgesFor(Object node) Returns a collection view of the edges joining node to nodes in the graph.
int	getDegree(Object node) Returns the degree of node.
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.

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.

Throws:

UnsupportedOperationException - addNode is not supported by this graph.

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

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

addEdge

boolean addEdge(Object m,
                Object n)

Ensures that this graph contains an edge between m and n (optional operation).
modifies: this.
effects: If this method returns normally, an edge between m and n will be in this. Returns true if this changed as a result of the call.

Throws:

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

UnsupportedOperationException - addEdge is not supported by this graph.

getDegree

int getDegree(Object node)

Returns the degree of node.
effects: Returns the number of other Objects that node is joined with.

Throws:

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

nodeSet

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.

neighborsOf

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.

Throws:

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

edges

Collection edges()

Returns a collection view of the edges contained in this graph.
effects: Returns a Collection of two-element Collections (known as pairs) where each pair corresponds to an edge { n1, n2 } in this. If the graph is modified while an iteration over the collection is in progress, the results of the iteration are undefined. Order may or may not be significant in the pairs returned.

edgesFor

Collection edgesFor(Object node)

Returns a collection view of the edges joining node to nodes in the graph.
effects: Returns a Collection of two-element Collections (known as pairs) where each pair corresponds to an edge { node, n } in this. If the graph is modified while an iteration over the collection is in progress, the results of the iteration are undefined. Order may or may not be significant in the pairs returned.

Throws:

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