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 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<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 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 java.lang.Object

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

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 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 Detail

VoronoiDiagramComputation

VoronoiDiagramComputation()

Constructs a new instance of the algorithm.

Method Detail

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