PaperlayerView exact revision on arXiv

Source-linked AI summary

Customizable Contraction Hierarchies

Julian Dibbelt, Ben Strasser, Dorothea Wagner

arXiv:1402.0402v5cs.DScs.AI

TL;DR

The paper addresses shortest-path computation when edge weights change often, making metric-dependent preprocessing expensive. It extends Contraction Hierarchies with fast customization based on metric-independent nested dissection orders and evaluates the approach on road and game maps. The reported experiments show that CCH is practicable and efficient across these settings, while practical game hardware and partial-update behavior impose limits.

  • Problem

    Changing edge weights can make metric-dependent preprocessing expensive, motivating a shortest-path method that separates topology preprocessing from metric customization.

  • Method

    CCH uses metric-independent nested dissection orders, introduces direction and traversal weights during customization, and updates customized metrics through triangle-based operations and partial updates.

  • Results

    CCH is reported as a practicable and efficient three-phase extension of Contraction Hierarchies on real-world road graphs and game maps.

  • Takeaways & Limitations

    CCH supports scenarios with frequently changing edge weights while retaining practical shortest-path query performance across road and game settings.

  • Takeaways & Limitations

    On ordinary game hardware, full customization took 1.06s in one experiment and was still too slow for use alongside graphics, networking, and game logic.

Abstract

from arXiv · show

We consider the problem of quickly computing shortest paths in weighted graphs given auxiliary data derived in an expensive preprocessing phase. By adding a fast weight-customization phase, we extend Contraction Hierarchies by Geisberger et al to support the three-phase workflow introduced by Delling et al. Our Customizable Contraction Hierarchies use nested dissection orders as suggested by Bauer et al. We provide an in-depth experimental analysis on large road and game maps that clearly shows that Customizable Contraction Hierarchies are a very practicable solution in scenarios where edge weights often change.

1 Introduction

Customizable Contraction Hierarchies address the difficulty of recomputing metric-dependent preprocessing when edge weights change. They use metric-independent nested dissection orders and support directed traffic by introducing directions and weights during customization.

  • Motivation: Large road networks make Dijkstra impractical for interactive shortest-path queries, motivating preprocessing with auxiliary shortcuts.Road graphs can contain tens of millions of vertices, and a single query may take seconds.
  • Motivation: Metric-dependent CH preprocessing may require expensive recomputation after substantial weight changes such as user preferences or traffic congestion.CRP addresses this with a three-phase workflow whose first phase exploits topology independently of the metric.
  • Applications: Game maps motivate metric independence because topology is fixed while obstacles, player knowledge, and traversable terrain produce evolving metrics.Different players and unit types can require substantially different metrics, making metric-dependent preprocessing difficult.
  • Approach: CCH uses metric-independent nested dissection orders instead of the metric-dependent orders used by earlier CH approaches.The paper positions ND-orders as a central building block for metric-independent CH precomputation.
  • Approach: The preprocessing pipeline drops edge directions and weights initially, then introduces traffic direction and upward or downward weights during customization.One-way streets are represented by setting one of the two directional weights to infinity.
  • Contributions: CCH is reported as feasible and practical, with a preprocessing–query tradeoff comparable to CRP and below-original-CH query times for travel distance.The paper also reports faster metric-independent CH construction and provably minimum-arc CHs from perfect witness searches.

2 Basics

The basics define contraction hierarchies through vertex orders, upward graphs, shortcuts, witness searches, and search spaces. Weighted contraction preserves shortest-path distances while omitting shortcuts that have alternative witnesses.

  • Graph and order definitions: An order assigns every vertex a rank and orients each undirected edge upward toward the higher-ranked endpoint, producing an acyclic upward graph.Upward and downward neighborhoods are defined by whether neighboring vertices have higher or lower rank.
  • Hierarchy structure: The contraction hierarchy is the original graph augmented with shortcuts, while the core graph contracts vertices in increasing rank order.The corresponding upward directed graph supports hierarchical shortest-path search.
  • Contraction: Weighted contraction removes a vertex and adds the minimum necessary shortcuts so distances between all remaining vertex pairs are preserved.Neighbor pairs are processed in increasing distance order, and witness searches determine whether a shortcut is needed.
  • Witness searches: A witness path allows a candidate shortcut to be omitted when it preserves the same shortest-path distance after contraction.The contraction example shows that an existing edge can witness a candidate shortcut.
  • Queries: A shortest path can be represented by an up-down path whose upward and downward parts meet at the highest-ranked vertex.Bidirectional search is restricted to the source and target search spaces.

