problemreductions/models/graph/
partition_into_perfect_matchings.rs

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

problemreductions/models/graph/
partition_into_perfect_matchings.rs
