Package org.jgrapht.traverse
Class CrossComponentIterator<V,E,D>
- java.lang.Object
-
- org.jgrapht.traverse.AbstractGraphIterator<V,E>
-
- org.jgrapht.traverse.CrossComponentIterator<V,E,D>
-
- Type Parameters:
V
- vertex typeE
- edge typeD
- type of data associated to seen vertices
- All Implemented Interfaces:
java.util.Iterator<V>
,GraphIterator<V,E>
- Direct Known Subclasses:
BreadthFirstIterator
,ClosestFirstIterator
,DepthFirstIterator
,TopologicalOrderIterator
public abstract class CrossComponentIterator<V,E,D> extends AbstractGraphIterator<V,E>
Provides a cross-connected-component traversal functionality for iterator subclasses.- Since:
- Jan 31, 2004
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static interface
CrossComponentIterator.SimpleContainer<T>
protected static class
CrossComponentIterator.VisitColor
Standard vertex visit state enumeration.-
Nested classes/interfaces inherited from class org.jgrapht.traverse.AbstractGraphIterator
AbstractGraphIterator.DirectedSpecifics<VV,EE>, AbstractGraphIterator.FlyweightEdgeEvent<VV,localE>, AbstractGraphIterator.FlyweightVertexEvent<VV>, AbstractGraphIterator.Specifics<VV,EE>, AbstractGraphIterator.UndirectedSpecifics<VV,EE>
-
-
Field Summary
Fields Modifier and Type Field Description private ConnectedComponentTraversalEvent
ccFinishedEvent
private static int
CCS_AFTER_COMPONENT
private static int
CCS_BEFORE_COMPONENT
private static int
CCS_WITHIN_COMPONENT
private ConnectedComponentTraversalEvent
ccStartedEvent
private Graph<V,E>
graph
private java.util.Map<V,D>
seen
Stores the vertices that have been seen during iteration and (optionally) some additional traversal info regarding each vertex.private V
startVertex
private int
state
The connected component stateprivate java.util.Iterator<V>
vertexIterator
-
Fields inherited from class org.jgrapht.traverse.AbstractGraphIterator
nListeners, reusableEdgeEvent, reusableVertexEvent, specifics
-
-
Constructor Summary
Constructors Constructor Description CrossComponentIterator(Graph<V,E> g, V startVertex)
Creates a new iterator for the specified graph.
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description private void
addUnseenChildrenOf(V vertex)
private EdgeTraversalEvent<E>
createEdgeTraversalEvent(E edge)
private VertexTraversalEvent<V>
createVertexTraversalEvent(V vertex)
private void
encounterStartVertex()
protected abstract void
encounterVertex(V vertex, E edge)
Update data structures the first time we see a vertex.protected abstract void
encounterVertexAgain(V vertex, E edge)
Called whenever we re-encounter a vertex.protected void
finishVertex(V vertex)
Called when a vertex has been finished (meaning is dependent on traversal represented by subclass).Graph<V,E>
getGraph()
protected D
getSeenData(V vertex)
Access the data stored for a seen vertex.boolean
hasNext()
protected abstract boolean
isConnectedComponentExhausted()
Returns true if there are no more uniterated vertices in the currently iterated connected component; false otherwise.protected boolean
isSeenVertex(V vertex)
Determines whether a vertex has been seen yet by this traversal.V
next()
protected abstract V
provideNextVertex()
Returns the vertex to be returned in the following call to the iteratornext
method.protected D
putSeenData(V vertex, D data)
Stores iterator-dependent data for a vertex that has been seen.-
Methods inherited from class org.jgrapht.traverse.AbstractGraphIterator
addTraversalListener, createGraphSpecifics, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexFinished, fireVertexTraversed, isCrossComponentTraversal, isReuseEvents, remove, removeTraversalListener, setCrossComponentTraversal, setReuseEvents
-
-
-
-
Field Detail
-
CCS_BEFORE_COMPONENT
private static final int CCS_BEFORE_COMPONENT
- See Also:
- Constant Field Values
-
CCS_WITHIN_COMPONENT
private static final int CCS_WITHIN_COMPONENT
- See Also:
- Constant Field Values
-
CCS_AFTER_COMPONENT
private static final int CCS_AFTER_COMPONENT
- See Also:
- Constant Field Values
-
ccFinishedEvent
private final ConnectedComponentTraversalEvent ccFinishedEvent
-
ccStartedEvent
private final ConnectedComponentTraversalEvent ccStartedEvent
-
vertexIterator
private java.util.Iterator<V> vertexIterator
-
seen
private java.util.Map<V,D> seen
Stores the vertices that have been seen during iteration and (optionally) some additional traversal info regarding each vertex.
-
startVertex
private V startVertex
-
state
private int state
The connected component state
-
-
Constructor Detail
-
CrossComponentIterator
public CrossComponentIterator(Graph<V,E> g, V startVertex)
Creates a new iterator for the specified graph. Iteration will start at the specified start vertex. If the specified start vertex isnull
, Iteration will start at an arbitrary graph vertex.- Parameters:
g
- the graph to be iterated.startVertex
- the vertex iteration to be started.- Throws:
java.lang.IllegalArgumentException
- ifg==null
or does not containstartVertex
-
-
Method Detail
-
hasNext
public boolean hasNext()
- See Also:
Iterator.hasNext()
-
next
public V next()
- See Also:
Iterator.next()
-
isConnectedComponentExhausted
protected abstract boolean isConnectedComponentExhausted()
Returns true if there are no more uniterated vertices in the currently iterated connected component; false otherwise.- Returns:
- true if there are no more uniterated vertices in the currently iterated connected component; false otherwise.
-
encounterVertex
protected abstract void encounterVertex(V vertex, E edge)
Update data structures the first time we see a vertex.- Parameters:
vertex
- the vertex encounterededge
- the edge via which the vertex was encountered, or null if the vertex is a starting point
-
provideNextVertex
protected abstract V provideNextVertex()
Returns the vertex to be returned in the following call to the iteratornext
method.- Returns:
- the next vertex to be returned by this iterator.
-
getSeenData
protected D getSeenData(V vertex)
Access the data stored for a seen vertex.- Parameters:
vertex
- a vertex which has already been seen.- Returns:
- data associated with the seen vertex or
null
if no data was associated with the vertex. Anull
return can also indicate that the vertex was explicitly associated withnull
.
-
isSeenVertex
protected boolean isSeenVertex(V vertex)
Determines whether a vertex has been seen yet by this traversal.- Parameters:
vertex
- vertex in question- Returns:
- true if vertex has already been seen
-
encounterVertexAgain
protected abstract void encounterVertexAgain(V vertex, E edge)
Called whenever we re-encounter a vertex. The default implementation does nothing.- Parameters:
vertex
- the vertex re-encounterededge
- the edge via which the vertex was re-encountered
-
putSeenData
protected D putSeenData(V vertex, D data)
Stores iterator-dependent data for a vertex that has been seen.- Parameters:
vertex
- a vertex which has been seen.data
- data to be associated with the seen vertex.- Returns:
- previous value associated with specified vertex or
null
if no data was associated with the vertex. Anull
return can also indicate that the vertex was explicitly associated withnull
.
-
finishVertex
protected void finishVertex(V vertex)
Called when a vertex has been finished (meaning is dependent on traversal represented by subclass).- Parameters:
vertex
- vertex which has been finished
-
addUnseenChildrenOf
private void addUnseenChildrenOf(V vertex)
-
createEdgeTraversalEvent
private EdgeTraversalEvent<E> createEdgeTraversalEvent(E edge)
-
createVertexTraversalEvent
private VertexTraversalEvent<V> createVertexTraversalEvent(V vertex)
-
encounterStartVertex
private void encounterStartVertex()
-
-