diagnose.py: --negotiate, as the router

Every connection is routed N times on the empty board, where routes may
share cells at a price that doubles each round for every other net on a
cell, and a cell that stays shared gains history. The real routing then
pays that history on free cells, so the first routes stop taking the space
later routes (a fine-pitch part's escapes) have no way round. Off by
default.

The old history term never steered: it only accrued at rip-up fights,
after the first routes had claimed the contested space, and routed
connections are never revisited in later passes.

bench/diagnose.py

@@ -186,6 +186,7 @@ def _flood(router: GridRouter, pin, net_no: int, conns) -> tuple[int, Counter]:
 def diagnose(
     dsn_text: str, edge_clearance_mm: float | None, resolution: int = 2, shove: bool = False,
     access_cost: float = 0.0, hole_to_hole_mm: float = 0.25, seed: int | None = None,
+    negotiate: int = 0,
 ) -> dict:
     dsn = parse_dsn(dsn_text)
     names = {i + 1: n.name for i, n in enumerate(dsn.nets)}
@@ -202,6 +203,7 @@ def diagnose(
         shove=shove,
         access_cost=access_cost,
         seed=seed,
+        negotiate=negotiate,
         # the product's configuration: net-class widths and hole spacing
         net_widths=_net_widths_board(dsn, scale),
         via_drill=_via_drill_board(dsn, scale),
@@ -278,12 +280,13 @@ def main(argv: list[str] | None = None) -> int:
     ap.add_argument("--shove", action="store_true", help="as mckicad routes")
     ap.add_argument("--access-cost", type=float, default=0.0)
     ap.add_argument("--seed", type=int, help="route in this shuffled order, as bench.py does")
+    ap.add_argument("--negotiate", type=int, default=0, metavar="N", help="as the router's --negotiate")
     ap.add_argument("--hole-to-hole", type=float, default=0.25, metavar="MM")
     ap.add_argument("--json", type=Path, help="also write the full table here")
     args = ap.parse_args(argv)
 
     report = diagnose(args.dsn.read_text(), args.edge_clearance, args.grid_resolution, args.shove,
-                      args.access_cost, args.hole_to_hole, args.seed)
+                      args.access_cost, args.hole_to_hole, args.seed, args.negotiate)
     for row in report["failures"]:
         extra = ""
         for w in row.get("walled", []):

src/freeroute/cli.py

@@ -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", "promote", "access", "rollback"}),
-    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access", "rollback"}),
+    "grid": frozenset({"rip_up", "max_passes", "seed", "orders", "promote", "access", "negotiate", "rollback"}),
+    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access", "negotiate", "rollback"}),
     "room": frozenset({"shove", "pack"}),
 }
 
@@ -46,6 +46,7 @@ _FLAG_NAMES = {
     "orders": "--orders",
     "promote": "--promote-failures",
     "access": "--access-cost",
+    "negotiate": "--negotiate",
     "rollback": "--no-rollback",
 }
 
@@ -167,6 +168,14 @@ def build_parser() -> argparse.ArgumentParser:
         help="grid and exact engines: extra cost for a route to pass where it would close "
         "another pin's way out while that pin still has connections to route (default 0: off)",
     )
+    parser.add_argument(
+        "--negotiate",
+        type=int,
+        metavar="N",
+        help="grid and exact engines: before routing, N rounds of negotiation on the empty "
+        "board, where routes may share space at a price that rises where they compete; "
+        "the contested cells then cost extra in the real routing (default 0: off)",
+    )
     parser.add_argument(
         "--no-rollback",
         dest="rollback",
@@ -212,6 +221,7 @@ def main(argv: list[str] | None = None) -> int:
             ("orders", args.orders is not None),
             ("promote", args.promote_failures is not None),
             ("access", args.access_cost is not None),
+            ("negotiate", args.negotiate is not None),
             ("rollback", not args.rollback),
         )
         if asked
@@ -247,6 +257,7 @@ def main(argv: list[str] | None = None) -> int:
             "resolution": 2 if args.grid_resolution is None else args.grid_resolution,
             "heuristic_weight": args.heuristic_weight,
             "access_cost": args.access_cost or 0.0,
