Class DefaultManyToManyShortestPaths<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
ManyToManyShortestPathsAlgorithm<V,
,E> ShortestPathAlgorithm<V,
E>
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.
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) static class
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
FieldsModifier and TypeFieldDescriptionProvides implementation ofShortestPathAlgorithm
for a given graph.Fields inherited from class org.jgrapht.alg.shortestpath.BaseManyToManyShortestPaths
graph
-
Constructor Summary
ConstructorsConstructorDescriptionDefaultManyToManyShortestPaths
(Graph<V, E> graph) Constructs a new instance of the algorithm for a givengraph
.DefaultManyToManyShortestPaths
(Graph<V, E> graph, Function<Graph<V, E>, ShortestPathAlgorithm<V, E>> function) Constructs a new instance of the algorithm for a givengraph
andfunction
. -
Method Summary
Modifier and TypeMethodDescriptiongetManyToManyPaths
(Set<V> sources, 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 Details
-
function
Provides implementation ofShortestPathAlgorithm
for a given graph.
-
-
Constructor Details
-
DefaultManyToManyShortestPaths
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, 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 Details
-
getManyToManyPaths
public ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E> getManyToManyPaths(Set<V> sources, 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
-