Class 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 java.lang.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 Summary

      Fields 
      Modifier and Type Field Description
      private java.util.Map<V,​java.util.Set<V>> bSets  
      private java.util.function.Consumer<java.util.List<V>> cycleConsumer  
      private Graph<V,​E> graph  
      private V[] iToV  
      private java.util.Set<V> marked  
      private int[] position  
      private boolean[] reach  
      private java.util.Map<V,​java.util.Set<V>> removed  
      private java.util.ArrayDeque<V> stack  
      private java.util.List<V> startVertices  
      private java.util.Map<V,​java.lang.Integer> vToI  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void clearState()  
      private boolean cycle​(int v, int q)  
      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)  
      Graph<V,​E> getGraph()
      Get the graph
      private java.util.Set<V> getRemoved​(V v)  
      private void initState​(java.util.function.Consumer<java.util.List<V>> consumer)  
      private void noCycle​(int x, int y)  
      void setGraph​(Graph<V,​E> graph)
      Set the graph
      private java.lang.Integer toI​(V v)  
      private V toV​(int i)  
      private void unmark​(int x)  
      • 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
      • bSets

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

        private java.util.ArrayDeque<V> stack
      • marked

        private java.util.Set<V> marked
      • removed

        private java.util.Map<V,​java.util.Set<V>> removed
      • position

        private int[] position
      • reach

        private boolean[] reach
      • startVertices

        private java.util.List<V> startVertices
    • Constructor Detail

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

      • 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​(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.
      • 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​(java.util.function.Consumer<java.util.List<V>> consumer)
      • clearState

        private void clearState()
      • toI

        private java.lang.Integer toI​(V v)
      • toV

        private V toV​(int i)
      • getBSet

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

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