Class DijkstraClosestFirstIterator<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
Iterator<V>
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. This iterator can use a custom heap implementation.
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 faster since it does not support graph traversal listeners nor disconnected
components.
-
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionDijkstraClosestFirstIterator
(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.DijkstraClosestFirstIterator
(Graph<V, E> graph, V source, double radius, Supplier<org.jheaps.AddressableHeap<Double, Pair<V, E>>> heapSupplier) Creates a new radius-bounded iterator for the specified graph.DijkstraClosestFirstIterator
(Graph<V, E> graph, V source, Supplier<org.jheaps.AddressableHeap<Double, Pair<V, E>>> heapSupplier) Creates a new iterator for the specified graph. -
Method Summary
Modifier and TypeMethodDescriptionReturn all paths using the traditional representation of the shortest path tree, which stores for each vertex (a) the distance of the path from the source vertex and (b) the last edge used to reach the vertex from the source vertex.getPaths()
Return the paths computed by this iterator.boolean
hasNext()
next()
private void
updateDistance
(V v, E e, double distance) Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface java.util.Iterator
forEachRemaining, remove
-
Field Details
-
graph
-
source
-
radius
private final double radius -
seen
-
heap
-
-
Constructor Details
-
DijkstraClosestFirstIterator
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. This iterator will use pairing heap as a default heap implementation.- Parameters:
graph
- the graph to be iterated.source
- the source vertex
-
DijkstraClosestFirstIterator
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. This iterator will use pairing heap as a default heap implementation.- Parameters:
graph
- the graphsource
- the source vertexradius
- limit on weighted path length, or Double.POSITIVE_INFINITY for unbounded search
-
DijkstraClosestFirstIterator
public DijkstraClosestFirstIterator(Graph<V, E> graph, V source, Supplier<org.jheaps.AddressableHeap<Double, Pair<V, E>>> heapSupplier) 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. This iterator will use heap supplied by theheapSupplier
- Parameters:
graph
- the graph to be iterated.source
- the source vertexheapSupplier
- supplier of the preferable heap implementation
-
DijkstraClosestFirstIterator
public DijkstraClosestFirstIterator(Graph<V, E> graph, V source, double radius, Supplier<org.jheaps.AddressableHeap<Double, Pair<V, E>>> heapSupplier) 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. This iterator will use the heap supplied byheapSupplier
- Parameters:
graph
- the graphsource
- the source vertexradius
- limit on weighted path length, or Double.POSITIVE_INFINITY for unbounded searchheapSupplier
- supplier of the preferable heap implementation
-
-
Method Details
-
hasNext
public boolean hasNext() -
next
-
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
-
getDistanceAndPredecessorMap
Return all paths using the traditional representation of the shortest path tree, which stores for each vertex (a) the distance of the path from the source vertex and (b) the last edge used to reach the vertex from the source vertex.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:
- a distance and predecessor map
-
updateDistance
-