3 Metric-Dependent Orders

Metric-dependent preprocessing maintains vertex importance in a priority queue and repeatedly contracts the least-important vertex. Importance updates are localized to adjacent vertices when witness searches are perfect.

  • Witness search: The implementation aborts witness searches after finding a shorter path or after each search direction settles at most p vertices, usually with p = 50.This bounded search is an implementation choice for most experiments.
  • Greedy ordering: The preprocessing priority queue initially contains all vertices weighted by their importance I, and the minimum-I vertex is contracted repeatedly.Contracting a vertex changes the importance of other vertices.
  • Greedy ordering: With perfect witness searches, only vertices adjacent to the contracted vertex need importance updates.Limited witness searches can require additional practical handling.

4 Metric-Independent Order

Metric-independent nested dissection orders recursively separate graphs with balanced separators and place separator vertices last. Under separator assumptions, these orders provide constant-factor approximations of optimal metric-independent search spaces.

  • Order construction: Nested dissection recursively splits a graph with balanced separators, assigns separator vertices the highest ranks, and recurses on the two remaining parts.The construction assumes an efficient graph-bisection heuristic is available.
  • Search-space bounds: For graph classes with recursive O(n^α)-size balanced separators, a nested-dissection order has O(n^α) vertices and O(n^2α) arcs in the maximum search space.The same bounds also apply to average search-space sizes through the stated argument.
  • Assumption: The proof relies on the graph class admitting recursive balanced separators of size O(n^α).This is the scope condition under which the stated approximation result applies.
  • Lower bounds: Every contraction order contains a clique of separator size in its chordal supergraph, and this clique lies in the search spaces of at least n/3 vertices.These lower bounds apply to both vertex and arc search-space measures.
  • Guarantee: The nested-dissection order is an O(1)-approximation to the optimal metric-independent hierarchy for average and maximum search spaces, measured in vertices and arcs.The proof matches nested-dissection upper bounds with order-independent lower bounds.

5 Constructing the Contraction Hierarchy

The hierarchy is constructed by contracting vertices in a fixed order while representing the evolving core with a contraction graph. The implementation uses union-find and cache-friendly structures, with total construction time O(ˆmα(n)) and O(m) working space.

  • Performance Analysis: O(ˆmα(n)) total time and O(m) working space are achieved by charging contraction and neighborhood enumeration to upward degrees.The analysis uses Σd(x)=ˆm, while neighborhood cleanup and union-find operations are bounded by inverse-Ackermann factors.
  • The hierarchy G∧π is built by iteratively contracting vertices and adding shortcuts between their neighbors.
  • Contracting Vertices: A contraction graph H stores uncontracted core vertices and an independent set of virtually contracted super vertices, avoiding dynamic shortcut insertion.Contracting all super vertices in H yields the current core graph G′.
  • Contracting Vertices: Neighboring super vertices are merged using linked neighbor lists and union-find, with representatives resolving stale references after rewiring.Merging can create duplicate references, loops, and multi-edges that the enumeration procedure cleans up.
  • Implementation: A hybrid linked-list and adjacency-array representation preserves worst-case performance while improving cache behavior in practice.

6 Enumerating Triangles

