--promote-failures: reroute with the connections that failed moved first

Each round routes every connection that has failed so far ahead of the
rest, which keep their order. The promoted set only grows, so two groups
cannot take turns failing; the best round is kept.

src/freeroute/cli.py

@@ -19,7 +19,7 @@ import argparse
 import sys
 
 from freeroute.dsn.reader import parse_dsn
-from freeroute.route.orders import best_of_orders
+from freeroute.route.orders import best_of_orders, promote_failures
 from freeroute.route.pipeline import (
     build_exact_routing_result,
     build_rooms_routing_result,
@@ -30,8 +30,8 @@ from freeroute.ses import write_ses
 #: which optional flags each engine actually implements. Anything not listed for
 #: an engine is rejected by :func:`_validate` rather than quietly ignored.
 ENGINE_OPTIONS: dict[str, frozenset[str]] = {
-    "grid": frozenset({"rip_up", "max_passes", "seed", "orders"}),
+    "grid": frozenset({"rip_up", "max_passes", "seed", "orders", "promote"}),
-    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders"}),
+    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote"}),
     "room": frozenset({"shove", "pack"}),
 }
 
@@ -44,6 +44,7 @@ _FLAG_NAMES = {
     "max_passes": "-mp/--max-passes",
     "seed": "--seed",
     "orders": "--orders",
+    "promote": "--promote-failures",
 }
 
 
@@ -150,6 +151,13 @@ def build_parser() -> argparse.ArgumentParser:
         help="grid and exact engines: route N connection orders in parallel and keep the "
         "one leaving the fewest connections unrouted (the default order is one of them)",
     )
+    parser.add_argument(
+        "--promote-failures",
+        type=int,
+        metavar="R",
+        help="grid and exact engines: up to R rounds, each routing the connections that "
+        "failed so far first; keeps the best round",
+    )
     parser.add_argument(
         "--jobs",
         type=int,
@@ -177,6 +185,7 @@ def main(argv: list[str] | None = None) -> int:
             ("max_passes", args.max_passes is not None),
             ("seed", args.seed is not None),
             ("orders", args.orders is not None),
+            ("promote", args.promote_failures is not None),
         )
         if asked
     ]
@@ -224,6 +233,14 @@ def main(argv: list[str] | None = None) -> int:
             dsn, layers=layers, shove=args.shove, pack=args.pack,
             edge_clearance_mm=args.edge_clearance,
         )
