Module org.jgrapht.core

Package org.jgrapht.alg.shortestpath

Class CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl

java.lang.Object

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

org.jgrapht.alg.shortestpath.CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl

All Implemented Interfaces:

ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E>

Enclosing class:

CHManyToManyShortestPaths<V,E>

private class CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl
extends ManyToManyShortestPathsAlgorithm.BaseManyToManyShortestPathsImpl<V,E>

Implementation of ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths for many-to-many shortest paths algorithm based on contraction hierarchy. Paths are stored in form of bidirectional single source shortest paths trees. When a path weight is queried a value that is stored in distanceAndMiddleVertexMap is returned. When an actual paths is required it is constructed by recursively unpacking edges stored in the shortest paths trees corresponding to source and target vertices.

Field Summary

Fields

Modifier and Type	Field	Description
private Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>>	backwardSearchSpaces	Stores backward search space for each target vertex.
private final Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>>	contractionGraph	Contraction hierarchy for graph.
private final Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>>	contractionMapping	Mapping from original to contracted vertices.
private Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionVertex<V>>,Pair<Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>>	distanceAndMiddleVertexMap	Stores pair of path weight and middle vertex for each source-target pair.
private Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>>	forwardSearchSpaces	Stores forward search space for each start vertex.
private final Graph<V,E>	graph	The underlying graph.

Constructor Summary

Constructors

Constructor

Description

CHManyToManyShortestPathsImpl(Graph<V,E> graph, ContractionHierarchyPrecomputation.ContractionHierarchy<V,E> hierarchy, Set<V> sources, Set<V> targets, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> backwardSearchSpaces, Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionVertex<V>>,Pair<Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceAndMiddleVertexMap)

Constructs a new instance for the given graph, contractionGraph, contractionMapping, forwardSearchSpaces, backwardSearchSpaces and distanceAndMiddleVertexMap.

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 Details

graph

private final Graph<V,E> graph

The underlying graph.

contractionGraph

private final Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph

Contraction hierarchy for graph.

contractionMapping

private final Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>> contractionMapping

Mapping from original to contracted vertices.

forwardSearchSpaces

private Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces

Stores forward search space for each start vertex.

backwardSearchSpaces

private Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> backwardSearchSpaces

Stores backward search space for each target vertex.

distanceAndMiddleVertexMap

private Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionVertex<V>>,Pair<Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceAndMiddleVertexMap

Stores pair of path weight and middle vertex for each source-target pair.

Constructor Details

CHManyToManyShortestPathsImpl

public CHManyToManyShortestPathsImpl(Graph<V,E> graph,
 ContractionHierarchyPrecomputation.ContractionHierarchy<V,E> hierarchy,
 Set<V> sources,
 Set<V> targets,
 Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces,
 Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> backwardSearchSpaces,
 Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionVertex<V>>,Pair<Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceAndMiddleVertexMap)

Constructs a new instance for the given graph, contractionGraph, contractionMapping, forwardSearchSpaces, backwardSearchSpaces and distanceAndMiddleVertexMap.

Parameters:

graph - underlying graph.

hierarchy - contraction hierarchy

forwardSearchSpaces - search spaces of source vertices

backwardSearchSpaces - search spaces of target vertices

distanceAndMiddleVertexMap - weights and middle vertices of paths

Method Details

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