Refactor: address KISS and DRY violations (#70) by GiggleLiu · Pull Request #71 · CodingThrust/problem-reductions

GiggleLiu · 2026-02-15T14:50:18Z

Summary

DRY Roadmap #1: Trim duplicated delegation methods from 5 graph problem structs (~325 lines removed) — callers use problem.graph().method() directly
DRY Implement remaining reduction rules #2: Implement BipartiteGraph and PlanarGraph as validated SimpleGraph wrappers with proper VariantParam registration
KISS feat: Feature parity with ProblemReductions.jl #4: Extract classify_problem_category, filter_redundant_base_nodes, and is_natural_edge helpers from the 190-line to_json() monolith
Docs: Polish design.md with variant system section, lattice diagrams, and improved trait hierarchy visuals
Style: Apply rustfmt formatting across touched files

Closes #70

Test plan

All 1487 unit tests pass
All 47 doc tests pass
Clippy clean (zero warnings)
CI passes

🤖 Generated with Claude Code

Remove delegation methods (num_vertices, num_edges, edges, has_edge, set_weights, from_graph_unit_weights) from MaximumIndependentSet so callers go through .graph() directly. Rename weights_ref() to weights() returning &[W] instead of &Vec<W>. Co-Authored-By: Claude Opus 4.6 <[email protected]>

Remove num_vertices(), num_edges(), edges(), has_edge(), set_weights(), from_graph_unit_weights(), and cloning weights() from MinimumVertexCover. Rename weights_ref() to weights() returning &[W]. Callers now access graph topology via .graph() and get weights by reference. Co-Authored-By: Claude Opus 4.6 <[email protected]>

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

Replace the ZST marker in graph_types.rs with a real BipartiteGraph implementation in src/topology/ that stores left/right partition sizes and edges in bipartite-local coordinates. The Graph trait maps to a unified vertex space where right vertices are offset by left_size. Co-Authored-By: Claude Opus 4.6 <[email protected]>

Allow KSatisfiability<KN> construction by skipping clause-length validation when K::K is None, enabling the natural K3→KN widening step. Replace the short chaining example in getting-started.md with a richer 3-SAT→SAT→MIS pipeline that demonstrates ReductionGraph path planning, variant casts, and ILPSolver extraction. Co-Authored-By: Claude Opus 4.6 <[email protected]>

Replace the ZST marker PlanarGraph in graph_types.rs with a real topology type that wraps SimpleGraph and validates the necessary planarity condition |E| <= 3|V| - 6 for |V| >= 3. Co-Authored-By: Claude Opus 4.6 <[email protected]>

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

Rewrite design.md with clearer structure: add variant system section, lattice diagrams, and improved trait hierarchy visuals. Update Makefile diagram target to support --root flag. Co-Authored-By: Claude Opus 4.6 <[email protected]>

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

codecov · 2026-02-15T14:54:08Z

Codecov Report

❌ Patch coverage is 97.00000% with 15 lines in your changes missing coverage. Please review.
✅ Project coverage is 96.77%. Comparing base (a4264a6) to head (9135218).
⚠️ Report is 1 commits behind head on main.

Files with missing lines	Patch %	Lines
src/topology/planar_graph.rs	72.41%	8 Missing ⚠️
src/topology/kings_subgraph.rs	0.00%	3 Missing ⚠️
src/rules/graph.rs	93.54%	2 Missing ⚠️
src/topology/bipartite_graph.rs	96.77%	2 Missing ⚠️

Additional details and impacted files

@@           Coverage Diff            @@
##             main      #71    +/-   ##
========================================
  Coverage   96.76%   96.77%            
========================================
  Files         185      189     +4     
  Lines       25789    25906   +117     
========================================
+ Hits        24955    25070   +115     
- Misses        834      836     +2

☔ 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.

Copilot

Pull request overview

Refactors the variant-aware reduction graph and several graph problem models to remove duplicated delegation APIs (KISS/DRY), while introducing validated topology wrappers (PlanarGraph, BipartiteGraph) and improving reduction-graph JSON generation + docs/diagrams.

Changes:

Remove duplicated graph/weight delegation methods from multiple graph problems; update call sites to use problem.graph().* and problem.weights().
Add PlanarGraph and BipartiteGraph as SimpleGraph-backed topology types with validation and VariantParam registration.
Extract filter_redundant_base_nodes, classify_problem_category, and is_natural_edge helpers; update docs/diagrams and formatting.

Reviewed changes

Copilot reviewed 71 out of 78 changed files in this pull request and generated 1 comment.

Show a summary per file

File	Description
tests/suites/reductions.rs	Update tests to use `graph()` accessors
tests/suites/integration.rs	Switch weighted tests to `with_weights`
src/unit_tests/unitdiskmapping_algorithms/weighted.rs	Rustfmt-only cleanup in tests
src/unit_tests/unitdiskmapping_algorithms/mapping_result.rs	Import ordering cleanup in tests
src/unit_tests/unitdiskmapping_algorithms/julia_comparison.rs	Formatting cleanup in assertions
src/unit_tests/unitdiskmapping_algorithms/gadgets_ground_truth.rs	Rustfmt cleanup for macros
src/unit_tests/topology/planar_graph.rs	Add unit tests for `PlanarGraph`
src/unit_tests/topology/bipartite_graph.rs	Add unit tests for `BipartiteGraph`
src/unit_tests/rules/unitdiskmapping/triangular/mod.rs	Formatting cleanup in tests
src/unit_tests/rules/unitdiskmapping/triangular/mapping.rs	Formatting cleanup in tests
src/unit_tests/rules/sat_minimumdominatingset.rs	Update tests to use `graph()`
src/unit_tests/rules/sat_maximumindependentset.rs	Update tests to use `graph()`
src/unit_tests/rules/minimumvertexcover_maximumindependentset.rs	Update weights/graph assertions
src/unit_tests/rules/maximumindependentset_triangular.rs	Update tests to use `graph()`
src/unit_tests/rules/maximumindependentset_maximumsetpacking.rs	Update tests to use `graph()`
src/unit_tests/rules/maximumindependentset_gridgraph.rs	Update tests to use `graph()`
src/unit_tests/rules/maximumclique_ilp.rs	Update tests to use `graph()`/weights slice
src/unit_tests/rules/graph.rs	Add helper-focused tests for graph JSON export
src/unit_tests/models/satisfiability/ksat.rs	Add KN-focused tests
src/unit_tests/models/graph/minimum_vertex_cover.rs	Update tests to use `graph()`/weights slice
src/unit_tests/models/graph/minimum_dominating_set.rs	Update tests to use `graph()`/weights slice
src/unit_tests/models/graph/maximum_independent_set.rs	Update tests to use `graph()`/weights slice
src/unit_tests/models/graph/maximum_clique.rs	Update tests to use `graph()`/weights slice
src/unit_tests/models/graph/maximal_is.rs	Update tests to use `graph()`/weights slice
src/unit_tests/io.rs	Update IO tests to use `graph()`
src/unit_tests/graph_types.rs	Adjust tests for new topology types
src/unit_tests/graph_models.rs	Update tests to use `graph()`/weights slice
src/topology/planar_graph.rs	Introduce validated `PlanarGraph` wrapper
src/topology/mod.rs	Wire in new topology modules/exports
src/topology/kings_subgraph.rs	Formatting-only change
src/topology/bipartite_graph.rs	Introduce `BipartiteGraph` topology type
src/rules/unitdiskmapping/weighted.rs	Formatting-only change
src/rules/sat_ksat.rs	Formatting-only change
src/rules/minimumvertexcover_qubo.rs	Use `graph()` + weights slice
src/rules/minimumvertexcover_minimumsetcovering.rs	Use `graph()` + weights slice
src/rules/minimumvertexcover_maximumindependentset.rs	Use `graph()` + weights slice
src/rules/minimumvertexcover_ilp.rs	Use `graph()` + weights slice
src/rules/minimumdominatingset_ilp.rs	Use `graph()` accessor
src/rules/maximumindependentset_triangular.rs	Use `graph()` accessor
src/rules/maximumindependentset_qubo.rs	Use `graph()` + weights slice
src/rules/maximumindependentset_maximumsetpacking.rs	Use `graph()` + weights slice
src/rules/maximumindependentset_ilp.rs	Use `graph()` accessor
src/rules/maximumindependentset_gridgraph.rs	Use `graph()` accessor
src/rules/maximumclique_ilp.rs	Use `graph()` accessor
src/rules/graph.rs	Extract helpers used by `to_json()`
src/models/satisfiability/ksat.rs	Allow `KN` without clause-length validation
src/models/graph/minimum_vertex_cover.rs	Remove delegation APIs; expose weights slice
src/models/graph/minimum_dominating_set.rs	Remove delegation APIs; expose weights slice
src/models/graph/maximum_independent_set.rs	Remove delegation APIs; expose weights slice
src/models/graph/maximum_clique.rs	Remove delegation APIs; expose weights slice
src/models/graph/maximal_is.rs	Remove delegation APIs; expose weights slice
src/graph_types.rs	Remove Planar/Bipartite marker types
examples/reduction_satisfiability_to_minimumdominatingset.rs	Update example to use `graph()`
examples/reduction_satisfiability_to_maximumindependentset.rs	Update example to use `graph()`
examples/reduction_minimumvertexcover_to_qubo.rs	Update example to use `graph()`
examples/reduction_minimumvertexcover_to_minimumsetcovering.rs	Update example to use `graph()`
examples/reduction_minimumvertexcover_to_maximumindependentset.rs	Update example to use `graph()`
examples/reduction_minimumvertexcover_to_ilp.rs	Update example to use `graph()`
examples/reduction_minimumdominatingset_to_ilp.rs	Update example to use `graph()`
examples/reduction_maximumindependentset_to_qubo.rs	Update example to use `graph()`
examples/reduction_maximumindependentset_to_minimumvertexcover.rs	Update example to use `graph()`
examples/reduction_maximumindependentset_to_maximumsetpacking.rs	Update example to use `graph()`
examples/reduction_maximumindependentset_to_ilp.rs	Update example to use `graph()`
examples/reduction_maximumclique_to_ilp.rs	Update example to use `graph()`
examples/export_petersen_mapping.rs	Formatting-only change
examples/export_mapping_stages.rs	Formatting-only change
docs/src/static/variant-hierarchy.typ	Diagram layout tweak
docs/src/static/variant-hierarchy.svg	Regenerated diagram asset
docs/src/static/trait-hierarchy.typ	Update trait hierarchy diagram
docs/src/static/lattices.typ	New lattice/topology diagram source
docs/src/getting-started.md	Expand reduction chaining explanation
docs/src/design.md	Major variant/reduction graph doc refresh
Makefile	Adjust Typst diagram compilation

💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.

Copilot · 2026-02-15T15:03:19Z

src/unit_tests/rules/graph.rs

+    );
+    assert_eq!(
+        classify_problem_category("problemreductions::models::sat::satisfiability"),
+        "sat"
+    );
+    assert_eq!(
+        classify_problem_category("problemreductions::models::set::maximum_set_packing"),
+        "set"
+    );


