com.phoenixst.plexus.traversals

Class DepthFirstTraverser

java.lang.Object

com.phoenixst.plexus.traversals.DepthFirstTraverser

All Implemented Interfaces:

PruningTraverser, Traverser, Iterator

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

Constructors

Constructor and Description
DepthFirstTraverser(Object startNode, Graph graph, org.apache.commons.collections.Predicate traverserPredicate) Creates a new DepthFirstTraverser.
DepthFirstTraverser(Object startNode, Graph graph, org.apache.commons.collections.Transformer traverserFactory) 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, org.apache.commons.collections.Transformer traverserFactory) Creates a new DepthFirstTraverser.

Method Summary

Methods

Modifier and Type	Method and Description
Graph.Edge	getEdge() Returns the Edge which was traversed to get to the last node returned by next(), or null if no Edge was traversed.
boolean	hasNext()
boolean	isDescending() Returns true if the last node returned by next() is being traversed away from the start node, false if the traversal is on its way back out.
Object	next()
void	prune() Signals this Traverser to not explore beyond the last node returned by next().
void	remove() Removes from the underlying Graph the last node returned by next().
void	removeEdge() Removes from the underlying Graph the Edge that would be returned by getEdge().

Methods inherited from class java.lang.Object

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

Constructor Detail

DepthFirstTraverser

public DepthFirstTraverser(Object startNode,
                   Graph graph,
                   org.apache.commons.collections.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 remove() when using this constructor.

DepthFirstTraverser

public DepthFirstTraverser(Object startNode,
                   org.apache.commons.collections.Transformer traverserFactory)

Creates a new DepthFirstTraverser. The specified startNode cannot be removed by remove() when using this constructor.

DepthFirstTraverser

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

Creates a new DepthFirstTraverser. If the graph argument is null, the specified startNode cannot be removed by remove().

Method Detail

hasNext

public boolean hasNext()

Specified by:

hasNext in interface Iterator

next

public Object next()

Specified by:

next in interface Iterator

remove

public void remove()

Removes from the underlying Graph the last node returned by next(). 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 removeEdge().

Specified by:

remove in interface Iterator

Throws:

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

getEdge

public Graph.Edge getEdge()

Description copied from interface: Traverser

Returns the Edge which was traversed to get to the last node returned by next(), or null if no Edge was traversed. This call can be made only if remove() or removeEdge() has not been called after the last call to next().

Specified by:

getEdge in interface Traverser

Returns:

The Edge which was traversed to get to the last node returned by next(), or null if no Edge was traversed.

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
Removes from the underlying Graph the Edge that would be returned by getEdge() (optional operation). If no Edge was traversed (as in the root of a breadth-first search), this method throws a IllegalStateException. This method can be called only once per call to next(). The behavior of a 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 remove().

Specified by:

removeEdge in interface Traverser

prune

public void prune()

Description copied from interface: PruningTraverser

Signals this Traverser to not explore beyond the last node returned by next(). This method can be called only once per call to next(). After calling this method (and before calling next() again), remove(), getEdge(), and removeEdge() will all throw IllegalStateExceptions.

Specified by:

prune in interface PruningTraverser

isDescending

public boolean isDescending()

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