structural-computing 0.13.0a1

Declarative structural computation: exact polynomial-time answers to combinatorial questions on structured graphs, with automatic routing to the cheapest correct evaluator.

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.

What this lets you do

• 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

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.

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.

Status

Alpha (v0.6.0a1; live on PyPI 2026-05-31). pip install structural-computing pulls in holant-tools 0.6.1 transparently. API may still shift before v1.0, but the public surface is now stable enough for downstream prototyping. 281 tests across ~15 test modules pass; the orchestrator handles all three problem types (graphs / constraint sets / signatures) with full provenance, including non-symmetric signatures via the general tensor-power holographic transform. The reductions / compositions / recursive-decomposition layer ships real Cai-Gorenstein and Cai-Lu constructions, not placeholders -- every v0.2-era NotImplementedError stub is now a working primitive. v0.3 closed the calibration loop and the holographic toolkit; v0.4 added MGI realisability checking, Lipton-Tarjan auto-separator, and a closed-form SRP shortcut; v0.5 closed three honest-scope gaps (full d-admissibility at arity 6 odd-parity, Lipton-Tarjan tree-edge backup, closed-form SRP for complex roots); v0.6 is a cleanup + math-completeness round:

• Augmented Plücker helper promoted to holant-tools v0.6.0 (D1) — the v0.5 prototype-in-place math primitive now lives in the mathematical engine, honouring the architectural principle.
• Lipton-Tarjan level-based + articulation-augmentation backup (D2) — three-step backup chain (simple → tree-edge → level-based) catches star K_{1,n} and complete-bipartite K_{2,n} adversarial graphs that defeat v0.5's tree-edge approach.
• |S| = 4 (m = 3) augmented Plücker at arity ≥ 8 (D3) — via holant-tools v0.6.1, the augmented enumeration count grows from 280 (m=1) to 560 (m=1 + m=3) at arity 8, and from 1260 to 5460 at arity 10.

See CHANGELOG.md for what's in this release and what's coming.

Companion repo structural-computing-bench calibrates the router's cost models on your machine and produces a data file the framework loads via apply_calibration() — see the "Calibrated cost models" section below.

What this is for

When you have a combinatorially structured question with a graph-like shape — perfect matching count, rare-tail failure probability, single-point-of-failure detection, regulator-grade configuration comparison, satisfying-assignment count — and the underlying graph is planar / bounded-genus / GF(2)-affine in structure, this package gives you exact polynomial-time answers via the FKT theorem, Kasteleyn orientations, and the matchgate-Holant family.

When your problem is outside the structural family, the package honest-stops with advised:external-solver rather than producing a false answer.

What's inside

The friendly entry point

from structural_computing import StructuralComputer

sc = StructuralComputer()
sc.count_matchings(graph)              # how many perfect matchings?
sc.witness(graph)                       # find one specific matching
sc.tail_probability(graph, p_fail)      # exact P(no matching survives)
sc.single_points_of_failure(graph)      # critical edges
sc.compare(a, b, p_fail)                # which is more reliable?
sc.audit(graph)                         # everything in one call
sc.explain(graph)                       # human-readable plan, no jargon

Framework primitives (for composing custom pipelines)

from structural_computing import (
    Stage, Route, run_pipeline,        # the pipeline-router driver
    classify_graph, classify_constraint_set, classify_signature,  # the classifier
    route,                              # tier -> member + cost
    RichTrace,                          # aggregated routing trace
    ReplayCache, cached_runner,         # memoisation
    verify_pipeline,                    # small-n brute-force harness
)

Orchestrator (the "give me an answer" top-level engine)

For when you don't want to think about tiers, evaluators, or reductions — just hand the framework a problem and a question:

from structural_computing import Orchestrator

orch = Orchestrator()

# A planar dependency graph -- direct dispatch via T2 free-fermion.
K4 = {
    "rotation": {0: [1, 2, 3], 1: [0, 3, 2], 2: [0, 1, 3], 3: [0, 2, 1]},
    "vertices": [0, 1, 2, 3],
    "edges": [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)],
}
result = orch.evaluate(K4, question="matching_count")
print(result.answer)                  # -> 3
print(result.classification.tier)     # -> "T2"
print(result.leaf_evaluator_used)     # -> "_brute_force_matching_leaf"

