Module org.jgrapht.core

Package org.jgrapht.alg.shortestpath

Class BaseManyToManyShortestPaths<V,E>

java.lang.Object

org.jgrapht.alg.shortestpath.BaseManyToManyShortestPaths<V,E>

Type Parameters:

V - the graph vertex type

E - 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 java.lang.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

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

Constructor Summary

Constructors

Constructor	Description
BaseManyToManyShortestPaths(Graph<V,E> graph)	Constructs a new instance of the algorithm for a given graph.

Method Summary

Modifier and Type	Method	Description
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 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

Methods inherited from interface org.jgrapht.alg.interfaces.ManyToManyShortestPathsAlgorithm

getManyToManyPaths

Field Detail

graph

protected final Graph<V,E> graph

Constructor Detail

BaseManyToManyShortestPaths

public BaseManyToManyShortestPaths(Graph<V,E> graph)

Constructs a new instance of the algorithm for a given graph.

Parameters:

graph - the graph

Method Detail

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,
                                                                                                     java.util.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