Skip to content

Fix #249: [Model] KthBestSpanningTree#692

Merged
zazabap merged 10 commits intomainfrom
issue-249-kth-best-spanning-tree-v2
Mar 18, 2026
Merged

Fix #249: [Model] KthBestSpanningTree#692
zazabap merged 10 commits intomainfrom
issue-249-kth-best-spanning-tree-v2

Conversation

@isPANN
Copy link
Copy Markdown
Collaborator

@isPANN isPANN commented Mar 17, 2026

Summary

Notes

Fixes #249

Comments from PR #654

Implementation Summary

Changes

  • Added the new KthBestSpanningTree graph model with schema metadata, canonical example data, crate exports, and CLI creation support.
  • Added focused unit tests plus trait-consistency coverage for the new model.
  • Documented the model in the paper and regenerated the exported schema/reduction-graph artifacts and example fixtures.

Deviations from Plan

  • No associated rule issue exists yet for KthBestSpanningTree, so this PR adds the standalone model and its documentation only.
  • pipeline_pr.py create previously timed out on GraphQL/TLS, so the PR itself was created via the GitHub REST API; implementation work stayed on the same branch/PR.

Review Pipeline Report

Check Result
Copilot comments 2 fixed
Issue/human comments 3 checked, already addressed
Structural review passed
CI green
Agentic test passed
Needs human decision none

Also fixed CLI discoverability on this branch: KthBestSpanningTree help now points to --edge-weights, and incorrect --weights usage is rejected with guidance.

@codecov
Copy link
Copy Markdown

codecov bot commented Mar 17, 2026 •
edited
Loading

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 97.23%. Comparing base (3b71c18) to head (61c556b).
⚠️ Report is 1 commits behind head on main.

Additional details and impacted files 
@@            Coverage Diff             @@
##             main     #692      +/-   ##
==========================================
+ Coverage   97.22%   97.23%   +0.01%     
==========================================
  Files         314      316       +2     
  Lines       40877    41105     +228     
==========================================
+ Hits        39743    39970     +227     
- Misses       1134     1135       +1

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

isPANN and others added 2 commits March 17, 2026 22:04
@isPANN @claude
fix: safe bound cast and remove dead code in KthBestSpanningTree
260fe93 
Use i32::try_from instead of `as i32` for CLI --bound to prevent
silent truncation. Remove unreachable defensive branches in
evaluate_config to eliminate coverage gaps.

Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>
@isPANN @claude
revert: restore original bound cast to match existing pattern
346dcad 
Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>
@isPANN isPANN requested a review from zazabap March 17, 2026 14:25
isPANN and others added 2 commits March 18, 2026 13:56
@isPANN @claude
fix: use small canonical example for KthBestSpanningTree
36ac4f2 
Replace the 24-variable example (5v, k=3, B=12) with a K4 instance
(12 variables, k=2, B=4) that has exactly 2 satisfying configs.
This enables exhaustive brute-force verification via regenerate-fixtures
and eliminates the need for explicit_example with hard-coded solutions.
Update paper example and tests accordingly.

Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>
@zazabap @claude
Merge origin/main into issue-249-kth-best-spanning-tree-v2
61c556b 
Resolve conflicts in references.bib, lib.rs, models/mod.rs,
trait_consistency.rs. Regenerated fixtures.

Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>
@zazabap
Copy link
Copy Markdown
Collaborator

zazabap commented Mar 18, 2026

Agentic Review Report

Structural Check

Item Status Details
Model implementation PASS src/models/graph/kth_best_spanning_tree.rs — correct Problem + SatisfactionProblem impl
declare_variants! PASS default sat KthBestSpanningTree<i32> => "2^(num_edges * k)"
ProblemSchemaEntry PASS Registered via inventory::submit! with all fields
Canonical example PASS K4, weights [1,1,2,2,2,3], k=2, B=4
Unit tests PASS 14 tests: creation, evaluation (yes/no/edge cases), brute-force exhaustive, serialization, panics
mod.rs registration PASS kth_best_spanning_tree module + re-export in graph/mod.rs
lib.rs re-export PASS In prelude
trait_consistency entry PASS Added
Paper display-name PASS "KthBestSpanningTree": [Kth Best Spanning Tree]
Paper problem-def PASS Full definition with example using load-model-example
Paper references PASS @lawler1972 and @eppstein1992 added
CLI integration PASS pred create, pred show, pred solve --solver brute-force all work
examples.json fixture PASS Model example present

Build: make build PASS, make clippy PASS, make check PASS

Semantic Review — Mathematical Correctness:

  • evaluate() correctly checks: (1) config length = k * |E|, (2) each block selects exactly n-1 edges forming a connected tree, (3) each tree weight ≤ B, (4) all k blocks are pairwise distinct
  • Tree connectivity verified via BFS — correct
  • Edge cases: single vertex (no edges, k=1 accepts empty tree), k=0 rejected by constructor
  • dims() returns vec![2; k * num_edges] — correct binary configuration space

Complexity: 2^(num_edges * k) is brute-force enumeration over all k blocks of binary edge selections. Reasonable for a satisfaction problem with no known faster exact algorithm.

Quality Check

Design Principles:

  • DRY: OK — no duplicated logic
  • KISS: Good — straightforward BFS connectivity check, clean block-based evaluation
  • Cohesion/Coupling: Good — self-contained module, minimal imports

Test Quality: Excellent — 14 tests covering:

  • Creation and field accessors
  • Positive/negative evaluation
  • Duplicate tree rejection, overweight rejection, wrong-length config, non-binary values
  • Exhaustive brute-force search (yes and no instances)
  • Serialization round-trip
  • Edge cases (single vertex, k=0 panic, weight mismatch panic)

Issues: None found.

Overall: Good. Clean, well-structured, comprehensive tests.

Agentic Feature Tests

# Test Command Status Notes
1 Catalog presence pred list PASS Listed with complexity O(2^(k * num_edges))
2 Show details pred show KthBestSpanningTree PASS Fields and complexity displayed correctly
3 Example creation pred create --example KthBestSpanningTree PASS Valid K4 instance
4 Brute-force solve pred solve --solver brute-force PASS Returns true with valid witness
5 Unit tests cargo test kth_best_spanning_tree PASS 14/14 pass

Issues found: None.

Generated by review-pipeline

@zazabap zazabap merged commit 6053e8f into main Mar 18, 2026
5 checks passed
@GiggleLiu GiggleLiu deleted the issue-249-kth-best-spanning-tree-v2 branch April 12, 2026 00:53
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@zazabap zazabap zazabap approved these changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

[Model] KthBestSpanningTree

3 participants

@isPANN @zazabap @GiggleLiu