com.phoenixst.plexus.traversals

Class DepthFirstTraverser

public class DepthFirstTraverser extends Object implements PruningTraverser

A depth-first Traverser for a Graph, with no cycle detection. This Traverser hits each node twice (assuming it has not been removed), once on the way down and once on the way back up. The first and last nodes returned are the start node, and no Edge is traversed to reach it. All of the caveats concerning the ordering of the operations hasNext(), next(), and remove() detailed by the Traverser class documentation apply here.

Since: 1.0

Version: $Revision: 1.7 $

Author: Ray A. Conner

Constructor Summary
DepthFirstTraverser(Object startNode, Graph graph, Predicate traverserPredicate)
Creates a new DepthFirstTraverser.
DepthFirstTraverser(Object startNode, OrientedForest forest)
Creates a new DepthFirstTraverser, which depth-first traverses the descendants of the specified startNode.
DepthFirstTraverser(Object startNode, Transformer traverserFactory)
Creates a new DepthFirstTraverser.
DepthFirstTraverser(Object startNode, Graph graph, Transformer traverserFactory)
Creates a new DepthFirstTraverser.
Method Summary
Graph.EdgegetEdge()
booleanhasNext()
booleanisDescending()
Returns true if the last node returned by DepthFirstTraverser is being traversed away from the start node, false if the traversal is on its way back out.
Objectnext()
voidprune()
voidremove()
Removes from the underlying Graph the last node returned by DepthFirstTraverser.
voidremoveEdge()
Removes from the underlying Graph the Edge that would be returned by getEdge().

Constructor Detail

DepthFirstTraverser

public DepthFirstTraverser(Object startNode, Graph graph, Predicate traverserPredicate)
Creates a new DepthFirstTraverser.

DepthFirstTraverser

public DepthFirstTraverser(Object startNode, OrientedForest forest)
Creates a new DepthFirstTraverser, which depth-first traverses the descendants of the specified startNode. The specified startNode cannot be removed by DepthFirstTraverser when using this constructor.

DepthFirstTraverser

public DepthFirstTraverser(Object startNode, Transformer traverserFactory)
Creates a new DepthFirstTraverser. The specified startNode cannot be removed by DepthFirstTraverser when using this constructor.

DepthFirstTraverser

public DepthFirstTraverser(Object startNode, Graph graph, Transformer traverserFactory)
Creates a new DepthFirstTraverser. If the graph argument is null, the specified startNode cannot be removed by DepthFirstTraverser.

Method Detail

getEdge

public Graph.Edge getEdge()

hasNext

public boolean hasNext()

isDescending

public boolean isDescending()
Returns true if the last node returned by DepthFirstTraverser is being traversed away from the start node, false if the traversal is on its way back out.

next

public Object next()

prune

public void prune()

remove

public void remove()
Removes from the underlying Graph the last node returned by DepthFirstTraverser. If this method is called during descent, this will prevent the exploration of those nodes that would have been reached through the removed node (unless they are reachable by another route). This method can be called only once per call to next(). The behavior of this Traverser is unspecified if the underlying graph structure is modified while the traversal is in progress in any way other than by calling this method or DepthFirstTraverser.

Throws: IllegalStateException if next() has not yet been called, or remove() or removeEdge has been called after the last call to next().

removeEdge

public void removeEdge()
Removes from the underlying Graph the Edge that would be returned by getEdge(). If this method is called during descent, this will prevent the exploration of those nodes that would have been reached through the removed Edge (unless they are reachable by another route).

Description copied from interface: Traverser
{@inheritDoc }

See the Plexus project home, hosted by SourceForge.
Copyright B) 1994-2006, by Phoenix Software Technologists, Inc. and others. All Rights Reserved. Use is subject to license terms.