Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath

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

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

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

    • 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 between source and sink contains a transit vertex.

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • 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 forward ContractionHierarchyBFS.

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

    • 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 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 Detail

      • 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