com.phoenixst.plexus
Class DefaultGraph

java.lang.Object
  com.phoenixst.plexus.DefaultGraph

All Implemented Interfaces:

Graph, ObservableGraph, Serializable

Direct Known Subclasses:

DefaultOrientedForest

public class DefaultGraph
extends Object
implements ObservableGraph, Serializable

A default implementation of the ObservableGraph interface.

Design Criteria

There are many ways of representing graphs in software, and this package uses just one of those for the general implementation. Of the two most basic, adjacency list and adjacency matrix, adjacency list is the most efficient for even remotely sparse graphs. Also, the design constraint that nodes and edges are user-provided objects would have made an adjacency matrix representation much more costly in terms of space (a HashMap would be required to map nodes to indices).

In general, it seems preferable to implement a graph as a HashMap from nodes to their adjacency lists. The alternative (using some non-O(1) access Collection) is just too prohibitive in time for the modest gains in space. The design constraints (allowing both directed and undirected edges and edges having identity) really don't leave a lot of room for implementations largely different from the one found here. An adjacency list is pretty much just a list of Edges, with some extra bookkeeping information. Only if a single adjacency list could grow very large would it be worthwhile to implement it as something other than a simple list.

Since:

1.0

Version:

$Revision: 1.117 $

Author:

Ray A. Conner

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from interface com.phoenixst.plexus.Graph

Graph.Edge

Constructor Summary

	DefaultGraph() Creates a new DefaultGraph.
	DefaultGraph(Graph graph) Creates a new DefaultGraph which is a copy of the specified Graph.
protected	DefaultGraph(int nodeSize) Creates a new DefaultGraph with a capacity for the specified number of nodes (avoiding unnecessary rehashing).

Method Summary

Graph.Edge	addEdge(Object object, Object tail, Object head, boolean isDirected) Adds the specified edge to the Graph (optional operation).
protected Graph.Edge	addEdge(Object object, Object tail, Object head, boolean isDirected, Object edgeState) Adds a new Graph.Edge with additional information provided by the edgeState argument, which is given to the createEdge() method.
void	addGraphListener(GraphListener listener) Adds the specified GraphListener which will be notified whenever this ObservableGraph's structure changes.
boolean	addNode(Object node) Adds node to this Graph (optional operation).
Collection	adjacentNodes(Object node, org.apache.commons.collections.Predicate traverserPredicate) Returns the nodes adjacent to the specified node for which the specified Predicate is satisfied.
boolean	containsEdge(Graph.Edge edge) Returns true if this Graph contains the specified Graph.Edge.
boolean	containsNode(Object node) Returns true if this Graph contains the specified node.
protected Graph.Edge	createEdge(Object object, Object tail, Object head, boolean isDirected, Object edgeState) Creates a new Graph.Edge.
int	degree(Object node) Returns the degree of node, defined as the number of edges incident on node, with self-loops counted twice.
int	degree(Object node, org.apache.commons.collections.Predicate traverserPredicate) Returns the degree of node for which the specified Predicate is satisfied, defined as the number of edges incident on node that pass the predicate, with self-loops counted only once.
protected void	edgeAdded(Graph.Edge edge) Invoked after an edge has been added to this Graph and any GraphListeners have been notified.
protected void	edgeAdding(Graph.Edge edge) Invoked before an edge has been added to this Graph and any GraphListeners have been notified.
protected void	edgeRemoved(Graph.Edge edge) Invoked after an edge has been removed from this Graph and any GraphListeners have been notified.
protected void	edgeRemoving(Graph.Edge edge) Invoked before an edge has been removed from this Graph and any GraphListeners have been notified.
Collection	edges(org.apache.commons.collections.Predicate edgePredicate) Returns the Graph.Edges from this Graph that satisfy the specified predicate.
boolean	equals(Object object)
Object	getAdjacentNode(Object node, org.apache.commons.collections.Predicate traverserPredicate) Returns a node adjacent to the specified node for which the specified Predicate is satisfied.
Graph.Edge	getEdge(org.apache.commons.collections.Predicate edgePredicate) Returns a Graph.Edge from this Graph that satisfies the specified predicate, or null if no such Graph.Edge exists.
Graph.Edge	getIncidentEdge(Object node, org.apache.commons.collections.Predicate traverserPredicate) Returns a Graph.Edge incident on the specified node for which the specified Predicate is satisfied.
Object	getNode(org.apache.commons.collections.Predicate nodePredicate) Returns a node from this Graph that satisfies the specified predicate, or null if no such node exists.
int	hashCode()
Collection	incidentEdges(Object node, org.apache.commons.collections.Predicate traverserPredicate) Returns the Graph.Edges incident on the specified node for which the specified Predicate is satisfied.
protected void	nodeAdded(Object node) Invoked after a node has been added to this Graph and any GraphListeners have been notified.
protected void	nodeAdding(Object node) Invoked before a node has been added to this Graph and any GraphListeners have been notified.
protected void	nodeRemoved(Object node) Invoked after a node has been removed from this Graph and any GraphListeners have been notified.
protected void	nodeRemoving(Object node) Invoked before a node has been removed from this Graph and any GraphListeners have been notified.
Collection	nodes(org.apache.commons.collections.Predicate nodePredicate) Returns the nodes from this Graph that satisfy the specified predicate.
boolean	removeEdge(Graph.Edge edge) Removes the specified Graph.Edge from this Graph (optional operation).
void	removeGraphListener(GraphListener listener) Removes a previously added GraphListener.
boolean	removeNode(Object node) Removes node from this Graph (optional operation).
String	toString()
Traverser	traverser(Object node, org.apache.commons.collections.Predicate traverserPredicate) Returns a Traverser from node to all adjacent nodes for which the specified filter is satisfied.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

