public abstract class AbstractGraph extends Object implements Graph
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:
addNode( node )
addEdge( object, tail, head, isDirected )
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.
Graph.Edge
Modifier | Constructor and Description |
---|---|
protected |
AbstractGraph()
Protected constructor, called implicitly by subclasses.
|
Modifier and Type | Method and Description |
---|---|
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 . |
protected AbstractGraph()
protected abstract Collection nodes()
Collection
view of all the nodes
in this Graph
. This method is only called
by nodes( Predicate )
.protected abstract Collection edges()
Collection
view of all the
Graph.Edges
in this Graph
.
This method is only called by edges( Predicate )
.protected abstract Traverser traverser(Object node)
Traverser
over those
Graph.Edges
incident to the specified node.
This method is only called by traverser( node, Predicate )
.public boolean addNode(Object node)
UnsupportedOperationException
.public boolean removeNode(Object node)
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.
removeNode
in interface Graph
node
- the node to be removed from this
Graph
.true
if this Graph
contained
node
.public boolean containsNode(Object node)
containsNode
in interface Graph
node
- the node whose presence in this Graph
is to be tested.true
if this Graph
contains
the specified node.public Graph.Edge addEdge(Object object, Object tail, Object head, boolean isDirected)
UnsupportedOperationException
.addEdge
in interface Graph
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.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.public boolean removeEdge(Graph.Edge edge)
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.
removeEdge
in interface Graph
edge
- the Graph.Edge
to be removed from
this Graph
.true
if this Graph
contained
the specified Graph.Edge
.public boolean containsEdge(Graph.Edge edge)
edge
,
looking for it and returning true
if found.containsEdge
in interface Graph
edge
- the Graph.Edge
whose presence in this
Graph
is to be tested.true
if this Graph
contains
the specified Graph.Edge
.public int degree(Object node)
traverser(
node, null )
method, counting self-loops twice.public int degree(Object node, org.apache.commons.collections.Predicate traverserPredicate)
traverser(
node, traverserPredicate )
method, without counting
self-loops twice.public Collection nodes(org.apache.commons.collections.Predicate nodePredicate)
nodes()
,
except for when the specified nodePredicate
is
either FalsePredicate.INSTANCE
or an instance of
EqualPredicate
. These two cases are optimized.public Collection edges(org.apache.commons.collections.Predicate edgePredicate)
edges()
,
except for when the specified edgePredicate
is
either FalsePredicate.INSTANCE
or an instance of
EqualPredicate
. These two cases are optimized.public Collection adjacentNodes(Object node, org.apache.commons.collections.Predicate traverserPredicate)
AdjacentNodeCollection
.adjacentNodes
in interface Graph
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.node
for which the specified predicate is satisfied.public Collection incidentEdges(Object node, org.apache.commons.collections.Predicate traverserPredicate)
IncidentEdgeCollection
.incidentEdges
in interface Graph
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.Graph.Edges
incident on the specified
node
for which the specified predicate is
satisfied.public Object getNode(org.apache.commons.collections.Predicate nodePredicate)
nodes(Predicate)
if present, otherwise it returns
null
.public Graph.Edge getEdge(org.apache.commons.collections.Predicate edgePredicate)
Edge
accessed by edges(Predicate)
if present, otherwise it
returns null
.public Object getAdjacentNode(Object node, org.apache.commons.collections.Predicate traverserPredicate)
Edge
returned by getIncidentEdge(Object,Predicate)
if present, otherwise it
returns null
.getAdjacentNode
in interface Graph
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.node
for
which the specified predicate is satisfied.public Graph.Edge getIncidentEdge(Object node, org.apache.commons.collections.Predicate traverserPredicate)
Edge
accessed by incidentEdges(Object,Predicate)
if
present, otherwise it returns null
.getIncidentEdge
in interface Graph
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.Graph.Edge
incident on the specified
node
for which the specified predicate is
satisfied.public Traverser traverser(Object node, org.apache.commons.collections.Predicate traverserPredicate)
traverser( node )
, except for when the specified
traverserPredicate
is either FalsePredicate.INSTANCE
or an instance of EqualsTraverserPredicate
. These two cases are optimized.traverser
in interface Graph
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.Traverser
from node
to all
adjacent nodes for which the specified predicate is satisfied.See the Plexus project home, hosted by SourceForge.
Copyright ? 1994-2006, by Phoenix Software Technologists, Inc. and others. All Rights Reserved. Use is subject to license terms.