com.phoenixst.plexus.algorithms
Class DepthFirstForestView

java.lang.Object
  com.phoenixst.plexus.AbstractOrientedForest
      com.phoenixst.plexus.algorithms.DepthFirstForestView

All Implemented Interfaces:

GraphView, OrientedForest

public class DepthFirstForestView
extends AbstractOrientedForest

A constructive (not lazy) depth-first tree for a portion of a 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.

Since:

1.0

Version:

$Revision: 1.15 $

Author:

Ray A. Conner

Constructor Summary

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.

Method Summary

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.

Methods inherited from class com.phoenixst.plexus.AbstractOrientedForest

getDepth, getHeight, getParent, getParentEndpoint, getRoot, isForestEdge

Methods inherited from class java.lang.Object

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

Constructor Detail

DepthFirstForestView

public DepthFirstForestView(Graph graph,
                            org.apache.commons.collections.Predicate traverserPredicate)

Creates a new DepthFirstForestView.

DepthFirstForestView

public DepthFirstForestView(Graph graph,
                            org.apache.commons.collections.Transformer traverserFactory)

Creates a new DepthFirstForestView.

Method Detail

rootNodes

public Collection rootNodes()

Returns a list of the root nodes for this depth-first traversal in the order encountered.

Description copied from interface: OrientedForest
Returns the root nodes of this forest.

hasProcessedNode

protected boolean hasProcessedNode(Object node)

getGraph

public Graph getGraph()

Description copied from interface: GraphView

Returns the Graph of which this is a view.

Specified by:

getGraph in interface GraphView

getParentEdge

public Graph.Edge getParentEdge(Object node)

Description copied from interface: OrientedForest

Gets the parent Edge of the specified node, or null if it doesn't have one.

Specified by:

getParentEdge in interface OrientedForest

childTraverser

public Traverser childTraverser(Object node)

Description copied from interface: OrientedForest

Traverses over the children of the specified node.

Specified by:

childTraverser in interface OrientedForest

isLeaf

public boolean isLeaf(Object node)

Description copied from class: AbstractOrientedForest

Returns true if the specified node has no children.

Specified by:

isLeaf in interface OrientedForest

Overrides:

isLeaf in class AbstractOrientedForest

isAncestor

public boolean isAncestor(Object ancestor,
                          Object descendant)

Description copied from class: AbstractOrientedForest

Returns true if ancestor is actually an ancestor of descendant.

Specified by:

isAncestor in interface OrientedForest

Overrides:

isAncestor in class AbstractOrientedForest

getLeastCommonAncestor

public Object getLeastCommonAncestor(Object aNode,
                                     Object bNode)

Description copied from class: AbstractOrientedForest

Returns the least common ancestor of the specified nodes, or null if none exists. If the graph may contain a null node, then some other method must be used to distinguish the two cases.

Specified by:

getLeastCommonAncestor in interface OrientedForest

Overrides:

getLeastCommonAncestor in class AbstractOrientedForest

getDiscoveryTime

public int getDiscoveryTime(Object node)

Returns the "time" that the specified node was first discovered during the depth-first traversal. The discovery time of the first node encountered starts at one and increments by one for each traversal step taken after that.

getFinishingTime

public int getFinishingTime(Object node)

Returns the "time" that the specified node was finished during the depth-first traversal. The discovery time time of the first node encountered starts at one and increments by one for each traversal step taken after that.

isCyclic

public boolean isCyclic()

Returns whether or not this traversal was cyclic. Specifically, returns true if and only if a self-loop or back edge was encountered during the traversal.

isDirectionAgnostic

public boolean isDirectionAgnostic()

Returns whether or not this traversal was direction agnostic, as defined in the class docs.

isArticulationPoint

public boolean isArticulationPoint(Object node)

Returns whether or not the specified node is an articulation point of this view. An articulation point (also called a cut vertex) is a node whose removal would increase the number of components in the graph. For this view, the question is restricted to whether removing the node 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 node was not reached during traversal, throws a NoSuchNodeException.

Parameters:

node - the node to test for being an articulation point.

Returns:

whether or not the specified node is an articulation point of this view.

Throws:

IllegalStateException - if this view is not direction agnostic.

NoSuchNodeException - if the specified node was not reached during traversal.

isBridge

public boolean isBridge(Graph.Edge edge)

Returns whether or not the specified 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.

Parameters:

edge - the Edge to test for being a bridge.

Returns:

whether or not the specified Edge is a bridge of this view.

Throws:

IllegalStateException - if this view is not direction agnostic.

IllegalArgumentException - if the specified Edge is not in the Graph.