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

Class HawickJamesSimpleCycles<V,​E>

java.lang.Object
org.jgrapht.alg.cycle.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

  • Constructor Summary

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

  • Method Summary

    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 Details

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

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