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(bound(deserialize = "G: serde::Deserialize<'de>"))]
63pub struct PartitionIntoPathsOfLength2<G> {
64    /// The underlying graph.
65    graph: G,
66}
67
68impl<G: Graph> PartitionIntoPathsOfLength2<G> {
69    /// Create a new PartitionIntoPathsOfLength2 problem from a graph.
70    ///
71    /// # Panics
72    /// Panics if `graph.num_vertices()` is not divisible by 3.
73    pub fn new(graph: G) -> Self {
74        assert_eq!(
75            graph.num_vertices() % 3,
76            0,
77            "Number of vertices ({}) must be divisible by 3",
78            graph.num_vertices()
79        );
80        Self { graph }
81    }
82
83    /// Get a reference to the underlying graph.
84    pub fn graph(&self) -> &G {
85        &self.graph
86    }
87
88    /// Get the number of vertices in the graph.
89    pub fn num_vertices(&self) -> usize {
90        self.graph.num_vertices()
91    }
92
93    /// Get the number of edges in the graph.
94    pub fn num_edges(&self) -> usize {
95        self.graph.num_edges()
96    }
97
98    /// Get q = |V| / 3, the number of groups in the partition.
99    pub fn num_groups(&self) -> usize {
100        self.graph.num_vertices() / 3
101    }
102
103    /// Check if a configuration represents a valid partition.
104    ///
105    /// A valid configuration assigns each vertex to a group (0..q-1) such that:
106    /// 1. Each group contains exactly 3 vertices.
107    /// 2. Each group induces at least 2 edges.
108    pub fn is_valid_partition(&self, config: &[usize]) -> bool {
109        let n = self.graph.num_vertices();
110        let q = self.num_groups();
111
112        if config.len() != n {
113            return false;
114        }
115
116        // Check all assignments are in range
117        if config.iter().any(|&g| g >= q) {
118            return false;
119        }
120
121        // Count vertices per group
122        let mut group_sizes = vec![0usize; q];
123        for &g in config {
124            group_sizes[g] += 1;
125        }
126
127        // Each group must have exactly 3 vertices
128        if group_sizes.iter().any(|&s| s != 3) {
129            return false;
130        }
131
132        // Check each group induces at least 2 edges (single pass over edges)
133        let mut group_edge_counts = vec![0usize; q];
134        for (u, v) in self.graph.edges() {
135            if config[u] == config[v] {
136                group_edge_counts[config[u]] += 1;
137            }
138        }
139        if group_edge_counts.iter().any(|&c| c < 2) {
140            return false;
141        }
142
143        true
144    }
145}
146
147impl<G> Problem for PartitionIntoPathsOfLength2<G>
148where
149    G: Graph + VariantParam,
150{
151    const NAME: &'static str = "PartitionIntoPathsOfLength2";
152    type Solution = Vec<usize>;
153    type Value = crate::types::Or;
154
155    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
156
157    fn variant() -> Vec<(&'static str, &'static str)> {
158        crate::variant_params![G]
159    }
160
161    fn evaluate(
162        &self,
163        config: &Self::Solution,
164    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
165        if config.len() != self.graph.num_vertices() {
166            return Err(crate::traits::EvaluationError::InvalidConfiguration(
167                "partition assignment length does not match the graph vertices".into(),
168            ));
169        }
170        if config.iter().any(|&group| group >= self.num_groups()) {
171            return Err(crate::traits::EvaluationError::InvalidConfiguration(
172                "partition assignment contains an out-of-range group".into(),
173            ));
174        }
175        Ok(crate::types::Or(self.is_valid_partition(config)))
176    }
177}
178
179impl<G> crate::solvers::BruteForceProblem for PartitionIntoPathsOfLength2<G>
180where
181    G: Graph + VariantParam,
182{
183    fn dimensions(&self) -> Vec<usize> {
184        let q = self.num_groups();
185        vec![q; self.graph.num_vertices()]
186    }
187}
188
189crate::declare_variants! {
190    default PartitionIntoPathsOfLength2<SimpleGraph> => "3^num_vertices",
191}
192
193crate::register_brute_force! {
194    PartitionIntoPathsOfLength2<SimpleGraph>,
195}
196
197#[cfg(feature = "example-db")]
198pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
199    vec![crate::example_db::specs::ModelExampleSpec {
200        id: "partition_into_paths_of_length_2_simplegraph",
201        instance: Box::new(PartitionIntoPathsOfLength2::new(SimpleGraph::new(
202            9,
203            vec![
204                (0, 1),
205                (1, 2),
206                (3, 4),
207                (4, 5),
208                (6, 7),
209                (7, 8),
210                (0, 3),
211                (2, 5),
212                (3, 6),
213                (5, 8),
214                (1, 4),
215                (4, 7),
216            ],
217        ))),
218        optimal_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1, 2, 2, 2]),
219        optimal_value: serde_json::json!(true),
220    }]
221}
222
223#[cfg(test)]
224#[path = "../../unit_tests/models/graph/partition_into_paths_of_length_2.rs"]
225mod tests;
problemreductions/models/graph/partition_into_paths_of_length_2.rs

problemreductions/models/graph/
partition_into_paths_of_length_2.rs
