Fix #244: Add IsomorphicSpanningTree model by zazabap · Pull Request #612 · CodingThrust/problem-reductions

zazabap · 2026-03-12T14:44:19Z

Summary

Add the IsomorphicSpanningTree satisfaction problem model: given a graph G and a tree T with |V(G)| = |V(T)|, determine if G contains a spanning tree isomorphic to T.

This is a classical NP-complete problem (Garey & Johnson ND8) that generalizes Hamiltonian Path.

Fixes #244

Co-Authored-By: Claude Opus 4.6 <[email protected]>

codecov · 2026-03-12T14:46:46Z

Codecov Report

❌ Patch coverage is 97.24907% with 37 lines in your changes missing coverage. Please review.
✅ Project coverage is 96.81%. Comparing base (e652ba6) to head (85012bf).
⚠️ Report is 14 commits behind head on main.

Files with missing lines	Patch %	Lines
src/models/graph/subgraph_isomorphism.rs	83.60%	10 Missing ⚠️
src/models/graph/isomorphic_spanning_tree.rs	88.40%	8 Missing ⚠️
src/canonical.rs	0.00%	5 Missing ⚠️
src/models/graph/minimum_feedback_arc_set.rs	93.22%	4 Missing ⚠️
src/expr.rs	86.95%	3 Missing ⚠️
src/models/graph/hamiltonian_path.rs	93.02%	3 Missing ⚠️
src/models/misc/flow_shop_scheduling.rs	95.58%	3 Missing ⚠️
src/rules/analysis.rs	0.00%	1 Missing ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #612      +/-   ##
==========================================
+ Coverage   96.79%   96.81%   +0.01%     
==========================================
  Files         230      244      +14     
  Lines       30310    31650    +1340     
==========================================
+ Hits        29339    30642    +1303     
- Misses        971     1008      +37

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

Implements the Isomorphic Spanning Tree decision problem: given a graph G and a tree T with |V(G)| = |V(T)|, determine if G contains a spanning tree isomorphic to T. NP-complete (Garey & Johnson ND8). - Model with SatisfactionProblem (Metric = bool), permutation-based config - Constructor validates tree connectivity and edge count - CLI support with --graph and --tree flags - 11 unit tests covering evaluation, solver, serialization, edge cases Co-Authored-By: Claude Opus 4.6 <[email protected]>

Co-Authored-By: Claude Opus 4.6 <[email protected]>

zazabap · 2026-03-12T14:52:49Z

Implementation Summary

Changes

src/models/graph/isomorphic_spanning_tree.rs — New satisfaction problem model with permutation-based configuration space
src/unit_tests/models/graph/isomorphic_spanning_tree.rs — 11 tests (evaluation, solver, serialization, edge cases, caterpillar example from issue)
src/models/graph/mod.rs, src/models/mod.rs, src/lib.rs — Module and prelude registration
problemreductions-cli/src/dispatch.rs — Load/serialize dispatch
problemreductions-cli/src/problem_name.rs — Alias resolution
problemreductions-cli/src/commands/create.rs — CLI creation with --graph and --tree flags
problemreductions-cli/src/cli.rs — New --tree flag and help table entry
docs/src/reductions/problem_schemas.json — Regenerated schemas

Deviations from Plan

Skipped paper documentation (no reduction rules to document yet; problem-def can be added when reductions are implemented)
Used num_vertices^num_vertices for complexity (n^n upper bound on brute-force over all mappings)

Open Questions

None

…spanning-tree

Copilot

Copilot encountered an error and was unable to review this pull request. You can try again by re-requesting a review.

zazabap · 2026-03-13T14:52:54Z

Review Pipeline Report

Check	Result
Merge with main	3 conflicts resolved, build verified
Copilot comments	Copilot errored, no actionable comments
Issue/human comments	3 checked, 0 requiring fixes
CI	green (all checks pass)
Agentic test	passed — API and CLI work correctly
Board	review-agentic → In Review

Agentic Test Notes

Positive/negative/edge cases all pass via API
CLI create + solve --solver brute-force works correctly
Minor: default ILP solver gives unhelpful error (no reduction path) — expected since IST has 0 reductions
Minor: cannot create edgeless graphs via CLI

🤖 Generated by review-pipeline

* Add plan for #412: ShortestCommonSupersequence model * Implement #412: Add ShortestCommonSupersequence model * style: apply rustfmt formatting * Address review: fix docs, add --alphabet-size flag, add edge case tests * chore: remove plan file after implementation * Address Copilot review comments - Align docs/schema wording: bound is exact config length, equivalent to |w| ≤ B via padding - Add alphabet_size > 0 validation in constructor - Handle empty string segments in --strings CLI parsing - Add --alphabet-size to CLI help text - Regenerate problem_schemas.json Co-Authored-By: Claude Opus 4.6 <[email protected]> * Fix agentic test issues: add SCS to prelude, fix CLI duplicate fields - Add ShortestCommonSupersequence to prelude re-exports (was missing unlike all other misc models) - Fix duplicate CLI struct fields (strings, bound) by sharing between LCS/SCS and RuralPostman/SCS with i64 type and casts at usage sites Co-Authored-By: Claude Opus 4.6 <[email protected]> * chore: trigger CI Co-Authored-By: Claude Opus 4.6 <[email protected]> * style: apply rustfmt formatting Co-Authored-By: Claude Opus 4.6 <[email protected]> --------- Co-authored-by: Claude Opus 4.6 <[email protected]> Co-authored-by: GiggleLiu <[email protected]>

