tiny-hypergraph

Tiny hypergraph implementation. Read more about HyperGraph Autorouting, check out online animated examples

Usage

Solve a serialized hypergraph

import type { SerializedHyperGraph } from "@tscircuit/hypergraph"
import { loadSerializedHyperGraph } from "lib/compat/loadSerializedHyperGraph"
import { TinyHyperGraphSolver } from "lib"

const inputGraph: SerializedHyperGraph = /* ... */

const { topology, problem } = loadSerializedHyperGraph(inputGraph)
const solver = new TinyHyperGraphSolver(topology, problem)

solver.solve()

if (!solver.solved || solver.failed) {
  throw new Error(solver.error ?? "Solver did not finish successfully")
}

const solvedGraph = solver.getOutput()

Existing routing can be preloaded through the standard region assignments:

const inputGraph: SerializedHyperGraph = {
  regions: [
    {
      regionId: "middle",
      pointIds: ["left-port", "right-port"],
      assignments: [
        {
          regionPort1Id: "left-port",
          regionPort2Id: "right-port",
          connectionId: "trace-1",
        },
      ],
      d: {},
    },
  ],
  ports,
  connections,
}

The assignments seed regular route-owned solver state. They reserve their existing ports and contribute to region congestion immediately, but remain eligible for the normal rip-and-reroute process. They do not create regions or otherwise change the hypergraph topology.

Set isFixed: true on a serialized connection to preserve its assignments through global retries, selective and partial rerips, and section optimization. The loader stores this policy in problem.routeIsFixed, and serialized output preserves it. A fixed route requires complete initial assignments connecting its endpoints. Its ports and segments remain native routing state, so other routes on the same net can reuse them. Omitted isFixed keeps the normal mutable policy. The independent bus and region-path solvers reject fixed routes.

Outside-in partial reripping

SelectiveReripTinyHyperGraphSolver preserves the unaffected prefix and suffix of each route that crosses a hot region. Only a bounded window around the route's hottest affected segment is reopened. The reopened span is searched from both retained ends, with a hard geometric travel limit on each frontier; if the frontiers cannot meet within that limit, the span safely falls back to the regular one-ended search.

The behavior can be tuned through TinyHyperGraphSolverOptions:

const solver = new SelectiveReripTinyHyperGraphSolver(topology, problem, {
  PARTIAL_RIP_ENABLED: true,
  PARTIAL_RIP_MIN_ROUTE_COUNT: 100,
  PARTIAL_RIP_MAX_ROUTE_COUNT: 350,
  PARTIAL_RIP_MAX_DISTANCE: 12,
  PARTIAL_RIP_QUALITY_MAX_DISTANCE: 24,
  PARTIAL_RIP_MAX_ATTEMPTS: 10,
  OUTSIDE_IN_ROUTING: true,
  OUTSIDE_IN_MAX_DISTANCE: 24,
})

Set PARTIAL_RIP_ENABLED or OUTSIDE_IN_ROUTING to false to use the legacy whole-route or one-ended behavior respectively. PARTIAL_RIP_MIN_ROUTE_COUNT and PARTIAL_RIP_MAX_ROUTE_COUNT provide an inclusive scale window; graphs outside it use the legacy behavior. The solver exposes aggregate partial-rip, retained-segment, frontier-expansion, distance-prune, and fallback counts through solver.stats. When the first completed solution is already within 1.5 times the configured final rip threshold, the solver uses the quality-recovery distance (twice the normal distance when unspecified) for the entire partial-rip run; this gives low-cost solutions enough room to remove a last hotspot without slowing heavily congested cases.

Export a solved solver back to SerializedHyperGraph

solver.getOutput() now returns a SerializedHyperGraph for a solved TinyHyperGraphSolver.

Under the hood it uses lib/compat/convertToSerializedHyperGraph.ts, which reconstructs:

• regions
• region assignments
• ports
• connections
• solvedRoutes

The serialized region and port ids from loadSerializedHyperGraph(...) are preserved, so a graph loaded through the compat layer can be solved and then round-tripped back into the same serialized shape.

If you want to call the converter directly:

import { convertToSerializedHyperGraph } from "lib/compat/convertToSerializedHyperGraph"

const solvedGraph = convertToSerializedHyperGraph(solver)

The converter expects the solver to be fully solved and not failed.