Triangle enumeration supports customization and path unpacking by classifying triangles through vertex ranks and intersecting upward or downward neighborhoods. Precomputed triangle adjacency arrays accelerate access, while a hybrid scheme limits space on graphs with many triangles.

  • Triangles are classified as lower, intermediate, or upper according to the relative ranks of their three vertices and the arc under consideration.
  • Basic Triangle Enumeration: Lower, intermediate, and upper triangles can be enumerated by intersecting downward or upward neighborhoods of an arc’s endpoints.Adjacency arrays also store arc IDs for later metric access.
  • Triangle Preprocessing: Triangle adjacency arrays map each arc to participating arc IDs for its triangles, trading space proportional to t for very fast access.Analogous structures support all three triangle types.
  • Hybrid Approach: When t can greatly exceed the number of arcs, precomputing every triangle may be prohibitive; a level threshold therefore trades preprocessing space for enumeration time.In a complete graph, t is Θ(n3) while the number of arcs is Θ(n2).
  • Comparison with CRP: The approach uses less space than micro code and offers macro-code-like space when one-way streets are rare, while providing random access.

7 Customization

Customization extends a metric-independent hierarchy with weights that support shortest-path queries. Basic customization processes lower triangles bottom-up, maintaining respecting weights and enforcing the lower triangle inequality.

  • The customization phase assigns weights to all arcs of the hierarchy after the metric-independent preprocessing phase.
  • Correct CH queries require shortest up-down paths to preserve the input-graph distances, expressed as distI(s,t)=distA(s,t)=distUD(s,t).
  • A respecting metric can be initialized by retaining input weights on original arcs and assigning +∞ to added arcs.
  • Basic Customization: Basic customization scans arcs bottom-up and updates each weight with mC(x,y) ← min{mC(x,y), mC(x,z)+mC(z,y)} over lower triangles.Because z has lower rank, the two contributing weights have already been finalized when (x,y) is processed.
  • Basic Customization: Every respecting metric satisfying the lower triangle inequality is customized, and the algorithm produces such a metric.The lower triangle inequality is mC(x,y) ≤ mC(x,z)+mC(z,y).

7.2 Perfect Customization

Perfect customization refines a customized metric by processing arcs top-down and relaxing through intermediate and upper triangles. It produces shortest-path weights for every hierarchy arc using shortest-path information among upward neighbors.

  • Perfect customization copies mC into mP, then scans arcs in decreasing rank order while relaxing through intermediate and upper triangles.Each relaxation applies mP(x,y) ← min{mP(x,y), mP(x,z)+mP(z,y)}.
  • After perfect customization, mP(x,y) equals the shortest-path distance for every arc (x,y).
  • The upward neighbors of a processed vertex form a clique whose weights encode a complete shortest-path distance table.
  • For an outgoing arc (x,yj), either its current weight is already shortest or a shortest up-down path can use an upward neighbor yk before reaching yj.

7.3 Perfect Witness Search

Perfect customization removes unnecessary CH arcs while preserving shortest up-down paths. A second variant handles multiple shortest paths by exploiting upper and intermediate triangles, with correctness established through height-ordered path transformations.

  • Perfect customization computes a weighted CH with the minimum number of arcs for the fixed contraction order.
  • Variant for Graphs with Unique Shortest Paths: The first variant removes arcs whose customized weight exceeds the corresponding shortest-path distance and is optimal when shortest paths are unique.
  • Variant for Graphs with Unique Shortest Paths: The uniqueness proof preserves a shortest up-down path because every arc on such a path is itself a shortest path and therefore is not removed.
  • Variant for General Graphs: The second variant additionally removes an arc exactly when an upper or intermediate triangle provides an equally short decomposition through a third vertex.
  • Variant for General Graphs: Paths are ordered by lexicographically comparing decreasing sequences of minimum endpoint ranks, called their height.
  • Variant for General Graphs: For every non-up-down path, an up-down path exists that is strictly higher and no longer under the customized metric.

7.4 Parallelization

Both customization algorithms can process arcs within the same level in parallel and synchronize between levels. The perfect variant remains correct despite execution-order-dependent intermediate states because its final shortest-path weights are execution-order independent.

  • Basic customization processes arcs departing within each level in parallel and uses barriers between levels, avoiding locks and atomic operations.
  • Perfect customization uses the same level-parallel structure, although concurrent triangle enumeration can observe different intermediate values.
  • The final perfect-customization result is independent of thread execution order because existing shortest paths are retained rather than modified.

