com.phoenixst.plexus

Class AbstractGraph

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:

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.

Any modifiable concrete extensions of this class must also implement:

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

Constructor Summary
protected AbstractGraph()
Protected constructor, called implicitly by subclasses.
Method Summary
Graph.EdgeaddEdge(Object object, Object tail, Object head, boolean isDirected)
This implementation throws an UnsupportedOperationException.
booleanaddNode(Object node)
This implementation throws an UnsupportedOperationException.
CollectionadjacentNodes(Object node, Predicate traverserPredicate)
This implementation returns a new AdjacentNodeCollection.
booleancontainsEdge(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.
booleancontainsNode(Object node)
This implementation iterates over the nodes in this graph looking for the specified element.
intdegree(Object node)
This implementation counts the number of elements accessed by this graph's traverser( node, null ) method, counting self-loops twice.
intdegree(Object node, 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 Collectionedges()
Returns a Collection view of all the Graph.Edges in this Graph.
Collectionedges(Predicate edgePredicate)
This implementation delegates to edges(), except for when the specified edgePredicate is either INSTANCE or an instance of EqualPredicate.
ObjectgetAdjacentNode(Object node, Predicate traverserPredicate)
This implementation returns the other endpoint of the Edge returned by getIncidentEdge if present, otherwise it returns null.
Graph.EdgegetEdge(Predicate edgePredicate)
This implementation returns the first Edge accessed by edges if present, otherwise it returns null.
Graph.EdgegetIncidentEdge(Object node, Predicate traverserPredicate)
This implementation returns the first Edge accessed by incidentEdges if present, otherwise it returns null.
ObjectgetNode(Predicate nodePredicate)
This implementation returns the first node accessed by nodes if present, otherwise it returns null.
CollectionincidentEdges(Object node, Predicate traverserPredicate)
This implementation returns a new IncidentEdgeCollection.
protected abstract Collectionnodes()
Returns a Collection view of all the nodes in this Graph.
Collectionnodes(Predicate nodePredicate)
This implementation delegates to nodes(), except for when the specified nodePredicate is either INSTANCE or an instance of EqualPredicate.
booleanremoveEdge(Graph.Edge edge)
This implementation traverses over the edges in this graph incident on the tail of the specified edge.
booleanremoveNode(Object node)
This implementation iterates over the nodes in this graph looking for the specified element.
protected abstract Traversertraverser(Object node)
Returns an unfiltered Traverser over those Graph.Edges incident to the specified node.
Traversertraverser(Object node, Predicate traverserPredicate)
This implementation delegates to traverser( node ), except for when the specified traverserPredicate is either INSTANCE or an instance of EqualsTraverserPredicate.

Constructor Detail

AbstractGraph

protected AbstractGraph()
Protected constructor, called implicitly by subclasses.

Method Detail

addEdge

public Graph.Edge addEdge(Object object, Object tail, Object head, boolean isDirected)
This implementation throws an UnsupportedOperationException.

addNode

public boolean addNode(Object node)
This implementation throws an UnsupportedOperationException.

adjacentNodes

public Collection adjacentNodes(Object node, Predicate traverserPredicate)
This implementation returns a new AdjacentNodeCollection.

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.

containsNode

public boolean containsNode(Object node)
This implementation iterates over the nodes in this graph looking for the specified element.

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.

degree

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

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

edges

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

getAdjacentNode

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

getEdge

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

getIncidentEdge

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

getNode

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

incidentEdges

public Collection incidentEdges(Object node, Predicate traverserPredicate)
This implementation returns a new IncidentEdgeCollection.

nodes

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

nodes

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

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

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.

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

traverser

public Traverser traverser(Object node, Predicate traverserPredicate)
This implementation delegates to traverser( node ), except for when the specified traverserPredicate is either INSTANCE or an instance of EqualsTraverserPredicate. These two cases are optimized.
See the Plexus project home, hosted by SourceForge.
Copyright B) 1994-2006, by Phoenix Software Technologists, Inc. and others. All Rights Reserved. Use is subject to license terms.