Crate fnx_cgse 

Canonical Graph Semantics Engine (CGSE)

Deterministic tie-break policies with complexity witness artifacts per algorithm family. This is FrankenNetworkX’s crown-jewel innovation: every algorithm declares its ordering policy at the type level, and every execution emits a cryptographic witness that proves which tie-break decisions were taken.

Architecture

• TieBreakPolicy: closed sum type with 13 named ordering variants.
• ComplexityWitness: per-execution record carrying (n, m, observed_ops, policy_id, decision_path_blake3).
• WitnessSink: thread-local collector that algorithms call on every tie-break decision.
• WitnessLedger: append-only log of witnesses, serializable to JSONL with RaptorQ sidecar support.

Structs

AlgorithmFamilyPolicy

Declares the canonical tie-break policy for an algorithm family.

ComplexityBoundResult

Result of complexity bound verification.

ComplexityWitness

A per-execution record emitted by every CGSE-instrumented algorithm.

CounterExample

A counter-example candidate found during witness-hash mining.

MiningConfig

Configuration for counter-example mining.

MiningResult

Result of a counter-example mining session.

WitnessLedger

Append-only ledger of ComplexityWitness records.

WitnessSink

Collects tie-break decisions during a single algorithm execution.

Enums

ReferenceAlgorithm

The V1 reference algorithms whose call sites are wired through CGSE.

TieBreakPolicy

The 13 canonical tie-break orderings that NetworkX algorithms exhibit.

Functions

analytic_upper_bound

Evaluate the analytic upper bound for a complexity class.

assert_complexity_within_bounds

Complexity oracle assertion: panic if witness exceeds expected bounds.

collect_witnesses

Run a closure with CGSE witness collection enabled and return the drained witnesses produced inside it.

compare_witnesses

Compares two witnesses for consistency.

drain_witnesses

Drain and return all witnesses from the thread-local ledger.

generate_random_edges

Generates random graph edges for testing.

mining_result_to_jsonl

Serializes a mining result to JSONL format.

v1_policy_registry

The canonical policy registry for V1 algorithms.

verify_complexity_bound

Verify that a witness’s observed count is within the expected complexity bounds. Returns a result indicating whether the count is acceptable.

verify_witness_determinism

Verifies witness determinism by running the same algorithm multiple times and checking for hash consistency.

with_ledger

Execute a closure with access to the thread-local witness ledger.

witness_collection_enabled

Return whether CGSE witness collection is active for the current thread.