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

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.function.Consumer<java.util.List<V>> cycleConsumer  
      private Graph<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  

    • Constructor Summary

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

    • Field Detail

      • graph

        private Graph<V,​E> graph

      • cycleConsumer

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

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

      • backtrack

        private boolean backtrack​(V start,
                          V vertex)

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

      • getRemoved

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