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)]
57#[serde(try_from = "MaximalISData<G, W>")]
58#[serde(bound(deserialize = "G: Graph + Deserialize<'de>, W: Clone + Default + Deserialize<'de>"))]
59pub struct MaximalIS<G, W> {
60    /// The underlying graph.
61    graph: G,
62    /// Weights for each vertex.
63    weights: Vec<W>,
64}
65
66#[derive(Deserialize)]
67struct MaximalISData<G, W> {
68    graph: G,
69    weights: Vec<W>,
70}
71
72impl<G, W> TryFrom<MaximalISData<G, W>> for MaximalIS<G, W>
73where
74    G: Graph,
75    W: Clone + Default,
76{
77    type Error = crate::registry::ConstructionError;
78
79    fn try_from(data: MaximalISData<G, W>) -> Result<Self, Self::Error> {
80        Self::try_new(data.graph, data.weights)
81    }
82}
83
84#[derive(Debug, Deserialize, crate::CreateSpec)]
85struct MaximalISCreateSpec {
86    /// The underlying graph G=(V,E).
87    graph: SimpleGraph,
88    /// Vertex weights w: V -> R.
89    weights: Vec<i64>,
90}
91
92impl TryFrom<MaximalISCreateSpec> for MaximalIS<SimpleGraph, i64> {
93    type Error = crate::registry::ConstructionError;
94    fn try_from(spec: MaximalISCreateSpec) -> Result<Self, Self::Error> {
95        Self::try_new(spec.graph, spec.weights)
96    }
97}
98
99impl<G: Graph, W: Clone + Default> MaximalIS<G, W> {
100    /// Create a Maximal Independent Set problem from a graph with given weights.
101    pub fn new(graph: G, weights: Vec<W>) -> Self {
102        Self::try_new(graph, weights).unwrap_or_else(|error| panic!("{error}"))
103    }
104
105    fn try_new(graph: G, weights: Vec<W>) -> Result<Self, crate::registry::ConstructionError> {
106        if weights.len() != graph.num_vertices() {
107            return Err(crate::registry::ConstructionError::length_mismatch(
108                "weights",
109                weights.len(),
110                graph.num_vertices(),
111            ));
112        }
113        Ok(Self { graph, weights })
114    }
115
116    /// Get a reference to the underlying graph.
117    pub fn graph(&self) -> &G {
118        &self.graph
119    }
120
121    /// Get a reference to the weights.
122    pub fn weights(&self) -> &[W] {
123        &self.weights
124    }
125
126    /// Check if the problem uses a non-unit weight type.
127    pub fn is_weighted(&self) -> bool
128    where
129        W: WeightElement,
130    {
131        !W::IS_UNIT
132    }
133
134    /// Check if a configuration is a valid maximal independent set.
135    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
136        self.is_maximal(config)
137    }
138
139    /// Check if a configuration is an independent set.
140    fn is_independent(&self, config: &[bool]) -> bool {
141        for (u, v) in self.graph.edges() {
142            if config.get(u).copied().unwrap_or(false) && config.get(v).copied().unwrap_or(false) {
143                return false;
144            }
145        }
146        true
147    }
148
149    /// Check if an independent set is maximal (cannot be extended).
150    fn is_maximal(&self, config: &[bool]) -> bool {
151        if !self.is_independent(config) {
152            return false;
153        }
154
155        let n = self.graph.num_vertices();
156        for v in 0..n {
157            if config.get(v).copied().unwrap_or(false) {
158                continue; // Already in set
159            }
160
161            // Check if v can be added
162            let neighbors = self.graph.neighbors(v);
163            let can_add = neighbors
164                .iter()
165                .all(|&u| !config.get(u).copied().unwrap_or(false));
166
167            if can_add {
168                return false; // Set is not maximal
169            }
170        }
171
172        true
173    }
174}
175
176impl<G: Graph, W: WeightElement> MaximalIS<G, W> {
177    /// Get the number of vertices in the underlying graph.
178    pub fn num_vertices(&self) -> usize {
179        self.graph().num_vertices()
180    }
181
182    /// Get the number of edges in the underlying graph.
183    pub fn num_edges(&self) -> usize {
184        self.graph().num_edges()
185    }
186}
187
188impl<G, W> Problem for MaximalIS<G, W>
189where
190    G: Graph + crate::variant::VariantParam,
191    W: WeightElement + crate::variant::VariantParam,
192{
193    const NAME: &'static str = "MaximalIS";
194    type Solution = Vec<bool>;
195    type Value = Max<W::Sum>;
196
197    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
198
199    fn variant() -> Vec<(&'static str, &'static str)> {
200        crate::variant_params![G, W]
201    }
202
203    fn evaluate(
204        &self,
205        config: &Self::Solution,
206    ) -> Result<Max<W::Sum>, crate::traits::EvaluationError> {
207        if config.len() != self.graph.num_vertices() {
208            return Err(crate::traits::EvaluationError::InvalidConfiguration(
209                "vertex-selection length does not match the graph".into(),
210            ));
211        }
212        Ok({
213            if !self.is_maximal(config) {
214                return Ok(Max(None));
215            }
216            let mut total = W::Sum::zero();
217            for (i, &selected) in config.iter().enumerate() {
218                if selected {
219                    total = W::checked_add_to_sum(
220                        total,
221                        self.weights[i].to_sum(),
222                        "summing selected maximal-independent-set weights",
223                    )?;
224                }
225            }
226            Max(Some(total))
227        })
228    }
229}
230
231impl<G, W> crate::solvers::BruteForceProblem for MaximalIS<G, W>
232where
233    G: Graph + crate::variant::VariantParam,
234    W: WeightElement + crate::variant::VariantParam,
235{
236    fn dimensions(&self) -> Vec<usize> {
237        vec![2; self.graph.num_vertices()]
238    }
239}
240
241#[cfg(feature = "example-db")]
242pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
243    vec![crate::example_db::specs::ModelExampleSpec {
244        id: "maximal_is_simplegraph",
245        instance: Box::new(MaximalIS::new(
246            SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4)]),
247            vec![1i64; 5],
248        )),
249        optimal_config: serde_json::json!(vec![true, false, true, false, true]),
250        optimal_value: serde_json::json!(3),
251    }]
252}
253
254/// Check if a set is a maximal independent set.
255///
256/// # Panics
257/// Panics if `selected.len() != graph.num_vertices()`.
258#[cfg(test)]
259pub(crate) fn is_maximal_independent_set<G: Graph>(graph: &G, selected: &[bool]) -> bool {
260    assert_eq!(
261        selected.len(),
262        graph.num_vertices(),
263        "selected length must match num_vertices"
264    );
265
266    // Check independence
267    for (u, v) in graph.edges() {
268        if selected[u] && selected[v] {
269            return false;
270        }
271    }
272
273    // Check maximality: no unselected vertex can be added
274    for v in 0..graph.num_vertices() {
275        if selected[v] {
276            continue;
277        }
278        if graph.neighbors(v).iter().all(|&u| !selected[u]) {
279            return false;
280        }
281    }
282
283    true
284}
285
286crate::impl_random_generate!(MaximalIS<SimpleGraph, i64>, crate::random::SimpleGraphRandomSpec, |spec| {
287    Ok(MaximalIS::new(spec.graph()?, vec![1; spec.num_vertices]))
288});
289
290crate::declare_variants! {
291    default MaximalIS<SimpleGraph, i64> => "3^(num_vertices / 3)" create MaximalISCreateSpec random,
292}
293
294crate::register_brute_force! {
295    MaximalIS<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
296}
297
298#[cfg(test)]
299#[path = "../../unit_tests/models/graph/maximal_is.rs"]
300mod tests;
problemreductions/models/graph/maximal_is.rs

problemreductions/models/graph/
maximal_is.rs
