Uses of Class
org.jgrapht.alg.shortestpath.ContractionHierarchyPrecomputation.ContractionVertex
Packages that use ContractionHierarchyPrecomputation.ContractionVertex
-
Uses of ContractionHierarchyPrecomputation.ContractionVertex in org.jgrapht.alg.shortestpath
Fields in org.jgrapht.alg.shortestpath declared as ContractionHierarchyPrecomputation.ContractionVertexModifier and TypeFieldDescription(package private) ContractionHierarchyPrecomputation.ContractionVertex
<V> CHManyToManyShortestPaths.BucketEntry.target
Start vertex of the backward search during which this entry is created.Fields in org.jgrapht.alg.shortestpath with type parameters of type ContractionHierarchyPrecomputation.ContractionVertexModifier and TypeFieldDescriptionprivate Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl.backwardSearchSpaces
Stores backward search space for each target vertex.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl.backwardSearchSpaces
Stores backward search space for each target vertex.ContractionHierarchyPrecomputation.computeIndependentSetConsumer
Computes independent set during contraction.ContractionHierarchyPrecomputation.computeInitialPrioritiesConsumers
Consumers that perform computation of initial priorities for vertices incontractionGraph
.ContractionHierarchyPrecomputation.computeShortcutsConsumer
Computes shortcuts for a vertex.(package private) Consumer
<ContractionHierarchyPrecomputation.ContractionVertex<V>> ContractionHierarchyPrecomputation.ContractionTask.consumer
Performs needed action with vertices.TransitNodeRoutingPrecomputation.contractedTransitVerticesSet
Set of contracted transit vertices.private final Graph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl.contractionGraph
Contraction hierarchy forgraph
.private Graph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> CHManyToManyShortestPaths.contractionGraph
Contracted version ofgraph
.private Graph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> ContractionHierarchyBidirectionalDijkstra.contractionGraph
Contracted graph, which is used during the queries.private Graph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> ContractionHierarchyPrecomputation.contractionGraph
Graph that stores the computed contraction hierarchy.private Graph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> ContractionHierarchyPrecomputation.ContractionHierarchy.contractionGraph
Graph that stores the computed contraction hierarchy.private Graph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> TransitNodeRoutingPrecomputation.contractionGraph
Contracted graph.private Graph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> TransitNodeRoutingPrecomputation.ContractionHierarchyBFS.contractionGraph
Search graph.private final Map
<V, ContractionHierarchyPrecomputation.ContractionVertex<V>> CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl.contractionMapping
Mapping from original to contracted vertices.CHManyToManyShortestPaths.contractionMapping
Mapping from vertices in the originalgraph
to vertices in thecontractionGraph
.ContractionHierarchyBidirectionalDijkstra.contractionMapping
Mapping from original to contracted vertices.ContractionHierarchyPrecomputation.ContractionHierarchy.contractionMapping
Mapping of the vertices in the original graph to the vertices in the contraction hierarchy graph.ContractionHierarchyPrecomputation.contractionMapping
Mapping of the vertices in the original graph to the vertices in the contraction hierarchy graph.TransitNodeRoutingPrecomputation.contractionMapping
Mapping of vertices in the initial graph to contracted vertices.TransitNodeRoutingPrecomputation.LocalityFilter.contractionMapping
Mapping of vertices in the initial graph to the vertices in the contraction graph.TransitNodeRoutingPrecomputation.contractionVertices
List of contracted vertices.private Map
<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionVertex<V>>, Pair<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl.distanceAndMiddleVertexMap
Stores pair of path weight and middle vertex for each source-target pair.private Map
<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionVertex<V>>, Pair<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl.distanceAndMiddleVertexMap
Stores pair of path weight and middle vertex for each source-target pair.private Map
<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionVertex<V>>, Pair<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl.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>>>> CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl.forwardSearchSpaces
Stores forward search space for each start vertex.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl.forwardSearchSpaces
Stores forward search space for each start vertex.private org.jheaps.AddressableHeap
<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> TransitNodeRoutingPrecomputation.VoronoiDiagramComputation.heap
Priority queue which stores vertices ordered by theirs distances to the corresponding Voronoi cell center.private Supplier
<org.jheaps.AddressableHeap<Double, Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> ContractionHierarchyBidirectionalDijkstra.heapSupplier
Supplier for preferable heap implementation.private Supplier
<org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> TransitNodeRoutingPrecomputation.heapSupplier
Supplier for the preferable heap implementation.ContractionHierarchyPrecomputation.markUpwardEdgesConsumer
Sets value ofisUpward
for the outgoing edges of a vertex.private Graph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> ContractionHierarchyPrecomputation.maskedContractionGraph
The immutable view of thecontractionGraph
which masks already contracted vertices.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> TransitNodeRoutingPrecomputation.VoronoiDiagramComputation.seen
For every vertex added to theheap
stores a corresponding handle.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> TransitNodeRoutingPrecomputation.VoronoiDiagramComputation.seen
For every vertex added to theheap
stores a corresponding handle.private Supplier
<org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> ContractionHierarchyPrecomputation.shortcutsSearchHeapSupplier
Supplier for the preferable heap implementation.TransitNodeRoutingPrecomputation.TransitNodeRouting.transitVertices
Selected transit vertices.ContractionHierarchyPrecomputation.updateNeighboursConsumer
Updates neighbours priorities of a vertex.ContractionHierarchyPrecomputation.vertices
Vertices of thecontractionGraph
.Methods in org.jgrapht.alg.shortestpath that return types with arguments of type ContractionHierarchyPrecomputation.ContractionVertexModifier and TypeMethodDescriptionGraph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> ContractionHierarchyPrecomputation.ContractionHierarchy.getContractionGraph()
Returns contracted graph.ContractionHierarchyPrecomputation.ContractionHierarchy.getContractionMapping()
Returns mapping of the vertices in the original graph to the vertices in the contracted graph.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>> CHManyToManyShortestPaths.getDistanceAndPredecessorMap
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> targets) Computes distance and predecessor map for a single source shortest paths search starting at source and finishing the search as soon as alltargets
are reached.TransitNodeRoutingPrecomputation.TransitNodeRouting.getTransitVertices()
Returns transit vertices of this transit node routing.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> ContractionHierarchyPrecomputation.iterateToSuccessors
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> successors, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore, double radius) Performs Dijkstra search in thegraph
starting at vertexsource
ignoring vertexvertexToIgnore
.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> ContractionHierarchyPrecomputation.iterateToSuccessors
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> successors, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore, double radius) Performs Dijkstra search in thegraph
starting at vertexsource
ignoring vertexvertexToIgnore
.TransitNodeRoutingPrecomputation.selectTopKTransitVertices
(int numberOfTransitVertices) Selects topnumberOfTransitVertices
vertices in the contraction hierarchy as transit vertices.Methods in org.jgrapht.alg.shortestpath with parameters of type ContractionHierarchyPrecomputation.ContractionVertexModifier and TypeMethodDescriptionvoid
TransitNodeRoutingPrecomputation.AccessVerticesBuilder.addBackwardAccessVertices
(ContractionHierarchyPrecomputation.ContractionVertex<V> v, Set<V> vertices) Computes a list of backward access vertices forv
usingvertices
and adds them to thebackwardAccessVertices
.void
TransitNodeRoutingPrecomputation.LocalityFilterBuilder.addBackwardVisitedVoronoiCells
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, Set<Integer> visitedVoronoiCells) AddsvisitedVoronoiCells
to this builder in the backward direction forvertex
.void
TransitNodeRoutingPrecomputation.AccessVerticesBuilder.addForwardAccessVertices
(ContractionHierarchyPrecomputation.ContractionVertex<V> v, Set<V> vertices) Computes a list of forward access vertices forv
usingvertices
and adds them to theforwardAccessVertices
.void
TransitNodeRoutingPrecomputation.LocalityFilterBuilder.addForwardVisitedVoronoiCells
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, Set<Integer> visitedVoronoiCells) AddsvisitedVoronoiCells
to this builder in the forward direction forvertex
.private void
CHManyToManyShortestPaths.backwardSearch
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> target, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractedSources, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, List<CHManyToManyShortestPaths<V, E>.BucketEntry>> bucketsMap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> backwardSearchSpaces, boolean reversed) Performs backward single source shortest paths search incontractionGraph
starting fromtarget
tosources
.private void
ContractionHierarchyPrecomputation.contractVertex
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, int contractionLevel) Contracts providedvertex
and assigns the specifiedcontractionLevel
to it.ContractionHierarchyBidirectionalDijkstra.createPath
(ContractionHierarchyBidirectionalDijkstra.ContractionSearchFrontier<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> forwardFrontier, ContractionHierarchyBidirectionalDijkstra.ContractionSearchFrontier<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> backwardFrontier, double weight, ContractionHierarchyPrecomputation.ContractionVertex<V> source, ContractionHierarchyPrecomputation.ContractionVertex<V> commonVertex, ContractionHierarchyPrecomputation.ContractionVertex<V> sink) Builds shortest unpacked path betweensource
andsink
based on the information provided by search frontiers and common vertex.private void
CHManyToManyShortestPaths.forwardSearch
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractedTargets, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, List<CHManyToManyShortestPaths<V, E>.BucketEntry>> bucketsMap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces, Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionVertex<V>>, Pair<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> middleVerticesMap, boolean reversed) Performs forward search from the givensource
totargets
.TransitNodeRoutingPrecomputation.AccessVertices.getBackwardAccessVertices
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex) Given a contraction vertexvertex
returns its backward access verticesprivate Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>> CHManyToManyShortestPaths.getDistanceAndPredecessorMap
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> targets) Computes distance and predecessor map for a single source shortest paths search starting at source and finishing the search as soon as alltargets
are reached.TransitNodeRoutingPrecomputation.AccessVertices.getForwardAccessVertices
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex) Given a contraction vertexvertex
returns its forward access verticesprivate List
<Pair<ContractionHierarchyPrecomputation.ContractionEdge<E>, ContractionHierarchyPrecomputation.ContractionEdge<E>>> ContractionHierarchyPrecomputation.getShortcuts
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex) Computes shortcuts for vertexvertex
wrt the overlay graph.ContractionHierarchyPrecomputation.getStatistics
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex) Computes statistics for specifiedvertex
.ContractionHierarchyPrecomputation.getVertexData
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, int random) Creates an instance ofVertexData
forvertex
using specified random number and sets itspriority
value.int
TransitNodeRoutingPrecomputation.VoronoiDiagram.getVoronoiCellId
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex) Returns Voronoi cell id which corresponds tovertex
.private boolean
ContractionHierarchyPrecomputation.isGreater
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex1, ContractionHierarchyPrecomputation.ContractionVertex<V> vertex2) Determines if priority ofvertex1
is greater than the priority ofvertex2
.private void
ContractionHierarchyPrecomputation.iterateShortcutEdges
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, BiConsumer<ContractionHierarchyPrecomputation.ContractionEdge<E>, ContractionHierarchyPrecomputation.ContractionEdge<E>> shortcutConsumer) Runs forward shortest-path searches in current overlay graph to find shortcuts ofvertex
.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> ContractionHierarchyPrecomputation.iterateToSuccessors
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> successors, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore, double radius) Performs Dijkstra search in thegraph
starting at vertexsource
ignoring vertexvertexToIgnore
.private void
ContractionHierarchyPrecomputation.relaxNode
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceMap, ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, double vertexDistance, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore) Relaxes outgoing edges ofvertex
ingraph
ignoring successors marked as independent andvertexToIgnore
.TransitNodeRoutingPrecomputation.ContractionHierarchyBFS.runSearch
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex) Runs a forward CH BFS query to calculate access vertices and ids of visited Voronoi cells.private void
ContractionHierarchyPrecomputation.updateDistance
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, double distance, org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceMap) Updates distance forvertex
in theheap
if needed.private void
TransitNodeRoutingPrecomputation.VoronoiDiagramComputation.updateDistance
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, ContractionHierarchyPrecomputation.ContractionVertex<V> predecessor, double distance) If necessary updates distance of thevertex
in theheap
.private void
ContractionHierarchyPrecomputation.updateNeighboursData
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex) Updates neighbours priorities and theirsdepth
values for a givenvertex
.private void
ContractionHierarchyPrecomputation.updatePriority
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, ContractionHierarchyPrecomputation.VertexData data) Updatespriority
field value ofdata
, which corresponds to thevertex
.private boolean
ContractionHierarchyPrecomputation.vertexIsIndependent
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex) Determines if avertex
is independent wrt the overlay graph.private void
TransitNodeRoutingPrecomputation.VoronoiDiagramComputation.visitVertex
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, ContractionHierarchyPrecomputation.ContractionVertex<V> predecessor, double distance) If necessary updates Voronoi cell id and distance invoronoiCells
anddistanceToCenter
for vertex.Method parameters in org.jgrapht.alg.shortestpath with type arguments of type ContractionHierarchyPrecomputation.ContractionVertexModifier and TypeMethodDescriptionprivate void
CHManyToManyShortestPaths.backwardSearch
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> target, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractedSources, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, List<CHManyToManyShortestPaths<V, E>.BucketEntry>> bucketsMap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> backwardSearchSpaces, boolean reversed) Performs backward single source shortest paths search incontractionGraph
starting fromtarget
tosources
.private void
CHManyToManyShortestPaths.backwardSearch
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> target, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractedSources, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, List<CHManyToManyShortestPaths<V, E>.BucketEntry>> bucketsMap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> backwardSearchSpaces, boolean reversed) Performs backward single source shortest paths search incontractionGraph
starting fromtarget
tosources
.private void
CHManyToManyShortestPaths.backwardSearch
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> target, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractedSources, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, List<CHManyToManyShortestPaths<V, E>.BucketEntry>> bucketsMap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> backwardSearchSpaces, boolean reversed) Performs backward single source shortest paths search incontractionGraph
starting fromtarget
tosources
.ContractionHierarchyBidirectionalDijkstra.createPath
(ContractionHierarchyBidirectionalDijkstra.ContractionSearchFrontier<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> forwardFrontier, ContractionHierarchyBidirectionalDijkstra.ContractionSearchFrontier<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> backwardFrontier, double weight, ContractionHierarchyPrecomputation.ContractionVertex<V> source, ContractionHierarchyPrecomputation.ContractionVertex<V> commonVertex, ContractionHierarchyPrecomputation.ContractionVertex<V> sink) Builds shortest unpacked path betweensource
andsink
based on the information provided by search frontiers and common vertex.private void
CHManyToManyShortestPaths.forwardSearch
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractedTargets, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, List<CHManyToManyShortestPaths<V, E>.BucketEntry>> bucketsMap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces, Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionVertex<V>>, Pair<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> middleVerticesMap, boolean reversed) Performs forward search from the givensource
totargets
.private void
CHManyToManyShortestPaths.forwardSearch
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractedTargets, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, List<CHManyToManyShortestPaths<V, E>.BucketEntry>> bucketsMap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces, Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionVertex<V>>, Pair<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> middleVerticesMap, boolean reversed) Performs forward search from the givensource
totargets
.private void
CHManyToManyShortestPaths.forwardSearch
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractedTargets, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, List<CHManyToManyShortestPaths<V, E>.BucketEntry>> bucketsMap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces, Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionVertex<V>>, Pair<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> middleVerticesMap, boolean reversed) Performs forward search from the givensource
totargets
.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>> CHManyToManyShortestPaths.getDistanceAndPredecessorMap
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> targets) Computes distance and predecessor map for a single source shortest paths search starting at source and finishing the search as soon as alltargets
are reached.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>> CHManyToManyShortestPaths.getDistanceAndPredecessorMap
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> targets) Computes distance and predecessor map for a single source shortest paths search starting at source and finishing the search as soon as alltargets
are reached.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> ContractionHierarchyPrecomputation.iterateToSuccessors
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> successors, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore, double radius) Performs Dijkstra search in thegraph
starting at vertexsource
ignoring vertexvertexToIgnore
.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> ContractionHierarchyPrecomputation.iterateToSuccessors
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> successors, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore, double radius) Performs Dijkstra search in thegraph
starting at vertexsource
ignoring vertexvertexToIgnore
.private void
ContractionHierarchyPrecomputation.relaxNode
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceMap, ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, double vertexDistance, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore) Relaxes outgoing edges ofvertex
ingraph
ignoring successors marked as independent andvertexToIgnore
.private void
ContractionHierarchyPrecomputation.relaxNode
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceMap, ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, double vertexDistance, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore) Relaxes outgoing edges ofvertex
ingraph
ignoring successors marked as independent andvertexToIgnore
.private void
ContractionHierarchyPrecomputation.relaxNode
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceMap, ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, double vertexDistance, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore) Relaxes outgoing edges ofvertex
ingraph
ignoring successors marked as independent andvertexToIgnore
.private void
ContractionHierarchyPrecomputation.relaxNode
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceMap, ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, double vertexDistance, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore) Relaxes outgoing edges ofvertex
ingraph
ignoring successors marked as independent andvertexToIgnore
.private void
ContractionHierarchyPrecomputation.submitTasks
(int segmentStart, int segmentEnd, Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>> consumer) Submitstasks
to thecompletionService
setting start and end of the working segment and consumer for themprivate void
ContractionHierarchyPrecomputation.submitTasks
(int segmentStart, int segmentEnd, List<Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>> consumers) Submitstasks
to thecompletionService
setting start and end of the working segment and an individual instance of consumer provided inconsumers
.private void
ContractionHierarchyPrecomputation.updateDistance
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, double distance, org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceMap) Updates distance forvertex
in theheap
if needed.private void
ContractionHierarchyPrecomputation.updateDistance
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, double distance, org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceMap) Updates distance forvertex
in theheap
if needed.private void
ContractionHierarchyPrecomputation.updateDistance
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, double distance, org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceMap) Updates distance forvertex
in theheap
if needed.Constructors in org.jgrapht.alg.shortestpath with parameters of type ContractionHierarchyPrecomputation.ContractionVertexModifierConstructorDescriptionBucketEntry
(ContractionHierarchyPrecomputation.ContractionVertex<V> target, double distance) Constrcuts an instance of an entry for the giventarget
anddistance
.Constructor parameters in org.jgrapht.alg.shortestpath with type arguments of type ContractionHierarchyPrecomputation.ContractionVertexModifierConstructorDescriptionCHManyToManyShortestPathsImpl
(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 givengraph
,contractionGraph
,contractionMapping
,forwardSearchSpaces
,backwardSearchSpaces
anddistanceAndMiddleVertexMap
.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 givengraph
,contractionGraph
,contractionMapping
,forwardSearchSpaces
,backwardSearchSpaces
anddistanceAndMiddleVertexMap
.(package private)
ContractionHierarchy
(Graph<V, E> graph, Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, Map<V, ContractionHierarchyPrecomputation.ContractionVertex<V>> contractionMapping) Constructs a new instance for the givengraph
,contractionGraph
andcontractionMapping
.ContractionHierarchyBFS
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph) Constructs a new instance of the algorithm for the givengraph
.ContractionHierarchyBidirectionalDijkstra
(ContractionHierarchyPrecomputation.ContractionHierarchy<V, E> hierarchy, double radius, Supplier<org.jheaps.AddressableHeap<Double, Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> heapSupplier) Constructs a new instance of the algorithm for the givenhierarchy
,radius
andheapSupplier
.LocalityFilter
(Map<V, ContractionHierarchyPrecomputation.ContractionVertex<V>> contractionMapping, List<Set<Integer>> visitedForwardVoronoiCells, List<Set<Integer>> visitedBackwardVoronoiCells) Constructs a new instance for the givencontractionMapping
,visitedForwardVoronoiCells
andvisitedBackwardVoronoiCells
.TransitNodeRouting
(ContractionHierarchyPrecomputation.ContractionHierarchy<V, E> contractionHierarchy, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> transitVertices, ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V, E> transitVerticesPaths, TransitNodeRoutingPrecomputation.VoronoiDiagram<V> voronoiDiagram, TransitNodeRoutingPrecomputation.AccessVertices<V, E> accessVertices, TransitNodeRoutingPrecomputation.LocalityFilter<V> localityFilter) Constructs a new instance for the givencontractionHierarchy
,transitVertices
,transitVerticesPaths
,voronoiDiagram
,accessVertices
andlocalityFilter
.TransitNodeRoutingPrecomputation
(ContractionHierarchyPrecomputation.ContractionHierarchy<V, E> hierarchy, int numberOfTransitVertices, Supplier<org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> heapSupplier, ThreadPoolExecutor executor) Constructs an instance of the algorithm for a givencontractionHierarchy
,parallelism
,numberOfTransitVertices
,heapSupplier
andexecutor
.