javaslam.tjt.graph
Class Traversal

java.lang.Object
  |
  +--javaslam.tjt.graph.Traversal
Direct Known Subclasses:
BreadthFirstTraversal, DepthFirstTraversal

public abstract class Traversal
extends Object

An iterator that traverses the nodes of a graph.


Field Summary
protected  Node current
          The most recently returned node, or null if next() has not yet been called.
protected  boolean cycle
          If true, then this iterator has traversed a node more than once.
protected  HashMap edges
          A mapping from each node to the Edge used to arrive at that node (most recently).
 
Constructor Summary
Traversal(Node n)
          Constructor.
 
Method Summary
 Node current()
          Returns the current node without advancing the iterator.
protected abstract  Node dequeue()
          Dequeues a node to visit.
 Edge edge()
          Returns the edge traversed to arrive at the current node.
protected abstract  void enqueue(Node n)
          Enqueues a node for later visit.
abstract  boolean hasNext()
          Returns true if the iteration has more elements.
 boolean isCyclic()
          Returns true if the traversal has visited a node more than once, implying the existence of a cycle if the graph is undirected.
 Node next()
          Returns the next Node in the iteration.
 List path()
          Returns a list of Edges that were traversed in order to reach the Node most recently returned by next().
 int size()
          Returns the number of nodes traversed thus far.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

cycle

protected boolean cycle
If true, then this iterator has traversed a node more than once.


edges

protected HashMap edges
A mapping from each node to the Edge used to arrive at that node (most recently).


current

protected Node current
The most recently returned node, or null if next() has not yet been called.

Constructor Detail

Traversal

public Traversal(Node n)
Constructor. Implementations of this class should invoke this constructor, and then enqueue the Node parameter.

Parameters:
n - the node from which to start the traversal; this will be the first node returned by the iterator
Method Detail

hasNext

public abstract boolean hasNext()
Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing an exception.)


isCyclic

public boolean isCyclic()
Returns true if the traversal has visited a node more than once, implying the existence of a cycle if the graph is undirected.


size

public int size()
Returns the number of nodes traversed thus far.


enqueue

protected abstract void enqueue(Node n)
Enqueues a node for later visit.


dequeue

protected abstract Node dequeue()
Dequeues a node to visit.


next

public Node next()
Returns the next Node in the iteration.


current

public Node current()
Returns the current node without advancing the iterator. This method will return null if next() has not yet been called.


edge

public Edge edge()
Returns the edge traversed to arrive at the current node. This method will return null if next() has not yet been called more than once.


path

public List path()
          throws IllegalStateException
Returns a list of Edges that were traversed in order to reach the Node most recently returned by next().

Returns:
a list of the Edge objects that were traversed in order to reach the Node most recently returned by next().
Throws:
IllegalStateException - if next() has not yet been called.