# Graph assembly algorithm — Seet et al. (2025) Publication-based implementation record, started 2026-09-19 before code. The independent C++17 implementation is in `solvers/seet/`, deployed through the fixed `seet-2025` registry entry after native/API/browser checks. Native/API checks are recorded below; the live deployment and browser verification log is in [VERIFICATION.md](../VERIFICATION.md). ## Sources and provenance - Seet, Patarroyo, Siebert, Walker and Cronin, *Rapid Exploration of the Assembly Chemical Space of Molecular Graphs*, DOI [10.1021/acs.jcim.5c01964](https://doi.org/10.1021/acs.jcim.5c01964), published 7 December 2025. Reviewed the Definitions, Data Structures, Algorithm, Branch-and-Bound Heuristic (Eqs. 3–6), Fragmentation, Assembly State Hashing, and Recursion and Pathway Generation sections, including both algorithm figures. [Author-deposited PDF](https://eprints.gla.ac.uk/372619/1/372619.pdf), SHA-256 `1256ddc96fc0162e33492aaabcafee8b70222341bfcca8ca70445f69901be3b5`. - [Supplement, Section 1, Algorithm A1 and Fig. A1](https://doi.org/10.1021/acs.jcim.5c01964.s001), [publisher file](https://ndownloader.figshare.com/files/60171252), SHA-256 `6cb34722acf468307497bb10ea3cabf6a191fe6789b1a072ca572140fec3ee66`. The six-page supplement was read; reconstruction figures were inspected. - The main article is CC BY 4.0. The publisher's supplement metadata separately specifies **CC BY-NC 4.0** (Figshare article 30815358, version 1). Associated assemblycpp-v5 source was previously recorded as CC BY-NC 4.0. These licenses govern the corresponding expression/assets, not an automatic license for an independently written algorithm implementation. No paper figure, pseudocode transcription or upstream solver source is included in the implementation. This is an engineering provenance record, not patent clearance/legal advice. - Prior project research inspected other upstream implementations; this work is publication-based independent code, not a claimed clean-room implementation. - Cyclic graph equality uses Boost.Graph's VF2 implementation, under the Boost Software License, already compatible with this project's Boost dependency. [VF2 interface](https://www.boost.org/doc/libs/1_83_0/libs/graph/doc/vf2_sub_graph_iso.html). A separately written labelled-tree encoding handles acyclic fragments, as in the publication's tree-isomorphism/VF2 distinction. ## Scope and conventions Display name: **Graph assembly algorithm — Seet et al. (2025)**. “Graph assembly algorithm” is the paper's descriptive name; “duplicate-removal” describes its search representation. This C++17 baseline implements the simple conditional addition-chain bound of Eqs. 3–4. The optional refined bound in the paragraph after Eq. 6 and a precomputed addition-chain table are not this variant. Input is the app's connected, element/bond-order-labelled molecular graph. The paper's chemical examples exclude hydrogen vertices; the shared graph input preserves whatever vertices were supplied, including explicit hydrogens. Results therefore apply to that exact supplied graph; literature benchmarks require its matching heavy-atom representation. No hydrogen/aromatic/charge normalization occurs. Strings and arbitrary supplied assembly spaces retain their existing methods; this molecular specialization has no invented string adaptation. ## Independent mathematical specification Represent an occurrence by a target-edge bitset. Enumerate candidate occurrences by increasing edge count, growing each connected occurrence by one adjacent edge. Group by exact element/order-preserving isomorphism. Retain occurrences with a disjoint equal-type partner; only these need further growth. Remove unique bond types before growth. Retain each occurrence's first encountered growth parent as a reusable occurrence DAG. Parent containment is a necessary condition for child containment in every later state. Enumeration must finish before any proof. The search state holds connected edge masks, a last-duplicate ordering key, the distinguished retained occurrence, accumulated savings S, and a parent/removal history. Types are ordered by size, then deterministic discovery ID. Evaluate types largest-first and only at/below the last key. For a disjoint equal-type pair A,B, each wholly inside a current piece, detach A, remove B, split the remaining edges into connected components, and add |B|−1 to S. Both orientations are considered. The initial bound for an N-edge connected target is N−1; maximizing S minimizes this count. Candidate-edge pruning removes edges participating in no remaining allowed pair, retaining the full history for reconstruction. For component sizes L_i and largest allowed duplicate size m, the remaining savings bound is the maximum over 2 ≤ x ≤ m of -ceil(log2(x)) + sum_i (L_i - ceil(L_i / x)). Zero also represents stopping without another removal. Use integer arithmetic. Apply this bound before component splitting and again afterward. Sorted edge masks plus the distinguished last duplicate/key identify a cached state; retain the largest S, and revisit only when S improves. Hash equality alone never establishes state/graph equality. Do not seed this search with another algorithm or use incidental extra reuse found during rendering to strengthen its bound. Reconstruct with the supplement's bag-of-pieces procedure: start with residual edges, construct the smallest retained duplicate from its pieces, insert its recorded copy, and continue upward; finally join the remaining adjacent pieces. Store one producing join per type in the common witness. The shared certificate checker verifies all joins, embeddings, basis and target. The exact claim requires complete enumeration/search plus agreement between the optimized saving and the checked witness count. Any interruption retains only a previously checked upper bound, with exact=false. Unspecified deterministic choices: ascending input-edge masks within a size, first-discovered type IDs for equal-size order, both keep/remove orientations, sorted remnant masks, and the first adjacent bag pair when reconstructing. These choices do not introduce multistart, an extra pruning rule or our producing-join solver's heuristics. Runtime/output equality with the authors' package is not asserted. Every checkpoint counts startup, preprocessing and certificate work within the same deadline. ## Verification gate Before enabling: independently enumerate small connected subgraphs/matching pairs; check tree/VF2 identity against the existing canonicalizer; compare search optima against an independent subset-of-types assembly-space oracle; verify bound admissibility on reachable states; test nested/remnant reconstruction, element/order sensitivity, reorderings, elementary targets, timeout/memory/output limits, and the common CLI/API protocol. Compare bounds-on vs bounds-off and cache-on vs cache-off in the test harness only, not as silent published variants. Verified native/API coverage (2026-09-19): - 3,298 C++ assertions: complete small-space oracle through four vertices; 100 deterministic random five-vertex labelled/bond-order cases; exact matching against exhaustive connected subsets; tree/VF2 identity versus the existing exact canonicalizer; cyclic shared-vertex duplicates and edge reorderings. - An independent removal oracle checks the conditional bound over every bipartition of the cyclic fixture and ten random fixtures. Complete search agrees with bounds/cache/fragment pruning disabled in test-only ablations. - Native CLI tests cover elementary targets and chains through 64 bonds, checked progress/result certificates, deadlines during enumeration, SIGTERM, output/memory limits, serial allocation and invalid/input-kind rejection. The sanitizer build uses a 60-second chain-test allowance because instrumentation made that proof exceed the original 10-second test budget; production limits and interrupted-result semantics are unchanged. - Independent Python validation of every returned certificate across all 28 palette molecules, including time-limited large molecules. Separate API tests check the three-method comparison's input identity, allocations, proofs and paths, sequential/parallel execution, cancellation and rejection of late, wrong-method, invalid-phase or unfinished-branch proof events. - Release OpenMP/MPI 9/9; serial Release 7/7; serial ASan/UBSan 7/7. The full Python/API suite passes 314 tests, including the original general-object core. These checks support the implementation, not a claim that the authors' package has identical tie choices, output paths, timings or measured performance. ## Separately labelled parallel execution The 2026-09-21 OpenMP/MPI implementation uses ID `seet-2025-parallel` and separate executables. The serial baseline and its registry identity remain unchanged. [SEET_PARALLEL.md](SEET_PARALLEL.md) documents continuation ownership, shared validated incumbents, global proof termination, per-rank resource controls, the replicated serial-enumeration limitation, and verification. This is our execution extension of the independently implemented method, not code from the authors' package or a newly attributed publication variant.