edu.isi.pegasus.planner.partitioner.graph

## 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
`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 and Description
`TopologicalSortIterator(Graph graph)` The overloaded constructor.

### Method Summary

All Methods Instance Methods Concrete Methods
`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.

### Methods inherited from class java.lang.Object

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

### Methods inherited from interface java.util.Iterator

`forEachRemaining`

### 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 interface `java.util.Iterator`
Returns:
  boolean

#### next

    public java.lang.Object next()

Returns the next node to be traversed

Specified by:
  `next` in interface `java.util.Iterator`
Returns:

#### remove

    public void remove()

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

Specified by:
  `remove` in interface `java.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