problemreductions/models/graph/
partition_into_triangles.rs

1//! Partition Into Triangles problem implementation.
2//!
3//! Given a graph G = (V, E) where |V| = 3q, determine whether V can be
4//! partitioned into q triples, each forming a triangle (K3) in G.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::variant::VariantParam;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "PartitionIntoTriangles",
15        display_name: "Partition Into Triangles",
16        aliases: &[],
17        dimensions: &[
18            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
19        ],
20        module_path: module_path!(),
21        description: "Partition vertices into triangles (K3 subgraphs)",
22        fields: &[
23            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E) with |V| divisible by 3" },
24        ],
25    }
26}
27
28/// The Partition Into Triangles problem.
29///
30/// Given a graph G = (V, E) where |V| = 3q, determine whether V can be
31/// partitioned into q triples, each forming a triangle (K3) in G.
32///
33/// # Type Parameters
34///
35/// * `G` - Graph type (e.g., SimpleGraph)
36///
37/// # Example
38///
39/// ```
40/// use problemreductions::models::graph::PartitionIntoTriangles;
41/// use problemreductions::topology::SimpleGraph;
42/// use problemreductions::{Problem, Solver, BruteForce};
43///
44/// // Triangle graph: 3 vertices forming a single triangle
45/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]);
46/// let problem = PartitionIntoTriangles::new(graph);
47///
48/// let solver = BruteForce::new();
49/// let solution = solver.find_witness(&problem);
50/// assert!(solution.is_some());
51/// ```
52#[derive(Debug, Clone, Serialize, Deserialize)]
53#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
54pub struct PartitionIntoTriangles<G> {
55    /// The underlying graph.
56    graph: G,
57}
58
59impl<G: Graph> PartitionIntoTriangles<G> {
60    /// Create a new Partition Into Triangles problem from a graph.
61    ///
62    /// # Panics
63    /// Panics if the number of vertices is not divisible by 3.
64    pub fn new(graph: G) -> Self {
65        assert!(
66            graph.num_vertices().is_multiple_of(3),
67            "Number of vertices ({}) must be divisible by 3",
68            graph.num_vertices()
69        );
70        Self { graph }
71    }
72
73    /// Get a reference to the underlying graph.
74    pub fn graph(&self) -> &G {
75        &self.graph
76    }
77
78    /// Get the number of vertices in the underlying graph.
79    pub fn num_vertices(&self) -> usize {
80        self.graph.num_vertices()
81    }
82
83    /// Get the number of edges in the underlying graph.
84    pub fn num_edges(&self) -> usize {
85        self.graph.num_edges()
86    }
87}
88
89impl<G> Problem for PartitionIntoTriangles<G>
90where
91    G: Graph + VariantParam,
92{
93    const NAME: &'static str = "PartitionIntoTriangles";
94    type Value = crate::types::Or;
95
96    fn variant() -> Vec<(&'static str, &'static str)> {
97        crate::variant_params![G]
98    }
99
100    fn dims(&self) -> Vec<usize> {
101        let q = self.graph.num_vertices() / 3;
102        vec![q; self.graph.num_vertices()]
103    }
104
105    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
106        crate::types::Or({
107            let n = self.graph.num_vertices();
108            let q = n / 3;
109
110            // Check config length
111            if config.len() != n {
112                return crate::types::Or(false);
113            }
114
115            // Check all values are in range [0, q)
116            if config.iter().any(|&c| c >= q) {
117                return crate::types::Or(false);
118            }
119
120            // Count vertices per group
121            let mut counts = vec![0usize; q];
122            for &c in config {
123                counts[c] += 1;
124            }
125
126            // Each group must have exactly 3 vertices
127            if counts.iter().any(|&c| c != 3) {
128                return crate::types::Or(false);
129            }
130
131            // Build per-group vertex lists in a single pass over config.
132            let mut group_verts = vec![[0usize; 3]; q];
133            let mut group_pos = vec![0usize; q];
134
135            for (v, &g) in config.iter().enumerate() {
136                let pos = group_pos[g];
137                group_verts[g][pos] = v;
138                group_pos[g] = pos + 1;
139            }
140
141            // Check each group forms a triangle
142            for verts in &group_verts {
143                if !self.graph.has_edge(verts[0], verts[1]) {
144                    return crate::types::Or(false);
145                }
146                if !self.graph.has_edge(verts[0], verts[2]) {
147                    return crate::types::Or(false);
148                }
149                if !self.graph.has_edge(verts[1], verts[2]) {
150                    return crate::types::Or(false);
151                }
152            }
153
154            true
155        })
156    }
157}
158
159crate::declare_variants! {
160    default PartitionIntoTriangles<SimpleGraph> => "2^num_vertices",
161}
162
163#[cfg(feature = "example-db")]
164pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
165    vec![crate::example_db::specs::ModelExampleSpec {
166        id: "partition_into_triangles_simplegraph",
167        instance: Box::new(PartitionIntoTriangles::new(SimpleGraph::new(
168            6,
169            vec![(0, 1), (0, 2), (1, 2), (3, 4), (3, 5), (4, 5), (0, 3)],
170        ))),
171        optimal_config: vec![0, 0, 0, 1, 1, 1],
172        optimal_value: serde_json::json!(true),
173    }]
174}
175
176#[cfg(test)]
177#[path = "../../unit_tests/models/graph/partition_into_triangles.rs"]
178mod tests;
problemreductions/models/graph/partition_into_triangles.rs

problemreductions/models/graph/
partition_into_triangles.rs