7.5 Directed Graphs

For directed inputs, CCH builds its order and hierarchy from the underlying undirected unweighted graph, then introduces direction through separate upward and downward metrics during customization.

  • The toolchain computes an order from the underlying undirected unweighted graph before building the upward directed CH.
  • Directed customization assigns two weights per hierarchy arc, one for each travel direction.
  • One-way streets are represented by assigning infinity to the forbidden traversal direction.
  • The upward and downward metrics place each input weight according to the relative order of its endpoints, with all other values set to infinity.
  • Basic and perfect customization update both directional metrics using lower, intermediate, and upper triangle relaxations.

7.6 Single Instruction Multiple Data

CCH supports vectorized customization for multiple metrics and partial updates. These techniques improve reuse and responsiveness, but queued updates can temporarily leave distance queries based on outdated data.

  • 7.6 Single Instruction Multiple Data: Each CH arc can store a vector of k weights, allowing multiple metrics to be customized together and triangle enumeration costs to be amortized.
  • 7.6 Single Instruction Multiple Data: Vector storage also packs the two directional metrics needed for directed graphs into a 2-dimensional vector.
  • 7.6 Single Instruction Multiple Data: SIMD customization requires component-wise minimum, saturated addition, and efficient component swapping for directed metrics.
  • 7.7 Partial Updates: Partial updates begin with a queue of changed arcs ordered by level, propagating newly triggered changes until the queue is empty.
  • 7.7 Partial Updates: An updated arc is first checked against lower-triangle bypasses, while intermediate triangles can queue changes to neighboring arcs.
  • 7.7 Partial Updates: A single weight change can trigger few or many subsequent changes depending on the metric and affected network segment.
  • 7.7 Partial Updates: Fixed-time update rounds amortize variable workloads but can leave some distance queries using outdated data while the queue remains nonempty.

8 Distance Query

Distance queries compute shortest up-down paths using bidirectional searches, with pruning and elimination-tree techniques reducing query work while preserving correctness. The elimination-tree approach avoids priority queues and performs well for uniformly random queries.

  • Path reconstruction: Shortest-path distances require only the up-down path, whereas returning original graph edges additionally requires unpacking that path.The paper distinguishes distance computation from reconstructing the edge sequence in the original graph.
  • Basic query: Bidirectional Dijkstra searches from s and t operate on upward and downward metrics, stopping when neither search can improve the best path found.For undirected graphs both searches use the same metric; directed graphs use upward and downward metrics respectively.
  • Stall-on-demand: Stall-on-demand prunes a queued vertex x when d(x) ≥ m(x,y) + d(y) for an outgoing arc, and Theorem 6 establishes this pruning rule.The proof guarantees an unprunable shortest up-down path for every vertex pair.
  • Elimination tree: The elimination-tree query finds the lowest common ancestor of s and t, relaxes search-space arcs from both endpoints toward it, and then completes the remaining intersection search.The search-space regions and arc classes correspond to the dotted, dashed, and solid arcs illustrated in Figure 7.
  • Elimination tree: The elimination-tree query can be combined with perfect witness search while ignoring ancestors outside the pruned search space through infinity-distance checks.Every vertex retained in the pruned search space remains an ancestor, which suffices for query correctness.
  • Performance: Elimination-tree queries avoid priority queues and process every vertex in the search space, yet experiments report lower query times for uniformly random endpoints.The advantage may not extend to nearby endpoints, which are not sampled uniformly in that observation.

9 Experiments

