Package net.minecraftforge.fml.loading.toposort

Class TopologicalSort

  • public final class TopologicalSort
extends java.lang.Object
    Provides a topological sort algorithm.

    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 Summary

      Constructors 
      Constructor Description
      TopologicalSort()  

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method 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.

      • Methods inherited from class java.lang.Object

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

    • Constructor Detail

      • TopologicalSort

        public TopologicalSort()

    • Method Detail

      • topologicalSort

        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
        A breath-first-search based topological sort.

        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.

        Type Parameters:
        T - the node type of the graph
        Parameters:
        graph - the graph to sort
        comparator - the secondary comparator, may be null
        Returns:
        the ordered nodes from the graph
        Throws:
        java.lang.IllegalArgumentException - if the graph is undirected or allows self loops
        CyclePresentException - if the graph contains cycles

      • throwCyclePresentException

        private static <T> void throwCyclePresentException​(java.util.Set<java.util.Set<T>> components)