problemreductions/models/graph/
maximum_matching.rs

1//! MaximumMatching problem implementation.
2//!
3//! The Maximum Matching problem asks for a maximum weight set of edges
4//! such that no two edges share a vertex.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::{Max, WeightElement};
10use num_traits::Zero;
11use serde::{Deserialize, Serialize};
12use std::collections::HashMap;
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "MaximumMatching",
17        display_name: "Maximum Matching",
18        aliases: &["MaxMatching"],
19        dimensions: &[
20            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
21            VariantDimension::new("weight", "i32", &["i32"]),
22        ],
23        module_path: module_path!(),
24        description: "Find maximum weight matching in a graph",
25        fields: &[
26            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
27            FieldInfo { name: "edge_weights", type_name: "Vec<W>", description: "Edge weights w: E -> R" },
28        ],
29    }
30}
31
32/// The Maximum Matching problem.
33///
34/// Given a graph G = (V, E) with edge weights, find a maximum weight
35/// subset M ⊆ E such that no two edges in M share a vertex.
36///
37/// # Type Parameters
38///
39/// * `G` - The graph type (e.g., `SimpleGraph`, `KingsSubgraph`, `UnitDiskGraph`)
40/// * `W` - The weight type (e.g., `i32`, `f64`, `One`)
41///
42/// # Example
43///
44/// ```
45/// use problemreductions::models::graph::MaximumMatching;
46/// use problemreductions::topology::SimpleGraph;
47/// use problemreductions::{Problem, Solver, BruteForce};
48///
49/// // Path graph 0-1-2
50/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2)]);
51/// let problem = MaximumMatching::<_, i32>::unit_weights(graph);
52///
53/// let solver = BruteForce::new();
54/// let solutions = solver.find_all_witnesses(&problem);
55///
56/// // Maximum matching has 1 edge
57/// for sol in &solutions {
58///     assert_eq!(sol.iter().sum::<usize>(), 1);
59/// }
60/// ```
61#[derive(Debug, Clone, Serialize, Deserialize)]
62pub struct MaximumMatching<G, W> {
63    /// The underlying graph.
64    graph: G,
65    /// Weights for each edge (in edge index order).
66    edge_weights: Vec<W>,
67}
68
69impl<G: Graph, W: Clone + Default> MaximumMatching<G, W> {
70    /// Create a MaximumMatching problem from a graph with given edge weights.
71    ///
72    /// # Arguments
73    /// * `graph` - The graph
74    /// * `edge_weights` - Weight for each edge (in graph.edges() order)
75    pub fn new(graph: G, edge_weights: Vec<W>) -> Self {
76        assert_eq!(
77            edge_weights.len(),
78            graph.num_edges(),
79            "edge_weights length must match num_edges"
80        );
81        Self {
82            graph,
83            edge_weights,
84        }
85    }
86
87    /// Create a MaximumMatching problem with unit weights.
88    pub fn unit_weights(graph: G) -> Self
89    where
90        W: From<i32>,
91    {
92        let edge_weights = vec![W::from(1); graph.num_edges()];
93        Self {
94            graph,
95            edge_weights,
96        }
97    }
98
99    /// Get a reference to the underlying graph.
100    pub fn graph(&self) -> &G {
101        &self.graph
102    }
103
104    /// Get edge endpoints.
105    pub fn edge_endpoints(&self, edge_idx: usize) -> Option<(usize, usize)> {
106        self.graph.edges().get(edge_idx).copied()
107    }
108
109    /// Get all edges with their endpoints and weights.
110    pub fn edges(&self) -> Vec<(usize, usize, W)> {
111        self.graph
112            .edges()
113            .into_iter()
114            .zip(self.edge_weights.iter().cloned())
115            .map(|((u, v), w)| (u, v, w))
116            .collect()
117    }
118
119    /// Build a map from vertices to incident edges.
120    pub fn vertex_to_edges(&self) -> HashMap<usize, Vec<usize>> {
121        let mut v2e: HashMap<usize, Vec<usize>> = HashMap::new();
122        for (idx, (u, v)) in self.graph.edges().iter().enumerate() {
123            v2e.entry(*u).or_default().push(idx);
124            v2e.entry(*v).or_default().push(idx);
125        }
126        v2e
127    }
128
129    /// Check if a configuration is a valid matching.
130    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
131        self.is_valid_matching(config)
132    }
133
134    /// Check if a configuration is a valid matching (internal).
135    fn is_valid_matching(&self, config: &[usize]) -> bool {
136        let mut vertex_used = vec![false; self.graph.num_vertices()];
137
138        for (idx, &selected) in config.iter().enumerate() {
139            if selected == 1 {
140                if let Some((u, v)) = self.edge_endpoints(idx) {
141                    if vertex_used[u] || vertex_used[v] {
142                        return false;
143                    }
144                    vertex_used[u] = true;
145                    vertex_used[v] = true;
146                }
147            }
148        }
149        true
150    }
151
152    /// Set new weights for the problem.
153    pub fn set_weights(&mut self, weights: Vec<W>) {
154        assert_eq!(weights.len(), self.graph.num_edges());
155        self.edge_weights = weights;
156    }
157
158    /// Get the weights for the problem.
159    pub fn weights(&self) -> Vec<W> {
160        self.edge_weights.clone()
161    }
162
163    /// Check if the problem uses a non-unit weight type.
164    pub fn is_weighted(&self) -> bool
165    where
166        W: WeightElement,
167    {
168        !W::IS_UNIT
169    }
170}
171
172impl<G: Graph, W: WeightElement> MaximumMatching<G, W> {
173    /// Get the number of vertices in the underlying graph.
174    pub fn num_vertices(&self) -> usize {
175        self.graph().num_vertices()
176    }
177
178    /// Get the number of edges in the underlying graph.
179    pub fn num_edges(&self) -> usize {
180        self.graph().num_edges()
181    }
182}
183
184impl<G, W> Problem for MaximumMatching<G, W>
185where
186    G: Graph + crate::variant::VariantParam,
187    W: WeightElement + crate::variant::VariantParam,
188{
189    const NAME: &'static str = "MaximumMatching";
190    type Value = Max<W::Sum>;
191
192    fn variant() -> Vec<(&'static str, &'static str)> {
193        crate::variant_params![G, W]
194    }
195
196    fn dims(&self) -> Vec<usize> {
197        vec![2; self.graph.num_edges()]
198    }
199
200    fn evaluate(&self, config: &[usize]) -> Max<W::Sum> {
201        if !self.is_valid_matching(config) {
202            return Max(None);
203        }
204        let mut total = W::Sum::zero();
205        for (idx, &selected) in config.iter().enumerate() {
206            if selected == 1 {
207                if let Some(w) = self.edge_weights.get(idx) {
208                    total += w.to_sum();
209                }
210            }
211        }
212        Max(Some(total))
213    }
214}
215
216crate::declare_variants! {
217    default MaximumMatching<SimpleGraph, i32> => "num_vertices^3",
218}
219
220#[cfg(feature = "example-db")]
221pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
222    vec![crate::example_db::specs::ModelExampleSpec {
223        id: "maximum_matching_simplegraph_i32",
224        instance: Box::new(MaximumMatching::<_, i32>::unit_weights(SimpleGraph::new(
225            5,
226            vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)],
227        ))),
228        optimal_config: vec![1, 0, 0, 0, 1, 0],
229        optimal_value: serde_json::json!(2),
230    }]
231}
232
233/// Check if a selection of edges forms a valid matching.
234///
235/// # Panics
236/// Panics if `selected.len() != graph.num_edges()`.
237#[cfg(test)]
238pub(crate) fn is_matching<G: Graph>(graph: &G, selected: &[bool]) -> bool {
239    assert_eq!(
240        selected.len(),
241        graph.num_edges(),
242        "selected length must match num_edges"
243    );
244
245    let edges = graph.edges();
246    let mut vertex_used = vec![false; graph.num_vertices()];
247    for (idx, &sel) in selected.iter().enumerate() {
248        if sel {
249            let (u, v) = edges[idx];
250            if vertex_used[u] || vertex_used[v] {
251                return false;
252            }
253            vertex_used[u] = true;
254            vertex_used[v] = true;
255        }
256    }
257    true
258}
259
260#[cfg(test)]
261#[path = "../../unit_tests/models/graph/maximum_matching.rs"]
262mod tests;
problemreductions/models/graph/maximum_matching.rs

problemreductions/models/graph/
maximum_matching.rs
