Class TopologicalSort
While this algorithm is used for mod loading in forge, it can be utilized in other fashions, e.g. topologybased registry loading, prioritization for renderers, and even mod module loading.

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionprivate static <T> void
throwCyclePresentException
(Set<Set<T>> components) static <T> List<T>
topologicalSort
(com.google.common.graph.Graph<T> graph, Comparator<? super T> comparator) A breathfirstsearch based topological sort.

Constructor Details

TopologicalSort
public TopologicalSort()


Method Details

topologicalSort
public static <T> List<T> topologicalSort(com.google.common.graph.Graph<T> graph, @Nullable Comparator<? super T> comparator) throws IllegalArgumentException A breathfirstsearch based topological sort.Compared to the depthfirstsearch version, it does not reverse the graph and supports custom secondary ordering specified by a comparator. It also utilizes the recently introduced Guava Graph API, which is more straightforward than the old directed graph.
The graph to sort must be directed, must not allow self loops, and must not contain cycles.
IllegalArgumentException
will be thrown otherwise.When
null
is used for the comparator and multiple nodes have no prerequisites, the order depends on the iteration order of the set returned by theGraph.successors(Object)
call, which is random by default.Given the number of edges
E
and the number of vertexesV
, the time complexity of a sort without a secondary comparator isO(E + V)
. With a secondary comparator of time complexityO(T)
, the overall time complexity would beO(E + TV log(V))
. As a result, the comparator should be as efficient as possible.Examples of topological sort usage can be found in Forge test code.
 Type Parameters:
T
 the node type of the graph Parameters:
graph
 the graph to sortcomparator
 the secondary comparator, may be null Returns:
 the ordered nodes from the graph
 Throws:
IllegalArgumentException
 if the graph is undirected or allows self loopsCyclePresentException
 if the graph contains cycles

throwCyclePresentException
