java.lang.Object
org.jgrapht.alg.shortestpath.BaseManyToManyShortestPaths<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
ManyToManyShortestPathsAlgorithm<V,
,E> ShortestPathAlgorithm<V,
E>
- Direct Known Subclasses:
CHManyToManyShortestPaths
,DefaultManyToManyShortestPaths
,DijkstraManyToManyShortestPaths
abstract class BaseManyToManyShortestPaths<V,E>
extends Object
implements ManyToManyShortestPathsAlgorithm<V,E>
Base class for many-to-many shortest paths algorithms. Currently extended by
CHManyToManyShortestPaths
and DijkstraManyToManyShortestPaths
.-
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> -
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionBaseManyToManyShortestPaths
(Graph<V, E> graph) Constructs a new instance of the algorithm for a given graph. -
Method Summary
Modifier and TypeMethodDescriptionGet a shortest path from a source vertex to a sink vertex.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, Set<V> targets) Computes shortest paths tree starting atsource
and stopping as soon as all of thetargets
are reached.Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface org.jgrapht.alg.interfaces.ManyToManyShortestPathsAlgorithm
getManyToManyPaths
-
Field Details
-
graph
-
-
Constructor Details
-
BaseManyToManyShortestPaths
Constructs a new instance of the algorithm for a given graph.- Parameters:
graph
- the graph
-
-
Method Details
-
getPath
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
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
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, 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
-