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

    Author:
    Luiz Kill

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void clearPathLimit()
      This is the default behaviour of the algorithm.
      long countSimpleCycles()
      Count the number of simple cycles.
      java.util.List<java.util.List<V>> findSimpleCycles()
      Find the simple cycles of the graph.
      Graph<V,​E> getGraph()
      Get the graph
      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.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • 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

      • 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 java.util.List<java.util.List<V>> findSimpleCycles()
                                                   throws java.lang.IllegalArgumentException
        Find the simple cycles of the graph.
        Specified by:
        findSimpleCycles in interface DirectedSimpleCycles<V,​E>
        Returns:
        The list of all simple cycles. Possibly empty but never null.
        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

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