Class 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 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  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method 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)