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        category: crate::registry::ProblemCategory::Graph,
21        module_path: module_path!(),
22        description: "Partition vertices into triangles (K3 subgraphs)",
23        fields: &[
24            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E) with |V| divisible by 3" },
25        ],
26    }
27}
28
29/// The Partition Into Triangles problem.
30///
31/// Given a graph G = (V, E) where |V| = 3q, determine whether V can be
32/// partitioned into q triples, each forming a triangle (K3) in G.
33///
34/// # Type Parameters
35///
36/// * `G` - Graph type (e.g., SimpleGraph)
37///
38/// # Example
39///
40/// ```
41/// use problemreductions::models::graph::PartitionIntoTriangles;
42/// use problemreductions::topology::SimpleGraph;
43/// use problemreductions::{Problem, BruteForce};
44///
45/// // Triangle graph: 3 vertices forming a single triangle
46/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]);
47/// let problem = PartitionIntoTriangles::new(graph);
48///
49/// let solver = BruteForce::new();
50/// let solution = solver.solve(&problem).unwrap();
51/// assert!(solution.is_some());
52/// ```
53#[derive(Debug, Clone, Serialize, Deserialize)]
54#[serde(try_from = "PartitionIntoTrianglesData<G>")]
55#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
56pub struct PartitionIntoTriangles<G> {
57    /// The underlying graph.
58    graph: G,
59}
60
61#[derive(Deserialize)]
62#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
63struct PartitionIntoTrianglesData<G> {
64    graph: G,
65}
66
67impl<G> TryFrom<PartitionIntoTrianglesData<G>> for PartitionIntoTriangles<G>
68where
69    G: Graph,
70{
71    type Error = crate::registry::ConstructionError;
72
73    fn try_from(data: PartitionIntoTrianglesData<G>) -> Result<Self, Self::Error> {
74        Self::try_new(data.graph)
75    }
76}
77
78impl<G: Graph> PartitionIntoTriangles<G> {
79    /// Create a new Partition Into Triangles problem from a graph.
80    ///
81    /// # Panics
82    /// Panics if the number of vertices is not divisible by 3.
83    pub fn new(graph: G) -> Self {
84        Self::try_new(graph).unwrap_or_else(|error| panic!("{error}"))
85    }
86
87    fn try_new(graph: G) -> Result<Self, crate::registry::ConstructionError> {
88        if !graph.num_vertices().is_multiple_of(3) {
89            return Err(format!(
90                "Number of vertices ({}) must be divisible by 3",
91                graph.num_vertices()
92            )
93            .into());
94        }
95        Ok(Self { graph })
96    }
97
98    /// Get a reference to the underlying graph.
99    pub fn graph(&self) -> &G {
100        &self.graph
101    }
102
103    /// Get the number of vertices in the underlying graph.
104    pub fn num_vertices(&self) -> usize {
105        self.graph.num_vertices()
106    }
107
108    /// Get the number of edges in the underlying graph.
109    pub fn num_edges(&self) -> usize {
110        self.graph.num_edges()
111    }
112}
113
114impl<G> Problem for PartitionIntoTriangles<G>
115where
116    G: Graph + VariantParam,
117{
118    const NAME: &'static str = "PartitionIntoTriangles";
119    type Solution = Vec<usize>;
120    type Value = crate::types::Or;
121
122    crate::problem_parameters![("num_vertices", num_vertices),];
123
124    fn variant() -> Vec<(&'static str, &'static str)> {
125        crate::variant_params![G]
126    }
127
128    fn evaluate(
129        &self,
130        config: &Self::Solution,
131    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
132        Ok({
133            crate::types::Or({
134                let n = self.graph.num_vertices();
135                let q = n / 3;
136
137                // Check config length
138                if config.len() != n {
139                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
140                        "partition assignment length does not match the graph vertices".into(),
141                    ));
142                }
143
144                // Check all values are in range [0, q)
145                if config.iter().any(|&c| c >= q) {
146                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
147                        "partition assignment contains an out-of-range group".into(),
148                    ));
149                }
150
151                // Count vertices per group
152                let mut counts = vec![0usize; q];
153                for &c in config {
154                    counts[c] += 1;
155                }
156
157                // Each group must have exactly 3 vertices
158                if counts.iter().any(|&c| c != 3) {
159                    return Ok(crate::types::Or(false));
160                }
161
162                // Build per-group vertex lists in a single pass over config.
163                let mut group_verts = vec![[0usize; 3]; q];
164                let mut group_pos = vec![0usize; q];
165
166                for (v, &g) in config.iter().enumerate() {
167                    let pos = group_pos[g];
168                    group_verts[g][pos] = v;
169                    group_pos[g] = pos + 1;
170                }
171
172                // Check each group forms a triangle
173                for verts in &group_verts {
174                    if !self.graph.has_edge(verts[0], verts[1]) {
175                        return Ok(crate::types::Or(false));
176                    }
177                    if !self.graph.has_edge(verts[0], verts[2]) {
178                        return Ok(crate::types::Or(false));
179                    }
180                    if !self.graph.has_edge(verts[1], verts[2]) {
181                        return Ok(crate::types::Or(false));
182                    }
183                }
184
185                true
186            })
187        })
188    }
189}
190
191impl<G> crate::solvers::BruteForceProblem for PartitionIntoTriangles<G>
192where
193    G: Graph + VariantParam,
194{
195    fn dimensions(&self) -> Vec<usize> {
196        let q = self.graph.num_vertices() / 3;
197        vec![q; self.graph.num_vertices()]
198    }
199}
200
201crate::declare_variants! {
202    default PartitionIntoTriangles<SimpleGraph> => "2^num_vertices",
203}
204
205crate::register_brute_force! {
206    PartitionIntoTriangles<SimpleGraph>,
207}
208
209#[cfg(feature = "example-db")]
210pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
211    vec![crate::example_db::specs::ModelExampleSpec {
212        id: "partition_into_triangles_simplegraph",
213        instance: Box::new(PartitionIntoTriangles::new(SimpleGraph::new(
214            6,
215            vec![(0, 1), (0, 2), (1, 2), (3, 4), (3, 5), (4, 5), (0, 3)],
216        ))),
217        optimal_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1]),
218        optimal_value: serde_json::json!(true),
219    }]
220}
221
222#[cfg(test)]
223#[path = "../../unit_tests/models/graph/partition_into_triangles.rs"]
224mod tests;
problemreductions/models/graph/partition_into_triangles.rs

problemreductions/models/graph/
partition_into_triangles.rs