test_classify_problem_category uses a module path containing models::sat::..., but the crate's models module is models::satisfiability (see existing test_category_from_module_path expectations). This makes the test (and/or the helper contract) inconsistent and likely failing. Update the test input to use problemreductions::models::satisfiability::... (or adjust classify_problem_category to intentionally map satisfiability -> sat, but then align the other tests and call sites).

The test used "models::sat" but the actual module is "models::satisfiability". Co-Authored-By: Claude Opus 4.6 <[email protected]>

Remove num_vertices() and num_edges() from KColoring, MaxCut, MaximumMatching, and TravelingSalesman. Callers now use graph().num_vertices() and graph().num_edges() via the Graph trait, matching the pattern established for MIS and other types in PR #71. Co-Authored-By: Claude Opus 4.6 <[email protected]>

* refactor: variant-level reduction graph with explicit cast reductions Replace auto-generated natural edges with explicit #[reduction] variant cast declarations. The reduction graph now uses variant-level nodes (each node is a unique problem_name + variant pair) with all edges coming from inventory registrations. Key changes: - Add impl_variant_reduction! macro: `Problem, <Src> => <Dst>, fields, closure` Single-arm design, works with any number of type parameters - Add ReductionOverhead::identity() for variant casts - Create 5 variant cast files (8 edges total) for KColoring, KSatisfiability, MaximumIndependentSet, MaximumSetPacking, SpinGlass - Refactor ReductionGraph from name-level to variant-level nodes - Remove old infrastructure: VariantTypeEntry inventory, build_variant_hierarchy, is_variant_reducible, EdgeKind::NaturalCast, resolve_path - Update docs: design.md, getting-started.md, introduction.md, reduction-graph.js - Interactive graph: dashed edges for variant casts (same name + identity overhead) Co-Authored-By: Claude Opus 4.6 <[email protected]> * feat: add DynReductionResult trait and reduce_fn to ReductionEntry Co-Authored-By: Claude Opus 4.6 <[email protected]> * refactor: store reduce_fn on graph edges alongside overhead Co-Authored-By: Claude Opus 4.6 <[email protected]> * refactor: variant-level ReductionPath, add ExecutablePath/ChainedReduction, remove Clone from ReductionResult - Make ReductionPath variant-level with Vec<ReductionStep> instead of Vec<&'static str> - Add type_names() method for backward-compatible name-level path access - Remove ResolvedPath and EdgeKind (superseded by variant-level ReductionPath) - Add ExecutablePath<S,T> for typed, executable reduction paths via find_executable_path() - Add ChainedReduction<S,T> for composing multi-step reductions at runtime - Remove Clone bound from ReductionResult trait (no callers clone through trait) - Remove #[allow(dead_code)] from reduce_fn now that it's used Co-Authored-By: Claude Opus 4.6 <[email protected]> * test: add variant cast path test for ChainedReduction Add test_chained_reduction_with_variant_casts that exercises find_executable_path across variant boundaries. Tests two paths: - MIS<UnitDiskGraph> -> MIS<SimpleGraph> (variant cast) -> MVC (reduction) - KSat<K3> -> Satisfiability -> MIS (multi-step cross-problem reduction) Both paths verify end-to-end correctness by solving the target problem and extracting/validating the solution in the source domain. Co-Authored-By: Claude Opus 4.6 <[email protected]> * docs: update getting-started and design for path-based reduction API Co-Authored-By: Claude Opus 4.6 <[email protected]> * fix: variant-aware find_cheapest_path API Rework find_cheapest_path to accept exact source and target variant maps, matching a single node on each end. This mirrors Julia's ProblemReductions.jl approach where path finding is always variant-aware. - Source: exact (name, variant) node — single Dijkstra start point - Target: exact (name, variant) node — single destination - Expose variant_to_map as pub(crate) for test ergonomics - Simplify Dijkstra: no outer loop over source nodes - Clarify find_best_entry fallback doc (intentional for export) - Fix test_find_direct_path to not depend on HashMap iteration order Co-Authored-By: Claude Opus 4.6 <[email protected]> * docs: reduce edge click area in reduction graph and use blue docs badge Shrink the interactive edge hit region by setting overlay-padding to 0 and edge width to 1px. Change the docs badge from green to traditional blue. Co-Authored-By: Claude Opus 4.6 <[email protected]> * refactor: replace find_executable_path with make_executable, unify Dijkstra - Extract shared `dijkstra(src, dst, ...)` taking NodeIndex directly - Add `lookup_node(name, variant)` as first-class node lookup - Add `make_executable(path)` to convert ReductionPath → ExecutablePath - Remove `find_executable_path` — callers now compose find + make_executable - Update docs and tests to use the new two-step pattern Co-Authored-By: Claude Opus 4.6 <[email protected]> * fix: improve downcast panic message with expected and actual type names Co-Authored-By: Claude Opus 4.6 <[email protected]> * feat: add chained reduction example with ILP solver, include in mdBook - Add examples/chained_reduction_ksat_to_mis.rs (KSat<K3> → MIS via ILP) - Use {{#include}} in getting-started.md to keep doc in sync with example - Make variant_to_map public for external use - Fix latent bug: use find_cheapest_path for variant-exact matching (find_shortest_path is name-based and may cross variant boundaries) Co-Authored-By: Claude Opus 4.6 <[email protected]> * fix: resolve PR review comments for path safety and KColoring KN runtime - dijkstra: return None on inconsistent predecessor map instead of partial path - make_executable: return None for paths with <2 steps (no edges) - KColoring: add num_colors field so KN variant carries runtime k value - Update coloring_ilp and coloring_qubo to use stored num_colors Co-Authored-By: Claude Opus 4.6 <[email protected]> * refactor: restrict from_graph_with_k to KColoring<KN> only Prevents type parameter / field inconsistency by making from_graph_with_k a compile error for concrete K types (K3, K4, etc.). Co-Authored-By: Claude Opus 4.6 <[email protected]> * refactor: remove redundant graph accessor methods from problem types Remove num_vertices() and num_edges() from KColoring, MaxCut, MaximumMatching, and TravelingSalesman. Callers now use graph().num_vertices() and graph().num_edges() via the Graph trait, matching the pattern established for MIS and other types in PR #71. Co-Authored-By: Claude Opus 4.6 <[email protected]> * docs: update design.md for current find_cheapest_path signature - Fix find_cheapest_path signature: now takes separate name + variant BTreeMap instead of (name, graph_type) tuple - Fix executable path example: use find_cheapest_path with variant maps instead of find_shortest_path (which can pick wrong variants) Co-Authored-By: Claude Opus 4.6 <[email protected]> --------- Co-authored-by: Claude Opus 4.6 <[email protected]>

