Package org.jgrapht.alg.shortestpath
Class DefaultManyToManyShortestPaths<V,E>
- java.lang.Object
-
- 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 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
andtarget
vertex aShortestPathAlgorithm
is used to compute the path. There is a way to provide the preferable implementation of the interface via thefunction
.- Author:
- Semen Chudakov
-
-
Nested Class Summary
-
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>
-
-
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 Static 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
.GraphPath<V,E>
getPath(V source, V sink)
Get a shortest path from a source vertex to a sink vertex.ShortestPathAlgorithm.SingleSourcePaths<V,E>
getPaths(V source)
Compute all shortest paths starting from a single source vertex.double
getPathWeight(V source, V sink)
Get the weight of the shortest path from a source vertex to a sink vertex.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 atsource
and stopping as soon as all of thetargets
are reached.
-
-
-
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 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
-
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 interfaceShortestPathAlgorithm<V,E>
- Parameters:
source
- the source vertexsink
- 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. ReturnsDouble.POSITIVE_INFINITY
if no path exists.- Specified by:
getPathWeight
in interfaceShortestPathAlgorithm<V,E>
- Parameters:
source
- the source vertexsink
- 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
-
getPaths
public ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)
Compute all shortest paths starting from a single source vertex.- Specified by:
getPaths
in interfaceShortestPathAlgorithm<V,E>
- Parameters:
source
- the source vertex- Returns:
- the shortest paths
-
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 atsource
and stopping as soon as all of thetargets
are reached. Here theDijkstraClosestFirstIterator
is used.- Type Parameters:
V
- the graph vertex typeE
- the graph edge type- Parameters:
graph
- a graphsource
- source vertextargets
- target vertices- Returns:
- shortest paths starting from
source
and reaching alltargets
-
-