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>
private class TransitNodeRoutingPrecomputation.VoronoiDiagramComputation extends java.lang.Object
Algorithm which computes Voronoi diagram for thecontractionGraph
. It usestransitVertices
as Voronoi cells centers. To build the diagram runs a Dijkstra`s algorithm with multiple sources on a reversedgraph
. 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
Fields Modifier and Type Field Description private double[]
distanceToCenter
For every vertex stores distance to the closest Voronoi cell center.private org.jheaps.AddressableHeap<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>
heap
Priority queue which stores vertices ordered by theirs distances to the corresponding Voronoi cell center.private java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>>
seen
For every vertex added to theheap
stores a corresponding handle.private int[]
voronoiCells
For every vertex stores an id of a corresponding Voronoi cell center.
-
Constructor Summary
Constructors Constructor Description VoronoiDiagramComputation()
Constructs a new instance of the algorithm.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) TransitNodeRoutingPrecomputation.VoronoiDiagram<V>
computeVoronoiDiagram()
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 Detail
-
heap
private org.jheaps.AddressableHeap<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>> heap
Priority queue which stores vertices ordered by theirs distances to the corresponding Voronoi cell center.
-
seen
private java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> seen
For every vertex added to theheap
stores a corresponding handle.
-
voronoiCells
private int[] voronoiCells
For every vertex stores an id of a corresponding Voronoi cell center.
-
distanceToCenter
private double[] distanceToCenter
For every vertex stores distance to the closest Voronoi cell center.
-
-
Method Detail
-
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
-
-