Package net.minecraftforge.fml.loading.toposort

Class StronglyConnectedComponentDetector<T>

java.lang.Object
net.minecraftforge.fml.loading.toposort.StronglyConnectedComponentDetector<T>
public class StronglyConnectedComponentDetector<T> extends Object
An object that splits a graph into strongly connected components lazily with Tarjan's Strongly Connected Components Algorithm.

This algorithm allows to detect all cycles in dependencies that prevent topological sorting.

This detector evaluates the graph lazily and won't reflect the modifications in the graph after initial evaluation.

  • Field Details

    • graph

      private final com.google.common.graph.Graph<T> graph

    • ids

      private Map<T,​Integer> ids

    • elements

      private T[] elements

    • dfn

      private int[] dfn

    • low

      private int[] low

    • stack

      private int[] stack

    • top

      private int top

    • onStack

      private BitSet onStack

    • components

      private Set<Set<T>> components

  • Constructor Details

    • StronglyConnectedComponentDetector

      public StronglyConnectedComponentDetector​(com.google.common.graph.Graph<T> graph)

  • Method Details

    • getComponents

      public Set<Set<T>> getComponents()

    • calculate

      private void calculate()

    • dfs

      private void dfs​(int now, int depth)