net.minecraftforge.fml.loading.toposort

Class StronglyConnectedComponentDetector<T>

java.lang.Object

net.minecraftforge.fml.loading.toposort.StronglyConnectedComponentDetector<T>

public class StronglyConnectedComponentDetector<T>
extends java.lang.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 Summary

Fields

Modifier and Type	Field and Description
private java.util.Set<java.util.Set<T>>	components
private int[]	dfn
private T[]	elements
private com.google.common.graph.Graph<T>	graph
private java.util.Map<T,java.lang.Integer>	ids
private int[]	low
private java.util.BitSet	onStack
private int[]	stack
private int	top

Constructor Summary

Constructors

Constructor and Description
StronglyConnectedComponentDetector(com.google.common.graph.Graph<T> graph)

Method Summary

Modifier and Type	Method and Description
private void	calculate()
private void	dfs(int now, int depth)
java.util.Set<java.util.Set<T>>	getComponents()

Methods inherited from class java.lang.Object

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

Field Detail

graph

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

ids

private java.util.Map<T,java.lang.Integer> ids

elements

private T[] elements

dfn

private int[] dfn

low

private int[] low

stack

private int[] stack

top

private int top

onStack

private java.util.BitSet onStack

components

private java.util.Set<java.util.Set<T>> components

Constructor Detail

StronglyConnectedComponentDetector

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

Method Detail

getComponents

public java.util.Set<java.util.Set<T>> getComponents()

calculate

private void calculate()

dfs

private void dfs(int now,
                 int depth)