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