Module org.jgrapht.core

Package org.jgrapht.alg.cycle

Class CycleDetector.ProbeIterator<V,E>

java.lang.Object

org.jgrapht.traverse.AbstractGraphIterator<V,E>

org.jgrapht.traverse.CrossComponentIterator<V,E,DepthFirstIterator.VisitColor>

org.jgrapht.traverse.DepthFirstIterator<V,E>

org.jgrapht.alg.cycle.CycleDetector.ProbeIterator<V,E>

All Implemented Interfaces:

Iterator<V>, GraphIterator<V,E>

Enclosing class:

CycleDetector<V,E>

private static class CycleDetector.ProbeIterator<V,E>
extends DepthFirstIterator<V,E>

Version of DFS which maintains a backtracking path used to probe for cycles.

Nested Class Summary

Nested classes/interfaces inherited from class org.jgrapht.traverse.DepthFirstIterator

DepthFirstIterator.VisitColor

Field Summary

Fields

Modifier and Type	Field	Description
private Set<V>	cycleSet
private List<V>	path
private V	root

Fields inherited from class org.jgrapht.traverse.DepthFirstIterator

SENTINEL

Fields inherited from class org.jgrapht.traverse.AbstractGraphIterator

crossComponentTraversal, graph, nListeners, reusableEdgeEvent, reusableVertexEvent, reuseEvents

Constructor Summary

Constructors

Constructor	Description
ProbeIterator(Graph<V,E> graph, Set<V> cycleSet, V startVertex)

Method Summary

Modifier and Type	Method	Description
protected void	encounterVertexAgain(V vertex, E edge)	Called whenever we re-encounter a vertex.
protected V	provideNextVertex()	Returns the vertex to be returned in the following call to the iterator next method.

Methods inherited from class org.jgrapht.traverse.DepthFirstIterator

encounterVertex, getStack, isConnectedComponentExhausted

Methods inherited from class org.jgrapht.traverse.CrossComponentIterator

finishVertex, getEntireGraphVertexIterator, getSeenData, hasNext, isSeenVertex, next, putSeenData, selectOutgoingEdges

Methods inherited from class org.jgrapht.traverse.AbstractGraphIterator

addTraversalListener, createEdgeTraversalEvent, createVertexTraversalEvent, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexFinished, fireVertexTraversed, getGraph, isCrossComponentTraversal, isReuseEvents, remove, removeTraversalListener, setCrossComponentTraversal, setReuseEvents

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.Iterator

forEachRemaining

Field Details

path

private List<V> path

cycleSet

private Set<V> cycleSet

root

private V root

Constructor Details

ProbeIterator

ProbeIterator(Graph<V,E> graph,
 Set<V> cycleSet,
 V startVertex)

Method Details

encounterVertexAgain

protected void encounterVertexAgain(V vertex,
 E edge)

Called whenever we re-encounter a vertex. The default implementation does nothing.

Overrides:

encounterVertexAgain in class DepthFirstIterator<V,E>

Parameters:

vertex - the vertex re-encountered

edge - the edge via which the vertex was re-encountered

provideNextVertex

protected V provideNextVertex()

Returns the vertex to be returned in the following call to the iterator next method.

Overrides:

provideNextVertex in class DepthFirstIterator<V,E>

Returns:

the next vertex to be returned by this iterator.