public class DepthFirstTreeView extends AbstractOrientedForest implements RootedTree
Graph
. As described in the RootedTree
class docs, all methods in this view which take a
node argument will throw a NoSuchNodeException
if
given a node which is not a descendant of the root node.
This implementation tracks discovery time and finishing time,
and can possibly answer a few structural questions about the
portion of the underlying Graph
reachable from the
specified start node. Whether or not these questions can be
answered depends upon whether the supplied Traverser
predicate or factory is direction agnostic. If at least
one encountered edge can be traversed in only one direction, then
many structural queries cannot be answered by this class, and will
throw exceptions. The only exception is in the case of
self-loops; these may only be traversed in one direction with no
ill effect. These cases are documented in the appropriate
methods.
If the underlying Graph
changes, this view may
become invalid, but perhaps not detectably so.
Constructor and Description |
---|
DepthFirstTreeView(Object startNode,
Graph graph,
org.apache.commons.collections.Predicate traverserPredicate)
Creates a new
DepthFirstTreeView starting at
the specified node. |
DepthFirstTreeView(Object startNode,
Graph graph,
org.apache.commons.collections.Transformer traverserFactory)
Creates a new
DepthFirstTreeView starting at
the specified node. |
Modifier and Type | Method and Description |
---|---|
Traverser |
childTraverser(Object node)
Traverses over the children of the specified node.
|
int |
getDiscoveryTime(Object node)
Returns the "time" that the specified node was first
discovered during the depth-first traversal.
|
int |
getFinishingTime(Object node)
Returns the "time" that the specified node was
finished during the depth-first traversal.
|
Graph |
getGraph()
Returns the
Graph of which this is a view. |
Object |
getLeastCommonAncestor(Object aNode,
Object bNode)
Returns the least common ancestor of the specified nodes, or
null if none exists. |
Graph.Edge |
getParentEdge(Object node)
Gets the parent
Edge of the specified node, or
null if it doesn't have one. |
Object |
getRoot()
Gets the root node.
|
Object |
getRoot(Object node)
Gets the root of the subgraph containing the specified node.
|
protected boolean |
hasProcessedNode(Object node) |
boolean |
isAncestor(Object ancestor,
Object descendant)
Returns
true if ancestor is actually
an ancestor of descendant . |
boolean |
isArticulationPoint(Object node)
Returns whether or not the specified node is an articulation
point of this view.
|
boolean |
isBridge(Graph.Edge edge)
Returns whether or not the specified
Edge is a
bridge of this view. |
boolean |
isCyclic()
Returns whether or not this traversal was cyclic.
|
boolean |
isDirectionAgnostic()
Returns whether or not this traversal was direction agnostic,
as defined in the class docs.
|
boolean |
isLeaf(Object node)
Returns
true if the specified node has no
children. |
boolean |
isTreeNode(Object node)
Returns
true if the specified node is a
descendant of the root node. |
Collection |
rootNodes()
Returns the root nodes of this forest.
|
void |
setRoot(Object root)
Throws an
UnsupportedOperationException . |
getDepth, getHeight, getParent, getParentEndpoint, isForestEdge
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
childTraverser, getDepth, getHeight, getLeastCommonAncestor, getParent, getParentEdge, getParentEndpoint, isAncestor, isForestEdge, isLeaf
public DepthFirstTreeView(Object startNode, Graph graph, org.apache.commons.collections.Predicate traverserPredicate)
DepthFirstTreeView
starting at
the specified node.public void setRoot(Object root)
UnsupportedOperationException
.public Collection rootNodes()
OrientedForest
rootNodes
in interface OrientedForest
public Object getRoot(Object node)
AbstractOrientedForest
getRoot
in interface OrientedForest
getRoot
in class AbstractOrientedForest
public boolean isTreeNode(Object node)
RootedTree
true
if the specified node is a
descendant of the root node.isTreeNode
in interface RootedTree
protected boolean hasProcessedNode(Object node)
public Graph getGraph()
GraphView
Graph
of which this is a view.public Graph.Edge getParentEdge(Object node)
OrientedForest
Edge
of the specified node, or
null
if it doesn't have one.getParentEdge
in interface OrientedForest
public Traverser childTraverser(Object node)
OrientedForest
childTraverser
in interface OrientedForest
public boolean isLeaf(Object node)
AbstractOrientedForest
true
if the specified node has no
children.isLeaf
in interface OrientedForest
isLeaf
in class AbstractOrientedForest
public boolean isAncestor(Object ancestor, Object descendant)
AbstractOrientedForest
true
if ancestor
is actually
an ancestor of descendant
.isAncestor
in interface OrientedForest
isAncestor
in class AbstractOrientedForest
public Object getLeastCommonAncestor(Object aNode, Object bNode)
AbstractOrientedForest
null
if none exists. If the graph may contain a
null
node, then some other method must be used to
distinguish the two cases.getLeastCommonAncestor
in interface OrientedForest
getLeastCommonAncestor
in class AbstractOrientedForest
public int getDiscoveryTime(Object node)
public int getFinishingTime(Object node)
public boolean isCyclic()
true
if and only if a
self-loop or back edge was encountered during the traversal.public boolean isDirectionAgnostic()
public boolean isArticulationPoint(Object node)
If this view is not direction agnostic, throws an
IllegalStateException
. If the specified node was
not reached during traversal, throws a
NoSuchNodeException
.
node
- the node to test for being an articulation point.IllegalStateException
- if this view is not direction
agnostic.NoSuchNodeException
- if the specified node was not
reached during traversal.public boolean isBridge(Graph.Edge edge)
Edge
is a
bridge of this view. A bridge is an Edge
whose
removal would increase the number of components in the graph.
For this view, the question is restricted to whether removing
the Edge
would increase the number of components
in the graph covered by the traversal.
If this view is not direction agnostic, throws an
IllegalStateException
. If the specified
Edge
is not in the Graph
, throws an
IllegalArgumentException
.
edge
- the Edge
to test for being a bridge.Edge
is a
bridge of this view.IllegalStateException
- if this view is not direction
agnostic.IllegalArgumentException
- if the specified
Edge
is not in the Graph
.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.