Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath
Class TransitNodeRoutingPrecomputation.VoronoiDiagramComputation
java.lang.Object
org.jgrapht.alg.shortestpath.TransitNodeRoutingPrecomputation.VoronoiDiagramComputation
- Enclosing class:
TransitNodeRoutingPrecomputation<V,
E>
Algorithm which computes Voronoi diagram for the
contractionGraph
. It uses
transitVertices
as Voronoi cells centers. To build the diagram runs a Dijkstra`s
algorithm with multiple sources on a reversed graph
. Uses Voronoi cells centers as
initial sources. During the computations for each vertex maintains distance to the closest
cell center as well as the id if this cell center.-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate double[]
For every vertex stores distance to the closest Voronoi cell center.private org.jheaps.AddressableHeap
<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> Priority queue which stores vertices ordered by theirs distances to the corresponding Voronoi cell center.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> For every vertex added to theheap
stores a corresponding handle.private int[]
For every vertex stores an id of a corresponding Voronoi cell center. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) TransitNodeRoutingPrecomputation.VoronoiDiagram
<V> Computes Voronoi diagram forgraph
.private void
updateDistance
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, ContractionHierarchyPrecomputation.ContractionVertex<V> predecessor, double distance) If necessary updates distance of thevertex
in theheap
.private void
visitVertex
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, ContractionHierarchyPrecomputation.ContractionVertex<V> predecessor, double distance) If necessary updates Voronoi cell id and distance invoronoiCells
anddistanceToCenter
for vertex.
-
Field Details
-
heap
private org.jheaps.AddressableHeap<Double,ContractionHierarchyPrecomputation.ContractionVertex<V>> heapPriority queue which stores vertices ordered by theirs distances to the corresponding Voronoi cell center. -
seen
private Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<Double, seenContractionHierarchyPrecomputation.ContractionVertex<V>>> For every vertex added to theheap
stores a corresponding handle. -
voronoiCells
private int[] voronoiCellsFor every vertex stores an id of a corresponding Voronoi cell center. -
distanceToCenter
private double[] distanceToCenterFor every vertex stores distance to the closest Voronoi cell center.
-
-
Constructor Details
-
VoronoiDiagramComputation
VoronoiDiagramComputation()Constructs a new instance of the algorithm.
-
-
Method Details
-
computeVoronoiDiagram
TransitNodeRoutingPrecomputation.VoronoiDiagram<V> computeVoronoiDiagram()Computes Voronoi diagram forgraph
.- Returns:
- Voronoi diagram
-
updateDistance
private void updateDistance(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, ContractionHierarchyPrecomputation.ContractionVertex<V> predecessor, double distance) If necessary updates distance of thevertex
in theheap
.- Parameters:
vertex
- vertexpredecessor
- predecessor ofvertex
in the shortest paths treedistance
- distance to vertex
-
visitVertex
private void visitVertex(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, ContractionHierarchyPrecomputation.ContractionVertex<V> predecessor, double distance) If necessary updates Voronoi cell id and distance invoronoiCells
anddistanceToCenter
for vertex.- Parameters:
vertex
- vertexpredecessor
- predecessor ofvertex
in the shortest paths treedistance
- distance to vertex
-