Class TransitNodeRoutingPrecomputation.ContractionHierarchyBFS

java.lang.Object

org.jgrapht.alg.shortestpath.TransitNodeRoutingPrecomputation.ContractionHierarchyBFS

Enclosing class:

TransitNodeRoutingPrecomputation<V,E>

private class TransitNodeRoutingPrecomputation.ContractionHierarchyBFS
extends Object

BFS algorithm which is used to compute access vertices and locality filter. Runs a CH BFS query over contractionGraph. Does not traverse edges leaving transit vertices. Reports all traversed transit vertices as access vertices. For every traversed non-transit vertex reports a corresponding Voronoi cell id. Those ids are then used to construct locality filter.

Field Summary

Fields

Modifier and Type	Field	Description
private Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>>	contractionGraph	Search graph.

Constructor Summary

Constructors

Constructor	Description
ContractionHierarchyBFS(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph)	Constructs a new instance of the algorithm for the given graph.

Method Summary

Modifier and Type	Method	Description
Pair<Set<V>, Set<Integer>>	runSearch(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex)	Runs a forward CH BFS query to calculate access vertices and ids of visited Voronoi cells.

Methods inherited from class Object

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

Field Details

contractionGraph

private Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph

Search graph.

Constructor Details

ContractionHierarchyBFS

public ContractionHierarchyBFS(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph)

Constructs a new instance of the algorithm for the given graph.

Parameters:

contractionGraph - contraction graph

Method Details

runSearch

public Pair<Set<V>, Set<Integer>> runSearch(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex)

Runs a forward CH BFS query to calculate access vertices and ids of visited Voronoi cells.

Parameters:

vertex - search starting vertex

Returns:

access vertices and visited Voronoi cells ids