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.

For every pair of source and target vertices computes a shortest path between them and caches the result.

For each pair of source and target vertex a ShortestPathAlgorithm is used to compute the path. There is a way to provide the preferable implementation of the interface via the function.

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>

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