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

Class SzwarcfiterLauerSimpleCycles<V,E>

java.lang.Object
org.jgrapht.alg.cycle.SzwarcfiterLauerSimpleCycles<V,E>
Type Parameters:
V - the vertex type.
E - the edge type.
All Implemented Interfaces:
DirectedSimpleCycles<V,E>
public class SzwarcfiterLauerSimpleCycles<V,E> extends Object implements DirectedSimpleCycles<V,E>
Find all simple cycles of a directed graph using the Schwarcfiter and Lauer's algorithm.

See:
J.L.Szwarcfiter and P.E.Lauer, Finding the elementary cycles of a directed graph in $O(n + m)$ per cycle, Technical Report Series, #60, May 1974, Univ. of Newcastle upon Tyne, Newcastle upon Tyne, England.

  • Field Details

    • graph

      private Graph<V,E> graph

    • cycleConsumer

      private Consumer<List<V>> cycleConsumer

    • iToV

      private V[] iToV

    • vToI

      private Map<V,Integer> vToI

    • bSets

      private Map<V,Set<V>> bSets

    • stack

      private ArrayDeque<V> stack

    • marked

      private Set<V> marked

    • removed

      private Map<V,Set<V>> removed

    • position

      private int[] position

    • reach

      private boolean[] reach

    • startVertices

      private List<V> startVertices

  • Constructor Details

    • SzwarcfiterLauerSimpleCycles

      public SzwarcfiterLauerSimpleCycles()
      Create a simple cycle finder with an unspecified graph.

    • SzwarcfiterLauerSimpleCycles

      public SzwarcfiterLauerSimpleCycles(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

    • getGraph

      public Graph<V,E> getGraph()
      Get the graph
      Returns:
      graph

    • setGraph

      public void setGraph(Graph<V,E> graph)
      Set the graph
      Parameters:
      graph - graph

    • 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.

    • cycle

      private boolean cycle(int v, int q)

    • noCycle

      private void noCycle(int x, int y)

    • unmark

      private void unmark(int x)

    • initState

      private void initState(Consumer<List<V>> consumer)

    • clearState

      private void clearState()

    • toI

      private Integer toI(V v)

    • toV

      private V toV(int i)

    • getBSet

      private Set<V> getBSet(V v)

    • getRemoved

      private Set<V> getRemoved(V v)