Class TopologicalSortIterator
- java.lang.Object
-
- edu.isi.pegasus.planner.partitioner.graph.TopologicalSortIterator
-
- All Implemented Interfaces:
java.util.Iterator
public class TopologicalSortIterator extends java.lang.Object implements java.util.Iterator
Does a topological sort on the Partition.- Version:
- $Revision$
- Author:
- Karan Vahi
-
-
Field Summary
Fields Modifier and Type Field 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 Summary
Constructors Constructor Description TopologicalSortIterator(Graph graph)
The overloaded constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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 traversedvoid
remove()
Removes a node from the graph.
-
-
-
Field Detail
-
mGraph
private Graph mGraph
The partition that has to be sorted.
-
mInDegree
private int[] mInDegree
An array that contains the number of incoming edges to a node.
-
mIndexMap
private java.util.Map mIndexMap
A Map that returns the index into mInDegree map for a particular node in graph. Maps a ID of the node to an int value, which is the index to to the array containing the in degree for each node.- See Also:
mInDegree
-
mQueue
private java.util.List<GraphNode> mQueue
The internal list of nodes that contains the nodes to be traversed.
-
mOrder
private int mOrder
The number of nodes in the graph.
-
-
Constructor Detail
-
TopologicalSortIterator
public TopologicalSortIterator(Graph graph)
The overloaded constructor.- Parameters:
p
- the graph that has to be sorted.
-
-
Method Detail
-
initialize
public void initialize()
Initializes the inDegree for each node of the partition.
-
hasNext
public boolean hasNext()
Returns whether there are more nodes to be traversed in the graph or not.- Specified by:
hasNext
in interfacejava.util.Iterator
- Returns:
- boolean
-
next
public java.lang.Object next()
Returns the next node to be traversed- Specified by:
next
in interfacejava.util.Iterator
- Returns:
-
remove
public void remove()
Removes a node from the graph. Operation not supported as yet.- Specified by:
remove
in interfacejava.util.Iterator
-
index
private int index(java.lang.String id)
Returns the index of a particular node. The index is used as an index into arrays.- Parameters:
id
- the id of the node.- Returns:
- the index
-
-