com.phoenixst.plexus.traversals
Class TopologicalSortTraverser

java.lang.Object
  com.phoenixst.plexus.traversals.TopologicalSortTraverser

All Implemented Interfaces:

Traverser, Iterator

public class TopologicalSortTraverser
extends Object
implements Traverser

A Traverser which returns nodes in a topologically sorted order.

Since:

1.0

Version:

$Revision: 1.6 $

Author:

Ray A. Conner

Constructor Summary

TopologicalSortTraverser(Graph graph, org.apache.commons.collections.Predicate traverserPredicate)
Creates a new TopologicalSortTraverser, where the traverserPredicate specifies adjacent nodes which should be returned before a given node.

TopologicalSortTraverser(Graph graph, org.apache.commons.collections.Transformer traverserFactory)
Creates a new TopologicalSortTraverser, where the traverserFactory returns a Traverser over adjacent nodes which should be returned before the given node.

TopologicalSortTraverser(Iterator nodeIter, org.apache.commons.collections.Transformer traverserFactory)
Creates a new TopologicalSortTraverser, where the traverserFactory returns a Traverser over adjacent nodes which should be returned before the given node.

Method Summary

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()
Object	next()
void	remove()
void	removeEdge() Removes from the underlying Graph the Edge that would be returned by getEdge() (optional operation).

Methods inherited from class java.lang.Object

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

Constructor Detail

TopologicalSortTraverser

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

Creates a new TopologicalSortTraverser, where the traverserPredicate specifies adjacent nodes which should be returned before a given node.

TopologicalSortTraverser

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

Creates a new TopologicalSortTraverser, where the traverserFactory returns a Traverser over adjacent nodes which should be returned before the given node.

TopologicalSortTraverser

public TopologicalSortTraverser(Iterator nodeIter,
                                org.apache.commons.collections.Transformer traverserFactory)

Creates a new TopologicalSortTraverser, where the traverserFactory returns a Traverser over adjacent nodes which should be returned before the given node.

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()

Specified by:

remove in interface Iterator

getEdge

public 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. Note that because the nodes of the underlying Graph are visited in no particular order by the internals of this algorithm, this method may return null even if some other adjacent node succeeds this one.

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()

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