Package org.geotools.graph.traverse
Interface GraphIterator
- All Known Implementing Classes:
AbstractGraphIterator
,AStarIterator
,BreadthFirstIterator
,BreadthFirstTopologicalIterator
,DepthFirstIterator
,DepthFirstTopologicalIterator
,DijkstraIterator
,DirectedBreadthFirstIterator
,DirectedBreadthFirstTopologicalIterator
,DirectedDepthFirstIterator
,DirectedDepthFirstTopologicalIterator
,DirectedDijkstraIterator
,NoBifurcationIterator
,SourceGraphIterator
public interface GraphIterator
Defines an algorithm in which to traverse the components of a graph. A graph iterator operates by repeatedly returing
graph components to the caller. The order in which to return the components is specific to the iterator. However,
most iterators follow the following conventions:
* indicates source of traversal
In order to analyze the traversal, the following terms are defined:
The Next Set of a traversal is the set of components that will be visited in a later stage of the traversal.
The Branch Set of an component e is defined as the set of components that can be visited in a later stage of the traversal as a direct result of visiting e.
In most traversals, the two sets are related. The Next Set is built by analyzing the Branch Set of the component being visited in the current stage of the traversal. Revisiting the above example, a Depth First Search Traversal operates as follows:
The following table summarizes the stages of the traversal:
At any stage of a travesal a branch may be killed.When a branch is killed at a stage of an iteration, no elements in the current Branch Set are added to the Next Set. This is illustrated by revisiting the Depth First Search Iteration, but this time killing the branch at node B. The following table summarizes the stages of the traversal:
In this example, killing the branch at node B results in nodes C, D, and E never being visited.
- Components are visited only once
- The next component to be returned is determined by the components that have been previously visited

In order to analyze the traversal, the following terms are defined:
The Next Set of a traversal is the set of components that will be visited in a later stage of the traversal.
The Branch Set of an component e is defined as the set of components that can be visited in a later stage of the traversal as a direct result of visiting e.
In most traversals, the two sets are related. The Next Set is built by analyzing the Branch Set of the component being visited in the current stage of the traversal. Revisiting the above example, a Depth First Search Traversal operates as follows:
- Each node is visited only once.
- The Next Set is organized as a Last In First Out Queue (Stack).
- At each stage, every node in the Branch Set that has not yet been visited is added to the Next Set.
The following table summarizes the stages of the traversal:
Stage | Visited Node | Branch Set | Next Set | Comment |
---|---|---|---|---|
0 | {A} | Initial stage, iteration starts explicitly from A | ||
1 | A | {B,F} | {F,B} | Related nodes added to Next Set in LIFO order. |
2 | F | {A,B} | {B,B} | A already visited so not added to Next Set B not yet visited so added to queue. |
3 | B | {A,C,D,E,F} | {B,E,D,C} | A,F already visited so not added to Next Set |
4 | B | {E,D,C} | B already visited so ignore and move to next stage | |
5 | E | {B} | {D,C} | |
6 | D | {B,C} | {C,C} | |
7 | C | {B,D} | {C} | |
8 | C | { } | C already visited so ignore and move to next stage | |
9 | { } | Next set empty, iteration complete. |
At any stage of a travesal a branch may be killed.When a branch is killed at a stage of an iteration, no elements in the current Branch Set are added to the Next Set. This is illustrated by revisiting the Depth First Search Iteration, but this time killing the branch at node B. The following table summarizes the stages of the traversal:
Stage | Visited Node | Branch Set | Next Set | Comment |
---|---|---|---|---|
0 | {A} | Initial stage, iteration starts explicitly from A | ||
1 | A | {B,F} | {F,B} | Related nodes added to Next Set in LIFO order. |
2 | F | {A,B} | {B,B} | A already visited so not added to Next Set B not yet visited so added to queue. |
3 | B | {A,C,D,E,F} | {B} | Branch Killed. No nodes added to Next Set |
4 | B | { } | B already visited so ignore and move to next stage | |
9 | { } | Next set empty, iteration complete. |
In this example, killing the branch at node B results in nodes C, D, and E never being visited.
- Author:
- Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
- See Also:
-
Method Summary
Modifier and TypeMethodDescriptionvoid
cont
(Graphable current, GraphTraversal traversal) Signals to the iterator that iteration should continue from the current component in the traversal.Returns the traversal for the iterator.void
init
(Graph graph, GraphTraversal traversal) Signals to the itereator that iteration is about to begin.void
killBranch
(Graphable current, GraphTraversal traversal) Signals the iterator to kill the branch at the current component.next
(GraphTraversal traversal) Returns the next graph component in the iteration.void
setTraversal
(GraphTraversal traversal) Sets the traversal for the iterator.
-
Method Details
-
setTraversal
Sets the traversal for the iterator.- Parameters:
traversal
- The traversal requesting components from the iterator.
-
getTraversal
GraphTraversal getTraversal()Returns the traversal for the iterator.- Returns:
- The traversal requesting components from the iterator.
-
init
Signals to the itereator that iteration is about to begin. This often results in the creation/initialization of any internal data structures used by the iterator.- Parameters:
graph
- The graph being whose components are being iterated over.
-
next
Returns the next graph component in the iteration. To signal to the caller that the iteration is complete, null should be returned.- Returns:
- The next component in the iteration, or null if iteration is complete.
-
cont
Signals to the iterator that iteration should continue from the current component in the traversal.- Parameters:
current
- The current component of the traversal.
-
killBranch
Signals the iterator to kill the branch at the current component.- Parameters:
current
- The current component of the traversal.
-