structural-computing

Exact polynomial-time answers to combinatorial questions that today's tools can only sample, estimate, or give up on — for the subset of problems with the right structural shape (planar, bounded-genus, near-matchgate, GF(2)-affine). When applicable, the framework returns bit-identical reproducible numbers in milliseconds-to-seconds. When inapplicable, it stops honestly with a clear pointer to the right external tool. No silent approximation.

📘 New here? Read the book first: Declarative Structural Computing — A Practitioner's Guide (17 chapters, ~6 hours end-to-end; a 1-hour skim is enough to decide whether the framework helps your work).

The book explains the paradigm this package embodies — what happens when entire codebases (100,000+ lines of Monte Carlo simulators, MIP timeouts, hand-rolled scheduling heuristics) collapse to a few lines of declarative query, in the same way SQL collapsed 1970s data-iteration code. It's written for regular humans — not mathematicians — with concrete characters, three runnable worked examples (reliability, scheduling, CP-SAT pre-flight), and a one-page business case with concrete dollar figures.

What this codebase / repo / library lets you do

The framework wraps a handful of polynomial-time exact algorithms (matchgate-Holant evaluation, FKT, Kasteleyn, Hungarian, CP-SAT diagnostic) behind a small declarative API. You ask a question about a combinatorially structured input — how many? which is cheapest? what's the failure probability? which configuration is more reliable? — and the framework picks the right algorithm and returns the exact answer. If your problem doesn't fit, the framework refuses to guess and tells you what tool to reach for instead. In concrete terms, this lets you:

• Compare two configurations exactly even when the difference is below Monte-Carlo's noise floor. Two network topologies, two reinsurance treaty structures, two CI pipeline designs that look equivalent to sampling — the framework returns "Configuration B is 90.2% more reliable, provably real, not a sampling artefact" in milliseconds.

• Compute exact rare-tail probabilities for failure modes you'd otherwise have to estimate by long-running Monte-Carlo. Risk reports for regulators, capacity-planning analyses that need defensible numbers, reliability claims that have to be bit-reproducible across runs.

• Count solutions to combinatorial problems exactly rather than finding just one. How many valid task-resource assignments exist? How many distinct ways can these components be paired? Which edges are structural single points of failure? Standard solvers find one answer; this framework counts and audits the whole solution space.

• Route different kinds of problems automatically. The framework's classifier figures out which structural shape your problem has, picks the right exact-evaluation kernel (FKT for planar graphs, bounded- genus Kasteleyn for higher-genus, CH-form for stabilizer arithmetic, tropical Pfaffian for max-weight optimisation), and produces an answer with a recorded provenance you can audit.

• Beat out-of-family problems into shape. A graph that isn't natively planar can often be made tractable via reductions (gadget substitution, basis changes, parity-split, hybrid decomposition), compositions (linear combinations of in-family evaluations, holographic basis pairs), or recursive decomposition (treewidth- bounded DP, Shannon expansion, circuit cutting). The framework's reduction layer makes this routine.

A taste — your first one-liner

Before the full mental model, here's the simplest possible end-to-end use. We define two candidate network topologies as edge lists (the framework accepts plain Python lists of tuples for graphs), then ask the framework which one is more reliable under random edge failures. The whole thing — install, import, two network definitions, the comparison — fits on one screen.

pip install structural-computing

from structural_computing import StructuralComputer

sc = StructuralComputer()

# Two candidate network topologies.
config_a = [(0, 1), (1, 2), (2, 3), (3, 0)]                  # 4-cycle
config_b = [(0, 1), (0, 2), (0, 3),                           # K_4
            (1, 2), (1, 3), (2, 3)]

# Exact rare-tail probability under independent edge failure.
print(sc.tail_probability(config_a, p_fail=0.05))    # 9.5063e-03 (exact, ~1.7 ms)
print(sc.tail_probability(config_b, p_fail=0.05))    # 9.2686e-04

# Compare them -- regulator-defensible verdict, no sampling noise.
report = sc.compare(config_a, config_b, p_fail=0.05)
print(report.explain())
# "Configuration B is 90.2% more reliable (9.5063e-03 vs 9.2686e-04).
#  This distinction is provably real (exact computation),
#  not a sampling artefact."

