Class TarjanSimpleCycles<V,​E>

  • Type Parameters:
    V - the vertex type.
    E - the edge type.
    All Implemented Interfaces:
    DirectedSimpleCycles<V,​E>

    public class TarjanSimpleCycles<V,​E>
    extends java.lang.Object
    implements DirectedSimpleCycles<V,​E>
    Find all simple cycles of a directed graph using the Tarjan's algorithm.

    See:
    R. Tarjan, Enumeration of the elementary circuits of a directed graph, SIAM J. Comput., 2 (1973), pp. 211-216.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.List<java.util.List<V>> cycles  
      private DirectedGraph<V,​E> graph  
      private java.util.Set<V> marked  
      private java.util.ArrayDeque<V> markedStack  
      private java.util.ArrayDeque<V> pointStack  
      private java.util.Map<V,​java.util.Set<V>> removed  
      private java.util.Map<V,​java.lang.Integer> vToI  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private boolean backtrack​(V start, V vertex)  
      private void clearState()  
      java.util.List<java.util.List<V>> findSimpleCycles()
      Finds the simple cycles of the graph.
      Note that the full algorithm is executed on every call since the graph may have changed between calls.
      DirectedGraph<V,​E> getGraph()
      Returns the graph on which the simple cycle search algorithm is executed by this object.
      private java.util.Set<V> getRemoved​(V v)  
      private void initState()  
      void setGraph​(DirectedGraph<V,​E> graph)
      Sets the graph on which the simple cycle search algorithm is executed by this object.
      private java.lang.Integer toI​(V v)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • cycles

        private java.util.List<java.util.List<V>> cycles
      • marked

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

        private java.util.ArrayDeque<V> markedStack
      • pointStack

        private java.util.ArrayDeque<V> pointStack
      • vToI

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

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

      • TarjanSimpleCycles

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

        public TarjanSimpleCycles​(DirectedGraph<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 DirectedGraph<V,​E> getGraph()
        Returns the graph on which the simple cycle search algorithm is executed by this object.
        Specified by:
        getGraph in interface DirectedSimpleCycles<V,​E>
        Returns:
        The graph.
      • setGraph

        public void setGraph​(DirectedGraph<V,​E> graph)
        Sets the graph on which the simple cycle search algorithm is executed by this object.
        Specified by:
        setGraph in interface DirectedSimpleCycles<V,​E>
        Parameters:
        graph - the graph.
      • findSimpleCycles

        public java.util.List<java.util.List<V>> findSimpleCycles()
        Finds the simple cycles of the graph.
        Note that the full algorithm is executed on every call since the graph may have changed between calls.
        Specified by:
        findSimpleCycles in interface DirectedSimpleCycles<V,​E>
        Returns:
        The list of all simple cycles. Possibly empty but never null.
      • backtrack

        private boolean backtrack​(V start,
                                  V vertex)
      • initState

        private void initState()
      • clearState

        private void clearState()
      • toI

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

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