edu.isi.pegasus.planner.partitioner.graph
Class TopologicalSortIterator

java.lang.Object
  edu.isi.pegasus.planner.partitioner.graph.TopologicalSortIterator

All Implemented Interfaces:

Iterator

public class TopologicalSortIterator
extends Object
implements Iterator

Does a topological sort on the Partition.

Version:

$Revision: 2576 $

Author:

Karan Vahi

Field Summary

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 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 List<GraphNode>	mQueue The internal list of nodes that contains the nodes to be traversed.

Constructor Summary

TopologicalSortIterator(Graph graph)
The overloaded constructor.

Method Summary

boolean	hasNext() Returns whether there are more nodes to be traversed in the graph or not.
private int	index(String id) Returns the index of a particular node.
void	initialize() Initializes the inDegree for each node of the partition.
Object	next() Returns the next node to be traversed
void	remove() Removes a node from the graph.

Methods inherited from class java.lang.Object

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

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 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 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 interface Iterator

Returns:

boolean

next

public Object next()

Returns the next node to be traversed

Specified by:

next in interface Iterator

Returns:

remove

public void remove()

Removes a node from the graph. Operation not supported as yet.

Specified by:

remove in interface Iterator

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