Module org.jgrapht.core
Package org.jgrapht.alg.cycle

Class JohnsonSimpleCycles<V,​E>

  • Type Parameters:
    V - the vertex type.
    E - the edge type.
    All Implemented Interfaces:
    DirectedSimpleCycles<V,​E>
    public class JohnsonSimpleCycles<V,​E>
extends java.lang.Object
implements DirectedSimpleCycles<V,​E>
    Find all simple cycles of a directed graph using the Johnson's algorithm.

    See:
    D.B.Johnson, Finding all the elementary circuits of a directed graph, SIAM J. Comput., 4 (1975), pp. 77-84.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.Set<V> blocked  
      private java.util.Map<V,​java.util.Set<V>> bSets  
      private java.util.function.Consumer<java.util.List<V>> cycleConsumer  
      private java.util.List<java.util.Set<V>> foundSCCs  
      private Graph<V,​E> graph  
      private int index  
      private V[] iToV  
      private java.util.ArrayDeque<V> path  
      private java.util.Set<V> pathSet  
      private java.util.ArrayDeque<V> stack  
      private java.util.Map<V,​java.lang.Integer> vIndex  
      private java.util.Map<V,​java.lang.Integer> vLowlink  
      private java.util.Map<V,​java.lang.Integer> vToI  

    • Constructor Summary

      Constructors 
      Constructor Description
      JohnsonSimpleCycles​(Graph<V,​E> graph)
      Create a simple cycle finder for the specified graph.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void clearMinSCCState()  
      private void clearState()  
      private boolean findCyclesInSCG​(int startIndex, int vertexIndex, Graph<V,​E> scg)  
      private Pair<Graph<V,​E>,​java.lang.Integer> findMinSCSG​(int startIndex)  
      private java.util.List<java.util.Set<V>> findSCCS​(int startIndex)  
      void findSimpleCycles​(java.util.function.Consumer<java.util.List<V>> consumer)
      Find the simple cycles of the graph.
      private java.util.Set<V> getBSet​(V v)  
      private void getSCCs​(int startIndex, int vertexIndex)  
      private void initMinSCGState()  
      private void initState​(java.util.function.Consumer<java.util.List<V>> consumer)  
      private java.lang.Integer toI​(V vertex)  
      private V toV​(java.lang.Integer i)  
      private void unblock​(V vertex)  

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • graph

        private Graph<V,​E> graph

      • cycleConsumer

        private java.util.function.Consumer<java.util.List<V>> cycleConsumer

      • iToV

        private V[] iToV

      • vToI

        private java.util.Map<V,​java.lang.Integer> vToI

      • blocked

        private java.util.Set<V> blocked

      • bSets

        private java.util.Map<V,​java.util.Set<V>> bSets

      • stack

        private java.util.ArrayDeque<V> stack

      • foundSCCs

        private java.util.List<java.util.Set<V>> foundSCCs

      • index

        private int index

      • vIndex

        private java.util.Map<V,​java.lang.Integer> vIndex

      • vLowlink

        private java.util.Map<V,​java.lang.Integer> vLowlink

      • path

        private java.util.ArrayDeque<V> path

      • pathSet

        private java.util.Set<V> pathSet

    • Constructor Detail

      • JohnsonSimpleCycles

        public JohnsonSimpleCycles​(Graph<V,​E> graph)
        Create a simple cycle finder for the specified graph.
        Parameters:
        graph - - the DirectedGraph in which to find cycles.
        Throws:
        java.lang.IllegalArgumentException - if the graph argument is null.

    • Method Detail

      • findSimpleCycles

        public void findSimpleCycles​(java.util.function.Consumer<java.util.List<V>> consumer)
        Find the simple cycles of the graph.
        Specified by:
        findSimpleCycles in interface DirectedSimpleCycles<V,​E>
        Parameters:
        consumer - Consumer that will be called with each cycle found.

      • findMinSCSG

        private Pair<Graph<V,​E>,​java.lang.Integer> findMinSCSG​(int startIndex)

      • findSCCS

        private java.util.List<java.util.Set<V>> findSCCS​(int startIndex)

      • getSCCs

        private void getSCCs​(int startIndex,
                     int vertexIndex)

      • findCyclesInSCG

        private boolean findCyclesInSCG​(int startIndex,
                                int vertexIndex,
                                Graph<V,​E> scg)

      • unblock

        private void unblock​(V vertex)

      • initState

        private void initState​(java.util.function.Consumer<java.util.List<V>> consumer)

      • clearState

        private void clearState()

      • initMinSCGState

        private void initMinSCGState()

      • clearMinSCCState

        private void clearMinSCCState()

      • toI

        private java.lang.Integer toI​(V vertex)

      • toV

        private V toV​(java.lang.Integer i)

      • getBSet

        private java.util.Set<V> getBSet​(V v)