Package org.geotools.graph.util.graph

Class CycleDetector

Object
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:

  • Constructor Details

    • CycleDetector

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

  • Method Details

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

    • finish

      public void finish()
      Does nothing.
      Specified by:
      finish in interface GraphWalker
      See Also:

    • createIterator

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