inire/docs/plans/implementation_plan.md

Implementation Plan

This plan outlines the step-by-step implementation of the inire auto-router. For detailed test cases, refer to Testing Plan.

Phase 1: Core Geometry & Move Generation

Goal: Implement Ports, Polygons, and Component Library with high geometric fidelity.

1. Project Setup: Initialize inire/ structure and pytest configuration. Include hypothesis for property-based testing.
2. geometry.primitives:
   • Port with 1nm snapping.
   • Basic 2D transformations (rotate, translate).
   • Property-Based Tests: Verify transform invariants (e.g., 90^\circ rotation cycles).
3. geometry.components:
   • Straight, Bend90, SBend.
   • Search Grid Snapping: Implement 1µm snapping for expanded ports.
   • Small S-Bends (O < 2R): Logic for parametric generation.
   • Edge Cases: Handle O=2R and L < 1\mu m.
4. Tests:
   • Verify geometric correctness (refer to Testing Plan Section 1).
   • Unit tests for Port snapping and component transformations.

Phase 2: Collision Engine & Cost

Goal: Build the R-Tree wrapper and the analytic cost function.

1. geometry.collision: Implement CollisionEngine.
   • Pre-dilation: Obstacles/Paths dilated by Clearance/2.
   • Safety Zone: Ignore collisions within 2nm of start/end ports.
2. router.danger_map:
   • Implement 1µm pre-computed proximity grid.
   • Optimize for design sizes up to 20x20mm (< 2GB memory).
3. router.cost: Implement CostEvaluator.
   • Bend cost: 10 \times (\text{Manhattan distance between ports}).
   • Integrate R-Tree for strict checks and Danger Map for heuristic.
4. Tests:
   • Verify collision detection with simple overlapping shapes (Testing Plan Section 2.1).
   • Verify Danger Map accuracy and memory footprint (Testing Plan Section 2.2).
   • Post-Route Validator: Implement the independent validate_path utility.

Phase 3: Single-Net A* Search

Goal: Route a single net from A to B with 1nm precision.

1. router.astar: Implement the priority queue loop.
   • State representation: (x_µm, y_µm, theta).
   • Move expansion loop with 1µm grid.
   • Natural S-Bends: Ensure search can find O \ge 2R shifts by combining moves.
   • Look-ahead Snapping: Actively bridge to the 1nm target when in the capture radius (10µm).
2. Heuristic: Manhattan distance h(n) + orientation penalty + Danger Map lookup.
3. Tests:
   • Solve simple maze problems and verify path optimality (Testing Plan Section 3).
   • Verify snap-to-target precision at 1nm resolution.
   • Determinism: Verify same seed = same path.

Phase 4: Multi-Net PathFinder

Goal: Implement the "Negotiated Congestion" loop for multiple nets.

1. router.pathfinder:
   • Sequential routing -> Identify congestion -> Inflate cost -> Reroute.
   • R-Tree Congestion: Store dilated path geometries.
2. Explicit Results: Return RoutingResult objects with is_valid and collisions metadata.
3. Tests:
   • Full multi-net benchmarks (Testing Plan Section 4).
   • Verify rerouting behavior in crowded environments.

Phase 5: Visualization, Benchmarking & Fuzzing

1. utils.visualization: Plot paths using matplotlib. Highlight collisions in red.
2. Benchmarks: Stress test with 50+ nets. Verify performance and node limits (Testing Plan Section 5).
3. Fuzzing: Run A* on randomized layouts to ensure stability.
4. Final Validation: Ensure all is_valid=True results pass the independent validate_path check.