com.phoenixst.plexus
Class AbstractGraph

java.lang.Object
  com.phoenixst.plexus.AbstractGraph

All Implemented Interfaces:

Graph

Direct Known Subclasses:

AbstractIntegerNodeGraph, FileSystemForest, FilteredGraph, Join, Product

public abstract class AbstractGraph
extends Object
implements Graph

This class provides a skeletal implementation of the Graph interface, to minimize the effort required to implement this interface. Any concrete extension of this class must override the following methods to provide a full implemnetation:

• nodes()
• edges()
• traverser( node )

Alternately, an extension may override one or more of the following methods (which normally defer to those listed above) if doing so admits a more efficient solution. In this case, the above methods should probably still be implemented correctly.

• nodes( nodePredicate )
• edges( edgePredicate )
• traverser( node, traverserPredicate )

Any modifiable concrete extensions of this class must also implement:

• addNode( node )
• addEdge( object, tail, head, isDirected )
• Modifying operations of the collection views and traversers

The documentation for each non-abstract method in this class describes its implementation in detail. Each of these methods may be overridden if the graph being implemented admits a more efficient implementation. Note that almost every method implementation here is written in terms of an iterator over the structure of this graph; these methods are all rather inefficient.

The programmer should generally provide a void (no argument) and Graph constructor, as per the recommendation in the Graph interface specification.

Since:

1.0

Version:

$Revision: 1.59 $

Author:

Ray A. Conner

Nested Class Summary

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

Graph.Edge

Constructor Summary

protected

AbstractGraph() Protected constructor, called implicitly by subclasses.

Method Summary

Graph.Edge	addEdge(Object object, Object tail, Object head, boolean isDirected) This implementation throws an UnsupportedOperationException.
boolean	addNode(Object node) This implementation throws an UnsupportedOperationException.
Collection	adjacentNodes(Object node, org.apache.commons.collections.Predicate traverserPredicate) This implementation returns a new AdjacentNodeCollection.
boolean	containsEdge(Graph.Edge edge) This implementation traverses over the edges in this graph incident on the tail of the specified edge, looking for it and returning true if found.
boolean	containsNode(Object node) This implementation iterates over the nodes in this graph looking for the specified element.
int	degree(Object node) This implementation counts the number of elements accessed by this graph's traverser( node, null ) method, counting self-loops twice.
int	degree(Object node, org.apache.commons.collections.Predicate traverserPredicate) This implementation counts the number of elements accessed by this graph's traverser( node, traverserPredicate ) method, without counting self-loops twice.
protected abstract Collection	edges() Returns a Collection view of all the Graph.Edges in this Graph.
Collection	edges(org.apache.commons.collections.Predicate edgePredicate) This implementation delegates to edges(), except for when the specified edgePredicate is either FalsePredicate.INSTANCE or an instance of EqualPredicate.
Object	getAdjacentNode(Object node, org.apache.commons.collections.Predicate traverserPredicate) This implementation returns the other endpoint of the Edge returned by getIncidentEdge(Object,Predicate) if present, otherwise it returns null.
Graph.Edge	getEdge(org.apache.commons.collections.Predicate edgePredicate) This implementation returns the first Edge accessed by edges(Predicate) if present, otherwise it returns null.
Graph.Edge	getIncidentEdge(Object node, org.apache.commons.collections.Predicate traverserPredicate) This implementation returns the first Edge accessed by incidentEdges(Object,Predicate) if present, otherwise it returns null.
Object	getNode(org.apache.commons.collections.Predicate nodePredicate) This implementation returns the first node accessed by nodes(Predicate) if present, otherwise it returns null.
Collection	incidentEdges(Object node, org.apache.commons.collections.Predicate traverserPredicate) This implementation returns a new IncidentEdgeCollection.
protected abstract Collection	nodes() Returns a Collection view of all the nodes in this Graph.
Collection	nodes(org.apache.commons.collections.Predicate nodePredicate) This implementation delegates to nodes(), except for when the specified nodePredicate is either FalsePredicate.INSTANCE or an instance of EqualPredicate.
boolean	removeEdge(Graph.Edge edge) This implementation traverses over the edges in this graph incident on the tail of the specified edge.
boolean	removeNode(Object node) This implementation iterates over the nodes in this graph looking for the specified element.
protected abstract Traverser	traverser(Object node) Returns an unfiltered Traverser over those Graph.Edges incident to the specified node.
Traverser	traverser(Object node, org.apache.commons.collections.Predicate traverserPredicate) This implementation delegates to traverser( node ), except for when the specified traverserPredicate is either FalsePredicate.INSTANCE or an instance of EqualsTraverserPredicate.

Methods inherited from class java.lang.Object

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

Constructor Detail

AbstractGraph

protected AbstractGraph()

Protected constructor, called implicitly by subclasses.

Method Detail

nodes

protected abstract Collection nodes()

Returns a Collection view of all the nodes in this Graph. This method is only called by nodes( Predicate ).

edges

protected abstract Collection edges()

Returns a Collection view of all the Graph.Edges in this Graph. This method is only called by edges( Predicate ).

traverser

protected abstract Traverser traverser(Object node)

Returns an unfiltered Traverser over those Graph.Edges incident to the specified node. This method is only called by traverser( node, Predicate ).

addNode

public boolean addNode(Object node)

This implementation throws an UnsupportedOperationException.

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)

This implementation iterates over the nodes in this graph looking for the specified element. If it finds the element, it removes the element using using the Iterator.remove() operation.

Note that this implementation will throw an UnsupportedOperationException if the iterator returned by this graph's nodes( null ).iterator() method does not implement the remove method and this graph contains the specified 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)

This implementation iterates over the nodes in this graph looking for the specified element.

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)

This implementation throws an UnsupportedOperationException.

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)

This implementation traverses over the edges in this graph incident on the tail of the specified edge. If it finds the element, it removes the element using using the Iterator.remove() operation.

Note that this implementation will throw an UnsupportedOperationException if the traverser returned by this graph's traverser( node, predicate ) method does not implement the removeEdge method and this graph contains the specified edge.

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)

This implementation traverses over the edges in this graph incident on the tail of the specified edge, looking for it and returning true if found.

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)

This implementation counts the number of elements accessed by this graph's traverser( node, null ) method, counting self-loops twice.

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)

This implementation counts the number of elements accessed by this graph's traverser( node, traverserPredicate ) method, without counting self-loops twice.

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)

This implementation delegates to nodes(), except for when the specified nodePredicate is either FalsePredicate.INSTANCE or an instance of EqualPredicate. These two cases are optimized.

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)

This implementation delegates to edges(), except for when the specified edgePredicate is either FalsePredicate.INSTANCE or an instance of EqualPredicate. These two cases are optimized.

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)

This implementation returns a new AdjacentNodeCollection.

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)

This implementation returns a new IncidentEdgeCollection.

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)

This implementation returns the first node accessed by nodes(Predicate) if present, otherwise it returns null.

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)

This implementation returns the first Edge accessed by edges(Predicate) if present, otherwise it returns null.

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)

This implementation returns the other endpoint of the Edge returned by getIncidentEdge(Object,Predicate) if present, otherwise it returns null.

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)

This implementation returns the first Edge accessed by incidentEdges(Object,Predicate) if present, otherwise it returns null.

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)

This implementation delegates to traverser( node ), except for when the specified traverserPredicate is either FalsePredicate.INSTANCE or an instance of EqualsTraverserPredicate. These two cases are optimized.

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.