DefaultGraph

public DefaultGraph()

Creates a new DefaultGraph.

DefaultGraph

public DefaultGraph(Graph graph)

Creates a new DefaultGraph which is a copy of the specified Graph.

DefaultGraph

protected DefaultGraph(int nodeSize)

Creates a new DefaultGraph with a capacity for the specified number of nodes (avoiding unnecessary rehashing).

Method Detail

createEdge

protected Graph.Edge createEdge(Object object,
                                Object tail,
                                Object head,
                                boolean isDirected,
                                Object edgeState)

Creates a new Graph.Edge. This method can be overridden by subclasses to provide a different implementation than this one, which produces a DefaultObjectEdge. This method should simply create the requested Graph.Edge, without checking to see whether it already exists. DefaultGraph will not allow two edges which are .equals() in the same adjacency list.

addEdge

protected final Graph.Edge addEdge(Object object,
                                   Object tail,
                                   Object head,
                                   boolean isDirected,
                                   Object edgeState)

Adds a new Graph.Edge with additional information provided by the edgeState argument, which is given to the createEdge() method. This method is intended to be called by subclasses which require more information than just the object, tail, head, and direction to construct the edge. This method cannot be overridden.

Returns the newly created Graph.Edge if this Graph changed as a result of the call. Returns null if this Graph does not allow duplicate edges and already contains the specified edge.

nodeAdding

protected void nodeAdding(Object node)

Invoked before a node has been added to this Graph and any GraphListeners have been notified.

nodeAdded

protected void nodeAdded(Object node)

Invoked after a node has been added to this Graph and any GraphListeners have been notified.

nodeRemoving

protected void nodeRemoving(Object node)

Invoked before a node has been removed from this Graph and any GraphListeners have been notified.

nodeRemoved

protected void nodeRemoved(Object node)

Invoked after a node has been removed from this Graph and any GraphListeners have been notified.

edgeAdding

protected void edgeAdding(Graph.Edge edge)

Invoked before an edge has been added to this Graph and any GraphListeners have been notified.

edgeAdded

protected void edgeAdded(Graph.Edge edge)

Invoked after an edge has been added to this Graph and any GraphListeners have been notified.

edgeRemoving

protected void edgeRemoving(Graph.Edge edge)

Invoked before an edge has been removed from this Graph and any GraphListeners have been notified.

edgeRemoved

protected void edgeRemoved(Graph.Edge edge)

Invoked after an edge has been removed from this Graph and any GraphListeners have been notified.

addNode

public boolean addNode(Object node)

Description copied from interface: Graph

Adds node to this Graph (optional operation). Returns true if this Graph changed as a result of the call. Returns false if this Graph already contains node.

If a Graph refuses to add a particular node for any reason other than that it already contains the node, it must throw an exception (rather than returning false). This preserves the invariant that a Graph always contains the specified node after this call returns. Graph classes should clearly specify in their documentation any other restrictions on what nodes may be added.

Specified by:

addNode in interface Graph

Parameters:

node - the node to be added to this Graph.

Returns:

true if this Graph changed as a result of the call, false if this Graph already contains the specified node.

removeNode

public boolean removeNode(Object node)

Description copied from interface: Graph

Removes node from this Graph (optional operation). This method will also remove all edges incident on node.

Specified by:

removeNode in interface Graph

Parameters:

node - the node to be removed from this Graph.

Returns:

true if this Graph contained node.

containsNode

public boolean containsNode(Object node)

Description copied from interface: Graph

Returns true if this Graph contains the specified node.

Specified by:

containsNode in interface Graph

Parameters:

node - the node whose presence in this Graph is to be tested.

Returns:

true if this Graph contains the specified node.

addEdge

public Graph.Edge addEdge(Object object,
                          Object tail,
                          Object head,
                          boolean isDirected)

Description copied from interface: Graph

Adds the specified edge to the Graph (optional operation). Returns the newly created Graph.Edge if this Graph changed as a result of the call. Returns null if this Graph does not allow duplicate edges and already contains the specified edge.

If a Graph refuses to add a particular edge for any reason other than that it already contains the edge, it must throw an exception (rather than returning null). This preserves the invariant that a Graph always contains the specified edge after this call returns. Graph classes should clearly specify in their documentation any other restrictions on what edges may be added.

Specified by:

addEdge in interface Graph

Parameters:

object - the user-defined object to be contained in the new edge.

tail - the first endpoint of the new edge.

head - the second endpoint of the new edge.

isDirected - whether the new edge is directed.

Returns:

the newly created Graph.Edge if this Graph changed as a result of the call, null if this Graph does not allow duplicate edges and already contains the specified edge.

removeEdge

public boolean removeEdge(Graph.Edge edge)

Description copied from interface: Graph

Removes the specified Graph.Edge from this Graph (optional operation).

Specified by:

removeEdge in interface Graph

Parameters:

edge - the Graph.Edge to be removed from this Graph.

Returns:

true if this Graph contained the specified Graph.Edge.

containsEdge

public boolean containsEdge(Graph.Edge edge)

Description copied from interface: Graph

Returns true if this Graph contains the specified Graph.Edge.

Specified by:

containsEdge in interface Graph

Parameters:

edge - the Graph.Edge whose presence in this Graph is to be tested.

Returns:

true if this Graph contains the specified Graph.Edge.

degree

public int degree(Object node)

Description copied from interface: Graph

Returns the degree of node, defined as the number of edges incident on node, with self-loops counted twice. If this node has more than Integer.MAX_VALUE incident edges, returns Integer.MAX_VALUE.

Specified by:

degree in interface Graph

Parameters:

node - return the degree of this node.

Returns:

the degree of node.

degree

public int degree(Object node,
                  org.apache.commons.collections.Predicate traverserPredicate)

Description copied from interface: Graph

Returns the degree of node for which the specified Predicate is satisfied, defined as the number of edges incident on node that pass the predicate, with self-loops counted only once. The argument to the Predicate.evaluate() method is expected to be an OrderedPair. The first element of the OrderedPair is the specified node, the second is the Graph.Edge. If this node has more than Integer.MAX_VALUE such edges, returns Integer.MAX_VALUE.

Specified by:

degree in interface Graph

Parameters:

node - return the degree of this node for which the specified predicate is satisfied.

traverserPredicate - the predicate which the counted Graph.Edges must satisfy.

Returns:

the degree of node for which the specified predicate is satisfied.

nodes

public Collection nodes(org.apache.commons.collections.Predicate nodePredicate)

Description copied from interface: Graph

Returns the nodes from this Graph that satisfy the specified predicate.

Specified by:

nodes in interface Graph

Parameters:

nodePredicate - the predicate which the returned nodes must satisfy.

Returns:

the nodes from this Graph that satisfy the specified predicate.

edges

public Collection edges(org.apache.commons.collections.Predicate edgePredicate)

Description copied from interface: Graph

Returns the Graph.Edges from this Graph that satisfy the specified predicate.

Specified by:

edges in interface Graph

Parameters:

edgePredicate - the predicate which the returned Graph.Edges must satisfy.

Returns:

the Graph.Edges from this Graph that satisfy the specified predicate.

adjacentNodes

public Collection adjacentNodes(Object node,
                                org.apache.commons.collections.Predicate traverserPredicate)

Description copied from interface: Graph

Returns the nodes adjacent to the specified node for which the specified Predicate is satisfied. The argument to the Predicate.evaluate() method is expected to be an OrderedPair. The first element of the OrderedPair is the specified node, the second is the Graph.Edge. It should be noted that removing a node from the returned Collection merely removes one instance of it being adjacent to the specified node. In other words, a connecting Graph.Edge is removed.

Specified by:

adjacentNodes in interface Graph

Parameters:

node - return the nodes adjacent to this node for which the specified predicate is satisfied.

traverserPredicate - the predicate which the returned nodes and the traversed Graph.Edges must satisfy.

Returns:

the nodes adjacent to the specified node for which the specified predicate is satisfied.

incidentEdges

public Collection incidentEdges(Object node,
                                org.apache.commons.collections.Predicate traverserPredicate)

Description copied from interface: Graph

Returns the Graph.Edges incident on the specified node for which the specified Predicate is satisfied. The argument to the Predicate.evaluate() method is expected to be an OrderedPair. The first element of the OrderedPair is the specified node, the second is the Graph.Edge.