That comparison — sub-statistical-noise-floor, bit-identically reproducible, regulator-defensible — no off-the-shelf reliability tool can produce, because their internal data models are structurally Monte-Carlo and the question's signal lives below the sampling floor.

More worked examples

Three more one-screen examples, each in a different domain. They use the same StructuralComputer object — only the question changes. If you've read the book (docs/book.md), these are condensed versions of Chapters 9, 10, and 11; if you haven't, they're the fastest way to see the framework's range across reliability, optimisation, and pre-flighting an existing CP-SAT solver.

Min-cost matching (tropical / Hungarian / Edmonds)

Suppose each edge of a graph has a weight (a cost) and you want the cheapest set of edges that pairs up every vertex exactly once. This is the min-weight perfect matching problem, and it shows up in production code under many names — assignment problems, dispatching, package routing, ad-slot allocation. The framework solves it exactly in polynomial time. The underlying algorithm is the same one used for counting matchings; only the arithmetic changes (replace standard (+, ×) with the tropical (min, +) semiring). You don't mention the semiring anywhere in the call — the question name min_weight_matching selects it for you:

from structural_computing import StructuralComputer
sc = StructuralComputer()

graph = [(0, 1), (1, 2), (2, 3), (3, 0)]
weights = {(0, 1): 1.0, (1, 2): 10.0, (2, 3): 1.0, (3, 0): 10.0}

result = sc.min_weight_matching(graph, weights)
# {'cost': 2.0, 'matching': [(0, 1), (2, 3)], 'feasible': True}

Polynomial-time exact via Hungarian (bipartite K_{n,n}) or Edmonds blossom (general non-bipartite); no MIP timeout, no heuristic.

CP-SAT pre-flight: faster solve via structural rewrite

If you already use Google's OR-Tools CP-SAT solver and don't want to migrate away from it, the framework can sit upstream of CP-SAT as a structural pre-processor. It reads your cp_model.CpModel, identifies rank-explosive constraints — cardinality (sum(xs) == k), at-most-k, certain all-different patterns — and rewrites them into a form CP-SAT handles more efficiently. The rewrite is mathematically equivalent on the original variables; you verify equivalence on a sample and then deploy with confidence. If no rewrite applies, the framework honestly says so via result.helped == False and you solve the original model — nothing has been changed, nothing is at risk. The total integration is three new lines around your existing solver.Solve(model) call:

from structural_computing import StructuralComputer
from ortools.sat.python import cp_model

sc = StructuralComputer()
model = cp_model.CpModel()
xs = [model.NewBoolVar(f"x{i}") for i in range(4)]
model.Add(sum(xs) == 2)

result = sc.rewrite_cpsat_model(model)
# result.helped == True
# result.help_reason_text:
#   "Rewrote 1 constraint(s) to time-slot rank-1 form;
#    added 8 auxiliary boolean(s)."

if result.helped:
    solver = cp_model.CpSolver()
    solver.Solve(result.rewritten_model)
else:
    # Honest stop: solver the original model with CP-SAT
    solver = cp_model.CpSolver()
    solver.Solve(model)

Optionally verify the rewrite preserves the feasible set on the original variables:

verify = sc.verify_cpsat_rewrite(model, result, enumeration_limit=1000)
# verify.equivalent == True
# verify.n_original_solutions == 6  (= C(4, 2))

Schedule optimisation in one line

Job-to-machine assignment, surgical rooming, nurse rostering, truck-to-route dispatch — the standard shape is N things to assign to M slots subject to constraints, minimising total cost. Production teams typically reach for a MIP solver (Gurobi, CPLEX, CBC) here. For the large fraction of these problems where the cost structure has the right rank — which is most of them in practice — the framework solves them exactly in polynomial time via the Hungarian algorithm (under the floor), with no commercial licence and no possibility of solver timeout. The whole thing fits in one sc.min_cost_schedule(...) call:

import holant_tools
from structural_computing import StructuralComputer

sc = StructuralComputer()

