Class DijkstraClosestFirstIterator<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - 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. 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 
      Modifier and Type Field Description
      private Graph<V,​E> graph  
      private org.jheaps.AddressableHeap<java.lang.Double,​Pair<V,​E>> heap  
      private double radius  
      private java.util.Map<V,​org.jheaps.AddressableHeap.Handle<java.lang.Double,​Pair<V,​E>>> seen  
      private V source  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.Map<V,​Pair<java.lang.Double,​E>> 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.
      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)  
      • 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 Detail

      • graph

        private final Graph<V,​E> graph
      • source

        private final V source
      • radius

        private final double radius
      • seen

        private final java.util.Map<V,​org.jheaps.AddressableHeap.Handle<java.lang.Double,​Pair<V,​E>>> seen
      • heap

        private org.jheaps.AddressableHeap<java.lang.Double,​Pair<V,​E>> heap
    • 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. This iterator will use pairing heap as a default heap implementation.
        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. This iterator will use pairing heap as a default heap implementation.
        Parameters:
        graph - the graph
        source - the source vertex
        radius - limit on weighted path length, or Double.POSITIVE_INFINITY for unbounded search
      • DijkstraClosestFirstIterator

        public DijkstraClosestFirstIterator​(Graph<V,​E> graph,
                                            V source,
                                            java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.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 the heapSupplier
        Parameters:
        graph - the graph to be iterated.
        source - the source vertex
        heapSupplier - supplier of the preferable heap implementation
      • DijkstraClosestFirstIterator

        public DijkstraClosestFirstIterator​(Graph<V,​E> graph,
                                            V source,
                                            double radius,
                                            java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.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 by heapSupplier
        Parameters:
        graph - the graph
        source - the source vertex
        radius - limit on weighted path length, or Double.POSITIVE_INFINITY for unbounded search
        heapSupplier - supplier of the preferable heap implementation
    • Method Detail

      • hasNext

        public boolean hasNext()
        Specified by:
        hasNext in interface java.util.Iterator<V>
      • next

        public V next()
        Specified by:
        next in interface java.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
      • getDistanceAndPredecessorMap

        public java.util.Map<V,​Pair<java.lang.Double,​E>> 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

        private void updateDistance​(V v,
                                    E e,
                                    double distance)