Class DefaultManyToManyShortestPaths<V,E>
- java.lang.Object
-
- org.jgrapht.alg.shortestpath.BaseManyToManyShortestPaths<V,E>
-
- org.jgrapht.alg.shortestpath.DefaultManyToManyShortestPaths<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
ManyToManyShortestPathsAlgorithm<V,E>
,ShortestPathAlgorithm<V,E>
public class DefaultManyToManyShortestPaths<V,E> extends BaseManyToManyShortestPaths<V,E>
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
andtarget
vertices computes a shortest path between them using provided implementation ofShortestPathAlgorithm
. By default this implementation usesBidirectionalDijkstraShortestPath
. If desired, a different implementation can be provided via thefunction
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 toShortestPathAlgorithm.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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
DefaultManyToManyShortestPaths.DefaultManyToManyShortestPathsImpl<V,E>
Implementation of theManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths
.-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ManyToManyShortestPathsAlgorithm
ManyToManyShortestPathsAlgorithm.BaseManyToManyShortestPathsImpl<V,E>, ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E>
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,E>
-
-
Field Summary
Fields Modifier and Type Field Description private java.util.function.Function<Graph<V,E>,ShortestPathAlgorithm<V,E>>
function
Provides implementation ofShortestPathAlgorithm
for a given graph.-
Fields inherited from class org.jgrapht.alg.shortestpath.BaseManyToManyShortestPaths
graph
-
-
Constructor Summary
Constructors Constructor Description DefaultManyToManyShortestPaths(Graph<V,E> graph)
Constructs a new instance of the algorithm for a givengraph
.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 givengraph
andfunction
.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E>
getManyToManyPaths(java.util.Set<V> sources, java.util.Set<V> targets)
Computes shortest paths from all vertices insources
to all vertices intargets
.-
Methods inherited from class org.jgrapht.alg.shortestpath.BaseManyToManyShortestPaths
getPath, getPaths, getPathWeight, getShortestPathsTree
-
-
-
-
Field Detail
-
function
private final java.util.function.Function<Graph<V,E>,ShortestPathAlgorithm<V,E>> function
Provides implementation ofShortestPathAlgorithm
for a given graph.
-
-
Constructor Detail
-
DefaultManyToManyShortestPaths
public DefaultManyToManyShortestPaths(Graph<V,E> graph)
Constructs a new instance of the algorithm for a givengraph
. Thefunction
is defaulted to returningBidirectionalDijkstraShortestPath
.- 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 givengraph
andfunction
.- Parameters:
graph
- a graphfunction
- provides implementation ofShortestPathAlgorithm
-
-
Method Detail
-
getManyToManyPaths
public ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E> getManyToManyPaths(java.util.Set<V> sources, java.util.Set<V> targets)
Description copied from interface:ManyToManyShortestPathsAlgorithm
Computes shortest paths from all vertices insources
to all vertices intargets
.- Parameters:
sources
- list of sources verticestargets
- list of target vertices- Returns:
- computed shortest paths
-
-