# Non-planar K_{3,3}: out-of-family by default, but HybridDecomposition
# reduces it to a sum of planar sub-problems. Supply the "extras" as hints.
K33 = {...}                            # see tests/test_orchestrator.py
result = orch.evaluate(K33, question="matching_count",
                        hints={"extra_edges": [(0, 3)]})
print(result.answer)                  # -> 6  (= 3!)
print(result.reductions_applied)      # -> ["HybridDecomposition(via hints)"]
print(result.sub_evaluations)         # -> 2  (forced-in branch + forced-out branch)

If the problem is out-of-family AND no registered reduction applies, the orchestrator raises NoKnownReduction with the classification attached so the caller can inspect what was tried.

Reductions / compositions / recursive decomposition

For users who want to compose their own transformations directly:

from structural_computing import (
    HybridDecomposition, ReductionPlan, NormaliseGraphFormat,    # transform.py
    LinearCombination,                                            # compose.py
    ShannonExpansion, TreewidthBoundedDP,                         # decompose.py
)

The reductions / compositions / decompositions layer is the framework's in-family-boundary widener. v0.2 ships these as REAL constructions (no placeholders):

Reductions (transform.py):

• NormaliseGraphFormat — coerce edge-list / adjacency-dict / rotation- system inputs into a canonical form.
• HybridDecomposition — branch on a small set of "extra" edges that make a graph non-planar; pay 2^|extras| × O(|V|^3) for the exact matching count. Includes auto_detect_extras greedy heuristic.
• RationaliseWeights — scale real-valued edge weights to integers at chosen precision, with inverse to descale the final answer.
• CrossingElimination — Cai-Gorenstein 6-vertex / weight-(-1) crossover gadget at each declared crossing (arXiv:1303.6729 Fig. 6). Preserves matchgate signature (signed Pfaffian).
• HighDegreeVertexSplit — Cai-Gorenstein 2k-node triangle-cycle realisation of matchgate-realisable symmetric signatures (Theorem 9 + Fig. 10).

Compositions (compose.py):

• LinearCombination — combine two or more in-family signature evaluations as sum(coeff_i * value_i).
• HolographicBasisPair — Cai-Lu 2011 polynomial-substitution basis change on symmetric signatures + matchgate-realisability check via the order-2 recurrence rank test (Theorem 2.5). The Hadamard basis transforms [1, 0, 0, 1] into the matchgate-standard [0, 2, 0, 2] — the canonical Valiant-style holographic unlock.

Decompositions (decompose.py):

• ShannonExpansion — branch on a binary variable; recurse on each branch; base case in-family.
• TreewidthBoundedDP — full Bodlaender-style multi-bag DP for matching count on bounded-treewidth graphs.

As of v0.3, every NotImplementedError sketch from earlier releases is shipped as a real construction (Projection, BranchSum, PlanarSeparator, RecursiveCircuitCut, transform_signature_general for non-symmetric HolographicBasisPair, discover_basis / discover_common_basis for Cai-Lu SRP). As of v0.4, the realisability verdict on non-symmetric signatures and the Lipton-Tarjan auto-mode on PlanarSeparator are wired through too.

See the full API reference at the worked-examples repo: docs/reference/.

Runnable examples

The examples/ folder contains 11 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

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

Calibrated cost models

The router's default cost estimates are hand-picked log2(ops) numbers. For machine-specific predictions, install the companion repo structural-computing-bench, run the calibration once, and load the resulting data file:

from my_calibration_file import CALIBRATED_COSTS
from structural_computing import apply_calibration

apply_calibration(CALIBRATED_COSTS)

# Now `route(..., question=...)` surfaces wall-clock predictions,
# and `orchestrator.evaluate(..., verbose=True)` emits a 'predict'
# step in the workflow trace before each leaf dispatch.

The calibration loader is opt-in; the framework runs with hand-picked cost models if you skip it. See bench/README.md for the calibration sweep details.

Documentation

The detailed documentation lives in the companion worked-examples repo free-fermion-quantum-simulation — the development-trail form of the framework, where the original worked examples and brute-force verification live. This package is the simplified PyPI form; together they form the full picture (origin

• polished form):

