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:
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.
-
-
-
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 interfaceGraphWalker
- 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)
-
finish
public void finish()
Does nothing.- Specified by:
finish
in interfaceGraphWalker
- See Also:
GraphWalker.finish()
-
createIterator
protected GraphIterator createIterator()
Creates the iterator to be used in the cycle detection.- Returns:
- a BreathFirstToplogicalIterator.
-
-