|
|||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object org.geotools.graph.traverse.basic.AbstractGraphIterator org.geotools.graph.traverse.standard.BreadthFirstTopologicalIterator
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.
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 |
public BreadthFirstTopologicalIterator()
Method Detail |
public void init(Graph graph, GraphTraversal traversal)
graph
- The graph being whose components are being iterated over.org.geotools.graph.traverse.GraphIterator#init(Graph)
public Graphable next(GraphTraversal traversal)
org.geotools.graph.traverse.GraphIterator#next()
public void cont(Graphable current, GraphTraversal traversal)
current
- The current component of the traversal.org.geotools.graph.traverse.GraphIterator#cont(Graphable)
public void killBranch(Graphable current, GraphTraversal traversal)
current
- The current component of the traversal.org.geotools.graph.traverse.GraphIterator#killBranch(Graphable)
protected Queue buildQueue(Graph graph)
graph
- The Graph whose components are being iterated over.
|
|||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |