org.geotools.graph.traverse.standard
Class BreadthFirstTopologicalIterator

java.lang.Object
  extended byorg.geotools.graph.traverse.basic.AbstractGraphIterator
      extended byorg.geotools.graph.traverse.standard.BreadthFirstTopologicalIterator
All Implemented Interfaces:
GraphIterator
Direct Known Subclasses:
DepthFirstTopologicalIterator

public class BreadthFirstTopologicalIterator
extends AbstractGraphIterator

Iterates over the nodes of a graph in Breadth First Topological Sort pattern. The following is an illustration of the iteration.


Initially all nodes of degree less than two are active (ready to be visited). As nodes are visited, a node can become active when all but one of its related nodes have been visited ( degree = counter + 1). When a node becomes active it is placed into the active node queue (queue of nodes to be visited). The Breadth First Topological iterator places nodes into the queue in First In First Out order.

To determine when a node is to become active the iterator uses the counter associated with each node. If these counters are modified by an entity other then the iterator, the iteration may be affected in undefined ways.

Author:
Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net

Constructor Summary
BreadthFirstTopologicalIterator()
           
 
Method Summary
protected  Queue buildQueue(Graph graph)
          Builds the active node queue.
 void cont(Graphable current, GraphTraversal traversal)
          Continues the iteration by incrementing the counters of any unvisited nodes related to the current node.
 void init(Graph graph, GraphTraversal traversal)
          Creates the active queue, and populates it with all nodes of degree less than 2.
 void killBranch(Graphable current, GraphTraversal traversal)
          Kills the current branch of the traversal by not incremening the counters of any related nodes.
 Graphable next(GraphTraversal traversal)
          Returns the next node in the active node queue.
 
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

BreadthFirstTopologicalIterator

public BreadthFirstTopologicalIterator()
Method Detail

init

public void init(Graph graph,
                 GraphTraversal traversal)
Creates the active queue, and populates it with all nodes of degree less than 2. Counters of all nodes are also reset to 0.

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 in the active node queue.

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)
Continues the iteration by incrementing the counters of any unvisited nodes related to the current node. If any related nodes have counters equal to degree of that node - 1, it is placed into the active queue.

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 of the traversal by not incremening the counters of any related nodes.

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 active node queue.

Parameters:
graph - The Graph whose components are being iterated over.
Returns:
A first in first out queue


Copyright © GeoTools. All Rights Reserved.