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.

    For every pair of source and target vertices computes a shortest path between them and caches the result.

    For each pair of source and target vertex a ShortestPathAlgorithm is used to compute the path. There is a way to provide the preferable implementation of the interface via the function.

    Author:
    Semen Chudakov
    • 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