[Tech debt]: Use NetworkX’s maintained graph6 codec instead of duplicating the parser in the producer

[morluto]

Summary

Draft PR #983 adds graph.encoding.graph6.decode.compute by implementing the graph6 format twice:

• the producer manually decodes the header, six-bit characters, order, length, padding, column-major upper-triangle bits, edge list, degrees, and digest;
• the independent checker repeats essentially the same bitstream parser.

The independent checker may legitimately retain a separate small replay implementation. The producer should not: Jacobian already depends on NetworkX, and NetworkX 3.6.1 exposes a maintained pure-Python graph6 codec through networkx.from_graph6_bytes() / to_graph6_bytes().

This is a concrete example of the anti-pattern tracked broadly in #699: reimplementing a maintained backend operation while increasing the code and review surface that must be independently proven.

Evidence

PR #983 adds approximately the following producer path in src/jacobian/domains/graph_optimization/invariants.py:

codes = [ord(character) - 63 for character in value]
order = codes[0]
bit_count = order * (order - 1) // 2
bits = [
    (code >> shift) & 1
    for code in codes[1:]
    for shift in range(5, -1, -1)
]
pairs = [
    (first, second)
    for second in range(1, order)
    for first in range(second)
]
edges = ...

src/jacobian_checkers/graph_exact_operations.py then adds another copy of the same algorithm.

NetworkX’s maintained implementation already:

• handles the optional >>graph6<< header;
• validates the character range;
• decodes one-, four-, and eight-unit order headers;
• validates the encoded length;
• uses the standard column-major upper-triangle ordering;
• returns a simple undirected graph;
• supports round-trip encoding through to_graph6_bytes().

Official documentation/source:

• https://networkx.org/documentation/stable/reference/readwrite/generated/networkx.readwrite.graph6.from_graph6_bytes.html
• https://networkx.org/documentation/stable/reference/readwrite/generated/networkx.readwrite.graph6.to_graph6_bytes.html
• https://networkx.org/documentation/stable/_modules/networkx/readwrite/graph6.html

NetworkX is already a core graph-domain dependency and provider in Jacobian; this does not add a new backend.

Why the current implementation is riskier

Two parser implementations must remain specification-equivalent

Both copies need the same decisions for:

• headers and newline handling;
• small versus extended order encodings;
• invalid character boundaries;
• exact length and unused padding bits;
• edge iteration order;
• canonical normalization;
• malformed sparse6/digraph6 rejection.

Any future format extension or bug fix becomes a coordinated producer/checker edit.

The producer’s advertised scope and parser behavior are entangled

The proposed capability intentionally supports only orders 0..62. That is a product scope decision; it need not be encoded by rejecting graph6’s maintained extended-order parser. The simpler boundary is:

maintained graph6 parse
→ explicit Jacobian order/resource preflight (`n <= 62`)
→ canonical graph projection

This keeps format correctness and capability resource policy separate.

Reimplementing in both producer and checker does not improve independence

Independent verification requires the checker not to trust the producer’s result or algorithm. It does not require the producer to avoid a maintained parser.

A sound split is:

• producer: NetworkX codec, then Jacobian-owned bounded/canonical projection;
• checker: separate stdlib bitstream replay (or another independently pinned codec), bound to the exact input/result contract.

That preserves implementation diversity while removing one unnecessary parser.

Proposed implementation

Producer

Use the maintained decoder and a strict canonical round trip:

import networkx as nx

raw = normalized_graph6.encode("ascii")
graph = nx.from_graph6_bytes(raw)

if len(graph) > 62:
    return unsupported_scope(...)

canonical = nx.to_graph6_bytes(graph, header=False).rstrip(b"\n")
if canonical != raw_without_optional_header:
    return malformed_or_noncanonical(...)

Then construct Jacobian’s typed result from:

• sorted(graph.edges());
• [graph.degree(i) for i in range(len(graph))];
• the existing canonical graph digest.

The round-trip equality preserves stricter requirements not necessarily rejected by the reader alone, including canonical small-order encoding and zero padding.

Decide explicitly whether a trailing newline is accepted/normalized or rejected; follow NetworkX’s documented behavior rather than implementing an accidental third convention.

Checker

Keep the checker’s independent stdlib replay if the project values implementation diversity. Move its duplicated wire-contract validation under #1110’s generated passive checker contract, leaving only the graph6 mathematics/bitstream replay in checker code.

Tests

Differentially test the producer against NetworkX and the independent checker across:

• every order 0..62 at boundaries 0, 1, 2, 62;
• optional standard header;
• random simple graphs and round trips;
• all invalid ASCII boundaries;
• sparse6 and digraph6 prefixes;
• incorrect encoded length;
• nonzero padding;
• trailing newline policy;
• extended-order input rejected by the capability scope even though the codec can parse it;
• the H24 reproduction from Add canonical graph6 decoding and bound graph-invariant certificates #947;
• mutation of one edge/degree/digest in the candidate.

Property tests can generate NetworkX graphs, encode them using to_graph6_bytes, and require the Jacobian producer and independent checker to agree.

Acceptance criteria

• The producer calls NetworkX’s maintained graph6 decoder rather than owning another bitstream parser.
• The order-62 capability bound is explicit operation policy, not a limitation of a local parser.
• Canonical header/newline/padding behavior is documented and enforced by a round trip or equivalent maintained-code check.
• The checker remains independent from the producer and still rejects structurally valid but incorrect candidates.
• Differential/property tests cover the full small-order boundary and malformed encodings.
• No new optional nauty dependency or external process is introduced.

Non-goals

• Removing the graph6 capability.
• Depending on the nauty executable.
• Using NetworkX in the independent checker if that would collapse desired implementation diversity.
• Broadening the public capability to extended-order graph6, sparse6, or digraph6 in this change.
• Treating successful decoding as verification of any downstream graph invariant.

Related

• PR Add canonical graph6 decoding and verification #983 — current draft implementation.
• Add canonical graph6 decoding and bound graph-invariant certificates #947 — capability request and H24 reproduction.
• [Tech debt]: Hand-rolled linear algebra and combinatorial algorithms with maintained-library equivalents #699 — broader audit of hand-rolled mathematical/graph algorithms.
• [Architecture]: Stop reimplementing producer wire contracts inside clean-room checkers #1110 — generated passive wire contracts for clean-room checkers.