Class TransitNodeRoutingPrecomputation.VoronoiDiagramComputation

java.lang.Object

org.jgrapht.alg.shortestpath.TransitNodeRoutingPrecomputation.VoronoiDiagramComputation

Enclosing class:

TransitNodeRoutingPrecomputation<V,E>

private class TransitNodeRoutingPrecomputation.VoronoiDiagramComputation
extends Object

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

Fields

Modifier and Type	Field	Description
private double[]	distanceToCenter	For every vertex stores distance to the closest Voronoi cell center.
private org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>	heap	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>>>	seen	For every vertex added to the heap 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

Modifier and Type	Method	Description
(package private) TransitNodeRoutingPrecomputation.VoronoiDiagram<V>	computeVoronoiDiagram()	Computes Voronoi diagram for graph.
private void	updateDistance(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, ContractionHierarchyPrecomputation.ContractionVertex<V> predecessor, double distance)	If necessary updates distance of the vertex in the heap.
private void	visitVertex(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, ContractionHierarchyPrecomputation.ContractionVertex<V> predecessor, double distance)	If necessary updates Voronoi cell id and distance in voronoiCells and distanceToCenter for vertex.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

heap

private org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> heap

Priority 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, ContractionHierarchyPrecomputation.ContractionVertex<V>>> seen

For every vertex added to the heap 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.

Constructor Details

VoronoiDiagramComputation

VoronoiDiagramComputation()

Constructs a new instance of the algorithm.

Method Details

computeVoronoiDiagram

TransitNodeRoutingPrecomputation.VoronoiDiagram<V> computeVoronoiDiagram()

Computes Voronoi diagram for graph.

Returns:

Voronoi diagram

updateDistance

private void updateDistance(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex,
 ContractionHierarchyPrecomputation.ContractionVertex<V> predecessor,
 double distance)

If necessary updates distance of the vertex in the heap.

Parameters:

vertex - vertex

predecessor - predecessor of vertex in the shortest paths tree

distance - 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 in voronoiCells and distanceToCenter for vertex.

Parameters:

vertex - vertex

predecessor - predecessor of vertex in the shortest paths tree

distance - distance to vertex