Class DepthFirstIterator
- Object
-
- AbstractGraphIterator
-
- SourceGraphIterator
-
- BreadthFirstIterator
-
- DepthFirstIterator
-
- All Implemented Interfaces:
GraphIterator
- Direct Known Subclasses:
DirectedDepthFirstIterator
public class DepthFirstIterator extends BreadthFirstIterator
Iterates over the nodes of a graph in a Depth First Search pattern starting from a specified node. The following illustrates the iteration order.
The iteration operates by maintaning a node queue of active nodes. An active node is a node that will returned at a later stage of the i teration. The node queue for a Depth First iteration is implemented as a Last In First Out queue (a Stack). A node is placed in the the node queue if it has not been visited, and it is adjacent to a a node that has been visited. The node queue intially contains only the source node of the traversal.- Author:
- Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
-
-
Constructor Summary
Constructors Constructor Description DepthFirstIterator()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected Queue<Graphable>
buildQueue(Graph graph)
Builds the node queue for the Iteration.-
Methods inherited from class BreadthFirstIterator
cont, getQueue, init, killBranch, next, setSource
-
Methods inherited from class SourceGraphIterator
getSource
-
Methods inherited from class AbstractGraphIterator
getGraph, getTraversal, getWalker, setTraversal
-
-
-
-
Method Detail
-
buildQueue
protected Queue<Graphable> buildQueue(Graph graph)
Builds the node queue for the Iteration.- Overrides:
buildQueue
in classBreadthFirstIterator
- Parameters:
graph
- The graph of the iteration.- Returns:
- A Last In First Out queue (Stack)
-
-