• Tutorial: docs/getting-started.md — 10-minute walkthrough.
• Originality: docs/originality.md — what's genuinely new here (dart-chain corrected primitive, basis-aware rank ≤ 2, diagnostic-layer triad).
• Concepts: docs/concepts/ — Holant problems, the tier hierarchy, the four coordinates, the paradigm.
• Cookbook: docs/cookbook/ — domain recipes.
• Reference: docs/reference/ — API specs.
• Glossary + FAQ: docs/glossary.md, docs/faq.md.

Scope

The framework's exact polynomial-time answers apply natively to problems with the right structural shape: planar, bounded-genus, matchgate-Holant- family, GF(2)-affine. The active development direction is the reduction / composition / recursive-decomposition layer that brings problems that don't look like this shape into it:

• Reductions — one-shot transformations: crossing-elimination gadgets, basis changes, hybrid planar/non-planar decompositions, parity-split, high-degree-vertex splitting, semiring choice, and the rest of the holographic-algorithm transformation arsenal.
• Compositions — combining two or more in-family evaluations to compute an out-of-family quantity: linear combinations, projections of joint distributions, conditional compositions, tensor/Cartesian products, polynomials in matchgate values, holographic-basis pairs (Valiant 2004's central technique), branch-sum recombinations.
• Recursive decomposition — recursively split a problem into sub-problems, base case in-family: tree-decomposition / treewidth- bounded dynamic programming, planar-separator divide-and-conquer, tensor-network contraction in the right order, Shannon expansion (branch on a variable, recurse on each branch), circuit-cutting followed by per-block recursive routing.

When the problem is in-shape (or reducible / composable / recursively- decomposable to in-shape), the framework produces exact, bit-identical answers in milliseconds-to-seconds.

When a problem is genuinely beyond reach (continuous mathematics with no discretisation, unbounded matchgate rank with no decomposition, etc.) and no known reduction or composition fits, the framework honestly stops and advises the right external tool. No silent approximation.

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 0.6.0a1, 2026.
https://github.com/pcoz/structural-computing

Roadmap

• v0.3.0a1: closed the calibration loop (route's cost field is log2(seconds) when calibrated, with cost_unit meter always present), shipped the holographic toolkit (HolographicBasisPair.transform_signature_general for non-symmetric signatures, discover_basis + discover_common_basis for Cai-Lu SRP single- and multi-signature), and filled in every v0.2-era NotImplementedError sketch (Projection, BranchSum, PlanarSeparator, RecursiveCircuitCut). 229 tests passing.
• v0.4.0a1: matchgate-identity (MGI) realisability check for general (non-symmetric) signatures via holant_tools.non_symmetric; PlanarSeparator(auto=True) mode invoking the simple BFS-layer case of Lipton-Tarjan 1979; closed-form SRP shortcut catching rank-1 signatures whose recurrence roots lie outside the v0.3 search's [-2, +2] grid. 262 tests passing.
• v0.5.0a1: full Cai-Lu §4 d-admissibility at even arity ≥ 6 odd-parity (augmented-Pfaffian Plücker enumeration on the (n+1)-vertex Kasteleyn matrix, |S|=2 case, prototype-in-place); spanning-tree fundamental-cycle backup for Lipton-Tarjan when the BFS-layer simple case fails on fat-middle-level planar graphs; closed-form SRP for complex-roots rank-2 signatures via T = [[1, -α], [0, β]]. 272 tests passing.
• v0.6.0a1 (current): D1 promoted the v0.5 augmented-Plücker helper to holant-tools v0.6.0 (architectural cleanup, math primitive now lives in the engine); D2 added a level-based + articulation-augmentation backup to _lipton_tarjan_separator catching star K_{1,n} and K_{2,n} adversarial graphs; D3 extended the augmented-Plücker enumeration with the m = 3 (|S|=4) configuration via holant-tools v0.6.1 (count at arity 8: 280 → 560; at arity 10: 1260 → 5460). 281 tests passing.
• v0.7.0 (next): higher-m augmented Plücker configurations (m = 5 at arity ≥ 10, m = 7 at arity ≥ 12, ...); full Lipton-Tarjan 1979 backup with planar-dual fundamental-cycle counting (for adversarial cases the v0.6 simplification can't bound); tropical optimisation (NEXT.md §δ) and/or CP-SAT diagnostic layer (§ε) as research-track extensions; PyPI publication.
• v1.0.0: API stability contract; production-ready for downstream packages.