jobs = [holant_tools.Job(name="J1"), holant_tools.Job(name="J2")]
machines = [holant_tools.Machine(name="M1"), holant_tools.Machine(name="M2")]
instance = holant_tools.SchedulingInstance(jobs=jobs, machines=machines)

def cost_fn(job, machine, slot):
    # cheap when matched to preferred machine
    if job.name == "J1": return 1.0 if machine.name == "M1" else 5.0
    return 5.0 if machine.name == "M1" else 1.0

result = sc.min_cost_schedule(instance, cost_fn)
# result['cost'] == 2.0
# result['schedule'] == {'J1': ('M1', 0), 'J2': ('M2', 0)}

The underlying claim

Many problems people actually care about — counting valid configurations, exact rare-tail probabilities, single-point-of-failure analysis, regulator-grade configuration comparison, partition functions of planar Ising models, free-fermion-equivalent quantum simulation, structural audit of workflow graphs — sit in a mathematically structured family called matchgate-Holant. For problems IN this family, exact polynomial-time computation is possible via Kasteleyn's FKT theorem (1961) and its bounded-genus extensions (Galluccio-Loebl). For many problems NOT directly in this family, transformations bring them in.

The framework is the runnable form of that claim: a Python package that takes your problem, classifies its structure, applies whatever transformation it needs, and produces an exact answer with provenance — or stops honestly and tells you what external tool to reach for.

The friendly entry point is StructuralComputer (one-liners hide every framework internal). The underlying Orchestrator exposes the routing decisions for users who want to compose custom pipelines or plug in their own evaluators. The transform.py / compose.py / decompose.py modules expose the reductions / compositions / recursive-decomposition layer for users widening the in-family boundary.

Where the framework helps — and where it stops

The framework's exact polynomial-time answers apply when your problem has the right structural shape — typically planar graphs, bounded-genus graphs, GF(2)-affine constraint sets, or the matchgate-Holant family. In practice this covers a lot of real-world problems: most physical-infrastructure networks (grids, pipes, roads), most workflow graphs, many scheduling and assignment instances, and a sizeable fraction of CP-SAT models with rank-explosive constraints.

For problems that don't natively fit one of these shapes, there's a second route: the reductions / compositions / recursive-decomposition layer can sometimes bring them in. A non-planar graph with a small number of "extra" edges can be hybrid-decomposed back into planar pieces; a constraint set with the wrong rank structure can sometimes be rewritten; a bounded-treewidth problem can be solved by recursive DP. The book (docs/book.md) chapter on "Five patterns that fit, five that don't" walks through this in detail.

When neither route applies — continuous mathematics with no discretisation, random expander graphs with no exploitable structure, problems that are genuinely too tangled — the framework refuses to guess. It raises NotInFamily with a structured explanation (the structural tier, the meters that failed, suggested alternative tools) so you know exactly why. No silent approximation, ever. That refusal is by design; the book has a whole chapter on why honest stops are valuable.

Status

v1.2.3 — Production / Stable (released 2026-06-02). pip install structural-computing pulls in holant-tools >= 0.7.3 transparently. The public API is semver-protected for downstream packages — see docs/STABILITY.md for the per-method stability contract. 338 tests across ~16 test modules pass (with the [test] optional dependencies installed — pip install -e ".[test]").

Capability surface:

• Counting + reliability (v0.1–v0.3): perfect matching counts, rare-tail failure probabilities, single-points-of-failure, regulator-grade configuration comparison.
• Realisability + holographic toolkit (v0.4–v0.6): MGI realisability check, full Cai-Lu §4 d-admissibility, Lipton-Tarjan 5-tier auto-separator cascade (v0.4 simple → v0.5 tree-edge → v0.6 level-based → v0.8 fundamental-cycle → v0.9 explicit planar-dual), closed-form SRP for both real and complex roots.
• Tropical / min-cost optimisation (v0.10–v0.11): the same admissible-set machinery computes MIN-COST configurations under the (min, +) semiring — sc.min_weight_matching, sc.min_cost_schedule, sc.min_cost_flow, sc.min_cost_roster, sc.min_cost_dedup, sc.tropical_instance_coordinates.
• CP-SAT pre-flight (v0.13): pass a cp_model.CpModel to sc.rewrite_cpsat_model(...) and get back either a structurally cheaper rewritten model OR an explicit "can't help here" signal.
• Wrapper consolidation (v0.12): the friendly StructuralComputer wrapper delegates through the Orchestrator engine; any new question registered in the leaf-evaluator registry is automatically reachable via a thin wrapper method.
• Systems metric (v1.2): an exact, auditable, directed cost between two structured shapes — sc.systems_metric(A, B, transforms=...). The cheapest admissible transformation path that carries A into B, priced in the tropical (min, +) semiring over the framework's named morphisms. Asymmetric by design (A→B need not equal B→A), obeys the triangle inequality, and honest-stops with incommensurable=True when no admissible path exists. An exact "structural diff" with an audit trail.

