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 Details

    • 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