* Add plan for #507: FlowShopScheduling model * Implement #507: Add FlowShopScheduling model Co-Authored-By: Claude Opus 4.6 <[email protected]> * chore: remove plan file after implementation * fix: address Copilot review comments on FlowShopScheduling - Switch dims() from vec![n;n] to Lehmer code encoding [n,n-1,...,1] - Update evaluate() to decode Lehmer code into permutations - Fix complexity from "3^num_jobs" to "num_jobs^num_jobs" - Add validation to compute_makespan() for out-of-bounds indices - Add --num-processors CLI flag instead of overloading --m - Validate task_lengths row lengths in CLI with bail! instead of panic - Fix test comment about deadline value Co-Authored-By: Claude Opus 4.6 <[email protected]> * docs: add Lehmer code encoding explanation to FlowShopScheduling Add concrete example of how Lehmer code configs map to job orderings in the struct doc comment, improving discoverability for new users. Co-Authored-By: Claude Opus 4.6 <[email protected]> * fix: remove unused enumerate in Lehmer code decoding Fixes clippy::unused_enumerate_index warning. Co-Authored-By: Claude Opus 4.6 <[email protected]> * fix: add missing paper section, trait_consistency entry, and correct complexity - Add FlowShopScheduling problem-def and display-name to docs/paper/reductions.typ - Add FlowShopScheduling to trait_consistency test - Fix complexity from "num_jobs^num_jobs" to "factorial(num_jobs)" (n! is the exact search space) - Relax check_problem_trait assertion from >= 2 to >= 1 (Lehmer code encoding produces trailing dim of 1) Co-Authored-By: Claude Opus 4.6 <[email protected]> * docs: add Gantt chart visualization and use issue's 5-job example in paper Replace the simple 2-machine example with the issue's canonical 3-machine, 5-job example. Add a CeTZ Gantt chart showing the feasible schedule with job order (j4, j1, j5, j3, j2) achieving makespan 23 within deadline 25. Co-Authored-By: Claude Opus 4.6 <[email protected]> --------- Co-authored-by: Claude Opus 4.6 <[email protected]> Co-authored-by: GiggleLiu <[email protected]>

Resolve merge conflicts to include both IsomorphicSpanningTree (this PR) and HamiltonianPath, SubgraphIsomorphism, etc. (from main). Co-Authored-By: Claude Opus 4.6 <[email protected]>

…IsomorphicSpanningTree - Add display-name and problem-def entry in docs/paper/reductions.typ with formal definition, background (Garey & Johnson ND8), and CeTZ figure - Add bibliography entry for Papadimitriou & Yannakakis 1982 - Add check_problem_trait for IsomorphicSpanningTree in trait_consistency.rs - Apply cargo fmt formatting fixes from merge Co-Authored-By: Claude Opus 4.6 <[email protected]>

Add plan for #244: [Model] IsomorphicSpanningTree

7f97359

Co-Authored-By: Claude Opus 4.6 <[email protected]>

zazabap and others added 2 commits March 12, 2026 14:52

chore: remove plan file after implementation

fc679af

Co-Authored-By: Claude Opus 4.6 <[email protected]>

Merge remote-tracking branch 'origin/main' into issue-244-isomorphic-…

a707074

…spanning-tree

zazabap requested a review from Copilot March 12, 2026 16:07

Copilot AI reviewed Mar 12, 2026

View reviewed changes

Merge origin/main into issue-244-isomorphic-spanning-tree

9995c52

zazabap and others added 4 commits March 14, 2026 01:38

Merge origin/main into issue-244-isomorphic-spanning-tree

da6c21c

Resolve merge conflicts to include both IsomorphicSpanningTree (this PR) and HamiltonianPath, SubgraphIsomorphism, etc. (from main). Co-Authored-By: Claude Opus 4.6 <[email protected]>

GiggleLiu merged commit 31ed79e into main Mar 13, 2026
3 checks passed

GiggleLiu deleted the issue-244-isomorphic-spanning-tree branch April 12, 2026 00:53

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Fix #244: Add IsomorphicSpanningTree model#612

Fix #244: Add IsomorphicSpanningTree model#612
GiggleLiu merged 9 commits intomainfrom
issue-244-isomorphic-spanning-tree

zazabap commented Mar 12, 2026

Uh oh!

codecov bot commented Mar 12, 2026 •

edited

Loading

Uh oh!

zazabap commented Mar 12, 2026

Uh oh!

Copilot AI left a comment

Uh oh!

zazabap commented Mar 13, 2026

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Conversation

zazabap commented Mar 12, 2026

Summary

Uh oh!

codecov bot commented Mar 12, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

zazabap commented Mar 12, 2026

Implementation Summary

Changes

Deviations from Plan

Open Questions

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Uh oh!

zazabap commented Mar 13, 2026

Review Pipeline Report

Agentic Test Notes

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

codecov bot commented Mar 12, 2026 •

edited

Loading