public class TopologicalSortIterator
extends java.lang.Object
implements java.util.Iterator
Modifier and Type | Field and Description |
---|---|
private Graph |
mGraph
The partition that has to be sorted.
|
private int[] |
mInDegree
An array that contains the number of incoming edges to a node.
|
private java.util.Map |
mIndexMap
A Map that returns the index into mInDegree map for a particular node
in graph.
|
private int |
mOrder
The number of nodes in the graph.
|
private java.util.List<GraphNode> |
mQueue
The internal list of nodes that contains the nodes to be traversed.
|
Constructor and Description |
---|
TopologicalSortIterator(Graph graph)
The overloaded constructor.
|
Modifier and Type | Method and Description |
---|---|
boolean |
hasNext()
Returns whether there are more nodes to be traversed in the graph or not.
|
private int |
index(java.lang.String id)
Returns the index of a particular node.
|
void |
initialize()
Initializes the inDegree for each node of the partition.
|
java.lang.Object |
next()
Returns the next node to be traversed
|
void |
remove()
Removes a node from the graph.
|
private Graph mGraph
private int[] mInDegree
private java.util.Map mIndexMap
mInDegree
private java.util.List<GraphNode> mQueue
private int mOrder
public TopologicalSortIterator(Graph graph)
p
- the graph that has to be sorted.public void initialize()
public boolean hasNext()
hasNext
in interface java.util.Iterator
public java.lang.Object next()
next
in interface java.util.Iterator
public void remove()
remove
in interface java.util.Iterator
private int index(java.lang.String id)
id
- the id of the node.