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

problemreductions/models/graph/
maximum_matching.rs