+            "negotiate": args.negotiate or 0,
             "hole_to_hole_mm": args.hole_to_hole,
             "rollback": args.rollback,
         }
@@ -258,6 +269,7 @@ def main(argv: list[str] | None = None) -> int:
             "edge_clearance_mm": args.edge_clearance,
             "resolution": 1 if args.grid_resolution is None else args.grid_resolution,
             "access_cost": args.access_cost or 0.0,
+            "negotiate": args.negotiate or 0,
             "hole_to_hole_mm": args.hole_to_hole,
             "rollback": args.rollback,
         }

src/freeroute/route/exact_router.py

@@ -99,6 +99,7 @@ def route_board_exact(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     rollback: bool = True,
     net_widths: dict[int, int] | None = None,
     via_drill: int | None = None,
@@ -134,6 +135,7 @@ def route_board_exact(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         rollback=rollback,
         net_widths=net_widths,
         via_drill=via_drill,
@@ -207,7 +209,9 @@ def route_board_exact(
             for i, (box, box_layers) in enumerate(boxes)
             for layer in box_layers
         ) or _end_in_rule_area(tree, wires, wire_half) or (
-            outline is not None and not all(outline.box_clear(b, edge) for b, _ in boxes)
+            outline is not None and not _inside_outline(
+                outline, boxes[:wire_count], vias, (via_half or wire_half) + edge, edge
+            )
         ):
             rejected.append((net_no, *ends))
             continue  # exact-clearance conflict -> drop (may be recovered by shove)
@@ -670,6 +674,15 @@ def _copper_boxes(wires, vias, half_width, via_layers, via_half=None):
     return boxes
 
 
+def _inside_outline(outline, wire_boxes, vias, via_reach, edge) -> bool:
+    """Copper inside the board, ``edge`` from its outline. A via is round, as
+    the grid and KiCad take it: its square box would reach past a chamfered
+    corner where the via itself does not."""
+    return all(outline.box_clear(b, edge) for b, _ in wire_boxes) and all(
+        outline.point_clear(v, via_reach) for v in vias
+    )
+
+
 def _is_rotated(shape) -> bool:
     return isinstance(shape, Simplex) and not shape.is_int_box()
 

src/freeroute/route/grid_router.py

@@ -180,6 +180,7 @@ class GridRouter:
         seed: int | None = None,
         route_first: frozenset | None = None,
         access_cost: float = 0.0,
+        negotiate: int = 0,
         rollback: bool = True,
         net_widths: dict[int, int] | None = None,
         via_drill: int | None = None,
@@ -191,6 +192,15 @@ class GridRouter:
         # and the clearance around both) cost other nets this much extra, so
         # they route round a fine-pitch pin's way out instead of sealing it.
         self.access_cost = max(float(access_cost), 0.0)
+        # Negotiated congestion (PathFinder): before the real routing, every
+        # connection is routed this many times on the empty board, where routes
+        # may overlap at a price that grows where they compete. The cells that
+        # stay contested keep a history cost the real routing pays, so the first
+        # routes leave room around the places later routes have no way round.
+        self.negotiate = max(int(negotiate), 0)
+        self._history: dict[Node, float] = {}
+        self._present: dict[Node, dict[int, int]] | None = None
+        self._present_cost = 0.0
         self._doorways: dict[Node, list[tuple[int, int]]] = {}
         self._pending: dict[int, int] = {}
         # Rip-up as a transaction: the connections a rip-up route crosses are
@@ -299,9 +309,9 @@ class GridRouter:
         self._zone_cells: dict[int, list[Node]] = {}
         # per-connection occupancy (owner = connection index)
         self._cell_owner: dict[Node, int] = {}
-        self._via_owner: dict[Cell, int] = {}
         # every connection whose via covers a cell, in claim order: a via two
-        # connections share still blocks after the first of them is ripped
+        # connections share still blocks after the first of them is ripped,
+        # and a route through it must rip all of them
         self._via_claims: dict[Cell, list[int]] = {}
         # trace halos: node -> indices of the connections claiming it
         self._halo: dict[Node, list[int]] = {}
@@ -520,9 +530,7 @@ class GridRouter:
         if owner is not None and conns[owner].net_no != net_no:
             blocking = owner
         else:
-            via_owner = self._via_owner.get(cell)
-            if via_owner is not None and conns[via_owner].net_no != net_no:
-                blocking = via_owner
+            blocking = self._via_blocker(cell, net_no, conns)
         if blocking is None:
             for i in self._halo.get(node, ()):
                 if conns[i].net_no != net_no:
@@ -537,6 +545,17 @@ class GridRouter:
             return None
         return self.rip_penalty * (1 + rip_count)
 
+    def _via_others(self, cell: Cell, net_no: int, conns: list[_Connection]) -> list[int]:
+        """Connections of other nets whose via covers ``cell``: all of them,
+        since two connections of a net can share one via."""
+        return [i for i in self._via_claims.get(cell, ()) if conns[i].net_no != net_no]
+
+    def _via_blocker(self, cell: Cell, net_no: int, conns: list[_Connection]) -> int | None:
+        """The other net's via connection on ``cell`` hardest to rip (the
+        penalty and the rip cap go by it), or None."""
+        others = self._via_others(cell, net_no, conns)
+        return max(others, key=lambda i: conns[i].rip_count) if others else None
+
     def _via_cells(self, cell: Cell) -> list[Cell]:
         """The cell a via sits in plus the neighbours its copper reaches."""
         r = self.via_reach
@@ -758,6 +777,8 @@ class GridRouter:
                         continue
                     if self._doorways:
                         enter += self._access(nxt, net_no)
+                    if self._history or self._present is not None:
+                        enter += self._congestion(nxt, net_no)
                 step = 1.0 if dx == 0 or dy == 0 else math.sqrt(2)
                 self._relax(
                     current, nxt, base + step + enter, goal_cell, g_score, came_from, open_heap
@@ -770,9 +791,12 @@ class GridRouter:
                     if layer == cl:
                         continue
                     nxt = (cx, cy, layer)
-                    if g_via < g_score.get(nxt, math.inf):
+                    g_layer = g_via
+                    if self._history or self._present is not None:
+                        g_layer += self._congestion(nxt, net_no)
+                    if g_layer < g_score.get(nxt, math.inf):
                         heapq.heappush(
-                            open_heap, (g_via + self._h(nxt, goal_cell), nxt, g_via, current)
+                            open_heap, (g_layer + self._h(nxt, goal_cell), nxt, g_layer, current)
                         )
         return None
 
@@ -927,9 +951,7 @@ class GridRouter:
                     if not any(g.overlaps(t) for tiles in other for t in tiles for g in grown):
                         continue
                 owners.add(owner)
-            via_owner = self._via_owner.get(c)
-            if via_owner is not None and conns[via_owner].net_no != net_no:
-                owners.add(via_owner)
+            owners.update(self._via_others(c, net_no, conns))
         return owners
 
     def _end_penalty(self, pin: Pin, node: Node, net_no: int, allow_ripup: bool, conns) -> float:
@@ -1206,7 +1228,6 @@ class GridRouter:
                 if conn.index not in claims:
                     claims.append(conn.index)
                     conn.via_halo.append(c)
-                self._via_owner.setdefault(c, conn.index)
         ends = ((conn.a_end, wire_segs[0], 0), (conn.b_end, wire_segs[-1], -1)) if wire_segs else ()
         conn.stubs = []
         for pin, (layer, cells), at in ends:
@@ -1259,11 +1280,6 @@ class GridRouter:
             claims = self._via_claims.get(cell)
             if claims is not None and conn.index in claims:
                 claims.remove(conn.index)
-            if self._via_owner.get(cell) == conn.index:
-                if claims:
-                    self._via_owner[cell] = claims[0]
-                else:
-                    del self._via_owner[cell]
             if claims is not None and not claims:
                 del self._via_claims[cell]
         conn.via_halo = []
@@ -1308,9 +1324,7 @@ class GridRouter:
             owner = self._cell_owner.get((cx, cy, cl))
             if owner is not None and conns[owner].net_no != net_no:
                 owners.add(owner)
-            via_owner = self._via_owner.get((cx, cy))
-            if via_owner is not None and conns[via_owner].net_no != net_no:
-                owners.add(via_owner)
+            owners.update(self._via_others((cx, cy), net_no, conns))
             for i in self._halo.get((cx, cy, cl), ()):
                 if conns[i].net_no != net_no:
                     owners.add(i)
@@ -1360,6 +1374,74 @@ class GridRouter:
                 return self.access_cost
         return 0.0
 
+    # --- negotiated congestion --------------------------------------------
+
+    def _congestion(self, node: Node, net_no: int) -> float:
+        """History of a contested cell, plus while negotiating the price of
+        sharing it with the other nets on it now."""
+        cost = self._history.get(node, 0.0)
+        if self._present is not None:
+            users = self._present.get(node)
+            if users:
+                others = len(users) - (1 if net_no in users else 0)
+                cost += self._present_cost * others
+        return cost
+
+    def _footprint(self, path: list[Node]) -> set[Node]:
+        """The nodes a route claims: its cells and their clearance halo on
+        its layer, and every via's footprint on all layers."""
+        wire_segs, via_cells = _split_path(path)
+        halo = [(0, 0), *self._halo_offsets]
+        nodes: set[Node] = set()
+        for layer, cells in wire_segs:
+            for cx, cy in cells:
+                for dx, dy in halo:
+                    nodes.add((cx + dx, cy + dy, layer))
+        for cell in via_cells:
+            for c in self._via_cells(cell):
+                for layer in self.layers:
+                    nodes.add((*c, layer))
+        return nodes
+
+    def _negotiate(self, order: list[_Connection], conns: list[_Connection]) -> None:
+        """Route every connection on the empty board ``self.negotiate`` times,
+        letting routes share cells at a price: the number of other nets on a
+        cell times a factor that doubles every round, plus the cell's history,
+        which grows by one for every extra net each round it stays shared.
+        Only the history is kept; the board is left empty."""
+        present: dict[Node, dict[int, int]] = {}
+        claimed: dict[int, set[Node]] = {}
+        ends = [(c, c.a_end, c.b_end) for c in conns]
+        self._present, self._present_cost = present, 0.5
+        try:
+            for _ in range(self.negotiate):
+                for conn in order:
+                    for node in claimed.pop(conn.index, ()):
+                        users = present[node]
+                        users[conn.net_no] -= 1
+                        if not users[conn.net_no]:
+                            del users[conn.net_no]
+                    path = self._search(conn, allow_ripup=False, conns=conns)
+                    if path is None:
+                        continue
+                    nodes = self._footprint(path)
+                    claimed[conn.index] = nodes
+                    for node in nodes:
+                        users = present.setdefault(node, {})
+                        users[conn.net_no] = users.get(conn.net_no, 0) + 1
+                shared = 0
+                for node, users in present.items():
+                    if len(users) > 1:
+                        shared += 1
+                        self._history[node] = self._history.get(node, 0.0) + len(users) - 1
+                if not shared:
+                    break
+                self._present_cost *= 2
+        finally:
+            self._present = None
+            for conn, a_end, b_end in ends:  # the search picks ends; undo that
+                conn.a_end, conn.b_end = a_end, b_end
+
     # --- passes -------------------------------------------------------------
 
     def route(self) -> RouteResult:
@@ -1383,6 +1465,8 @@ class GridRouter:
         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)
+        if self.negotiate:
+            self._negotiate(order, conns)
         for _ in range(passes):
             changed = False
             for conn in order:
@@ -1779,6 +1863,7 @@ def route_board(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     rollback: bool = True,
     net_widths: dict[int, int] | None = None,
     via_drill: int | None = None,
@@ -1801,6 +1886,7 @@ def route_board(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         rollback=rollback,
         net_widths=net_widths,
         via_drill=via_drill,

src/freeroute/route/pipeline.py

@@ -118,6 +118,7 @@ def route_dsn_board(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
     rollback: bool = True,
 ) -> tuple[RouteResult, int, list[str]]:
@@ -143,6 +144,7 @@ def route_dsn_board(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         rollback=rollback,
         net_widths=_net_widths_board(dsn, scale),
         via_drill=_via_drill_board(dsn, scale),
@@ -196,6 +198,7 @@ def build_routing_result(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
     rollback: bool = True,
 ) -> RoutingResult:
@@ -205,6 +208,7 @@ def build_routing_result(
         edge_clearance_mm=edge_clearance_mm, resolution=resolution, seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         hole_to_hole_mm=hole_to_hole_mm,
         rollback=rollback,
     )
@@ -225,6 +229,7 @@ def route_dsn_board_exact(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
     rollback: bool = True,
 ) -> tuple[ExactRouteResult, int, list[str]]:
@@ -254,6 +259,7 @@ def route_dsn_board_exact(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         rollback=rollback,
         net_widths=_net_widths_board(dsn, scale),
         via_drill=_via_drill_board(dsn, scale),
@@ -276,6 +282,7 @@ def build_exact_routing_result(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
     rollback: bool = True,
 ) -> RoutingResult:
@@ -293,6 +300,7 @@ def build_exact_routing_result(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         hole_to_hole_mm=hole_to_hole_mm,
         rollback=rollback,
     )

tests/route/test_grid_exact_agreement.py

@@ -143,11 +143,48 @@ def test_a_shared_via_keeps_its_footprint_when_one_user_is_ripped():
     router._rip(first)
 
     assert second.routed and via in second.via_cells
-    assert all(router._via_owner.get(c) == second.index for c in footprint)
+    assert all(router._via_claims.get(c) == [second.index] for c in footprint)
     # another net still keeps its distance from the via that is left
     assert all(router._enter_cost_base(c, 0, sig.net_no, False, conns) is None for c in footprint)
 
 
+def test_a_route_through_a_shared_via_rips_every_user():
+    """Two connections of a net share a via. Another net routed through it
+    in rip-up mode has to rip both, or the one left keeps its via under the
+    new trace and the exact check throws one of them out."""
+    dsn = parse_dsn(_SHARED_VIA)
+    s = dsn.resolution.value
+    router = GridRouter(
+        build_board(dsn),
+        trace_width=round(_rule_width_dsn(dsn) * s),
+        clearance=round(_rule_clearance_dsn(dsn) * s),
+        via_half=_via_half_board(dsn, s),
+    )
+    conns = router._conns = router._build_connections()
+    gnd = [c for c in conns if len({c.a.component_ref, c.b.component_ref} & {"G1", "G2", "G3"})]
+    sig = next(c for c in conns if c not in gnd)
+    first, second = gnd
+    g3 = router._cell_of(next(p for p in router.board.get_pins() if p.component_ref == "G3").location)
+    via = (g3[0] - 10, g3[1])
+
+    def through_via(conn):
+        a, b = router._cell_of(conn.a.location), router._cell_of(conn.b.location)
+        return _line(a, via, 0) + _line(via, b, 1)
+
+    router._commit(first, through_via(first))
+    router._commit(second, through_via(second))
+    # the via's copper alone: footprint cells no trace or trace halo covers
+    crossing = [
+        node
+        for c in router._via_cells(via)
+        for node in ((*c, 0), (*c, 1))
+        if node not in router._cell_owner and node not in router._halo
+    ]
+    assert crossing
+
+    assert router._crossed_owners(crossing, sig.net_no, conns) == {first.index, second.index}
+
+
 # --- a wider net class --------------------------------------------------------
 
 _WIDE = """(pcb wide (parser) (resolution um 10) (unit um)
@@ -225,3 +262,23 @@ def test_a_pad_cell_check_uses_the_rotated_outline():
         c = router._cell_center(cell)
         square = IntBox(c.x - margin, c.y - margin, c.x + margin, c.y + margin)
         assert oval.shape.intersection(square).dimension() != 2
+
+
+def test_a_via_by_a_chamfered_corner_is_judged_round():
+    """The grid keeps a via's centre its radius plus the edge clearance from
+    the outline. The exact check used the via's square, whose corner reaches
+    past a 45-degree chamfer where the round via does not."""
+    from freeroute.board.outline import BoardOutline
+    from freeroute.geometry import IntBox, IntPoint
+    from freeroute.route.exact_router import _inside_outline
+
+    # a 10 mm square with its lower-left corner cut at 45 degrees
+    outline = BoardOutline([IntPoint(*p) for p in
+                            [(30, 0), (100, 0), (100, 100), (0, 100), (0, 30)]])
+    half, edge = 4, 1
+    via = IntPoint(19, 20)  # its centre 6.4 from the chamfer x + y = 30
+    square = IntBox(via.x - half, via.y - half, via.x + half, via.y + half)
+    assert not outline.box_clear(square, edge)  # the square's corner: 0.7 away
+    assert _inside_outline(outline, [], [via], half + edge, edge)
+    # 4.2 from the chamfer: the round via itself is too close
+    assert not _inside_outline(outline, [], [IntPoint(18, 18)], half + edge, edge)

tests/route/test_negotiate.py

@@ -0,0 +1,65 @@
+"""--negotiate: PathFinder-style rounds on the empty board before routing."""
+
+from __future__ import annotations
+
+from pathlib import Path
+
+import pytest
+
+from freeroute.board import build_board
+from freeroute.dsn import parse_dsn
+from freeroute.route.grid_router import GridRouter
+from freeroute.route.pipeline import _rule_clearance_dsn, _rule_width_dsn, route_dsn_board
+
+FIXTURES = Path(__file__).resolve().parent.parent / "dsn" / "fixtures"
+
+
+def _router(name, negotiate):
+    dsn = parse_dsn((FIXTURES / name).read_text())
+    s = dsn.resolution.value
+    return GridRouter(
+        build_board(dsn),
+        trace_width=round(_rule_width_dsn(dsn) * s),
+        clearance=round(_rule_clearance_dsn(dsn) * s),
+        negotiate=negotiate,
+    )
+
+
+def test_negotiation_leaves_the_board_empty_and_the_ends_as_they_were():
+    router = _router("true_density.dsn", 3)
+    conns = router._conns = router._build_connections()
+    ends = [(c.a_end, c.b_end) for c in conns]
+    router._negotiate(list(conns), conns)
+    assert router._history  # a dense board has contested cells
+    assert not router._cell_owner and not router._halo and not router._via_claims
+    assert not any(c.routed for c in conns)
+    assert [(c.a_end, c.b_end) for c in conns] == ends
+    assert router._present is None
+
+
+def test_sharing_is_priced_only_for_other_nets():
+    router = _router("true_density.dsn", 1)
+    node = (3, 4, 0)
+    router._history[node] = 2.0
+    router._present, router._present_cost = {node: {7: 1, 9: 2}}, 0.5
+    assert router._congestion(node, 7) == pytest.approx(2.5)  # one other net
+    assert router._congestion(node, 5) == pytest.approx(3.0)  # two other nets
+    router._present = None
+    assert router._congestion(node, 5) == pytest.approx(2.0)  # history only, after
+
+
+@pytest.mark.parametrize("name", ["ripup_needed.dsn", "true_density.dsn", "kicad_routable.dsn"])
+def test_negotiated_routing_keeps_the_occupancy_honest(name):
+    """Only routed connections hold cells afterwards, as without negotiation."""
+    router = _router(name, 3)
+    router.route()
+    conns = router._conns
+    assert all(conns[i].routed for i in router._cell_owner.values())
+    assert all(conns[i].routed for claims in router._halo.values() for i in claims)
+
+
+def test_option_reaches_the_router_and_is_off_by_default():
+    text = (FIXTURES / "kicad_routable.dsn").read_text()
+    plain, _, _ = route_dsn_board(parse_dsn(text))
+    again, _, _ = route_dsn_board(parse_dsn(text), negotiate=0)
+    assert plain.unrouted == again.unrouted

tests/route/test_rollback.py

@@ -31,7 +31,7 @@ def test_occupancy_only_holds_routed_connections(name):
     router, _ = _routed_router(name)
     conns = router._conns
     assert all(conns[i].routed for i in router._cell_owner.values())
-    assert all(conns[i].routed for i in router._via_owner.values())
+    assert all(conns[i].routed for claims in router._via_claims.values() for i in claims)
     assert all(conns[i].routed for claims in router._halo.values() for i in claims)
 
 

tests/test_cli.py

@@ -158,6 +158,7 @@ def test_cli_supported_combinations_are_accepted(tmp_path):
         "orders": ["--orders", "2"],
         "promote": ["--promote-failures", "2"],
         "access": ["--access-cost", "5"],
+        "negotiate": ["--negotiate", "2"],
         "rollback": ["--no-rollback"],
     }
     for engine, options in ENGINE_OPTIONS.items():