Fix #232: Add PartitionIntoTriangles model#609
Conversation
Implement the Partition Into Triangles satisfaction problem (GJ GT11). Given a graph G with |V| = 3q, determine if vertices can be partitioned into q triples each forming a triangle. Includes CLI registration, unit tests, and brute-force solver support. Co-Authored-By: Claude Opus 4.6 <[email protected]>
Codecov Report❌ Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## main #609 +/- ##
==========================================
- Coverage 96.77% 96.77% -0.01%
==========================================
Files 226 228 +2
Lines 29919 30048 +129
==========================================
+ Hits 28955 29079 +124
- Misses 964 969 +5 ☔ View full report in Codecov by Sentry. 🚀 New features to boost your workflow:
|
There was a problem hiding this comment.
Pull request overview
Adds a new graph satisfaction model, PartitionIntoTriangles (GT11), to the core library and wires it through the CLI so instances can be created, serialized, and solved using existing tooling.
Changes:
- Introduces
PartitionIntoTriangles<G>model with schema registration, variants, and evaluation logic. - Integrates the model into public exports and graph module documentation.
- Registers the model in the CLI (name aliasing, JSON dispatch,
pred createsupport) and adds unit tests.
Reviewed changes
Copilot reviewed 9 out of 9 changed files in this pull request and generated 2 comments.
Show a summary per file
| File | Description |
|---|---|
src/models/graph/partition_into_triangles.rs |
Implements the new satisfaction problem model, schema entry, variants, and evaluation logic. |
src/unit_tests/models/graph/partition_into_triangles.rs |
Adds unit tests covering basic evaluation, solver behavior, serialization, and invalid inputs. |
src/models/graph/mod.rs |
Registers the module and re-exports PartitionIntoTriangles from the graph models module. |
src/models/mod.rs |
Re-exports PartitionIntoTriangles at the top-level models module. |
src/lib.rs |
Exposes PartitionIntoTriangles via the crate prelude. |
problemreductions-cli/src/problem_name.rs |
Adds CLI alias resolution for partitionintotriangles. |
problemreductions-cli/src/dispatch.rs |
Adds JSON (de)serialization dispatch for the new problem type. |
problemreductions-cli/src/commands/create.rs |
Adds pred create PartitionIntoTriangles instance creation support. |
problemreductions-cli/src/cli.rs |
Documents the new problem’s CLI flags in the help text. |
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
| // Check each group forms a triangle | ||
| for g in 0..q { | ||
| let verts: Vec<usize> = config | ||
| .iter() | ||
| .enumerate() | ||
| .filter(|(_, &c)| c == g) | ||
| .map(|(i, _)| i) | ||
| .collect(); |
There was a problem hiding this comment.
evaluate() rebuilds verts by scanning the entire config for every group (for g in 0..q), which makes evaluation O(n*q) and allocates a new Vec each iteration. Since brute-force solvers call evaluate() extremely frequently, consider building per-group vertex lists in a single pass over config (e.g., Vec<Vec<usize>> or fixed-size [usize; 3] buffers) and then checking the 3 edges for each group without repeated filtering/allocation.
| // Check each group forms a triangle | |
| for g in 0..q { | |
| let verts: Vec<usize> = config | |
| .iter() | |
| .enumerate() | |
| .filter(|(_, &c)| c == g) | |
| .map(|(i, _)| i) | |
| .collect(); | |
| // Build per-group vertex lists in a single pass over config. | |
| // Since each group has exactly 3 vertices, we can use fixed-size arrays. | |
| let mut group_verts = vec![[usize::MAX; 3]; q]; | |
| let mut group_pos = vec![0usize; q]; | |
| for (v, &g) in config.iter().enumerate() { | |
| let pos = group_pos[g]; | |
| // `counts` check above guarantees pos will be 0, 1, or 2. | |
| group_verts[g][pos] = v; | |
| group_pos[g] = pos + 1; | |
| } | |
| // Check each group forms a triangle | |
| for g in 0..q { | |
| let verts = group_verts[g]; |
| ( | ||
| ser(PartitionIntoTriangles::new(graph))?, | ||
| resolved_variant.clone(), | ||
| ) |
There was a problem hiding this comment.
The CLI create path calls PartitionIntoTriangles::new(graph), which asserts (panics) when the vertex count is not divisible by 3. That will crash the CLI with a panic backtrace instead of returning a user-facing error. Consider validating graph.num_vertices() % 3 == 0 here and bail! with a clear message/usage hint (or otherwise converting the precondition failure into a Result).
- Optimize PartitionIntoTriangles::evaluate() to build per-group vertex lists in a single pass instead of O(n*q) repeated filtering - Add vertex count validation in CLI create before calling new() to return a user-friendly error instead of panicking Co-Authored-By: Claude Opus 4.6 <[email protected]>
Co-Authored-By: Claude Opus 4.6 <[email protected]>
Review Pipeline Report
Agentic Test Notes
🤖 Generated by review-pipeline |
Summary
Fixes #232