problemreductions/models/graph/
maximal_is.rs

1//! Maximal Independent Set problem implementation.
2//!
3//! The Maximal Independent Set problem asks for an independent set that
4//! cannot be extended by adding any other 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};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MaximalIS",
16        display_name: "Maximal IS",
17        aliases: &[],
18        dimensions: &[
19            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
20            VariantDimension::new("weight", "i64", &["i64"]),
21        ],
22        category: crate::registry::ProblemCategory::Graph,
23        module_path: module_path!(),
24        description: "Find maximum weight maximal independent set",
25        fields: MaximalISCreateSpec::FIELDS,
26    }
27}
28
29/// The Maximal Independent Set problem.
30///
31/// Given a graph G = (V, E), find an independent set S that is maximal,
32/// meaning no vertex can be added to S while keeping it independent.
33///
34/// This is different from Maximum Independent Set - maximal means locally
35/// optimal (cannot extend), while maximum means globally optimal (largest).
36///
37/// # Example
38///
39/// ```
40/// use problemreductions::models::graph::MaximalIS;
41/// use problemreductions::topology::SimpleGraph;
42/// use problemreductions::{Problem, BruteForce};
43///
44/// // Path graph 0-1-2
45/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2)]);
46/// let problem = MaximalIS::new(graph, vec![1; 3]);
47///
48/// let solver = BruteForce::new();
49/// let solutions = solver.find_all_witnesses(&problem).unwrap();
50///
51/// // Maximal independent sets: {0, 2} or {1}
52/// for sol in &solutions {
53///     assert!(problem.evaluate(sol).unwrap().is_valid());
54/// }
55/// ```
56#[derive(Debug, Clone, Serialize, Deserialize)]
57pub struct MaximalIS<G, W> {
58    /// The underlying graph.
59    graph: G,
60    /// Weights for each vertex.
61    weights: Vec<W>,
62}
63
64#[derive(Debug, Deserialize, crate::CreateSpec)]
65struct MaximalISCreateSpec {
66    /// The underlying graph G=(V,E).
67    graph: SimpleGraph,
68    /// Vertex weights w: V -> R.
69    weights: Vec<i64>,
70}
71
72impl TryFrom<MaximalISCreateSpec> for MaximalIS<SimpleGraph, i64> {
73    type Error = crate::registry::ConstructionError;
74    fn try_from(spec: MaximalISCreateSpec) -> Result<Self, Self::Error> {
75        if spec.weights.len() != spec.graph.num_vertices() {
76            return Err(format!(
77                "weights has {} entries, expected {}",
78                spec.weights.len(),
79                spec.graph.num_vertices()
80            )
81            .into());
82        }
83        Ok(Self::new(spec.graph, spec.weights))
84    }
85}
86
87impl<G: Graph, W: Clone + Default> MaximalIS<G, W> {
88    /// Create a Maximal Independent Set problem from a graph with given weights.
89    pub fn new(graph: G, weights: Vec<W>) -> Self {
90        assert_eq!(
91            weights.len(),
92            graph.num_vertices(),
93            "weights length must match graph num_vertices"
94        );
95        Self { graph, weights }
96    }
97
98    /// Get a reference to the underlying graph.
99    pub fn graph(&self) -> &G {
100        &self.graph
101    }
102
103    /// Get a reference to the weights.
104    pub fn weights(&self) -> &[W] {
105        &self.weights
106    }
107
108    /// Check if the problem uses a non-unit weight type.
109    pub fn is_weighted(&self) -> bool
110    where
111        W: WeightElement,
112    {
113        !W::IS_UNIT
114    }
115
116    /// Check if a configuration is a valid maximal independent set.
117    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
118        self.is_maximal(config)
119    }
120
121    /// Check if a configuration is an independent set.
122    fn is_independent(&self, config: &[bool]) -> bool {
123        for (u, v) in self.graph.edges() {
124            if config.get(u).copied().unwrap_or(false) && config.get(v).copied().unwrap_or(false) {
125                return false;
126            }
127        }
128        true
129    }
130
131    /// Check if an independent set is maximal (cannot be extended).
132    fn is_maximal(&self, config: &[bool]) -> bool {
133        if !self.is_independent(config) {
134            return false;
135        }
136
137        let n = self.graph.num_vertices();
138        for v in 0..n {
139            if config.get(v).copied().unwrap_or(false) {
140                continue; // Already in set
141            }
142
143            // Check if v can be added
144            let neighbors = self.graph.neighbors(v);
145            let can_add = neighbors
146                .iter()
147                .all(|&u| !config.get(u).copied().unwrap_or(false));
148
149            if can_add {
150                return false; // Set is not maximal
151            }
152        }
153
154        true
155    }
156}
157
158impl<G: Graph, W: WeightElement> MaximalIS<G, W> {
159    /// Get the number of vertices in the underlying graph.
160    pub fn num_vertices(&self) -> usize {
161        self.graph().num_vertices()
162    }
163
164    /// Get the number of edges in the underlying graph.
165    pub fn num_edges(&self) -> usize {
166        self.graph().num_edges()
167    }
168}
169
170impl<G, W> Problem for MaximalIS<G, W>
171where
172    G: Graph + crate::variant::VariantParam,
173    W: WeightElement + crate::variant::VariantParam,
174{
175    const NAME: &'static str = "MaximalIS";
176    type Solution = Vec<bool>;
177    type Value = Max<W::Sum>;
178
179    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
180
181    fn variant() -> Vec<(&'static str, &'static str)> {
182        crate::variant_params![G, W]
183    }
184
185    fn evaluate(
186        &self,
187        config: &Self::Solution,
188    ) -> Result<Max<W::Sum>, crate::traits::EvaluationError> {
189        if config.len() != self.graph.num_vertices() {
190            return Err(crate::traits::EvaluationError::InvalidConfiguration(
191                "vertex-selection length does not match the graph".into(),
192            ));
193        }
194        Ok({
195            if !self.is_maximal(config) {
196                return Ok(Max(None));
197            }
198            let mut total = W::Sum::zero();
199            for (i, &selected) in config.iter().enumerate() {
200                if selected {
201                    total = W::checked_add_to_sum(
202                        total,
203                        self.weights[i].to_sum(),
204                        "summing selected maximal-independent-set weights",
205                    )?;
206                }
207            }
208            Max(Some(total))
209        })
210    }
211}
212
213impl<G, W> crate::solvers::BruteForceProblem for MaximalIS<G, W>
214where
215    G: Graph + crate::variant::VariantParam,
216    W: WeightElement + crate::variant::VariantParam,
217{
218    fn dimensions(&self) -> Vec<usize> {
219        vec![2; self.graph.num_vertices()]
220    }
221}
222
223#[cfg(feature = "example-db")]
224pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
225    vec![crate::example_db::specs::ModelExampleSpec {
226        id: "maximal_is_simplegraph",
227        instance: Box::new(MaximalIS::new(
228            SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4)]),
229            vec![1i64; 5],
230        )),
231        optimal_config: serde_json::json!(vec![true, false, true, false, true]),
232        optimal_value: serde_json::json!(3),
233    }]
234}
235
236/// Check if a set is a maximal independent set.
237///
238/// # Panics
239/// Panics if `selected.len() != graph.num_vertices()`.
240#[cfg(test)]
241pub(crate) fn is_maximal_independent_set<G: Graph>(graph: &G, selected: &[bool]) -> bool {
242    assert_eq!(
243        selected.len(),
244        graph.num_vertices(),
245        "selected length must match num_vertices"
246    );
247
248    // Check independence
249    for (u, v) in graph.edges() {
250        if selected[u] && selected[v] {
251            return false;
252        }
253    }
254
255    // Check maximality: no unselected vertex can be added
256    for v in 0..graph.num_vertices() {
257        if selected[v] {
258            continue;
259        }
260        if graph.neighbors(v).iter().all(|&u| !selected[u]) {
261            return false;
262        }
263    }
264
265    true
266}
267
268crate::impl_random_generate!(MaximalIS<SimpleGraph, i64>, crate::random::SimpleGraphRandomSpec, |spec| {
269    Ok(MaximalIS::new(spec.graph()?, vec![1; spec.num_vertices]))
270});
271
272crate::declare_variants! {
273    default MaximalIS<SimpleGraph, i64> => "3^(num_vertices / 3)" create MaximalISCreateSpec random,
274}
275
276crate::register_brute_force! {
277    MaximalIS<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
278}
279
280#[cfg(test)]
281#[path = "../../unit_tests/models/graph/maximal_is.rs"]
282mod tests;
problemreductions/models/graph/maximal_is.rs

problemreductions/models/graph/
maximal_is.rs
