Module org.jgrapht.core

Package org.jgrapht.alg.shortestpath

Class DijkstraManyToManyShortestPaths.DijkstraManyToManyShortestPathsImpl

java.lang.Object

org.jgrapht.alg.interfaces.ManyToManyShortestPathsAlgorithm.BaseManyToManyShortestPathsImpl<V,E>

org.jgrapht.alg.shortestpath.DijkstraManyToManyShortestPaths.DijkstraManyToManyShortestPathsImpl

All Implemented Interfaces:

ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E>

Enclosing class:

DijkstraManyToManyShortestPaths<V,E>

private class DijkstraManyToManyShortestPaths.DijkstraManyToManyShortestPathsImpl
extends ManyToManyShortestPathsAlgorithm.BaseManyToManyShortestPathsImpl<V,E>

Implementation of the ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths. For each source vertex a single source shortest paths tree is stored. It is used to retrieve both actual paths and theirs weights.

Field Summary

Fields

Modifier and Type	Field	Description
private boolean	reversed	Indicates is the search spaces were computed on the edge reversed graph.
private java.util.Map<V,ShortestPathAlgorithm.SingleSourcePaths<V,E>>	searchSpaces	Map from source vertices to corresponding single source shortest path trees.

Constructor Summary

Constructors

Constructor	Description
DijkstraManyToManyShortestPathsImpl(java.util.Set<V> sources, java.util.Set<V> targets, boolean reversed, java.util.Map<V,ShortestPathAlgorithm.SingleSourcePaths<V,E>> searchSpaces)	Constructs an instance of the algorithm for the given sources, targets, reversed and searchSpaces.

Method Summary

Modifier and Type	Method	Description
GraphPath<V,E>	getPath(V source, V target)	Return the path from the source vertex to the target vertex.
double	getWeight(V source, V target)	Return the weight of the path from the source vertex to the targetvertex or Double.POSITIVE_INFINITY if there is no such path in the graph.

Methods inherited from class org.jgrapht.alg.interfaces.ManyToManyShortestPathsAlgorithm.BaseManyToManyShortestPathsImpl

assertCorrectSourceAndTarget, getSources, getTargets

Methods inherited from class java.lang.Object

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

Field Detail

reversed

private boolean reversed

Indicates is the search spaces were computed on the edge reversed graph.

searchSpaces

private final java.util.Map<V,ShortestPathAlgorithm.SingleSourcePaths<V,E>> searchSpaces

Map from source vertices to corresponding single source shortest path trees.

Constructor Detail

DijkstraManyToManyShortestPathsImpl

DijkstraManyToManyShortestPathsImpl(java.util.Set<V> sources,
                                    java.util.Set<V> targets,
                                    boolean reversed,
                                    java.util.Map<V,ShortestPathAlgorithm.SingleSourcePaths<V,E>> searchSpaces)

Constructs an instance of the algorithm for the given sources, targets, reversed and searchSpaces.

Parameters:

sources - source vertices

targets - target vertices

reversed - if search spaces are reversed

searchSpaces - single source shortest paths trees map

Method Detail

getPath

public GraphPath<V,E> getPath(V source,
                                    V target)

Return the path from the source vertex to the target vertex. If no such path exists, null is returned.

Parameters:

source - source vertex

target - target vertex

Returns:

path between source and target or null if no such path exists

getWeight

public double getWeight(V source,
                        V target)

Return the weight of the path from the source vertex to the targetvertex or Double.POSITIVE_INFINITY if there is no such path in the graph. The weight of the path between a vertex and itself is always zero.

Parameters:

source - source vertex

target - target vertex

Returns:

the weight of the path between source and sink vertices or Double.POSITIVE_INFINITY in case no such path exists