Class CycleDetector

  • All Implemented Interfaces:
    GraphWalker
    Direct Known Subclasses:
    DirectedCycleDetector

    public class CycleDetector
    extends Object
    implements GraphWalker
    Detects cycles in a graph. A topological iteration of the nodes of the graph is performed. If the iteration includes all nodes in the graph then the graph is cycle free, otherwise a cycle exists.
    Author:
    Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
    See Also:
    BreadthFirstTopologicalIterator
    • Constructor Summary

      Constructors 
      Constructor Description
      CycleDetector​(Graph graph)
      Constructs a new CycleDetector.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean containsCycle()
      Performs the iteration to determine if a cycle exits in the graph.
      protected GraphIterator createIterator()
      Creates the iterator to be used in the cycle detection.
      void finish()
      Does nothing.
      int visit​(Graphable element, GraphTraversal traversal)
      Increments the count of nodes visited.
      • Methods inherited from class Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • CycleDetector

        public CycleDetector​(Graph graph)
        Constructs a new CycleDetector.
        Parameters:
        graph - The graph to be tested for cycle existance.
    • Method Detail

      • containsCycle

        public boolean containsCycle()
        Performs the iteration to determine if a cycle exits in the graph.
        Returns:
        True if a cycle exists, false if not.
      • visit

        public int visit​(Graphable element,
                         GraphTraversal traversal)
        Increments the count of nodes visited.
        Specified by:
        visit in interface GraphWalker
        Parameters:
        element - The component being visited.
        traversal - The traversal controlling the sequence of graph component visits.
        Returns:
        GraphTraversal#CONTINUE to signal that the traversal should continue.
        GraphTraversal#CONTINUE to signal that the traversal should suspend.
        GraphTraversal#KILL_BRANCH to signal that the traversal should kill its current branch.
        GraphTraversal#STOP to signal that the traversal should stop.
        See Also:
        GraphWalker.visit(Graphable, GraphTraversal)
      • createIterator

        protected GraphIterator createIterator()
        Creates the iterator to be used in the cycle detection.
        Returns:
        a BreathFirstToplogicalIterator.