Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath
Class TransitNodeRoutingPrecomputation.LocalityFilter<V>
java.lang.Object
org.jgrapht.alg.shortestpath.TransitNodeRoutingPrecomputation.LocalityFilter<V>
- Type Parameters:
V
- graph vertex type
- Enclosing class:
TransitNodeRoutingPrecomputation<V,
E>
Search space based locality filter.
Formally a locality filter is defined as $L : V × V → \{true, false\}$. $L(s, t)$ must be $true$ when no shortest path between $s$ and $t$ contains a transit vertex.
For every vertex in the contractionGraph
stores two sets of visited Voronoi cells by
forward and backward ContractionHierarchyBFS
.
-
Field Summary
FieldsModifier and TypeFieldDescriptionMapping of vertices in the initial graph to the vertices in the contraction graph.For every vertex in the contraction graph stores visited Voronoi cells ids by a backwardContractionHierarchyBFS
.For every vertex in the contraction graph stores visited Voronoi cells ids by a forwardContractionHierarchyBFS
. -
Constructor Summary
ConstructorsConstructorDescriptionLocalityFilter
(Map<V, ContractionHierarchyPrecomputation.ContractionVertex<V>> contractionMapping, List<Set<Integer>> visitedForwardVoronoiCells, List<Set<Integer>> visitedBackwardVoronoiCells) Constructs a new instance for the givencontractionMapping
,visitedForwardVoronoiCells
andvisitedBackwardVoronoiCells
. -
Method Summary
-
Field Details
-
contractionMapping
Mapping of vertices in the initial graph to the vertices in the contraction graph. -
visitedForwardVoronoiCells
For every vertex in the contraction graph stores visited Voronoi cells ids by a forwardContractionHierarchyBFS
. -
visitedBackwardVoronoiCells
For every vertex in the contraction graph stores visited Voronoi cells ids by a backwardContractionHierarchyBFS
.
-
-
Constructor Details
-
LocalityFilter
public LocalityFilter(Map<V, ContractionHierarchyPrecomputation.ContractionVertex<V>> contractionMapping, List<Set<Integer>> visitedForwardVoronoiCells, List<Set<Integer>> visitedBackwardVoronoiCells) Constructs a new instance for the givencontractionMapping
,visitedForwardVoronoiCells
andvisitedBackwardVoronoiCells
.- Parameters:
contractionMapping
- contraction mappingvisitedForwardVoronoiCells
- visited Voronoi cells ids by a forward searchvisitedBackwardVoronoiCells
- visited Voronoi cells ids by a backward search
-
-
Method Details
-
isLocal
Returns $true$ when no shortest paths betweensource
andsink
contains a transit vertex.- Parameters:
source
- source vertexsink
- sink vertex- Returns:
- $true$ iff no shortest paths between
source
andsink
contains a transit vertex
-