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

    • graph

      private Graph<V,E> graph
    • nVertices

      private int nVertices
    • nCycles

      private long nCycles
    • start

      private Integer start
    • aK

      private List<Integer>[] aK
    • b

      private List<Integer>[] b
    • blocked

      private boolean[] blocked
    • stack

      private ArrayDeque<Integer> stack
    • iToV

      private V[] iToV
    • vToI

      private Map<V,Integer> vToI
    • pathLimit

      private int pathLimit
    • hasLimit

      private boolean hasLimit
    • operation

      private Runnable operation
  • Constructor Details

    • HawickJamesSimpleCycles

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

      public HawickJamesSimpleCycles(Graph<V,E> graph) throws IllegalArgumentException
      Create a simple cycle finder for the specified graph.
      Parameters:
      graph - the DirectedGraph in which to find cycles.
      Throws:
      IllegalArgumentException - if the graph argument is null.
  • Method Details

    • initState

      private void initState()
    • buildAdjacencyList

      private List<Integer>[] buildAdjacencyList()
    • clearState

      private void clearState()
    • circuit

      private boolean circuit(Integer v, int steps)
    • unblock

      private void unblock(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(Consumer<List<V>> consumer) throws 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:
      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)