problemreductions/models/graph/
partition_into_paths_of_length_2.rs

1//! Partition into Paths of Length 2 problem implementation.
2//!
3//! Given a graph G = (V, E) with |V| = 3q, determine whether V can be partitioned
4//! into q disjoint sets of three vertices each, such that each set induces at least
5//! two edges (i.e., a path of length 2 or a triangle).
6//!
7//! This is a classical NP-complete problem from Garey & Johnson, Chapter 3, Section 3.3, p.76.
8
9use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
10use crate::topology::{Graph, SimpleGraph};
11use crate::traits::Problem;
12use crate::variant::VariantParam;
13use serde::{Deserialize, Serialize};
14
15inventory::submit! {
16    ProblemSchemaEntry {
17        name: "PartitionIntoPathsOfLength2",
18        display_name: "Partition into Paths of Length 2",
19        aliases: &[],
20        dimensions: &[
21            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
22        ],
23        category: crate::registry::ProblemCategory::Graph,
24        module_path: module_path!(),
25        description: "Partition vertices into triples each inducing at least two edges (P3 or triangle)",
26        fields: &[
27            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E) with |V| divisible by 3" },
28        ],
29    }
30}
31
32/// Partition into Paths of Length 2 problem.
33///
34/// Given a graph G = (V, E) with |V| = 3q for a positive integer q,
35/// determine whether V can be partitioned into q disjoint sets
36/// V_1, V_2, ..., V_q of three vertices each, such that each V_t
37/// induces at least two edges in G.
38///
39/// Each triple must form either a path of length 2 (exactly 2 edges)
40/// or a triangle (all 3 edges).
41///
42/// # Type Parameters
43///
44/// * `G` - Graph type (e.g., SimpleGraph)
45///
46/// # Example
47///
48/// ```
49/// use problemreductions::models::graph::PartitionIntoPathsOfLength2;
50/// use problemreductions::topology::SimpleGraph;
51/// use problemreductions::{Problem, BruteForce};
52///
53/// // 6-vertex graph with two P3 paths: 0-1-2 and 3-4-5
54/// let graph = SimpleGraph::new(6, vec![(0, 1), (1, 2), (3, 4), (4, 5)]);
55/// let problem = PartitionIntoPathsOfLength2::new(graph);
56///
57/// let solver = BruteForce::new();
58/// let solution = solver.solve(&problem).unwrap();
59/// assert!(solution.is_some());
60/// ```
61#[derive(Debug, Clone, Serialize, Deserialize)]
62#[serde(try_from = "PartitionIntoPathsOfLength2Data<G>")]
63#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
64pub struct PartitionIntoPathsOfLength2<G> {
65    /// The underlying graph.
66    graph: G,
67}
68
69#[derive(Deserialize)]
70#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
71struct PartitionIntoPathsOfLength2Data<G> {
72    graph: G,
73}
74
75impl<G> TryFrom<PartitionIntoPathsOfLength2Data<G>> for PartitionIntoPathsOfLength2<G>
76where
77    G: Graph,
78{
79    type Error = crate::registry::ConstructionError;
80
81    fn try_from(data: PartitionIntoPathsOfLength2Data<G>) -> Result<Self, Self::Error> {
82        Self::try_new(data.graph)
83    }
84}
85
86impl<G: Graph> PartitionIntoPathsOfLength2<G> {
87    /// Create a new PartitionIntoPathsOfLength2 problem from a graph.
88    ///
89    /// # Panics
90    /// Panics if `graph.num_vertices()` is not divisible by 3.
91    pub fn new(graph: G) -> Self {
92        Self::try_new(graph).unwrap_or_else(|error| panic!("{error}"))
93    }
94
95    fn try_new(graph: G) -> Result<Self, crate::registry::ConstructionError> {
96        if !graph.num_vertices().is_multiple_of(3) {
97            return Err(format!(
98                "Number of vertices ({}) must be divisible by 3",
99                graph.num_vertices()
100            )
101            .into());
102        }
103        Ok(Self { graph })
104    }
105
106    /// Get a reference to the underlying graph.
107    pub fn graph(&self) -> &G {
108        &self.graph
109    }
110
111    /// Get the number of vertices in the graph.
112    pub fn num_vertices(&self) -> usize {
113        self.graph.num_vertices()
114    }
115
116    /// Get the number of edges in the graph.
117    pub fn num_edges(&self) -> usize {
118        self.graph.num_edges()
119    }
120
121    /// Get q = |V| / 3, the number of groups in the partition.
122    pub fn num_groups(&self) -> usize {
123        self.graph.num_vertices() / 3
124    }
125
126    /// Check if a configuration represents a valid partition.
127    ///
128    /// A valid configuration assigns each vertex to a group (0..q-1) such that:
129    /// 1. Each group contains exactly 3 vertices.
130    /// 2. Each group induces at least 2 edges.
131    pub fn is_valid_partition(&self, config: &[usize]) -> bool {
132        let n = self.graph.num_vertices();
133        let q = self.num_groups();
134
135        if config.len() != n {
136            return false;
137        }
138
139        // Check all assignments are in range
140        if config.iter().any(|&g| g >= q) {
141            return false;
142        }
143
144        let mut groups = vec![Vec::new(); q];
145        for (vertex, &group) in config.iter().enumerate() {
146            groups[group].push(vertex);
147        }
148
149        // Each group must have exactly 3 vertices
150        if groups.iter().any(|vertices| vertices.len() != 3) {
151            return false;
152        }
153
154        // Count distinct pairs: loops and parallel edges cannot form a path.
155        groups.iter().all(|vertices| {
156            let [a, b, c] = [vertices[0], vertices[1], vertices[2]];
157            usize::from(self.graph.has_edge(a, b))
158                + usize::from(self.graph.has_edge(a, c))
159                + usize::from(self.graph.has_edge(b, c))
160                >= 2
161        })
162    }
163}
164
165impl<G> Problem for PartitionIntoPathsOfLength2<G>
166where
167    G: Graph + VariantParam,
168{
169    const NAME: &'static str = "PartitionIntoPathsOfLength2";
170    type Solution = Vec<usize>;
171    type Value = crate::types::Or;
172
173    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
174
175    fn variant() -> Vec<(&'static str, &'static str)> {
176        crate::variant_params![G]
177    }
178
179    fn evaluate(
180        &self,
181        config: &Self::Solution,
182    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
183        if config.len() != self.graph.num_vertices() {
184            return Err(crate::traits::EvaluationError::InvalidConfiguration(
185                "partition assignment length does not match the graph vertices".into(),
186            ));
187        }
188        if config.iter().any(|&group| group >= self.num_groups()) {
189            return Err(crate::traits::EvaluationError::InvalidConfiguration(
190                "partition assignment contains an out-of-range group".into(),
191            ));
192        }
193        Ok(crate::types::Or(self.is_valid_partition(config)))
194    }
195}
196
197impl<G> crate::solvers::BruteForceProblem for PartitionIntoPathsOfLength2<G>
198where
199    G: Graph + VariantParam,
200{
201    fn dimensions(&self) -> Vec<usize> {
202        let q = self.num_groups();
203        vec![q; self.graph.num_vertices()]
204    }
205}
206
207crate::declare_variants! {
208    default PartitionIntoPathsOfLength2<SimpleGraph> => "3^num_vertices",
209}
210
211crate::register_brute_force! {
212    PartitionIntoPathsOfLength2<SimpleGraph>,
213}
214
215#[cfg(feature = "example-db")]
216pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
217    vec![crate::example_db::specs::ModelExampleSpec {
218        id: "partition_into_paths_of_length_2_simplegraph",
219        instance: Box::new(PartitionIntoPathsOfLength2::new(SimpleGraph::new(
220            9,
221            vec![
222                (0, 1),
223                (1, 2),
224                (3, 4),
225                (4, 5),
226                (6, 7),
227                (7, 8),
228                (0, 3),
229                (2, 5),
230                (3, 6),
231                (5, 8),
232                (1, 4),
233                (4, 7),
234            ],
235        ))),
236        optimal_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1, 2, 2, 2]),
237        optimal_value: serde_json::json!(true),
238    }]
239}
240
241#[cfg(test)]
242#[path = "../../unit_tests/models/graph/partition_into_paths_of_length_2.rs"]
243mod tests;
problemreductions/models/graph/partition_into_paths_of_length_2.rs

problemreductions/models/graph/
partition_into_paths_of_length_2.rs
