Class ShortestPath<N>

  • Type Parameters:
    N - the type of graph nodes

    public final class ShortestPath<N>
    extends java.lang.Object
    The Dijkstra shortest path algorithm implemented as a lazy, incrementally-computed stream.

    Compared to traditional imperative implementations, this incremental algorithm supports more flexible use cases that'd otherwise require either full traversal of the graph (which can be large), or copying and tweaking the implementation code for each individual use case.

    For example, without traversing the entire map, find 3 nearest Sushi restaurants:

    
       List<Location> sushiPlaces = shortestPathsFrom(myLocation, Location::locationsAroundMe)
           .map(ShortestPath::to)
           .filter(this::isSushiRestaurant)
           .limit(3)
           .collect(toList());
     
    Or, find all gas stations within 5 miles:
    
       List<Location> gasStations = shortestPathsFrom(myLocation, Location::locationsAroundMe)
           .takeWhile(path -> path.distance() <= 5)
           .map(ShortestPath::to)
           .filter(this::isGasStation)
           .collect(toList());
     

    The streams returned by this class are not safe to run in parallel.

    Since:
    4.0
    • Method Summary

      Modifier and Type Method Description
      double distance()
      Returns the non-negative distance between the starting node and the last node of this path.
      static <N> java.util.stream.Stream<ShortestPath<N>> shortestPathsFrom​(N startNode, java.util.function.Function<? super N,​? extends BiStream<? extends N,​java.lang.Double>> findSuccessors)
      Returns a lazy stream of shortest paths starting from startNode.
      BiStream<N,​java.lang.Double> stream()
      Returns all nodes from the starting node along this path, with the cumulative distances from the starting node up to each node in the stream, respectively.
      N to()
      returns the last node of this path.
      java.lang.String toString()  
      static <N> java.util.stream.Stream<ShortestPath<N>> unweightedShortestPathsFrom​(N startNode, java.util.function.Function<? super N,​? extends java.util.stream.Stream<? extends N>> findSuccessors)
      Returns a lazy stream of unweighted shortest paths starting from startNode.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
    • Method Detail

      • shortestPathsFrom

        public static <N> java.util.stream.Stream<ShortestPath<N>> shortestPathsFrom​(N startNode,
                                                                                     java.util.function.Function<? super N,​? extends BiStream<? extends N,​java.lang.Double>> findSuccessors)
        Returns a lazy stream of shortest paths starting from startNode.

        The findSuccessors function is called on-the-fly to find the successors of the current node. It's is expected to return a BiStream with these direct neighbor nodes and their distances from the passed-in current node, respectively; null or empty stream if there are no successors.

        startNode will correspond to the first element in the returned stream, with distance equal to 0, followed by the next closest node, etc.

        Type Parameters:
        N - The node type. Must implement Object.equals(java.lang.Object) and Object.hashCode().
      • unweightedShortestPathsFrom

        public static <N> java.util.stream.Stream<ShortestPath<N>> unweightedShortestPathsFrom​(N startNode,
                                                                                               java.util.function.Function<? super N,​? extends java.util.stream.Stream<? extends N>> findSuccessors)
        Returns a lazy stream of unweighted shortest paths starting from startNode.

        The findSuccessors function is called on-the-fly to find the successors of the current node. It may return Null or empty stream when there are no successors.

        startNode will correspond to the first element in the returned stream, with distance equal to 0, followed by its successor nodes, etc.

        In the returned stream of ShortestPath objects, distance will be in terms of number of nodes, with the successor nodes of the starting node returning 1.

        Type Parameters:
        N - The node type. Must implement Object.equals(java.lang.Object) and Object.hashCode().
      • to

        public N to()
        returns the last node of this path.
      • stream

        public BiStream<N,​java.lang.Double> stream()
        Returns all nodes from the starting node along this path, with the cumulative distances from the starting node up to each node in the stream, respectively.

        Note that while the stream of ShortestPath objects are lazy, calling this method will incur O(N) cost of copying all the nodes along this path into a stream. So you should only do this for the path you care about. And if you need to access the nodes on this path repetitively, collect the nodes into a collection first.

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object