What would you like to Propose?

implementing the Contraction Hierarchies (CH) algorithm, a powerful preprocessing-based technique for extremely fast shortest path queries in large static graphs (e.g., road networks). It builds a node hierarchy and introduces shortcut edges to reduce query times significantly while maintaining exact path lengths.
CH is an optimization over Dijkstra’s algorithm using preprocessing. It first "contracts" nodes by removing them and adding shortcut edges that preserve shortest paths. Each node is assigned a level based on its contraction order. During queries, only upward edges (edges to higher-level nodes) are traversed, enabling extremely fast bidirectional search.

Issue details

1. Preprocessing Phase

• Compute a contraction order of nodes.

• For each node:
  - Remove it from the graph.
  - Add shortcut edges between its neighbors if needed (to preserve shortest path distances).
  - Assign the node a level: nodes contracted earlier get lower levels.

2. Query Phase

• Use bidirectional Dijkstra from source and target.
• Only traverse upward edges in both directions.
• Maintain two distance maps (forward and backward).
• Combine the two searches at meeting nodes to compute the final shortest path.

3. Data Structures

• Graph class with support for forward and backward adjacency lists.
• Node class with ID and level.
• Edge class with weights, direction, and possibly a "shortcut flag".
• Use Java’s PriorityQueue for efficient query processing.

Additional Information

This proposal is just one suggested structure. You're welcome to adjust the implementation details, class design, or performance strategies. The core goal is to provide a clean and educational CH implementation in pure Java for the community.

More Details on CH:

• https://en.wikipedia.org/wiki/Contraction_hierarchies
• https://jeansebastien-gonsette.medium.com/routing-faster-than-dijkstra-thanks-to-contraction-hierarchies-232302345921
• https://www.youtube.com/watch?v=5DdaoQeTis4
• https://www.youtube.com/watch?v=FXYs-fg1y8s