problemreductions/models/graph/
minimum_vertex_cover.rs

1//! Vertex Covering problem implementation.
2//!
3//! The Vertex Cover problem asks for a minimum weight subset of vertices
4//! such that every edge has at least one endpoint in the subset.
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};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MinimumVertexCover",
16        module_path: module_path!(),
17        description: "Find minimum weight vertex cover in a graph",
18        fields: &[
19            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
20            FieldInfo { name: "weights", type_name: "Vec<W>", description: "Vertex weights w: V -> R" },
21        ],
22    }
23}
24
25/// The Vertex Covering problem.
26///
27/// Given a graph G = (V, E) and weights w_v for each vertex,
28/// find a subset S ⊆ V such that:
29/// - Every edge has at least one endpoint in S (covering constraint)
30/// - The total weight Σ_{v ∈ S} w_v is minimized
31///
32/// # Example
33///
34/// ```
35/// use problemreductions::models::graph::MinimumVertexCover;
36/// use problemreductions::topology::SimpleGraph;
37/// use problemreductions::{Problem, Solver, BruteForce};
38///
39/// // Create a path graph 0-1-2
40/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2)]);
41/// let problem = MinimumVertexCover::new(graph, vec![1; 3]);
42///
43/// // Solve with brute force
44/// let solver = BruteForce::new();
45/// let solutions = solver.find_all_best(&problem);
46///
47/// // Minimum vertex cover is just vertex 1
48/// assert!(solutions.contains(&vec![0, 1, 0]));
49/// ```
50#[derive(Debug, Clone, Serialize, Deserialize)]
51pub struct MinimumVertexCover<G, W> {
52    /// The underlying graph.
53    graph: G,
54    /// Weights for each vertex.
55    weights: Vec<W>,
56}
57
58impl<G: Graph, W: Clone + Default> MinimumVertexCover<G, W> {
59    /// Create a Vertex Covering problem from a graph with given weights.
60    pub fn new(graph: G, weights: Vec<W>) -> Self {
61        assert_eq!(
62            weights.len(),
63            graph.num_vertices(),
64            "weights length must match graph num_vertices"
65        );
66        Self { graph, weights }
67    }
68
69    /// Get a reference to the underlying graph.
70    pub fn graph(&self) -> &G {
71        &self.graph
72    }
73
74    /// Get a reference to the weights.
75    pub fn weights(&self) -> &[W] {
76        &self.weights
77    }
78
79    /// Check if the problem uses a non-unit weight type.
80    pub fn is_weighted(&self) -> bool
81    where
82        W: WeightElement,
83    {
84        !W::IS_UNIT
85    }
86
87    /// Check if a configuration is a valid vertex cover.
88    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
89        is_vertex_cover_config(&self.graph, config)
90    }
91}
92
93impl<G: Graph, W: WeightElement> MinimumVertexCover<G, W> {
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, W> Problem for MinimumVertexCover<G, W>
106where
107    G: Graph + crate::variant::VariantParam,
108    W: WeightElement + crate::variant::VariantParam,
109{
110    const NAME: &'static str = "MinimumVertexCover";
111    type Metric = SolutionSize<W::Sum>;
112
113    fn variant() -> Vec<(&'static str, &'static str)> {
114        crate::variant_params![G, W]
115    }
116
117    fn dims(&self) -> Vec<usize> {
118        vec![2; self.graph.num_vertices()]
119    }
120
121    fn evaluate(&self, config: &[usize]) -> SolutionSize<W::Sum> {
122        if !is_vertex_cover_config(&self.graph, config) {
123            return SolutionSize::Invalid;
124        }
125        let mut total = W::Sum::zero();
126        for (i, &selected) in config.iter().enumerate() {
127            if selected == 1 {
128                total += self.weights[i].to_sum();
129            }
130        }
131        SolutionSize::Valid(total)
132    }
133}
134
135impl<G, W> OptimizationProblem for MinimumVertexCover<G, W>
136where
137    G: Graph + crate::variant::VariantParam,
138    W: WeightElement + crate::variant::VariantParam,
139{
140    type Value = W::Sum;
141
142    fn direction(&self) -> Direction {
143        Direction::Minimize
144    }
145}
146
147/// Check if a configuration forms a valid vertex cover.
148fn is_vertex_cover_config<G: Graph>(graph: &G, config: &[usize]) -> bool {
149    for (u, v) in graph.edges() {
150        let u_covered = config.get(u).copied().unwrap_or(0) == 1;
151        let v_covered = config.get(v).copied().unwrap_or(0) == 1;
152        if !u_covered && !v_covered {
153            return false;
154        }
155    }
156    true
157}
158
159crate::declare_variants! {
160    MinimumVertexCover<SimpleGraph, i32> => "1.1996^num_vertices",
161}
162
163/// Check if a set of vertices forms a vertex cover.
164///
165/// # Arguments
166/// * `graph` - The graph
167/// * `selected` - Boolean slice indicating which vertices are selected
168///
169/// # Panics
170/// Panics if `selected.len() != graph.num_vertices()`.
171#[cfg(test)]
172pub(crate) fn is_vertex_cover<G: Graph>(graph: &G, selected: &[bool]) -> bool {
173    assert_eq!(
174        selected.len(),
175        graph.num_vertices(),
176        "selected length must match num_vertices"
177    );
178    for (u, v) in graph.edges() {
179        if !selected[u] && !selected[v] {
180            return false;
181        }
182    }
183    true
184}
185
186#[cfg(test)]
187#[path = "../../unit_tests/models/graph/minimum_vertex_cover.rs"]
188mod tests;
problemreductions/models/graph/minimum_vertex_cover.rs

problemreductions/models/graph/
minimum_vertex_cover.rs
