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>
public static class TransitNodeRoutingPrecomputation.LocalityFilter<V> extends java.lang.Object
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 backwardContractionHierarchyBFS
.
-
-
Field Summary
Fields Modifier and Type Field Description private java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>>
contractionMapping
Mapping of vertices in the initial graph to the vertices in the contraction graph.private java.util.List<java.util.Set<java.lang.Integer>>
visitedBackwardVoronoiCells
For every vertex in the contraction graph stores visited Voronoi cells ids by a backwardContractionHierarchyBFS
.private java.util.List<java.util.Set<java.lang.Integer>>
visitedForwardVoronoiCells
For every vertex in the contraction graph stores visited Voronoi cells ids by a forwardContractionHierarchyBFS
.
-
Constructor Summary
Constructors Constructor Description LocalityFilter(java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>> contractionMapping, java.util.List<java.util.Set<java.lang.Integer>> visitedForwardVoronoiCells, java.util.List<java.util.Set<java.lang.Integer>> visitedBackwardVoronoiCells)
Constructs a new instance for the givencontractionMapping
,visitedForwardVoronoiCells
andvisitedBackwardVoronoiCells
.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
isLocal(V source, V sink)
Returns $true$ when no shortest paths betweensource
andsink
contains a transit vertex.
-
-
-
Field Detail
-
contractionMapping
private java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>> contractionMapping
Mapping of vertices in the initial graph to the vertices in the contraction graph.
-
visitedForwardVoronoiCells
private java.util.List<java.util.Set<java.lang.Integer>> visitedForwardVoronoiCells
For every vertex in the contraction graph stores visited Voronoi cells ids by a forwardContractionHierarchyBFS
.
-
visitedBackwardVoronoiCells
private java.util.List<java.util.Set<java.lang.Integer>> visitedBackwardVoronoiCells
For every vertex in the contraction graph stores visited Voronoi cells ids by a backwardContractionHierarchyBFS
.
-
-
Constructor Detail
-
LocalityFilter
public LocalityFilter(java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>> contractionMapping, java.util.List<java.util.Set<java.lang.Integer>> visitedForwardVoronoiCells, java.util.List<java.util.Set<java.lang.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
-
-