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>
private class TransitNodeRoutingPrecomputation.ContractionHierarchyBFS extends java.lang.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 givengraph
.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description Pair<java.util.Set<V>,java.util.Set<java.lang.Integer>>
runSearch(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex)
Runs a forward CH BFS query to calculate access vertices and ids of visited Voronoi cells.
-
-
-
Field Detail
-
contractionGraph
private Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph
Search graph.
-
-
Constructor Detail
-
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 Detail
-
runSearch
public Pair<java.util.Set<V>,java.util.Set<java.lang.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
-
-