Fix #412: Add ShortestCommonSupersequence model#627
Merged
Conversation
Codecov Report✅ All modified and coverable lines are covered by tests. Additional details and impacted files@@ Coverage Diff @@
## main #627 +/- ##
==========================================
+ Coverage 96.82% 96.83% +0.01%
==========================================
Files 238 240 +2
Lines 31129 31242 +113
==========================================
+ Hits 30140 30254 +114
+ Misses 989 988 -1 ☔ View full report in Codecov by Sentry. 🚀 New features to boost your workflow:
|
Collaborator
Author
Implementation SummaryChanges
Deviations from Plan
Open Questions
|
There was a problem hiding this comment.
Pull request overview
Adds the Shortest Common Supersequence (SCS) satisfaction problem model to the core library, wires it into the CLI (name resolution, dispatch, and pred create), and updates the paper documentation to include the new problem definition and references.
Changes:
- Introduce
ShortestCommonSupersequencemodel (schema registration, evaluation, variants) plus unit tests. - Extend CLI support: alias (
SCS), load/serialize dispatch, andpred createflags for constructing instances. - Update paper docs (problem definition + bibliography) and apply minor formatting/ordering tweaks in examples.
Reviewed changes
Copilot reviewed 13 out of 13 changed files in this pull request and generated 6 comments.
Show a summary per file
| File | Description |
|---|---|
src/models/misc/shortest_common_supersequence.rs |
New SCS model implementation + schema inventory entry + variant declaration + tests module hook |
src/unit_tests/models/misc/shortest_common_supersequence.rs |
Unit tests covering evaluation, brute force solving, edge cases, and serialization |
src/models/misc/mod.rs |
Registers and re-exports the new misc model module/type |
src/models/mod.rs |
Re-exports ShortestCommonSupersequence at the top-level models module |
problemreductions-cli/src/problem_name.rs |
Adds SCS alias and alias resolution for the new model |
problemreductions-cli/src/dispatch.rs |
Enables CLI load/serialize dispatch for SCS instances |
problemreductions-cli/src/commands/create.rs |
Adds pred create ShortestCommonSupersequence construction from --strings/--bound/--alphabet-size |
problemreductions-cli/src/cli.rs |
Adds new CLI flags (--strings, --bound, --alphabet-size) and mentions SCS in help text |
docs/paper/reductions.typ |
Adds a paper definition block for SCS (incl. explanation + figure) |
docs/paper/references.bib |
Adds Maier (1978) and Räihä & Ukkonen (1981) citations |
examples/reduction_binpacking_to_ilp.rs |
Formatting-only changes |
examples/detect_unreachable_from_3sat.rs |
Formatting-only changes |
docs/paper/examples/maximumindependentset_to_maximumclique.json |
Reorders JSON keys (example formatting) |
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
Comment on lines
+3
to
+7
| //! Given a set of strings over an alphabet and a bound `B`, the problem asks | ||
| //! whether there exists a common supersequence of length exactly `B`. A string | ||
| //! `w` is a supersequence of `s` if `s` is a subsequence of `w` (i.e., `s` can | ||
| //! be obtained by deleting zero or more characters from `w`). This problem is | ||
| //! NP-hard (Maier, 1978). |
Comment on lines
+117
to
+129
| fn dims(&self) -> Vec<usize> { | ||
| vec![self.alphabet_size; self.bound] | ||
| } | ||
|
|
||
| fn evaluate(&self, config: &[usize]) -> bool { | ||
| if config.len() != self.bound { | ||
| return false; | ||
| } | ||
| if config.iter().any(|&v| v >= self.alphabet_size) { | ||
| return false; | ||
| } | ||
| self.strings.iter().all(|s| is_subsequence(s, config)) | ||
| } |
| crate::variant_params![] | ||
| } | ||
|
|
||
| fn dims(&self) -> Vec<usize> { |
Comment on lines
+13
to
+24
| inventory::submit! { | ||
| ProblemSchemaEntry { | ||
| name: "ShortestCommonSupersequence", | ||
| module_path: module_path!(), | ||
| description: "Find a common supersequence of bounded length for a set of strings", | ||
| fields: &[ | ||
| FieldInfo { name: "alphabet_size", type_name: "usize", description: "Size of the alphabet" }, | ||
| FieldInfo { name: "strings", type_name: "Vec<Vec<usize>>", description: "Input strings over the alphabet {0, ..., alphabet_size-1}" }, | ||
| FieldInfo { name: "bound", type_name: "usize", description: "Upper bound on supersequence length" }, | ||
| ], | ||
| } | ||
| } |
Comment on lines
+475
to
+487
| let strings: Vec<Vec<usize>> = strings_str | ||
| .split(';') | ||
| .map(|s| { | ||
| s.trim() | ||
| .split(',') | ||
| .map(|v| { | ||
| v.trim() | ||
| .parse::<usize>() | ||
| .map_err(|e| anyhow::anyhow!("Invalid alphabet index: {}", e)) | ||
| }) | ||
| .collect::<Result<Vec<_>>>() | ||
| }) | ||
| .collect::<Result<Vec<_>>>()?; |
problemreductions-cli/src/cli.rs
Outdated
| BMF --matrix (0/1), --rank | ||
| CVP --basis, --target-vec [--bounds] | ||
| FVS --arcs [--weights] [--num-vertices] | ||
| SCS --strings, --bound |
Keep both ShortestCommonSupersequence (from PR) and LongestCommonSubsequence, SubgraphIsomorphism, SubsetSum (from main) in all affected files. Co-Authored-By: Claude Opus 4.6 <[email protected]>
- 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]>
- 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]>
Co-Authored-By: Claude Opus 4.6 <[email protected]>
Co-Authored-By: Claude Opus 4.6 <[email protected]>
Collaborator
Author
Review Pipeline Report
Fixes Applied
🤖 Generated by review-pipeline |
Co-Authored-By: Claude Opus 4.6 <[email protected]>
GiggleLiu
added a commit
that referenced
this pull request
Mar 13, 2026
* Add plan for #244: [Model] IsomorphicSpanningTree Co-Authored-By: Claude Opus 4.6 <[email protected]> * feat: add IsomorphicSpanningTree satisfaction problem model (#244) 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]> * chore: remove plan file after implementation Co-Authored-By: Claude Opus 4.6 <[email protected]> * Fix #412: Add ShortestCommonSupersequence model (#627) * 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]> * Fix #507: Add FlowShopScheduling model (#629) * 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]> * Add paper section, trait_consistency entry, and formatting fixes for 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]> --------- Co-authored-by: Claude Opus 4.6 <[email protected]> Co-authored-by: GiggleLiu <[email protected]>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
Fixes #412