|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||
java.lang.Objectorg.jgrapht.traverse.AbstractGraphIterator<V,E>
org.jgrapht.traverse.CrossComponentIterator<V,E,FibonacciHeapNode<org.jgrapht.traverse.ClosestFirstIterator.QueueEntry<V,E>>>
org.jgrapht.traverse.ClosestFirstIterator<V,E>
public class ClosestFirstIterator<V,E>
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. Graph.getEdgeWeight(Edge) is summed to calculate path length. Negative edge weights will result in an IllegalArgumentException. Optionally, path length may be bounded by a finite radius.
| Nested Class Summary |
|---|
| Nested classes/interfaces inherited from class org.jgrapht.traverse.CrossComponentIterator |
|---|
CrossComponentIterator.VisitColor |
| Field Summary |
|---|
| Fields inherited from class org.jgrapht.traverse.AbstractGraphIterator |
|---|
nListeners |
| Constructor Summary | |
|---|---|
ClosestFirstIterator(Graph<V,E> g)
Creates a new closest-first iterator for the specified graph. |
|
ClosestFirstIterator(Graph<V,E> g,
V startVertex)
Creates a new closest-first iterator for the specified graph. |
|
ClosestFirstIterator(Graph<V,E> g,
V startVertex,
double radius)
Creates a new radius-bounded closest-first iterator for the specified graph. |
|
| Method Summary | |
|---|---|
protected void |
encounterVertex(V vertex,
E edge)
Update data structures the first time we see a vertex. |
protected void |
encounterVertexAgain(V vertex,
E edge)
Override superclass. |
double |
getShortestPathLength(V vertex)
Get the length of the shortest path known to the given vertex. |
E |
getSpanningTreeEdge(V 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 V |
provideNextVertex()
Returns the vertex to be returned in the following call to the iterator next method. |
void |
setCrossComponentTraversal(boolean crossComponentTraversal)
Sets the cross component traversal flag - indicates whether to traverse the graph across connected components. |
| Methods inherited from class org.jgrapht.traverse.CrossComponentIterator |
|---|
finishVertex, getGraph, getSeenData, hasNext, isSeenVertex, next, putSeenData |
| Methods inherited from class org.jgrapht.traverse.AbstractGraphIterator |
|---|
addTraversalListener, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexFinished, fireVertexTraversed, isCrossComponentTraversal, isReuseEvents, remove, removeTraversalListener, setReuseEvents |
| Methods inherited from class java.lang.Object |
|---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Constructor Detail |
|---|
public ClosestFirstIterator(Graph<V,E> g)
g - the graph to be iterated.
public ClosestFirstIterator(Graph<V,E> g,
V startVertex)
null, iteration will start at an arbitrary vertex
and will not be limited, that is, will be able to traverse all the graph.
g - the graph to be iterated.startVertex - the vertex iteration to be started.
public ClosestFirstIterator(Graph<V,E> g,
V startVertex,
double radius)
null.
g - the graph to be iterated.startVertex - the vertex iteration to be started.radius - limit on path length, or Double.POSITIVE_INFINITY for
unbounded search.| Method Detail |
|---|
public void setCrossComponentTraversal(boolean crossComponentTraversal)
AbstractGraphIterator
setCrossComponentTraversal in class AbstractGraphIterator<V,E>crossComponentTraversal - if true traverses across
connected components.public double getShortestPathLength(V vertex)
vertex - vertex being sought from start vertex
public E getSpanningTreeEdge(V vertex)
vertex - the spanned vertex.
protected boolean isConnectedComponentExhausted()
CrossComponentIterator
isConnectedComponentExhausted in class CrossComponentIterator<V,E,FibonacciHeapNode<org.jgrapht.traverse.ClosestFirstIterator.QueueEntry<V,E>>>CrossComponentIterator.isConnectedComponentExhausted()
protected void encounterVertex(V vertex,
E edge)
CrossComponentIterator
encounterVertex in class CrossComponentIterator<V,E,FibonacciHeapNode<org.jgrapht.traverse.ClosestFirstIterator.QueueEntry<V,E>>>vertex - the vertex encounterededge - the edge via which the vertex was encountered, or null if the
vertex is a starting pointCrossComponentIterator.encounterVertex(Object, Object)
protected void encounterVertexAgain(V vertex,
E edge)
encounterVertexAgain in class CrossComponentIterator<V,E,FibonacciHeapNode<org.jgrapht.traverse.ClosestFirstIterator.QueueEntry<V,E>>>vertex - the vertex re-encounterededge - the edge via which the vertex was re-encounteredprotected V provideNextVertex()
CrossComponentIteratornext method.
provideNextVertex in class CrossComponentIterator<V,E,FibonacciHeapNode<org.jgrapht.traverse.ClosestFirstIterator.QueueEntry<V,E>>>CrossComponentIterator.provideNextVertex()
|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||