See CHANGELOG.md for the full release history. The companion repo structural-computing-bench ships a per-machine cost-model calibration runner the router loads via apply_calibration().

Runnable examples

The examples/ folder contains 14 self-contained scripts runnable after pip install:

01_count_matchings.py	exact perfect-matching count
02_rare_tail_probability.py	exact rare-tail probability
03_compare_configurations.py	sub-MC-noise-floor comparison
04_orchestrator_dispatch.py	Orchestrator direct-dispatch + honest-stop
05_hybrid_decomposition.py	exact matching count on non-planar K_{3,3}
06_signature_classification.py	basis-aware rank ≤ 2 across symmetric signatures
07_treewidth_bounded_dp.py	multi-bag Bodlaender DP on a tree decomp
08_rationalise_weighted_matching.py	float weights → integer arithmetic with exact descale
09_holographic_basis_unlock.py	Hadamard basis turns 3-AND into matchgate-standard form
10_crossing_elimination_k4.py	Cai-Gorenstein gadget at K_4's diagonal crossing
11_high_degree_vertex_split.py	2k-node triangle cycle realising a high-arity symmetric signature
12_discover_holographic_basis.py	auto-discovery of a holographic basis (the practical fragment of Cai-Lu's SRP)
13_general_holographic_transform.py	non-symmetric T^⊗a transform; symmetric-path agreement + round-trip
14_systems_metric.py	directed tropical cost between two designs: asymmetry + incommensurable honest-stop

Each example produces a bit-identically reproducible number. See examples/README.md for the index.

Documentation

The full documentation lives under docs/ — index at docs/README.md. The most useful entry points:

• The book — docs/book.md. A 17-chapter narrative guide covering the paradigm, the business case, three worked examples (reliability, scheduling, CP-SAT pre-flight), integration patterns, and the long-horizon view. Start here if you're a business analyst or a developer new to the framework.
• Tutorial — docs/tutorial/getting-started.md. A 30-minute hands-on walkthrough.
• How-to recipes — docs/how-to/ (min-cost scheduling, CP-SAT pre-flight).
• API reference — docs/reference/api.md: every public method on StructuralComputer with signature, return type, and one-line description.
• Stability contract — docs/STABILITY.md. Per-symbol stability tiers (Stable / Experimental / Internal) under semver.
• Architecture deep dive — docs/architecture.md. Comprehensive system reference for contributors.

The companion worked-examples repo free-fermion-quantum-simulation has the original development-trail with brute-force verification on every routine; this package is the simplified PyPI form.

Built on holant-tools

This package depends on holant-tools — the mathematical engine providing Pfaffian / FKT computation, Kasteleyn orientations, the corrected dart-chain passage-arc formula, basis-aware matchgate rank, the CH-form stabilizer representation, and the full set of matchgate-Holant tractability primitives.

import holant_tools  # automatically installed as a dependency

License

MIT-with-attribution. See LICENSE. Visible attribution to Edward Chalk (sapientronic.ai) is required for publications, presentations, derivative works, and products.

Citation

If you use this package in published work, please cite:

Edward Chalk (sapientronic.ai). "structural-computing: declarative
structural computation in Python." Version 1.0.0, 2026.
https://github.com/pcoz/structural-computing

For the full release history, see CHANGELOG.md.