Uses of Class
org.jgrapht.alg.shortestpath.ContractionHierarchyPrecomputation.ContractionVertex
-
Packages that use ContractionHierarchyPrecomputation.ContractionVertex Package Description org.jgrapht.alg.shortestpath Shortest-path related algorithms. -
-
Uses of ContractionHierarchyPrecomputation.ContractionVertex in org.jgrapht.alg.shortestpath
Fields in org.jgrapht.alg.shortestpath declared as ContractionHierarchyPrecomputation.ContractionVertex Modifier and Type Field Description (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.ContractionVertex Modifier and Type Field Description private java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>>
CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl. backwardSearchSpaces
Stores backward search space for each target vertex.private java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>>
CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl. backwardSearchSpaces
Stores backward search space for each target vertex.private java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>
ContractionHierarchyPrecomputation. computeIndependentSetConsumer
Computes independent set during contraction.private java.util.List<java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>>
ContractionHierarchyPrecomputation. computeInitialPrioritiesConsumers
Consumers that perform computation of initial priorities for vertices incontractionGraph
.private java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>
ContractionHierarchyPrecomputation. computeShortcutsConsumer
Computes shortcuts for a vertex.(package private) java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>
ContractionHierarchyPrecomputation.ContractionTask. consumer
Performs needed action with vertices.private java.util.Set<ContractionHierarchyPrecomputation.ContractionVertex<V>>
TransitNodeRoutingPrecomputation. contractedTransitVerticesSet
Set of contracted transit vertices.private 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 java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>>
CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl. contractionMapping
Mapping from original to contracted vertices.private java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>>
CHManyToManyShortestPaths. contractionMapping
Mapping from vertices in the originalgraph
to vertices in thecontractionGraph
.private java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>>
ContractionHierarchyBidirectionalDijkstra. contractionMapping
Mapping from original to contracted vertices.private java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>>
ContractionHierarchyPrecomputation.ContractionHierarchy. contractionMapping
Mapping of the vertices in the original graph to the vertices in the contraction hierarchy graph.private java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>>
ContractionHierarchyPrecomputation. contractionMapping
Mapping of the vertices in the original graph to the vertices in the contraction hierarchy graph.private java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>>
TransitNodeRoutingPrecomputation. contractionMapping
Mapping of vertices in the initial graph to contracted vertices.private java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>>
TransitNodeRoutingPrecomputation.LocalityFilter. contractionMapping
Mapping of vertices in the initial graph to the vertices in the contraction graph.private java.util.List<ContractionHierarchyPrecomputation.ContractionVertex<V>>
TransitNodeRoutingPrecomputation. contractionVertices
List of contracted vertices.private java.util.Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionVertex<V>>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>>
CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl. distanceAndMiddleVertexMap
Stores pair of path weight and middle vertex for each source-target pair.private java.util.Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionVertex<V>>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>>
CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl. distanceAndMiddleVertexMap
Stores pair of path weight and middle vertex for each source-target pair.private java.util.Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionVertex<V>>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>>
CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl. distanceAndMiddleVertexMap
Stores pair of path weight and middle vertex for each source-target pair.private java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>>
CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl. forwardSearchSpaces
Stores forward search space for each start vertex.private java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>>
CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl. forwardSearchSpaces
Stores forward search space for each start vertex.private org.jheaps.AddressableHeap<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>
TransitNodeRoutingPrecomputation.VoronoiDiagramComputation. heap
Priority queue which stores vertices ordered by theirs distances to the corresponding Voronoi cell center.private java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>>>>
ContractionHierarchyBidirectionalDijkstra. heapSupplier
Supplier for preferable heap implementation.private java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>>
TransitNodeRoutingPrecomputation. heapSupplier
Supplier for the preferable heap implementation.private java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>
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 java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>>
TransitNodeRoutingPrecomputation.VoronoiDiagramComputation. seen
For every vertex added to theheap
stores a corresponding handle.private java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>>
TransitNodeRoutingPrecomputation.VoronoiDiagramComputation. seen
For every vertex added to theheap
stores a corresponding handle.private java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>>
ContractionHierarchyPrecomputation. shortcutsSearchHeapSupplier
Supplier for the preferable heap implementation.private java.util.Set<ContractionHierarchyPrecomputation.ContractionVertex<V>>
TransitNodeRoutingPrecomputation.TransitNodeRouting. transitVertices
Selected transit vertices.private java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>
ContractionHierarchyPrecomputation. updateNeighboursConsumer
Updates neighbours priorities of a vertex.private java.util.List<ContractionHierarchyPrecomputation.ContractionVertex<V>>
ContractionHierarchyPrecomputation. vertices
Vertices of thecontractionGraph
.Methods in org.jgrapht.alg.shortestpath that return types with arguments of type ContractionHierarchyPrecomputation.ContractionVertex Modifier and Type Method Description Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>>
ContractionHierarchyPrecomputation.ContractionHierarchy. getContractionGraph()
Returns contracted graph.java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>>
ContractionHierarchyPrecomputation.ContractionHierarchy. getContractionMapping()
Returns mapping of the vertices in the original graph to the vertices in the contracted graph.private java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>
CHManyToManyShortestPaths. getDistanceAndPredecessorMap(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, java.util.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.java.util.Set<ContractionHierarchyPrecomputation.ContractionVertex<V>>
TransitNodeRoutingPrecomputation.TransitNodeRouting. getTransitVertices()
Returns transit vertices of this transit node routing.private java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>>
ContractionHierarchyPrecomputation. iterateToSuccessors(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, java.util.Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> successors, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore, double radius)
Performs Dijkstra search in thegraph
starting at vertexsource
ignoring vertexvertexToIgnore
.private java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>>
ContractionHierarchyPrecomputation. iterateToSuccessors(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, java.util.Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> successors, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore, double radius)
Performs Dijkstra search in thegraph
starting at vertexsource
ignoring vertexvertexToIgnore
.private java.util.Set<ContractionHierarchyPrecomputation.ContractionVertex<V>>
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.ContractionVertex Modifier and Type Method Description void
TransitNodeRoutingPrecomputation.AccessVerticesBuilder. addBackwardAccessVertices(ContractionHierarchyPrecomputation.ContractionVertex<V> v, java.util.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, java.util.Set<java.lang.Integer> visitedVoronoiCells)
AddsvisitedVoronoiCells
to this builder in the backward direction forvertex
.void
TransitNodeRoutingPrecomputation.AccessVerticesBuilder. addForwardAccessVertices(ContractionHierarchyPrecomputation.ContractionVertex<V> v, java.util.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, java.util.Set<java.lang.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, java.util.Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractedSources, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.List<CHManyToManyShortestPaths.BucketEntry>> bucketsMap, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.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.private GraphPath<V,E>
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, java.util.Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractedTargets, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.List<CHManyToManyShortestPaths.BucketEntry>> bucketsMap, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces, java.util.Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionVertex<V>>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> middleVerticesMap, boolean reversed)
Performs forward search from the givensource
totargets
.java.util.List<TransitNodeRoutingPrecomputation.AccessVertex<V,E>>
TransitNodeRoutingPrecomputation.AccessVertices. getBackwardAccessVertices(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex)
Given a contraction vertexvertex
returns its backward access verticesprivate java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>
CHManyToManyShortestPaths. getDistanceAndPredecessorMap(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, java.util.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.java.util.List<TransitNodeRoutingPrecomputation.AccessVertex<V,E>>
TransitNodeRoutingPrecomputation.AccessVertices. getForwardAccessVertices(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex)
Given a contraction vertexvertex
returns its forward access verticesprivate java.util.List<Pair<ContractionHierarchyPrecomputation.ContractionEdge<E>,ContractionHierarchyPrecomputation.ContractionEdge<E>>>
ContractionHierarchyPrecomputation. getShortcuts(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex)
Computes shortcuts for vertexvertex
wrt the overlay graph.private ContractionHierarchyPrecomputation.VertexStatistics
ContractionHierarchyPrecomputation. getStatistics(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex)
Computes statistics for specifiedvertex
.private ContractionHierarchyPrecomputation.VertexData
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, java.util.function.BiConsumer<ContractionHierarchyPrecomputation.ContractionEdge<E>,ContractionHierarchyPrecomputation.ContractionEdge<E>> shortcutConsumer)
Runs forward shortest-path searches in current overlay graph to find shortcuts ofvertex
.private java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>>
ContractionHierarchyPrecomputation. iterateToSuccessors(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, java.util.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<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<java.lang.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
.Pair<java.util.Set<V>,java.util.Set<java.lang.Integer>>
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<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<java.lang.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.Constructors in org.jgrapht.alg.shortestpath with parameters of type ContractionHierarchyPrecomputation.ContractionVertex Constructor Description BucketEntry(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.ContractionVertex Constructor Description CHManyToManyShortestPathsImpl(Graph<V,E> graph, ContractionHierarchyPrecomputation.ContractionHierarchy<V,E> hierarchy, java.util.Set<V> sources, java.util.Set<V> targets, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> backwardSearchSpaces, java.util.Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionVertex<V>>,Pair<java.lang.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, java.util.Set<V> sources, java.util.Set<V> targets, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> backwardSearchSpaces, java.util.Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionVertex<V>>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceAndMiddleVertexMap)
Constructs a new instance for the givengraph
,contractionGraph
,contractionMapping
,forwardSearchSpaces
,backwardSearchSpaces
anddistanceAndMiddleVertexMap
.ContractionHierarchy(Graph<V,E> graph, Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, java.util.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, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> heapSupplier)
Constructs a new instance of the algorithm for the givenhierarchy
,radius
andheapSupplier
.LocalityFilter(java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>> contractionMapping, java.util.List<java.util.Set<java.lang.Integer>> visitedForwardVoronoiCells, java.util.List<java.util.Set<java.lang.Integer>> visitedBackwardVoronoiCells)
Constructs a new instance for the givencontractionMapping
,visitedForwardVoronoiCells
andvisitedBackwardVoronoiCells
.TransitNodeRouting(ContractionHierarchyPrecomputation.ContractionHierarchy<V,E> contractionHierarchy, java.util.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, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> heapSupplier, java.util.concurrent.ThreadPoolExecutor executor)
Constructs an instance of the algorithm for a givencontractionHierarchy
,parallelism
,numberOfTransitVertices
,heapSupplier
andexecutor
.
-