Module org.jgrapht.core

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 type

E - the graph edge type

All Implemented Interfaces:

ManyToManyShortestPathsAlgorithm<V,E>, ShortestPathAlgorithm<V,E>

public class DefaultManyToManyShortestPaths<V,E>
extends Object

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 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.

Author:

Semen Chudakov

See Also:

DijkstraManyToManyShortestPaths, CHManyToManyShortestPaths

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

Modifier and Type	Field	Description
protected Graph<V,E>	graph

Constructor Summary

Constructors

Constructor	Description
DefaultManyToManyShortestPaths(Graph<V,E> graph)	Constructs a new instance of the algorithm for a given graph.
DefaultManyToManyShortestPaths(Graph<V,E> graph, Function<Graph<V,E>,ShortestPathAlgorithm<V,E>> function)	Constructs a new instance of the algorithm for a given graph and function.

Method Summary

Modifier and Type	Method	Description
ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E>	getManyToManyPaths(Set<V> sources, Set<V> targets)	Computes shortest paths from all vertices in sources to all vertices in targets.
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, Set<V> targets)	Computes shortest paths tree starting at source and stopping as soon as all of the targets are reached.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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,
                                      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

getManyToManyPaths

public ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E> getManyToManyPaths(Set<V> sources,
                                                                                              Set<V> targets)

Description copied from interface: ManyToManyShortestPathsAlgorithm

Computes shortest paths from all vertices in sources to all vertices in targets.

Parameters:

sources - list of sources vertices

targets - 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 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

getPaths

public ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)

Compute all shortest paths starting from a single source vertex.

Specified by:

getPaths in interface ShortestPathAlgorithm<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 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