Package com.google.mu.util.graph

Class ShortestPath<N>

java.lang.Object
com.google.mu.util.graph.ShortestPath<N>
Type Parameters:
N - the type of graph nodes
public final class ShortestPath<N> extends 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 Details

    • shortestPathsFrom

      public static <N> Stream<ShortestPath<N>> shortestPathsFrom(N startNode, Function<? super N,? extends BiStream<? extends N,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> Stream<ShortestPath<N>> unweightedShortestPathsFrom(N startNode, Function<? super N,? extends 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.

    • distance

      public double distance()
      Returns the non-negative distance between the starting node and the last node of this path. Zero for the first path in the stream returned by shortestPathsFrom(N, java.util.function.Function<? super N, ? extends com.google.mu.util.stream.BiStream<? extends N, java.lang.Double>>), in which case to() will return the starting node.

    • stream

      public BiStream<N,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 String toString()
      Overrides:
      toString in class Object