- java.lang.Object
-
- org.jgrapht.traverse.AbstractGraphIterator<V,E>
-
- org.jgrapht.traverse.TopologicalOrderIterator<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
java.util.Iterator<V>
,GraphIterator<V,E>
public class TopologicalOrderIterator<V,E> extends AbstractGraphIterator<V,E>
A topological ordering iterator for a directed acyclic graph.A topological order is a permutation
p
of the vertices of a graph such that an edge(i,j)
implies thati
appears beforej
inp
. For more information see wikipedia or wolfram.The iterator crosses components but does not track them, it only tracks visited vertices. The iterator will detect (at some point) if the graph is not a directed acyclic graph and throw a
NotDirectedAcyclicGraphException
.For this iterator to work correctly the graph must not be modified during iteration. Currently there are no means to ensure that, nor to fail-fast. The results of such modifications are undefined.
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from class org.jgrapht.traverse.AbstractGraphIterator
AbstractGraphIterator.FlyweightEdgeEvent<E>, AbstractGraphIterator.FlyweightVertexEvent<V>
-
-
Field Summary
Fields Modifier and Type Field Description private V
cur
private java.util.Map<V,ModifiableInteger>
inDegreeMap
private java.util.Queue<V>
queue
private int
remainingVertices
-
Fields inherited from class org.jgrapht.traverse.AbstractGraphIterator
crossComponentTraversal, graph, nListeners, reusableEdgeEvent, reusableVertexEvent, reuseEvents
-
-
Constructor Summary
Constructors Constructor Description TopologicalOrderIterator(Graph<V,E> graph)
Construct a topological order iterator.TopologicalOrderIterator(Graph<V,E> graph, java.util.Comparator<V> comparator)
Construct a topological order iterator.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private V
advance()
boolean
hasNext()
boolean
isCrossComponentTraversal()
Test whether this iterator is set to traverse the graph across connected components.V
next()
void
setCrossComponentTraversal(boolean crossComponentTraversal)
Sets the cross component traversal flag - indicates whether to traverse the graph across connected components.-
Methods inherited from class org.jgrapht.traverse.AbstractGraphIterator
addTraversalListener, createEdgeTraversalEvent, createVertexTraversalEvent, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexFinished, fireVertexTraversed, getGraph, isReuseEvents, remove, removeTraversalListener, setReuseEvents
-
-
-
-
Field Detail
-
queue
private java.util.Queue<V> queue
-
inDegreeMap
private java.util.Map<V,ModifiableInteger> inDegreeMap
-
remainingVertices
private int remainingVertices
-
cur
private V cur
-
-
Constructor Detail
-
TopologicalOrderIterator
public TopologicalOrderIterator(Graph<V,E> graph)
Construct a topological order iterator.Traversal will start at one of the graph's sources. See the definition of source at http://mathworld.wolfram.com/Source.html. In case of partial order, tie-breaking is arbitrary.
- Parameters:
graph
- the directed graph to be iterated
-
TopologicalOrderIterator
public TopologicalOrderIterator(Graph<V,E> graph, java.util.Comparator<V> comparator)
Construct a topological order iterator.Traversal will start at one of the graph's sources. See the definition of source at http://mathworld.wolfram.com/Source.html. In case of partial order, a comparator is used to break ties.
- Parameters:
graph
- the directed graph to be iteratedcomparator
- comparator in order to break ties in case of partial order
-
-
Method Detail
-
isCrossComponentTraversal
public boolean isCrossComponentTraversal()
Test whether this iterator is set to traverse the graph across connected components. Always returns true since the iterator does not care about components.- Specified by:
isCrossComponentTraversal
in interfaceGraphIterator<V,E>
- Overrides:
isCrossComponentTraversal
in classAbstractGraphIterator<V,E>
- Returns:
true
if traverses across connected components, otherwisefalse
.
-
setCrossComponentTraversal
public void setCrossComponentTraversal(boolean crossComponentTraversal)
Sets the cross component traversal flag - indicates whether to traverse the graph across connected components. Trying to disable the cross components nature of this iterator will result into throwing aIllegalArgumentException
.- Overrides:
setCrossComponentTraversal
in classAbstractGraphIterator<V,E>
- Parameters:
crossComponentTraversal
- iftrue
traverses across connected components.
-
hasNext
public boolean hasNext()
-
next
public V next()
-
advance
private V advance()
-
-