Class JohnsonSimpleCycles<V,E>

java.lang.Object
org.jgrapht.alg.cycle.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 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 Details

  • Constructor Details

    • 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:
      IllegalArgumentException - if the graph argument is null.
  • Method Details

    • findSimpleCycles

      public void findSimpleCycles(Consumer<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>,Integer> findMinSCSG(int startIndex)
    • findSCCS

      private List<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(Consumer<List<V>> consumer)
    • clearState

      private void clearState()
    • initMinSCGState

      private void initMinSCGState()
    • clearMinSCCState

      private void clearMinSCCState()
    • toI

      private Integer toI(V vertex)
    • toV

      private V toV(Integer i)
    • getBSet

      private Set<V> getBSet(V v)