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 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 backward ContractionHierarchyBFS.

Field Summary

Fields

Modifier and Type	Field	Description
private Map<V, ContractionHierarchyPrecomputation.ContractionVertex<V>>	contractionMapping	Mapping of vertices in the initial graph to the vertices in the contraction graph.
private List<Set<Integer>>	visitedBackwardVoronoiCells	For every vertex in the contraction graph stores visited Voronoi cells ids by a backward ContractionHierarchyBFS.
private List<Set<Integer>>	visitedForwardVoronoiCells	For every vertex in the contraction graph stores visited Voronoi cells ids by a forward ContractionHierarchyBFS.

Constructor Summary

Constructors

Constructor	Description
LocalityFilter(Map<V, ContractionHierarchyPrecomputation.ContractionVertex<V>> contractionMapping, List<Set<Integer>> visitedForwardVoronoiCells, List<Set<Integer>> visitedBackwardVoronoiCells)	Constructs a new instance for the given contractionMapping, visitedForwardVoronoiCells and visitedBackwardVoronoiCells.

Method Summary

Modifier and Type	Method	Description
boolean	isLocal(V source, V sink)	Returns $true$ when no shortest paths between source and sink contains a transit vertex.

Methods inherited from class Object

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

Field Details

contractionMapping

private Map<V, ContractionHierarchyPrecomputation.ContractionVertex<V>> contractionMapping

Mapping of vertices in the initial graph to the vertices in the contraction graph.

visitedForwardVoronoiCells

private List<Set<Integer>> visitedForwardVoronoiCells

For every vertex in the contraction graph stores visited Voronoi cells ids by a forward ContractionHierarchyBFS.

visitedBackwardVoronoiCells

private List<Set<Integer>> visitedBackwardVoronoiCells

For every vertex in the contraction graph stores visited Voronoi cells ids by a backward ContractionHierarchyBFS.

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 given contractionMapping, visitedForwardVoronoiCells and visitedBackwardVoronoiCells.

Parameters:

contractionMapping - contraction mapping

visitedForwardVoronoiCells - visited Voronoi cells ids by a forward search

visitedBackwardVoronoiCells - visited Voronoi cells ids by a backward search

Method Details

isLocal

public boolean isLocal(V source,
 V sink)

Returns $true$ when no shortest paths between source and sink contains a transit vertex.

Parameters:

source - source vertex

sink - sink vertex

Returns:

$true$ iff no shortest paths between source and sink contains a transit vertex