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::{CreateSpec, 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", "i64", &["i64"]),
22        ],
23        category: crate::registry::ProblemCategory::Graph,
24        module_path: module_path!(),
25        description: "Find maximum weight matching in a graph",
26        fields: MaximumMatchingCreateSpec::FIELDS,
27    }
28}
29
30/// The Maximum Matching problem.
31///
32/// Given a graph G = (V, E) with edge weights, find a maximum weight
33/// subset M ⊆ E such that no two edges in M share a vertex.
34///
35/// # Type Parameters
36///
37/// * `G` - The graph type (e.g., `SimpleGraph`, `KingsSubgraph`, `UnitDiskGraph`)
38/// * `W` - The weight type (e.g., `i64`, `f64`, `One`)
39///
40/// # Example
41///
42/// ```
43/// use problemreductions::models::graph::MaximumMatching;
44/// use problemreductions::topology::SimpleGraph;
45/// use problemreductions::{Problem, BruteForce};
46///
47/// // Path graph 0-1-2
48/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2)]);
49/// let problem = MaximumMatching::<_, i64>::unit_weights(graph);
50///
51/// let solver = BruteForce::new();
52/// let solutions = solver.find_all_witnesses(&problem).unwrap();
53///
54/// // Maximum matching has 1 edge
55/// for sol in &solutions {
56///     assert_eq!(sol.iter().filter(|&&selected| selected).count(), 1);
57/// }
58/// ```
59#[derive(Debug, Clone, Serialize, Deserialize)]
60#[serde(try_from = "MaximumMatchingData<G, W>")]
61#[serde(bound(deserialize = "G: Graph + Deserialize<'de>, W: Clone + Default + Deserialize<'de>"))]
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
69#[derive(Deserialize)]
70struct MaximumMatchingData<G, W> {
71    graph: G,
72    edge_weights: Vec<W>,
73}
74
75impl<G, W> TryFrom<MaximumMatchingData<G, W>> for MaximumMatching<G, W>
76where
77    G: Graph,
78    W: Clone + Default,
79{
80    type Error = crate::registry::ConstructionError;
81
82    fn try_from(data: MaximumMatchingData<G, W>) -> Result<Self, Self::Error> {
83        Self::try_new(data.graph, data.edge_weights)
84    }
85}
86
87#[derive(Debug, Deserialize, crate::CreateSpec)]
88struct MaximumMatchingCreateSpec {
89    #[create(codec = "edge-list")]
90    graph: Vec<(usize, usize)>,
91    num_vertices: Option<usize>,
92    #[create(codec = "comma-separated")]
93    edge_weights: Option<Vec<i64>>,
94}
95
96impl TryFrom<MaximumMatchingCreateSpec> for MaximumMatching<SimpleGraph, i64> {
97    type Error = crate::registry::ConstructionError;
98
99    fn try_from(spec: MaximumMatchingCreateSpec) -> Result<Self, Self::Error> {
100        let graph = simple_graph_from_create(spec.graph, spec.num_vertices)?;
101        let edge_weights = spec
102            .edge_weights
103            .unwrap_or_else(|| vec![1; graph.num_edges()]);
104        Self::try_new(graph, edge_weights)
105    }
106}
107
108fn simple_graph_from_create(
109    edges: Vec<(usize, usize)>,
110    num_vertices: Option<usize>,
111) -> Result<SimpleGraph, crate::registry::ConstructionError> {
112    if edges.is_empty() && num_vertices.is_none() {
113        return Err("num_vertices is required for an empty graph"
114            .to_string()
115            .into());
116    }
117    for (index, &(u, v)) in edges.iter().enumerate() {
118        if u == v {
119            return Err(format!("graph edge {index} is a self-loop at vertex {u}").into());
120        }
121    }
122    let inferred = edges
123        .iter()
124        .flat_map(|&(u, v)| [u, v])
125        .max()
126        .map(|vertex| vertex.checked_add(1).ok_or("vertex count overflows usize"))
127        .transpose()?
128        .unwrap_or(0);
129    let num_vertices = num_vertices.unwrap_or(inferred);
130    if num_vertices < inferred {
131        return Err(format!(
132            "num_vertices {num_vertices} is too small for graph endpoints; need at least {inferred}"
133        )
134        .into());
135    }
136    Ok(SimpleGraph::new(num_vertices, edges))
137}
138
139impl<G: Graph, W: Clone + Default> MaximumMatching<G, W> {
140    /// Create a MaximumMatching problem from a graph with given edge weights.
141    ///
142    /// # Arguments
143    /// * `graph` - The graph
144    /// * `edge_weights` - Weight for each edge (in graph.edges() order)
145    pub fn new(graph: G, edge_weights: Vec<W>) -> Self {
146        Self::try_new(graph, edge_weights).unwrap_or_else(|error| panic!("{error}"))
147    }
148
149    fn try_new(graph: G, edge_weights: Vec<W>) -> Result<Self, crate::registry::ConstructionError> {
150        Self::check_weights(&graph, &edge_weights)?;
151        Ok(Self {
152            graph,
153            edge_weights,
154        })
155    }
156
157    /// Create a MaximumMatching problem with unit weights.
158    pub fn unit_weights(graph: G) -> Self
159    where
160        W: WeightElement,
161    {
162        let edge_weights = vec![W::unit(); graph.num_edges()];
163        Self {
164            graph,
165            edge_weights,
166        }
167    }
168
169    /// Get a reference to the underlying graph.
170    pub fn graph(&self) -> &G {
171        &self.graph
172    }
173
174    /// Get edge endpoints.
175    pub fn edge_endpoints(&self, edge_idx: usize) -> Option<(usize, usize)> {
176        self.graph.edges().get(edge_idx).copied()
177    }
178
179    /// Get all edges with their endpoints and weights.
180    pub fn edges(&self) -> Vec<(usize, usize, W)> {
181        self.graph
182            .edges()
183            .into_iter()
184            .zip(self.edge_weights.iter().cloned())
185            .map(|((u, v), w)| (u, v, w))
186            .collect()
187    }
188
189    /// Build a map from vertices to incident edges.
190    pub fn vertex_to_edges(&self) -> HashMap<usize, Vec<usize>> {
191        let mut v2e: HashMap<usize, Vec<usize>> = HashMap::new();
192        for (idx, (u, v)) in self.graph.edges().iter().enumerate() {
193            v2e.entry(*u).or_default().push(idx);
194            v2e.entry(*v).or_default().push(idx);
195        }
196        v2e
197    }
198
199    /// Check if a configuration is a valid matching.
200    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
201        self.is_valid_matching(config)
202    }
203
204    /// Check if a configuration is a valid matching (internal).
205    fn is_valid_matching(&self, config: &[bool]) -> bool {
206        let mut vertex_used = vec![false; self.graph.num_vertices()];
207
208        for (idx, &selected) in config.iter().enumerate() {
209            if selected {
210                if let Some((u, v)) = self.edge_endpoints(idx) {
211                    if vertex_used[u] || vertex_used[v] {
212                        return false;
213                    }
214                    vertex_used[u] = true;
215                    vertex_used[v] = true;
216                }
217            }
218        }
219        true
220    }
221
222    /// Set new weights for the problem.
223    pub fn set_weights(&mut self, weights: Vec<W>) {
224        Self::check_weights(&self.graph, &weights).unwrap_or_else(|error| panic!("{error}"));
225        self.edge_weights = weights;
226    }
227
228    fn check_weights(
229        graph: &G,
230        edge_weights: &[W],
231    ) -> Result<(), crate::registry::ConstructionError> {
232        if edge_weights.len() != graph.num_edges() {
233            return Err(crate::registry::ConstructionError::length_mismatch(
234                "edge_weights",
235                edge_weights.len(),
236                graph.num_edges(),
237            ));
238        }
239        Ok(())
240    }
241
242    /// Get the weights for the problem.
243    pub fn weights(&self) -> Vec<W> {
244        self.edge_weights.clone()
245    }
246
247    /// Check if the problem uses a non-unit weight type.
248    pub fn is_weighted(&self) -> bool
249    where
250        W: WeightElement,
251    {
252        !W::IS_UNIT
253    }
254}
255
256impl<G: Graph, W: WeightElement> MaximumMatching<G, W> {
257    /// Get the number of vertices in the underlying graph.
258    pub fn num_vertices(&self) -> usize {
259        self.graph().num_vertices()
260    }
261
262    /// Get the number of edges in the underlying graph.
263    pub fn num_edges(&self) -> usize {
264        self.graph().num_edges()
265    }
266}
267
268impl<G, W> Problem for MaximumMatching<G, W>
269where
270    G: Graph + crate::variant::VariantParam,
271    W: WeightElement + crate::variant::VariantParam,
272{
273    const NAME: &'static str = "MaximumMatching";
274    type Solution = Vec<bool>;
275    type Value = Max<W::Sum>;
276
277    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
278
279    fn variant() -> Vec<(&'static str, &'static str)> {
280        crate::variant_params![G, W]
281    }
282
283    fn evaluate(
284        &self,
285        config: &Self::Solution,
286    ) -> Result<Max<W::Sum>, crate::traits::EvaluationError> {
287        if config.len() != self.graph.num_edges() {
288            return Err(crate::traits::EvaluationError::InvalidConfiguration(
289                "edge-selection length does not match the graph".into(),
290            ));
291        }
292        Ok({
293            if !self.is_valid_matching(config) {
294                return Ok(Max(None));
295            }
296            let mut total = W::Sum::zero();
297            for (idx, &selected) in config.iter().enumerate() {
298                if selected {
299                    if let Some(w) = self.edge_weights.get(idx) {
300                        total = W::checked_add_to_sum(
301                            total,
302                            w.to_sum(),
303                            "summing selected matching-edge weights",
304                        )?;
305                    }
306                }
307            }
308            Max(Some(total))
309        })
310    }
311}
312
313impl<G, W> crate::solvers::BruteForceProblem for MaximumMatching<G, W>
314where
315    G: Graph + crate::variant::VariantParam,
316    W: WeightElement + crate::variant::VariantParam,
317{
318    fn dimensions(&self) -> Vec<usize> {
319        vec![2; self.graph.num_edges()]
320    }
321}
322
323crate::impl_random_generate!(MaximumMatching<SimpleGraph, i64>, crate::random::SimpleGraphRandomSpec, |spec| {
324    let graph = spec.graph()?;
325    let weights = vec![1; graph.num_edges()];
326    Ok(MaximumMatching::new(graph, weights))
327});
328
329crate::declare_variants! {
330    default MaximumMatching<SimpleGraph, i64> => "num_vertices^3" create MaximumMatchingCreateSpec random,
331}
332
333crate::register_brute_force! {
334    MaximumMatching<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
335}
336
337#[cfg(feature = "example-db")]
338pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
339    vec![crate::example_db::specs::ModelExampleSpec {
340        id: "maximum_matching_simplegraph",
341        instance: Box::new(MaximumMatching::<_, i64>::unit_weights(SimpleGraph::new(
342            5,
343            vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)],
344        ))),
345        optimal_config: serde_json::json!(vec![true, false, false, false, true, false]),
346        optimal_value: serde_json::json!(2),
347    }]
348}
349
350/// Check if a selection of edges forms a valid matching.
351///
352/// # Panics
353/// Panics if `selected.len() != graph.num_edges()`.
354#[cfg(test)]
355pub(crate) fn is_matching<G: Graph>(graph: &G, selected: &[bool]) -> bool {
356    assert_eq!(
357        selected.len(),
358        graph.num_edges(),
359        "selected length must match num_edges"
360    );
361
362    let edges = graph.edges();
363    let mut vertex_used = vec![false; graph.num_vertices()];
364    for (idx, &sel) in selected.iter().enumerate() {
365        if sel {
366            let (u, v) = edges[idx];
367            if vertex_used[u] || vertex_used[v] {
368                return false;
369            }
370            vertex_used[u] = true;
371            vertex_used[v] = true;
372        }
373    }
374    true
375}
376
377#[cfg(test)]
378#[path = "../../unit_tests/models/graph/maximum_matching.rs"]
379mod tests;
problemreductions/models/graph/maximum_matching.rs

problemreductions/models/graph/
maximum_matching.rs