+    elif args.promote_failures and args.promote_failures > 1:
+        if args.orders:
+            parser.error("--orders and --promote-failures cannot be combined")
+        result, rounds = promote_failures(
+            dsn_text, args.engine, options, rounds=args.promote_failures, seed=args.seed
+        )
+        counts = ", ".join(str(m) for m, _z in rounds)
+        print(f"freeroute: {len(rounds)} rounds, unrouted {counts}; kept the best", file=sys.stderr)
     elif args.orders and args.orders > 1:
         result, kept, tried = best_of_orders(
             dsn_text, args.engine, options, orders=args.orders, seed=args.seed, jobs=args.jobs

src/freeroute/route/exact_router.py

@@ -95,6 +95,7 @@ def route_board_exact(
     resolution: int = 1,
     heuristic_weight: float = 1.0,
     seed: int | None = None,
+    route_first: frozenset | None = None,
 ) -> ExactRouteResult:
     """Route ``board`` orthogonally and verify the result with exact geometry.
 
@@ -124,6 +125,7 @@ def route_board_exact(
         resolution=resolution,
         heuristic_weight=heuristic_weight,
         seed=seed,
+        route_first=route_first,
     )
     edge = 0 if edge_clearance is None else edge_clearance
     outline = board.outline

src/freeroute/route/grid_router.py

@@ -156,11 +156,14 @@ class GridRouter:
         resolution: int = 1,
         heuristic_weight: float = 1.0,
         seed: int | None = None,
+        route_first: frozenset | None = None,
     ) -> None:
         self.board = board
         # None keeps the deterministic order; a seed shuffles which connection
         # routes first, to measure how much a result owes to the order
         self.seed = seed
+        # connections, as (net_no, one end, other end), to route before the rest
+        self.route_first = frozenset(route_first or ())
         # how far (in cells) an escape stub may run to leave a walled-in pin
         self._escape_cells = 12
         self._crowded_cache: dict = {}
@@ -828,6 +831,9 @@ class GridRouter:
         order = list(conns)
         if self.seed is not None:
             random.Random(self.seed).shuffle(order)
+        if self.route_first:
+            # stable: the promoted keep their order among themselves, as do the rest
+            order.sort(key=lambda c: (c.net_no, *_ends_of(c)) not in self.route_first)
         for _ in range(passes):
             changed = False
             for conn in order:
@@ -1060,6 +1066,7 @@ def route_board(
     resolution: int = 1,
     heuristic_weight: float = 1.0,
     seed: int | None = None,
+    route_first: frozenset | None = None,
 ) -> RouteResult:
     """Convenience wrapper: build a :class:`GridRouter` and route the board."""
     router = GridRouter(
@@ -1076,5 +1083,6 @@ def route_board(
         resolution=resolution,
         heuristic_weight=heuristic_weight,
         seed=seed,
+        route_first=route_first,
     )
     return router.route()

src/freeroute/route/orders.py

@@ -65,3 +65,34 @@ def best_of_orders(
     scores = [score(r) for r in results]
     best = min(range(len(seeds)), key=lambda i: (scores[i], i))
     return results[best], seeds[best], list(zip(seeds, scores, strict=True))
+
+
+def promote_failures(
+    dsn_text: str,
+    engine: str,
+    options: dict,
+    *,
+    rounds: int,
+    seed: int | None = None,
+) -> tuple[RoutingResult, list[tuple[int, int]]]:
+    """Route, then route again with every connection that has failed so far
+    moved to the front, keeping the rest in their order. Returns the best
+    round's result and every round's score.
+
+    The promoted set only grows, so a connection that failed once keeps its
+    early place and two groups cannot take turns failing. Stops early when a
+    round routes everything or fails nothing new."""
+    numbers = {n.name: i + 1 for i, n in enumerate(parse_dsn(dsn_text).nets)}
+    first: frozenset = frozenset()
+    best: RoutingResult | None = None
+    scores: list[tuple[int, int]] = []
+    for _ in range(max(int(rounds), 1)):
+        result = route_once(dsn_text, engine, {**options, "route_first": first}, seed)
+        scores.append(score(result))
+        if best is None or scores[-1] < score(best):
+            best = result
+        failed = {(numbers.get(name), a, b) for name, a, b, zone in result.unrouted if not zone}
+        if not failed or failed <= first:
+            break
+        first = first | failed
+    return best, scores

src/freeroute/route/pipeline.py

@@ -81,6 +81,7 @@ def route_dsn_board(
     rip_up: bool = True,
     max_passes: int = 10,
     seed: int | None = None,
+    route_first: frozenset | None = None,
 ) -> tuple[RouteResult, int, list[str]]:
     """Route a parsed :class:`DsnBoard`; return the board-unit result, the scale,
     and the layer names. ``layers`` restricts routing to those signal-layer
@@ -102,6 +103,7 @@ def route_dsn_board(
         rip_up=rip_up,
         max_passes=max_passes,
         seed=seed,
+        route_first=route_first,
     )
     return result, scale, [layer.name for layer in dsn.layers]
 
@@ -143,11 +145,13 @@ def build_routing_result(
     max_passes: int = 10,
     edge_clearance_mm: float | None = None,
     seed: int | None = None,
+    route_first: frozenset | None = None,
 ) -> RoutingResult:
     """Route ``dsn`` (grid track) and convert to a DSN-unit RoutingResult."""
     route, scale, layer_names = route_dsn_board(
         dsn, layers=layers, rip_up=rip_up, max_passes=max_passes,
         edge_clearance_mm=edge_clearance_mm, resolution=resolution, seed=seed,
+        route_first=route_first,
     )
     return _to_routing_result(route, dsn, scale, layer_names)
 
@@ -164,6 +168,7 @@ def route_dsn_board_exact(
     shove: bool = False,
     diagonal: bool = False,
     seed: int | None = None,
+    route_first: frozenset | None = None,
 ) -> tuple[ExactRouteResult, int, list[str]]:
     """Route a parsed :class:`DsnBoard` with the exact-geometry (orthogonal,
     DRC-verified) track; return the exact result, the scale, and layer names.
@@ -189,6 +194,7 @@ def route_dsn_board_exact(
         shove=shove,
         diagonal=diagonal,
         seed=seed,
+        route_first=route_first,
     )
     return exact, scale, [layer.name for layer in dsn.layers]
 
@@ -205,6 +211,7 @@ def build_exact_routing_result(
     max_passes: int = 10,
     edge_clearance_mm: float | None = None,
     seed: int | None = None,
+    route_first: frozenset | None = None,
 ) -> RoutingResult:
     """Route ``dsn`` (exact track) and convert to a DSN-unit RoutingResult."""
     exact, scale, layer_names = route_dsn_board_exact(
@@ -218,6 +225,7 @@ def build_exact_routing_result(
         resolution=resolution,
         heuristic_weight=heuristic_weight,
         seed=seed,
+        route_first=route_first,
     )
     return _to_routing_result(exact.result, dsn, scale, layer_names)
 

tests/route/test_orders.py

@@ -5,7 +5,13 @@ from __future__ import annotations
 from pathlib import Path
 
 from freeroute.cli import main
-from freeroute.route.orders import best_of_orders, candidate_seeds, route_once, score
+from freeroute.route.orders import (
+    best_of_orders,
+    candidate_seeds,
+    promote_failures,
+    route_once,
+    score,
+)
 
 FIXTURES = Path(__file__).resolve().parent.parent / "dsn" / "fixtures"
 # Greedy (no rip-up), the default order strands a net here and seeds 1 to 3 do not.
@@ -42,3 +48,31 @@ def test_cli_orders_writes_the_best_session(tmp_path, capsys):
     assert "tried 3 orders, kept --seed 1" in err
     assert "not routed" not in err
     assert out.read_text().startswith("(session")
+
+
+def test_promoting_the_failed_connection_routes_it():
+    best, rounds = promote_failures(RIPUP, "grid", GREEDY, rounds=3)
+    assert rounds == [(1, 0), (0, 0)]  # stops once nothing fails
+    assert score(best) == (0, 0)
+
+
+def test_nothing_promoted_is_the_plain_order():
+    plain = route_once(RIPUP, "grid", {}, None)
+    empty = route_once(RIPUP, "grid", {"route_first": frozenset()}, None)
+    assert plain == empty
+
+
+def test_cli_promote_failures(tmp_path, capsys):
+    out = tmp_path / "p.ses"
+    rc = main(
+        [
+            str(FIXTURES / "ripup_needed.dsn"),
+            "--no-rip-up",
+            "--promote-failures",
+            "3",
+            "-do",
+            str(out),
+        ]
+    )
+    assert rc == 0
+    assert "2 rounds, unrouted 1, 0" in capsys.readouterr().err

tests/test_cli.py

@@ -156,6 +156,7 @@ def test_cli_supported_combinations_are_accepted(tmp_path):
         "max_passes": ["-mp", "4"],
         "seed": ["--seed", "3"],
         "orders": ["--orders", "2"],
+        "promote": ["--promote-failures", "2"],
     }
     for engine, options in ENGINE_OPTIONS.items():
         for option in options: