org._3pq.jgrapht.traverse
Class ClosestFirstIterator
java.lang.Object
|
+--org._3pq.jgrapht.traverse.AbstractGraphIterator
|
+--org._3pq.jgrapht.traverse.CrossComponentIterator
|
+--org._3pq.jgrapht.traverse.ClosestFirstIterator
- All Implemented Interfaces:
- GraphIterator, java.util.Iterator
- public class ClosestFirstIterator
- extends CrossComponentIterator
A closest-first iterator for a directed or undirected graph. For this
iterator to work correctly the graph must not be modified during iteration.
Currently there are no means to ensure that, nor to fail-fast. The results
of such modifications are undefined.
The metric for closest here is the path length from a start vertex.
Edge.getWeight() is summed to calculate path length. Negative edge weights
will result in an IllegalArgumentException.
- Since:
- Sep 2, 2003
- Author:
- John V. Sichi
Method Summary |
protected void |
encounterVertex(java.lang.Object vertex,
Edge edge)
Update data structures the first time we see a vertex. |
protected void |
encounterVertexAgain(java.lang.Object vertex,
Edge edge)
Override superclass. |
Edge |
getSpanningTreeEdge(java.lang.Object vertex)
Get the spanning tree edge reaching a vertex which has been seen already
in this traversal. |
protected boolean |
isConnectedComponentExhausted()
Returns true if there are no more uniterated vertices in the
currently iterated connected component; false otherwise. |
protected java.lang.Object |
provideNextVertex()
Returns the vertex to be returned in the following call to the iterator
next method. |
Methods inherited from class org._3pq.jgrapht.traverse.AbstractGraphIterator |
addTraversalListener, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexTraversed, isCrossComponentTraversal, isReuseEvents, remove, removeTraversalListener, setCrossComponentTraversal, setReuseEvents |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
ClosestFirstIterator
public ClosestFirstIterator(Graph g)
- Creates a new closest-first iterator for the specified graph.
- Parameters:
g
- the graph to be iterated.
ClosestFirstIterator
public ClosestFirstIterator(Graph g,
java.lang.Object startVertex)
- Creates a new closest-first iterator for the specified graph. Iteration
will start at the specified start vertex and will be limited to the
connected component that includes that vertex. If the specified start
vertex is
null
, iteration will start at an arbitrary
vertex and will not be limited, that is, will be able to traverse all
the graph.
- Parameters:
g
- the graph to be iterated.startVertex
- the vertex iteration to be started.
getSpanningTreeEdge
public Edge getSpanningTreeEdge(java.lang.Object vertex)
- Get the spanning tree edge reaching a vertex which has been seen already
in this traversal. This edge is the last link in the shortest known
path between the start vertex and the requested vertex. If the vertex
has already been visited, then it is truly the minimum spanning tree
edge; otherwise, it is the best candidate seen so far.
- Parameters:
vertex
- the spanned vertex.- Returns:
- the spanning tree edge, or null if the vertex either has not
been seen yet or is the start vertex.
isConnectedComponentExhausted
protected boolean isConnectedComponentExhausted()
- Description copied from class:
CrossComponentIterator
- Returns true if there are no more uniterated vertices in the
currently iterated connected component; false otherwise.
- Overrides:
isConnectedComponentExhausted
in class CrossComponentIterator
- See Also:
CrossComponentIterator.isConnectedComponentExhausted()
encounterVertex
protected void encounterVertex(java.lang.Object vertex,
Edge edge)
- Description copied from class:
CrossComponentIterator
- Update data structures the first time we see a vertex.
- Overrides:
encounterVertex
in class CrossComponentIterator
- See Also:
CrossComponentIterator.encounterVertex(java.lang.Object,
org._3pq.jgrapht.Edge)
encounterVertexAgain
protected void encounterVertexAgain(java.lang.Object vertex,
Edge edge)
- Override superclass. When we see a vertex again, we need to see if the
new edge provides a shorter path than the old edge.
- Overrides:
encounterVertexAgain
in class CrossComponentIterator
- Parameters:
vertex
- the vertex re-encounterededge
- the edge via which the vertex was re-encountered
provideNextVertex
protected java.lang.Object provideNextVertex()
- Description copied from class:
CrossComponentIterator
- Returns the vertex to be returned in the following call to the iterator
next
method.
- Overrides:
provideNextVertex
in class CrossComponentIterator
- See Also:
CrossComponentIterator.provideNextVertex()