Class Topological
- java.lang.Object
-
- edu.isi.pegasus.planner.partitioner.Topological
-
public class Topological extends java.lang.Object
Does a topological sort on the Partition.- Version:
- $Revision$
- Author:
- Karan Vahi
-
-
Field Summary
Fields Modifier and Type Field Description 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 Partition
mPartition
The partition that has to be sorted.
-
Constructor Summary
Constructors Constructor Description Topological(Partition p)
The overloaded constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected java.util.Map
childrenRepresentation()
Returns a map that is index by GraphNode ID's and each value is the list of ID's of children of that GraphNode.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.util.List
sort()
Topologically sorts the partition and returns a List ofGraphNode
elements.
-
-
-
Field Detail
-
mPartition
private Partition mPartition
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
-
-
Constructor Detail
-
Topological
public Topological(Partition p)
The overloaded constructor.- Parameters:
p
- the partition that has to be sorted.
-
-
Method Detail
-
initialize
public void initialize()
Initializes the inDegree for each node of the partition.
-
sort
public java.util.List sort()
Topologically sorts the partition and returns a List ofGraphNode
elements. The iterator of the list, returns the elements in the topological order.- Returns:
- List of
GraphNode
objects
-
childrenRepresentation
protected java.util.Map childrenRepresentation()
Returns a map that is index by GraphNode ID's and each value is the list of ID's of children of that GraphNode.- Returns:
- Map that contains adjacency list's for each node.
-
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
-
-