Package ca.cgjennings.algo

Class TopologicalSorter<T extends DependencyRelation<T>>

  • Type Parameters:
    T - the type of object that will be sorted
    public class TopologicalSorter<T extends DependencyRelation<T>>
extends java.lang.Object
    A topological sorter produces an ordering that respects the requirement relationships of a collection of objects. For example, suppose that you are taking courses in school, and some courses are prerequisites for other courses. (To take course X, you must first have taken all of the courses that are its prerequisites.) A topological sorter would produce an ordering such that, if you took the courses in that order, all of the prerequisites would be satisfied.

    To create such an order, it is necessary that the dependency graph be acyclic. That is, you cannot have a situation where A depends on B and B also depends on A, directly or indirectly. For example, if A depends on B and C and C depends on D and D depends on A, then there is a cycle A → C → D → A. Attempting to sort a collection containing a cycle will throw an exception.

    Since:
    3.0
    Author:
    Chris Jennings

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      static <T extends DependencyRelation<T>>
      java.util.Set<T>      		 getAllDependants​(T object)
      Returns a set of the direct and indirect objects required by an object.
      java.util.Comparator<T> getComparator()
      Returns the comparator that will be used for lexicographic sorting.
      boolean isAllPresent()
      Returns true if this sorter will assume that all required elements are present in all collections that are to be sorted.
      boolean isLexicographicallySorted()
      If true, then the sort order will also be ordered according to a lexicographic sort.
      void setAllPresent​(boolean assumesAllPresent)
      Sets whether this sorter will assume that all possible elements are included in collections that it sorts.
      void setComparator​(java.util.Comparator<T> comparator)
      Sets the comparator that will be used if lexicographic sorting is enabled.
      void setLexicographicallySorted​(boolean lexSort)
      Sets whether collections will also be lexicographically sorted.
      java.util.List<T> topSort​(java.util.Collection<T> collection)
      Performs a topological sort on the elements of a collection using the current settings, returning the sorted elements in a list.

      • Methods inherited from class java.lang.Object

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

    • Constructor Detail

      • TopologicalSorter

        public TopologicalSorter()

    • Method Detail

      • isAllPresent

        public boolean isAllPresent()
        Returns true if this sorter will assume that all required elements are present in all collections that are to be sorted.
        Returns:
        true if all required objects are to be included in the input to topSort(java.util.Collection<T>)
        See Also:
        setAllPresent(boolean)

      • setAllPresent

        public void setAllPresent​(boolean assumesAllPresent)
        Sets whether this sorter will assume that all possible elements are included in collections that it sorts. Setting this to true makes a guarantee that when sorting a collection, for all elements E in the collection, if E depends on F then F is also in the collection. In other words, everything that is required is already included in the collection passed to topSort(java.util.Collection<T>). Setting this to true may result in more efficient sorting, but if it is set to true when the condition does not hold then the sorted output will be incomplete.

        When this is set to false, the sorter will detect the presence of required objects that were not part of the original collection and include them in the sorted output. Thus, the size of the sorted list may be larger than that of the unsorted list. A useful side effect of this feature is that if a single element is sorted, the result will be a list of all of the elements that are required (directly or indirectly) by that element.

        Parameters:
        assumesAllPresent - true if all required objects are to be included in the input to topSort(java.util.Collection<T>)

      • isLexicographicallySorted

        public boolean isLexicographicallySorted()
        If true, then the sort order will also be ordered according to a lexicographic sort.
        Returns:
        true
        See Also:
        setLexicographicallySorted(boolean)

      • setLexicographicallySorted

        public void setLexicographicallySorted​(boolean lexSort)
        Sets whether collections will also be lexicographically sorted. When set to true, then at any point in the sorted list, the element at that position is the one that is lexicographically least of all of the elements that could be placed there without violating the topological ordering. For example, a topological sort of a collection of courses could be further sorted lexicographically by their course number so that (to the maximum extent possible) the courses with the lowest number are listed first.
        Parameters:
        lexSort - whether output should also be lexicographically sorted
        See Also:
        setComparator(java.util.Comparator<T>)

      • getComparator

        public java.util.Comparator<T> getComparator()
        Returns the comparator that will be used for lexicographic sorting. If null, the natural order is used.
        Returns:
        the sorting comparator

      • setComparator

        public void setComparator​(java.util.Comparator<T> comparator)
        Sets the comparator that will be used if lexicographic sorting is enabled. If null, which is the default, the natural order is used.
        Parameters:
        comparator - the sorting comparator, or null for natural order

      • topSort

        public java.util.List<T> topSort​(java.util.Collection<T> collection)
        Performs a topological sort on the elements of a collection using the current settings, returning the sorted elements in a list.
        Parameters:
        collection - the collection of objects to sort
        Returns:
        a list of the objects in sorted order

      • getAllDependants

        public static <T extends DependencyRelation<T>> java.util.Set<T> getAllDependants​(T object)
        Returns a set of the direct and indirect objects required by an object.
        Type Parameters:
        T - the type of the objects that depend on each other
        Parameters:
        object - the object to return all dependants for
        Returns:
        a set of all objects that this object depends on, the objects that those objects depend on, and so on
        Throws:
        GraphCycleException - if there is a cycle in the dependency graph