GiggleLiu and others added 14 commits February 15, 2026 21:37

refactor: trim MaximumClique API — remove delegation methods

2d33c81

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

refactor: trim MaximalIS API — remove delegation methods

4efcc6c

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

refactor: trim MinimumDominatingSet API — remove delegation methods

d0201c7

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

refactor: extract classify_problem_category from to_json()

1dda66d

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

refactor: extract filter_redundant_base_nodes from to_json()

2d54990

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

refactor: extract is_natural_edge from to_json()

7069d4f

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

style: apply rustfmt formatting

6ef7d5a

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

docs: polish design.md and update diagrams

c3257ca

Rewrite design.md with clearer structure: add variant system section, lattice diagrams, and improved trait hierarchy visuals. Update Makefile diagram target to support --root flag. Co-Authored-By: Claude Opus 4.6 <[email protected]>

chore: remove plan files

cb28377

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

GiggleLiu requested a review from Copilot February 15, 2026 14:56

Copilot started reviewing on behalf of GiggleLiu February 15, 2026 14:57 View session

Copilot AI reviewed Feb 15, 2026

View reviewed changes

fix: use correct module path in test_classify_problem_category

9135218

The test used "models::sat" but the actual module is "models::satisfiability". Co-Authored-By: Claude Opus 4.6 <[email protected]>

GiggleLiu merged commit 148ef7f into main Feb 15, 2026
5 checks passed

GiggleLiu deleted the jg/issue-70 branch April 12, 2026 00:53

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Refactor: address KISS and DRY violations (#70)#71

Refactor: address KISS and DRY violations (#70)#71
GiggleLiu merged 15 commits intomainfrom
jg/issue-70

GiggleLiu commented Feb 15, 2026

Uh oh!

codecov bot commented Feb 15, 2026 •

edited

Loading

Uh oh!

Copilot AI left a comment

Uh oh!

Copilot AI Feb 15, 2026

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Conversation

GiggleLiu commented Feb 15, 2026

Summary

Test plan

Uh oh!

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

Uh oh!

Codecov Report

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Reviewed changes

Uh oh!

Copilot AI Feb 15, 2026

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

codecov bot commented Feb 15, 2026 •

edited

Loading