Package org.jgrapht.alg.cycle

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 java.util.List<java.util.List<V>> cycles  
      private DirectedGraph<V,​E> graph  
      private V[] iToV  
      private long nCycles  
      private int nVertices  
      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 java.util.List<java.lang.Integer>[] buildAdjacencyList()  
      private boolean circuit​(java.lang.Integer v, HawickJamesSimpleCycles.Operation o)  
      private void clearState()  
      long countSimpleCycles()
      Count the number of simple cycles.
      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 void initState​(HawickJamesSimpleCycles.Operation o)  
      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.
      private int removeFromList​(java.util.List<java.lang.Integer> list, java.lang.Integer u)
      Remove all occurrences of a value from the list.
      void setGraph​(DirectedGraph<V,​E> graph)
      Sets the graph on which the simple cycle search algorithm is executed by this object.
      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

      • nVertices

        private int nVertices

      • nCycles

        private long nCycles

      • cycles

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

      • 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

    • Constructor Detail

      • HawickJamesSimpleCycles

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

      • HawickJamesSimpleCycles

        public HawickJamesSimpleCycles​(DirectedGraph<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

      • buildAdjacencyList

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

      • clearState

        private void clearState()

      • unblock

        private void unblock​(java.lang.Integer u)

      • removeFromList

        private int removeFromList​(java.util.List<java.lang.Integer> list,
                           java.lang.Integer u)
        Remove all occurrences of a value from the list.
        Parameters:
        u - the Integer to be removed.
        list - the list from which all the occurrences of u must be removed.

      • 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)
              throws java.lang.IllegalArgumentException
        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.
        Throws:
        java.lang.IllegalArgumentException - if the argument is null.

      • findSimpleCycles

        public java.util.List<java.util.List<V>> findSimpleCycles()
                                                   throws java.lang.IllegalArgumentException
        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.
        Throws:
        java.lang.IllegalArgumentException - if the current graph is null.

      • 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