Class 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.
    • 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 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