Class TopologicalSorter<T extends DependencyRelation<T>>
- java.lang.Object
-
- ca.cgjennings.algo.TopologicalSorter<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
-
-
Constructor Summary
Constructors Constructor Description TopologicalSorter()
-
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()
Returnstrue
if this sorter will assume that all required elements are present in all collections that are to be sorted.boolean
isLexicographicallySorted()
Iftrue
, 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.
-
-
-
Method Detail
-
isAllPresent
public boolean isAllPresent()
Returnstrue
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 totopSort(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 totrue
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 totopSort(java.util.Collection<T>)
. Setting this totrue
may result in more efficient sorting, but if it is set totrue
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 totopSort(java.util.Collection<T>)
-
isLexicographicallySorted
public boolean isLexicographicallySorted()
Iftrue
, 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 totrue
, 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. Ifnull
, 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. Ifnull
, which is the default, the natural order is used.- Parameters:
comparator
- the sorting comparator, ornull
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
-
-