Experiments show that nested-dissection-based CCHs are practical across large road and game graphs, with strong customization and query performance when metrics change. The results also expose important trade-offs among vertex orders, witness-search strategies, and hardware resources.

  • Vertex orders: KaHIP produces better nested-dissection orders than Metis on road graphs, while the two approaches are nearly indistinguishable on the game map.Road separators follow a Θ(3√n)-law on Karlsruhe, whereas Europe has unusual top-level separator structure caused by continental geography and choke points.
  • CH size: At least 1.3 × 10^12 arcs arise when computing Europe’s CH with a metric-dependent order without witness search, compared with 4.2 × 10^7 arcs in the original graph.The experiment was aborted after several days, indicating that metric-dependent orders are impractical in this metric-independent setting.
  • Customization: Below one second is sufficient to customize Europe with all optimizations, including 415 ms amortized and 347 ms non-amortized comparison figures for CRP.On road graphs KaHIP customizes faster, whereas Metis dominates on the game map.
  • Customization: 1.06 s is enough to fully customize TheFrozenSea in an amortized setup without precomputed triangles, using hardware closer to a regular game scenario.The authors caution that the more aggressive optimizations require hardware and memory that may be unavailable in games.
  • Customization: Perfect customization takes about three times as long as basic customization because it enumerates lower, intermediate, and upper triangles instead of only lower triangles.Triangle precomputation is especially problematic in the game scenario because available memory is expected to be lower.

10 Further Instances

Additional experiments evaluate Customizable Contraction Hierarchies on OSM-Europe, further DIMACS road graphs, and diverse game maps. The results indicate broad applicability, while exposing hardware and customization-time constraints in game scenarios.

  • OSM-Europe: OSM-Europe is a detailed European road graph extracted from OpenStreetMap, complementing the standard DIMACS-Europe benchmark.The section compares graph sizes, CH sizes, customization, and query performance across both Europe instances.
  • OSM-Europe: The OSM-Europe experiments report CH sizes, customization performance, and query performance using dedicated tables and random-query sampling.Table 17 samples 10,000 vertices for search-space sizes; Tables 18 and 19 cover customization and queries.
  • Further DIMACS instances: On additional DIMACS road graphs, query times are very similar for one undirected metric and two directed metrics, while customization differs more substantially.The number of relaxed arcs does not depend on whether one or two weights are used; larger customization gaps are associated with executing twice as many instructions per triangle.
  • Further game instances: The additional game instances cover synthetic, StarCraft, WarCraft, Dragon Age, maze, and random-obstacle maps, supporting evaluation across varied graph structures.All additional game instances have fewer vertices than TheFrozenSea.
  • Further game instances: The slowest additional-game CH query takes 316 µs, while full customization is about twice as slow on AcrosstheCape as on TheFrozenSea.The authors attribute the customization difference most likely to slight structural differences and conclude that the technique works across a wide range of maps.

11 Conclusions

The paper concludes that Customizable Contraction Hierarchies provide a practical three-phase shortest-path approach for road and game graphs. It also identifies separator quality, order behavior, hardware limits, and real-world routing constraints as important boundaries and directions for further work.

  • Main conclusion: Customizable Contraction Hierarchies are reported as practicable and efficient on both real-world road graphs and game maps.The conclusion presents this as the outcome of an extensive experimental evaluation.
  • Algorithmic advances: The contraction graph structure accelerates metric-independent CH construction, while customization is essentially triangle enumeration.The paper also gives basic and perfect customization variants, with perfect customization and witness search achieving a provably minimum shortcut count within seconds for a fixed metric-independent order.
  • Algorithmic advances: The elimination-tree query avoids Dijkstra’s priority queue, reducing overhead per visited arc and enabling faster queries.This is presented as a query improvement over previous approaches.
  • Separators and orders: Better separators directly improve customization and query performance, but the paper’s KaHIP-based nested-dissection implementation prioritizes separator quality over computation speed.Separator computation is performed once per graph, so its runtime was not treated as a primary concern.
  • Open questions: Metric-independent orders behave differently from metric-dependent orders: stall-on-demand works with the latter but not the former in the reported experiments.The authors suggest further investigation into this difference and the role of small graph cuts.
  • Scope and future work: The experiments do not fully cover routing constraints such as turn costs, historical traffic, or electric-vehicle range limits.The authors assume applicability to turn-expanded graphs and call for further experimental analysis.
Loading 1402.0402v5…