com.phoenixst.plexus.algorithms
Class DepthFirstTreeView

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

All Implemented Interfaces:

GraphView, OrientedForest, Rooted, RootedTree

public class DepthFirstTreeView
extends AbstractOrientedForest
implements RootedTree

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

Since:

1.0

Version:

$Revision: 1.21 $

Author:

Ray A. Conner

Constructor Summary

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.

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

Methods inherited from class com.phoenixst.plexus.AbstractOrientedForest

getDepth, getHeight, getParent, getParentEndpoint, isForestEdge

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.phoenixst.plexus.OrientedForest

childTraverser, getDepth, getHeight, getLeastCommonAncestor, getParent, getParentEdge, getParentEndpoint, isAncestor, isForestEdge, isLeaf

Constructor Detail

DepthFirstTreeView

public DepthFirstTreeView(Object startNode,
                          Graph graph,
                          org.apache.commons.collections.Predicate traverserPredicate)

Creates a new DepthFirstTreeView starting at the specified node.

DepthFirstTreeView

public DepthFirstTreeView(Object startNode,
                          Graph graph,
                          org.apache.commons.collections.Transformer traverserFactory)

Creates a new DepthFirstTreeView starting at the specified node.

Method Detail

getRoot

public Object getRoot()

Description copied from interface: Rooted

Gets the root node.

Specified by:

getRoot in interface Rooted

setRoot

public void setRoot(Object root)

Throws an UnsupportedOperationException.

Specified by:

setRoot in interface Rooted

rootNodes

public Collection rootNodes()

Description copied from interface: OrientedForest

Returns the root nodes of this forest.

Specified by:

rootNodes in interface OrientedForest

getRoot

public Object getRoot(Object node)

Description copied from class: AbstractOrientedForest

Gets the root of the subgraph containing the specified node.

Specified by:

getRoot in interface OrientedForest

Overrides:

getRoot in class AbstractOrientedForest

isTreeNode

public boolean isTreeNode(Object node)

Description copied from interface: RootedTree

Returns true if the specified node is a descendant of the root node.

Specified by:

isTreeNode in interface RootedTree

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.