Class HawickJamesSimpleCycles<V,​E>

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

    public class HawickJamesSimpleCycles<V,​E>
    extends java.lang.Object
    implements DirectedSimpleCycles<V,​E>
    Find all simple cycles of a directed graph using the algorithm described by Hawick and James.

    See:
    K. A. Hawick, H. A. James. Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs. Computational Science Technical Note CSTN-013, 2008

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.List<java.lang.Integer>[] aK  
      private java.util.List<java.lang.Integer>[] b  
      private boolean[] blocked  
      private Graph<V,​E> graph  
      private boolean hasLimit  
      private V[] iToV  
      private long nCycles  
      private int nVertices  
      private java.lang.Runnable operation  
      private int pathLimit  
      private java.util.ArrayDeque<java.lang.Integer> stack  
      private java.lang.Integer start  
      private java.util.Map<V,​java.lang.Integer> vToI  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void analyzeCircuits()  
      private java.util.List<java.lang.Integer>[] buildAdjacencyList()  
      private boolean circuit​(java.lang.Integer v, int steps)  
      void clearPathLimit()
      This is the default behaviour of the algorithm.
      private void clearState()  
      long countSimpleCycles()
      Count the number of simple cycles.
      void findSimpleCycles​(java.util.function.Consumer<java.util.List<V>> consumer)
      Find the simple cycles of the graph.
      Graph<V,​E> getGraph()
      Get the graph
      private void initState()  
      private boolean limitReached​(int steps)  
      void printSimpleCycles()
      Print to the standard output all simple cycles without building a list to keep them, thus avoiding high memory consumption when investigating large and much connected graphs.
      void setGraph​(Graph<V,​E> graph)
      Set the graph
      void setPathLimit​(int pathLimit)
      Limits the maximum number of edges in a cycle.
      private void unblock​(java.lang.Integer u)  
      • 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
      • nVertices

        private int nVertices
      • nCycles

        private long nCycles
      • start

        private java.lang.Integer start
      • aK

        private java.util.List<java.lang.Integer>[] aK
      • b

        private java.util.List<java.lang.Integer>[] b
      • blocked

        private boolean[] blocked
      • stack

        private java.util.ArrayDeque<java.lang.Integer> stack
      • iToV

        private V[] iToV
      • vToI

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

        private int pathLimit
      • hasLimit

        private boolean hasLimit
      • operation

        private java.lang.Runnable operation
    • Constructor Detail

      • HawickJamesSimpleCycles

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

        public HawickJamesSimpleCycles​(Graph<V,​E> graph)
                                throws java.lang.IllegalArgumentException
        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

      • initState

        private void initState()
      • buildAdjacencyList

        private java.util.List<java.lang.Integer>[] buildAdjacencyList()
      • clearState

        private void clearState()
      • circuit

        private boolean circuit​(java.lang.Integer v,
                                int steps)
      • unblock

        private void unblock​(java.lang.Integer u)
      • 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)
                              throws java.lang.IllegalArgumentException
        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.
        Throws:
        java.lang.IllegalArgumentException
      • printSimpleCycles

        public void printSimpleCycles()
        Print to the standard output all simple cycles without building a list to keep them, thus avoiding high memory consumption when investigating large and much connected graphs.
      • countSimpleCycles

        public long countSimpleCycles()
        Count the number of simple cycles. It can count up to Long.MAX cycles in a graph.
        Returns:
        the number of simple cycles
      • analyzeCircuits

        private void analyzeCircuits()
      • setPathLimit

        public void setPathLimit​(int pathLimit)
        Limits the maximum number of edges in a cycle.
        Parameters:
        pathLimit - maximum paths.
      • clearPathLimit

        public void clearPathLimit()
        This is the default behaviour of the algorithm. It will keep looking as long as there are paths available.
      • limitReached

        private boolean limitReached​(int steps)