Uses of Class
org.jgrapht.alg.shortestpath.ContractionHierarchyPrecomputation.ContractionEdge
Packages that use ContractionHierarchyPrecomputation.ContractionEdge
-
Uses of ContractionHierarchyPrecomputation.ContractionEdge in org.jgrapht.alg.shortestpath
Fields in org.jgrapht.alg.shortestpath with type parameters of type ContractionHierarchyPrecomputation.ContractionEdgeModifier 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.(package private) Pair
<ContractionHierarchyPrecomputation.ContractionEdge<E1>, ContractionHierarchyPrecomputation.ContractionEdge<E1>> ContractionHierarchyPrecomputation.ContractionEdge.bypassedEdges
Pair of edges this edge bypasses in case it is a shortcut.(package private) Pair
<ContractionHierarchyPrecomputation.ContractionEdge<E1>, ContractionHierarchyPrecomputation.ContractionEdge<E1>> ContractionHierarchyPrecomputation.ContractionEdge.bypassedEdges
Pair of edges this edge bypasses in case it is a shortcut.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 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 Supplier
<org.jheaps.AddressableHeap<Double, Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> ContractionHierarchyBidirectionalDijkstra.heapSupplier
Supplier for preferable heap implementation.private Graph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> ContractionHierarchyPrecomputation.maskedContractionGraph
The immutable view of thecontractionGraph
which masks already contracted vertices.private List
<List<Pair<ContractionHierarchyPrecomputation.ContractionEdge<E>, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> ContractionHierarchyPrecomputation.shortcutEdges
Lists of shortcuts that correspond to vertices in thecontractionGraph
.private List
<List<Pair<ContractionHierarchyPrecomputation.ContractionEdge<E>, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> ContractionHierarchyPrecomputation.shortcutEdges
Lists of shortcuts that correspond to vertices in thecontractionGraph
.(package private) List
<Pair<ContractionHierarchyPrecomputation.ContractionEdge<E>, ContractionHierarchyPrecomputation.ContractionEdge<E>>> ContractionHierarchyPrecomputation.ToListConsumer.shortcuts
Resulting list of shortcuts.(package private) List
<Pair<ContractionHierarchyPrecomputation.ContractionEdge<E>, ContractionHierarchyPrecomputation.ContractionEdge<E>>> ContractionHierarchyPrecomputation.ToListConsumer.shortcuts
Resulting list of shortcuts.Methods in org.jgrapht.alg.shortestpath that return types with arguments of type ContractionHierarchyPrecomputation.ContractionEdgeModifier and TypeMethodDescriptionGraph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> ContractionHierarchyPrecomputation.ContractionHierarchy.getContractionGraph()
Returns 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.private List
<Pair<ContractionHierarchyPrecomputation.ContractionEdge<E>, ContractionHierarchyPrecomputation.ContractionEdge<E>>> ContractionHierarchyPrecomputation.getShortcuts
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex) Computes shortcuts for vertexvertex
wrt the overlay graph.private List
<Pair<ContractionHierarchyPrecomputation.ContractionEdge<E>, ContractionHierarchyPrecomputation.ContractionEdge<E>>> ContractionHierarchyPrecomputation.getShortcuts
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex) Computes shortcuts for vertexvertex
wrt the overlay graph.Methods in org.jgrapht.alg.shortestpath with parameters of type ContractionHierarchyPrecomputation.ContractionEdgeModifier and TypeMethodDescriptionvoid
ContractionHierarchyPrecomputation.ToListConsumer.accept
(ContractionHierarchyPrecomputation.ContractionEdge<E> e1, ContractionHierarchyPrecomputation.ContractionEdge<E> e2) void
ContractionHierarchyPrecomputation.ToStatisticsConsumer.accept
(ContractionHierarchyPrecomputation.ContractionEdge<E> e1, ContractionHierarchyPrecomputation.ContractionEdge<E> e2) void
ContractionHierarchyPrecomputation.ContractionHierarchy.unpackBackward
(ContractionHierarchyPrecomputation.ContractionEdge<E> edge, LinkedList<V> vertexList, LinkedList<E> edgeList) Unpacksedge
by recursively going from target to source.void
ContractionHierarchyPrecomputation.ContractionHierarchy.unpackForward
(ContractionHierarchyPrecomputation.ContractionEdge<E> edge, LinkedList<V> vertexList, LinkedList<E> edgeList) Unpacksedge
by recursively going from source to target.Method parameters in org.jgrapht.alg.shortestpath with type arguments of type ContractionHierarchyPrecomputation.ContractionEdgeModifier 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
.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 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 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 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
.Constructor parameters in org.jgrapht.alg.shortestpath with type arguments of type ContractionHierarchyPrecomputation.ContractionEdgeModifierConstructorDescriptionCHManyToManyShortestPathsImpl
(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)
ContractionEdge
(Pair<ContractionHierarchyPrecomputation.ContractionEdge<E1>, ContractionHierarchyPrecomputation.ContractionEdge<E1>> bypassedEdges) Constrcuts a contraction edge for the given pair of bypassed edges.(package private)
ContractionEdge
(Pair<ContractionHierarchyPrecomputation.ContractionEdge<E1>, ContractionHierarchyPrecomputation.ContractionEdge<E1>> bypassedEdges) Constrcuts a contraction edge for the given pair of bypassed edges.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
.