Class 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 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 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 of GraphNode 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