Specified by:

incidentEdges in interface Graph

Parameters:

node - return the Graph.Edges incident on this node for which the specified predicate is satisfied.

traverserPredicate - the predicate which the returned Graph.Edges must satisfy.

Returns:

the Graph.Edges incident on the specified node for which the specified predicate is satisfied.

getNode

public Object getNode(org.apache.commons.collections.Predicate nodePredicate)

Description copied from interface: Graph

Returns a node from this Graph that satisfies the specified predicate, or null if no such node exists.

Specified by:

getNode in interface Graph

Parameters:

nodePredicate - the predicate which the returned node must satisfy.

Returns:

a node from this Graph that satisfies the specified predicate, or null if no such node exists.

getEdge

public Graph.Edge getEdge(org.apache.commons.collections.Predicate edgePredicate)

Description copied from interface: Graph

Returns a Graph.Edge from this Graph that satisfies the specified predicate, or null if no such Graph.Edge exists.

Specified by:

getEdge in interface Graph

Parameters:

edgePredicate - the predicate which the returned Graph.Edge must satisfy.

Returns:

a Graph.Edge from this Graph that satisfies the specified predicate, or null if no such Graph.Edge exists.

getAdjacentNode

public Object getAdjacentNode(Object node,
                              org.apache.commons.collections.Predicate traverserPredicate)

Description copied from interface: Graph

Returns a node adjacent to the specified node for which the specified Predicate is satisfied. The argument to the Predicate.evaluate() method is expected to be an OrderedPair. The first element of the OrderedPair is the specified node, the second is the Graph.Edge.

Specified by:

getAdjacentNode in interface Graph

Parameters:

node - traverse to a node adjacent to this node for which the specified predicate is satisfied.

traverserPredicate - the predicate which the returned node and the traversed Graph.Edge must satisfy.

Returns:

a node adjacent to the specified node for which the specified predicate is satisfied.

getIncidentEdge

public Graph.Edge getIncidentEdge(Object node,
                                  org.apache.commons.collections.Predicate traverserPredicate)

Description copied from interface: Graph

Returns a Graph.Edge incident on the specified node for which the specified Predicate is satisfied. The argument to the Predicate.evaluate() method is expected to be an OrderedPair. The first element of the OrderedPair is the specified node, the second is the Graph.Edge.

Specified by:

getIncidentEdge in interface Graph

Parameters:

node - traverse to a Graph.Edge incident on this node for which the specified predicate is satisfied.

traverserPredicate - the predicate which the returned Graph.Edge must satisfy.

Returns:

a Graph.Edge incident on the specified node for which the specified predicate is satisfied.

traverser

public Traverser traverser(Object node,
                           org.apache.commons.collections.Predicate traverserPredicate)

Returns a Traverser from node to all adjacent nodes for which the specified filter is satisfied.

The returned Traverser is tolerant of changes to the underlying Graph. Note that this does not mean the Traverser is thread-safe. However, if a node or edge is added or removed while the iteration is is progress, the iteration will not throw a ConcurrentModificationException. In fact, its state will reflect the changes. This means that, among other things, you should always call Iterator.hasNext() before Iterator.next() if there is a chance the structure has changed since the last call to hasNext(). The one exception is that if the node upon which the returned Traverser is based is removed, then all operations except hasNext() will throw a ConcurrentModificationException.

Description copied from interface: Graph

Returns a Traverser from node to all adjacent nodes for which the specified Predicate is satisfied. The argument to the Predicate.evaluate() method is expected to be an OrderedPair. The first element of the OrderedPair is the specified node, the second is the Graph.Edge. The nodes returned by Iterator.next() are not necessarily distinct. Self-loops are only traversed once. There are no guarantees concerning the order in which the nodes are returned (unless this Graph is an instance of some class that provides a guarantee).

Specified by:

traverser in interface Graph

Parameters:

node - traverse over all nodes adjacent to this node for which the specified predicate is satisfied.

traverserPredicate - the predicate which the returned nodes and their traversed Graph.Edges must satisfy.

Returns:

a Traverser from node to all adjacent nodes for which the specified predicate is satisfied.

addGraphListener

public void addGraphListener(GraphListener listener)

Description copied from interface: ObservableGraph

Adds the specified GraphListener which will be notified whenever this ObservableGraph's structure changes.

Specified by:

addGraphListener in interface ObservableGraph

removeGraphListener

public void removeGraphListener(GraphListener listener)

Description copied from interface: ObservableGraph

Removes a previously added GraphListener.

Specified by:

removeGraphListener in interface ObservableGraph

equals

public boolean equals(Object object)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object

toString

public String toString()

Overrides:

toString in class Object