Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath
Class TransitNodeRoutingPrecomputation.ContractionHierarchyBFS
java.lang.Object
org.jgrapht.alg.shortestpath.TransitNodeRoutingPrecomputation.ContractionHierarchyBFS
- Enclosing class:
TransitNodeRoutingPrecomputation<V,
E>
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
FieldsModifier and TypeFieldDescriptionprivate Graph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> Search graph. -
Constructor Summary
ConstructorsConstructorDescriptionContractionHierarchyBFS
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph) Constructs a new instance of the algorithm for the givengraph
. -
Method Summary
-
Field Details
-
contractionGraph
private Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraphSearch graph.
-
-
Constructor Details
-
ContractionHierarchyBFS
public ContractionHierarchyBFS(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph) Constructs a new instance of the algorithm for the givengraph
.- 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
-