org._3pq.jgrapht.traverse
Class ClosestFirstIterator
- GraphIterator, Iterator
public class ClosestFirstIterator
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. Optionally, path length may be
bounded by a finite radius.
addTraversalListener , fireConnectedComponentFinished , fireConnectedComponentStarted , fireEdgeTraversed , fireVertexTraversed , isCrossComponentTraversal , isReuseEvents , remove , removeTraversalListener , setCrossComponentTraversal , setReuseEvents |
ClosestFirstIterator
public ClosestFirstIterator(Graph g)
Creates a new closest-first iterator for the specified graph.
g
- the graph to be iterated.
ClosestFirstIterator
public ClosestFirstIterator(Graph g,
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.
g
- the graph to be iterated.startVertex
- the vertex iteration to be started.
ClosestFirstIterator
public ClosestFirstIterator(Graph g,
Object startVertex,
double radius)
Creates a new radius-bounded closest-first iterator for the specified
graph. Iteration will start at the specified start vertex and will be
limited to the subset of the connected component which includes that
vertex and is reachable via paths of length less than or equal to the
specified radius. The specified start vertex may not be
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.
encounterVertex
protected void encounterVertex(Object vertex,
Edge edge)
- encounterVertex in interface CrossComponentIterator
org._3pq.jgrapht.traverse.CrossComponentIterator.encounterVertex(java.lang.Object,
org._3pq.jgrapht.Edge)
encounterVertexAgain
protected void encounterVertexAgain(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.
- encounterVertexAgain in interface CrossComponentIterator
vertex
- the vertex re-encounterededge
- the edge via which the vertex was re-encountered
getShortestPathLength
public double getShortestPathLength(Object vertex)
Get the length of the shortest path known to the given vertex. If the
vertex has already been visited, then it is truly the shortest path
length; otherwise, it is the best known upper bound.
vertex
- vertex being sought from start vertex
- length of shortest path known, or Double.POSITIVE_INFINITY if no
path found yet
getSpanningTreeEdge
public Edge getSpanningTreeEdge(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.
vertex
- the spanned vertex.
- the spanning tree edge, or null if the vertex either has not
been seen yet or is the start vertex.
setCrossComponentTraversal
public void setCrossComponentTraversal(boolean crossComponentTraversal)
Sets the cross component traversal flag - indicates whether to traverse
the graph across connected components.
- setCrossComponentTraversal in interface AbstractGraphIterator
crossComponentTraversal
- if true
traverses across
connected components.