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(bound(deserialize = "G: serde::Deserialize<'de>"))]
60pub struct PartitionIntoPerfectMatchings<G> {
61    /// The underlying graph.
62    graph: G,
63    /// Maximum number of matching groups.
64    num_matchings: usize,
65}
66
67impl<G: Graph> PartitionIntoPerfectMatchings<G> {
68    /// Create a new Partition Into Perfect Matchings instance.
69    ///
70    /// # Panics
71    /// Panics if `num_matchings` is zero or greater than `graph.num_vertices()`.
72    pub fn new(graph: G, num_matchings: usize) -> Self {
73        assert!(num_matchings >= 1, "num_matchings must be at least 1");
74        assert!(
75            num_matchings <= graph.num_vertices(),
76            "num_matchings must be at most num_vertices"
77        );
78        Self {
79            graph,
80            num_matchings,
81        }
82    }
83
84    /// Get a reference to the underlying graph.
85    pub fn graph(&self) -> &G {
86        &self.graph
87    }
88
89    /// Get the maximum number of matching groups.
90    pub fn num_matchings(&self) -> usize {
91        self.num_matchings
92    }
93
94    /// Get the number of vertices in the underlying graph.
95    pub fn num_vertices(&self) -> usize {
96        self.graph.num_vertices()
97    }
98
99    /// Get the number of edges in the underlying graph.
100    pub fn num_edges(&self) -> usize {
101        self.graph.num_edges()
102    }
103}
104
105impl<G> Problem for PartitionIntoPerfectMatchings<G>
106where
107    G: Graph + VariantParam,
108{
109    const NAME: &'static str = "PartitionIntoPerfectMatchings";
110    type Solution = Vec<usize>;
111    type Value = crate::types::Or;
112
113    crate::problem_parameters![
114        ("num_edges", num_edges),
115        ("num_matchings", num_matchings),
116        ("num_vertices", num_vertices),
117    ];
118
119    fn variant() -> Vec<(&'static str, &'static str)> {
120        crate::variant_params![G]
121    }
122
123    fn evaluate(
124        &self,
125        config: &Self::Solution,
126    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
127        if config.len() != self.graph.num_vertices() {
128            return Err(crate::traits::EvaluationError::InvalidConfiguration(
129                "partition assignment length does not match the graph vertices".into(),
130            ));
131        }
132        if config.iter().any(|&part| part >= self.num_matchings) {
133            return Err(crate::traits::EvaluationError::InvalidConfiguration(
134                "partition assignment contains an out-of-range matching".into(),
135            ));
136        }
137        Ok({
138            crate::types::Or(is_valid_perfect_matching_partition(
139                &self.graph,
140                self.num_matchings,
141                config,
142            ))
143        })
144    }
145}
146
147impl<G> crate::solvers::BruteForceProblem for PartitionIntoPerfectMatchings<G>
148where
149    G: Graph + VariantParam,
150{
151    fn dimensions(&self) -> Vec<usize> {
152        vec![self.num_matchings; self.graph.num_vertices()]
153    }
154}
155
156/// Check whether `config` is a valid K-perfect-matching partition of `graph`.
157fn is_valid_perfect_matching_partition<G: Graph>(
158    graph: &G,
159    num_matchings: usize,
160    config: &[usize],
161) -> bool {
162    let n = graph.num_vertices();
163
164    // Basic validity checks
165    if config.len() != n {
166        return false;
167    }
168    if config.iter().any(|&c| c >= num_matchings) {
169        return false;
170    }
171
172    // For each group, collect the vertices and check every vertex has exactly
173    // one neighbor within the group (i.e., the induced subgraph is a perfect matching).
174    for group in 0..num_matchings {
175        let members: Vec<usize> = (0..n).filter(|&v| config[v] == group).collect();
176        // Empty groups are OK
177        if members.is_empty() {
178            continue;
179        }
180        // A perfect matching requires an even number of vertices
181        if !members.len().is_multiple_of(2) {
182            return false;
183        }
184        // Each member must have exactly one neighbor in the group
185        for &v in &members {
186            let neighbor_count = members
187                .iter()
188                .filter(|&&u| u != v && graph.has_edge(v, u))
189                .count();
190            if neighbor_count != 1 {
191                return false;
192            }
193        }
194    }
195
196    true
197}
198
199crate::declare_variants! {
200    default PartitionIntoPerfectMatchings<SimpleGraph> => "num_matchings^num_vertices",
201}
202
203crate::register_brute_force! {
204    PartitionIntoPerfectMatchings<SimpleGraph>,
205}
206
207#[cfg(feature = "example-db")]
208pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
209    vec![crate::example_db::specs::ModelExampleSpec {
210        id: "partition_into_perfect_matchings_simplegraph",
211        instance: Box::new(PartitionIntoPerfectMatchings::new(
212            SimpleGraph::new(4, vec![(0, 1), (2, 3), (0, 2), (1, 3)]),
213            2,
214        )),
215        optimal_config: serde_json::json!(vec![0, 0, 1, 1]),
216        optimal_value: serde_json::json!(true),
217    }]
218}
219
220#[cfg(test)]
221#[path = "../../unit_tests/models/graph/partition_into_perfect_matchings.rs"]
222mod tests;
problemreductions/models/graph/partition_into_perfect_matchings.rs

problemreductions/models/graph/
partition_into_perfect_matchings.rs
