edu.isi.pegasus.planner.partitioner
Class Topological

java.lang.Object
  edu.isi.pegasus.planner.partitioner.Topological

public class Topological
extends Object

Does a topological sort on the Partition.

Version:

$Revision: 2576 $

Author:

Karan Vahi

Field Summary

private int[]	mInDegree An array that contains the number of incoming edges to a node.
private 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

Topological(Partition p)
The overloaded constructor.

Method Summary

protected 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(String id) Returns the index of a particular node.
void	initialize() Initializes the inDegree for each node of the partition.
List	sort() Topologically sorts the partition and returns a List of GraphNode elements.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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 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 List sort()

Topologically sorts the partition and returns a List of GraphNode elements. The iterator of the list, returns the elements in the topological order.

Returns:

List of GraphNode objects

childrenRepresentation

protected 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(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