public final class TopologicalSort
extends java.lang.Object
While this algorithm is used for mod loading in forge, it can be utilized in other fashions, e.g. topology-based registry loading, prioritization for renderers, and even mod module loading.
| Constructor and Description |
|---|
TopologicalSort() |
| Modifier and Type | Method and Description |
|---|---|
private static <T> void |
throwCyclePresentException(java.util.Set<java.util.Set<T>> components) |
static <T> java.util.List<T> |
topologicalSort(com.google.common.graph.Graph<T> graph,
java.util.Comparator<? super T> comparator)
A breath-first-search based topological sort.
|
public static <T> java.util.List<T> topologicalSort(com.google.common.graph.Graph<T> graph,
@Nullable
java.util.Comparator<? super T> comparator)
throws java.lang.IllegalArgumentException
Compared to the depth-first-search 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 the
Graph.successors(Object) call, which is random by default.
Given the number of edges E and the number of vertexes V,
the time complexity of a sort without a secondary comparator is O(E + V).
With a secondary comparator of time complexity O(T), the overall time
complexity would be O(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.
T - the node type of the graphgraph - the graph to sortcomparator - the secondary comparator, may be nulljava.lang.IllegalArgumentException - if the graph is undirected or allows self loopsCyclePresentException - if the graph contains cyclesprivate static <T> void throwCyclePresentException(java.util.Set<java.util.Set<T>> components)