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
public abstract class CrossComponentIterator<V,E,D> extends AbstractGraphIterator<V,E>
Provides a cross-connected-component traversal functionality for iterator subclasses.- Author:
- Barak Naveh
-
-
Field Summary
-
Fields inherited from class org.jgrapht.traverse.AbstractGraphIterator
crossComponentTraversal, graph, nListeners, reusableEdgeEvent, reusableVertexEvent, reuseEvents
-
-
Constructor Summary
Constructors Constructor Description CrossComponentIterator(Graph<V,E> g)
Creates a new iterator for the specified graph.CrossComponentIterator(Graph<V,E> g, java.lang.Iterable<V> startVertices)
Creates a new iterator for the specified graph.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 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).protected java.util.Iterator<V>
getEntireGraphVertexIterator()
Lazily instantiatesentireGraphVertexIterator
.protected D
getSeenData(V vertex)
Access the data stored for a seen vertex.boolean
hasNext()
protected abstract boolean
isConnectedComponentExhausted()
Returnstrue
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.protected java.util.Set<E>
selectOutgoingEdges(V vertex)
Selects the outgoing edges for a given vertex based on the source vertex and other traversal state.-
Methods inherited from class org.jgrapht.traverse.AbstractGraphIterator
addTraversalListener, createEdgeTraversalEvent, createVertexTraversalEvent, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexFinished, fireVertexTraversed, getGraph, isCrossComponentTraversal, isReuseEvents, remove, removeTraversalListener, setCrossComponentTraversal, setReuseEvents
-
-
-
-
Constructor Detail
-
CrossComponentIterator
public CrossComponentIterator(Graph<V,E> g)
Creates a new iterator for the specified graph.- Parameters:
g
- the graph to be iterated
-
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
-
CrossComponentIterator
public CrossComponentIterator(Graph<V,E> g, java.lang.Iterable<V> startVertices)
Creates a new iterator for the specified graph. Iteration will start at the specified start vertices. If the specified start vertices isnull
, Iteration will start at an arbitrary graph vertex.- Parameters:
g
- the graph to be iterated.startVertices
- the vertices iteration to be started.- Throws:
java.lang.IllegalArgumentException
- ifg==null
or does not containstartVertex
-
-
Method Detail
-
hasNext
public boolean hasNext()
-
next
public V next()
-
getEntireGraphVertexIterator
protected java.util.Iterator<V> getEntireGraphVertexIterator()
Lazily instantiatesentireGraphVertexIterator
.- Returns:
- iterator which provides start vertices for cross-component iteration
-
isConnectedComponentExhausted
protected abstract boolean isConnectedComponentExhausted()
Returnstrue
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
-
selectOutgoingEdges
protected java.util.Set<E> selectOutgoingEdges(V vertex)
Selects the outgoing edges for a given vertex based on the source vertex and other traversal state. The default implementation returns all outgoing edges.- Parameters:
vertex
- vertex in question- Returns:
- set of outgoing edges connected to the vertex
-
-