Package org.jgrapht.alg.shortestpath
Class DijkstraClosestFirstIterator<V,E>
- java.lang.Object
-
- org.jgrapht.alg.shortestpath.DijkstraClosestFirstIterator<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
java.util.Iterator<V>
class DijkstraClosestFirstIterator<V,E> extends java.lang.Object implements java.util.Iterator<V>
A light-weight version of the closest-first iterator for a directed or undirected graphs. 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 weighted path length from a start vertex, i.e. 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.
NOTE: This is an internal iterator for use in shortest paths algorithms. For an iterator that is suitable to return to the users see
ClosestFirstIterator
. This implementation is must faster since it does not support graph traversal listeners nor disconnected components.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) class
DijkstraClosestFirstIterator.DirectedSpecifics
(package private) class
DijkstraClosestFirstIterator.QueueEntry
(package private) class
DijkstraClosestFirstIterator.Specifics
(package private) class
DijkstraClosestFirstIterator.UndirectedSpecifics
-
Field Summary
Fields Modifier and Type Field Description private Graph<V,E>
graph
private FibonacciHeap<DijkstraClosestFirstIterator.QueueEntry>
heap
private double
radius
private java.util.Map<V,FibonacciHeapNode<DijkstraClosestFirstIterator.QueueEntry>>
seen
private V
source
private DijkstraClosestFirstIterator.Specifics
specifics
-
Constructor Summary
Constructors Constructor Description DijkstraClosestFirstIterator(Graph<V,E> graph, V source)
Creates a new iterator for the specified graph.DijkstraClosestFirstIterator(Graph<V,E> graph, V source, double radius)
Creates a new radius-bounded iterator for the specified graph.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description ShortestPathAlgorithm.SingleSourcePaths<V,E>
getPaths()
Return the paths computed by this iterator.boolean
hasNext()
V
next()
private void
updateDistance(V v, E e, double distance)
-
-
-
Field Detail
-
source
private final V source
-
radius
private final double radius
-
specifics
private final DijkstraClosestFirstIterator.Specifics specifics
-
heap
private final FibonacciHeap<DijkstraClosestFirstIterator.QueueEntry> heap
-
seen
private final java.util.Map<V,FibonacciHeapNode<DijkstraClosestFirstIterator.QueueEntry>> seen
-
-
Constructor Detail
-
DijkstraClosestFirstIterator
public DijkstraClosestFirstIterator(Graph<V,E> graph, V source)
Creates a new 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.- Parameters:
graph
- the graph to be iterated.source
- the source vertex
-
DijkstraClosestFirstIterator
public DijkstraClosestFirstIterator(Graph<V,E> graph, V source, double radius)
Creates a new radius-bounded 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 weighted length less than or equal to the specified radius.- Parameters:
graph
- the graphsource
- the source vertexradius
- limit on weighted path length, or Double.POSITIVE_INFINITY for unbounded search
-
-
Method Detail
-
hasNext
public boolean hasNext()
- Specified by:
hasNext
in interfacejava.util.Iterator<V>
-
getPaths
public ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths()
Return the paths computed by this iterator. Only the paths to vertices which are already returned by the iterator will be shortest paths. Additional paths to vertices which are not yet returned (settled) by the iterator might be included with the following properties: the distance will be an upper bound on the actual shortest path and the distance will be inside the radius of the search.- Returns:
- the single source paths
-
-