org.geotools.graph.traverse.standard
Class BreadthFirstIterator

java.lang.Object
  extended byorg.geotools.graph.traverse.basic.AbstractGraphIterator
      extended byorg.geotools.graph.traverse.basic.SourceGraphIterator
          extended byorg.geotools.graph.traverse.standard.BreadthFirstIterator
All Implemented Interfaces:
GraphIterator
Direct Known Subclasses:
DepthFirstIterator, DirectedBreadthFirstIterator

public class BreadthFirstIterator
extends SourceGraphIterator

Iterates over the nodes of a graph in a Breadth 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 Breadth First iteration is implemented as a First In First Out queue. 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
BreadthFirstIterator()
           
 
Method Summary
protected  Queue buildQueue(Graph graph)
          Builds the node queue for the iteration.
 void cont(Graphable current, GraphTraversal traversal)
          Looks for nodes adjacent to the current node to place into the node queue.
protected  Queue getQueue()
          Returns the node queue.
 void init(Graph graph, GraphTraversal traversal)
          Does nothing.
 void killBranch(Graphable current, GraphTraversal traversal)
          Kills the current branch by not looking for any adjacent nodes to place into the node queue.
 Graphable next(GraphTraversal traversal)
          Returns the next node from the node queue that has not yet been visited.
 void setSource(Graphable source)
          Sets the source of the traversal and places it in the node queue.
 
Methods inherited from class org.geotools.graph.traverse.basic.SourceGraphIterator
getSource
 
Methods inherited from class org.geotools.graph.traverse.basic.AbstractGraphIterator
getGraph, getTraversal, getWalker, setTraversal
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

BreadthFirstIterator

public BreadthFirstIterator()
Method Detail

setSource

public void setSource(Graphable source)
Sets the source of the traversal and places it in the node queue. The first call to this method will result in the internal node queue being built. Subsequent calls to the method clear the node queue and reset the iteration.

Overrides:
setSource in class SourceGraphIterator
Parameters:
source - The source of the iteration.
See Also:
SourceGraphIterator.setSource(Graphable)

init

public void init(Graph graph,
                 GraphTraversal traversal)
Does nothing.

Parameters:
graph - The graph being whose components are being iterated over.
See Also:
org.geotools.graph.traverse.GraphIterator#init(Graph)

next

public Graphable next(GraphTraversal traversal)
Returns the next node from the node queue that has not yet been visited. It is possible for the node queue to contain duplicate entries. To prevent the iteration returning the same node multiple times, the visited flag is checked on nodes coming out of the queue. If the flag is set, the node is ignored, not returned, and the next node in the queue is returned. This is however tranparent to the caller.

Returns:
The next component in the iteration, or null if iteration is complete.
See Also:
org.geotools.graph.traverse.GraphIterator#next()

cont

public void cont(Graphable current,
                 GraphTraversal traversal)
Looks for nodes adjacent to the current node to place into the node queue. An adjacent node is only placed into the node queue if its visited flag is unset.

Parameters:
current - The current component of the traversal.
See Also:
org.geotools.graph.traverse.GraphIterator#cont(Graphable)

killBranch

public void killBranch(Graphable current,
                       GraphTraversal traversal)
Kills the current branch by not looking for any adjacent nodes to place into the node queue.

Parameters:
current - The current component of the traversal.
See Also:
org.geotools.graph.traverse.GraphIterator#killBranch(Graphable)

buildQueue

protected Queue buildQueue(Graph graph)
Builds the node queue for the iteration.

Parameters:
graph - The graph being iterated over.
Returns:
A First In First Out queue.

getQueue

protected Queue getQueue()
Returns the node queue.

Returns:
The node queue.


Copyright © GeoTools. All Rights Reserved.