Class DefaultManyToManyShortestPaths<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    ManyToManyShortestPathsAlgorithm<V,​E>, ShortestPathAlgorithm<V,​E>

    public class DefaultManyToManyShortestPaths<V,​E>
    extends java.lang.Object
    Naive algorithm for many-to-many shortest paths problem using.

    Time complexity of the algorithm is $O(|S||T|C)$, where $S$ is the set of source vertices, $T$ is the set of target vertices and $C$ is the complexity of the ShortestPathAlgorithm.getPath(Object, Object) method of the provided implementation.

    For every pair of source and target vertices computes a shortest path between them using provided implementation of ShortestPathAlgorithm. By default this implementation uses BidirectionalDijkstraShortestPath. If desired, a different implementation can be provided via the function constructor parameter.

    The computation complexity of the algorithm consists of two main components - the $|S||T|$ multiplier and the $C$ multiplier. This yields two bottlenecks for the algorithm. First of them is the situation when the total number calls to ShortestPathAlgorithm.getPath(Object, Object) is large. The second situation is when the complexity of the individual call to ShortestPathAlgorithm.getPath(Object, Object) takes a lot of time. Therefore the ideal use cases for this algorithm are small graphs or large graphs with low total number of source and target vertices.

    Author:
    Semen Chudakov
    See Also:
    DijkstraManyToManyShortestPaths, CHManyToManyShortestPaths
    • Field Detail

      • graph

        protected final Graph<V,​E> graph
    • Constructor Detail

      • DefaultManyToManyShortestPaths

        public DefaultManyToManyShortestPaths​(Graph<V,​E> graph)
        Constructs a new instance of the algorithm for a given graph. The function is defaulted to returning BidirectionalDijkstraShortestPath.
        Parameters:
        graph - a graph
      • DefaultManyToManyShortestPaths

        public DefaultManyToManyShortestPaths​(Graph<V,​E> graph,
                                              java.util.function.Function<Graph<V,​E>,​ShortestPathAlgorithm<V,​E>> function)
        Constructs a new instance of the algorithm for a given graph and function.
        Parameters:
        graph - a graph
        function - provides implementation of ShortestPathAlgorithm
    • Method Detail

      • getPath

        public GraphPath<V,​E> getPath​(V source,
                                            V sink)
        Get a shortest path from a source vertex to a sink vertex.
        Specified by:
        getPath in interface ShortestPathAlgorithm<V,​E>
        Parameters:
        source - the source vertex
        sink - the target vertex
        Returns:
        a shortest path or null if no path exists
      • getPathWeight

        public double getPathWeight​(V source,
                                    V sink)
        Get the weight of the shortest path from a source vertex to a sink vertex. Returns Double.POSITIVE_INFINITY if no path exists.
        Specified by:
        getPathWeight in interface ShortestPathAlgorithm<V,​E>
        Parameters:
        source - the source vertex
        sink - the sink vertex
        Returns:
        the weight of the shortest path from a source vertex to a sink vertex, or Double.POSITIVE_INFINITY if no path exists
      • getShortestPathsTree

        protected static <V,​E> ShortestPathAlgorithm.SingleSourcePaths<V,​E> getShortestPathsTree​(Graph<V,​E> graph,
                                                                                                             V source,
                                                                                                             java.util.Set<V> targets)
        Computes shortest paths tree starting at source and stopping as soon as all of the targets are reached. Here the DijkstraClosestFirstIterator is used.
        Type Parameters:
        V - the graph vertex type
        E - the graph edge type
        Parameters:
        graph - a graph
        source - source vertex
        targets - target vertices
        Returns:
        shortest paths starting from source and reaching all targets