public class DepthFirstForestView extends AbstractOrientedForest
Graph
.
This implementation tracks discovery time and finishing time,
and can possibly answer a few structural questions about the
underlying Graph
. 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 |
---|
DepthFirstForestView(Graph graph,
org.apache.commons.collections.Predicate traverserPredicate)
Creates a new
DepthFirstForestView . |
DepthFirstForestView(Graph graph,
org.apache.commons.collections.Transformer traverserFactory)
Creates a new
DepthFirstForestView . |
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. |
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. |
Collection |
rootNodes()
Returns a list of the root nodes for this depth-first
traversal in the order encountered.
|
getDepth, getHeight, getParent, getParentEndpoint, getRoot, isForestEdge
public DepthFirstForestView(Graph graph, org.apache.commons.collections.Predicate traverserPredicate)
DepthFirstForestView
.public DepthFirstForestView(Graph graph, org.apache.commons.collections.Transformer traverserFactory)
DepthFirstForestView
.public Collection rootNodes()
Description copied from interface: OrientedForest
Returns the root nodes of this forest.
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.