org.geotools.graph.util.graph
Class CycleDetector

java.lang.Object
  org.geotools.graph.util.graph.CycleDetector

All Implemented Interfaces:

GraphWalker

Direct Known Subclasses:

DirectedCycleDetector

public class CycleDetector

extends java.lang.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

CycleDetector(Graph graph)
Constructs a new CycleDetector.

Method Summary

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 java.lang.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)

finish

public void finish()

Does nothing.

Specified by:

finish in interface GraphWalker

See Also:

GraphWalker.finish()

createIterator

protected GraphIterator createIterator()

Creates the iterator to be used in the cycle detection.

Returns:

a BreathFirstToplogicalIterator.