problemreductions/models/graph/
maximum_domatic_number.rs

1//! Maximum Domatic Number problem implementation.
2//!
3//! The Maximum Domatic Number problem asks for the maximum number k such that the
4//! vertex set V of a graph G=(V,E) can be partitioned into k disjoint dominating sets.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::Max;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "MaximumDomaticNumber",
15        display_name: "Maximum Domatic Number",
16        aliases: &[],
17        dimensions: &[
18            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
19        ],
20        category: crate::registry::ProblemCategory::Graph,
21        module_path: module_path!(),
22        description: "Find maximum number of disjoint dominating sets partitioning V",
23        fields: &[
24            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
25        ],
26    }
27}
28
29/// The Maximum Domatic Number problem.
30///
31/// Given a graph G = (V, E), find the maximum k such that V can be partitioned
32/// into k disjoint dominating sets. A dominating set D ⊆ V is a set such that
33/// every vertex is either in D or adjacent to a vertex in D.
34///
35/// The configuration assigns each vertex to a set index (0..n-1). The value is
36/// `Max(Some(k))` where k is the number of non-empty sets if all non-empty sets
37/// are dominating, or `Max(None)` if any non-empty set fails domination.
38///
39/// # Example
40///
41/// ```
42/// use problemreductions::models::graph::MaximumDomaticNumber;
43/// use problemreductions::topology::SimpleGraph;
44/// use problemreductions::{Problem, BruteForce};
45///
46/// // Path graph P3: 0-1-2
47/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2)]);
48/// let problem = MaximumDomaticNumber::new(graph);
49///
50/// let solver = BruteForce::new();
51/// let witness = solver.solve(&problem).unwrap().unwrap();
52/// let value = problem.evaluate(&witness).unwrap();
53/// // Domatic number of P3 is 2
54/// assert_eq!(value, problemreductions::types::Max(Some(2)));
55/// ```
56#[derive(Debug, Clone, Serialize, Deserialize)]
57pub struct MaximumDomaticNumber<G> {
58    /// The underlying graph.
59    graph: G,
60}
61
62impl<G: Graph> MaximumDomaticNumber<G> {
63    /// Create a Maximum Domatic Number problem from a graph.
64    pub fn new(graph: G) -> Self {
65        Self { graph }
66    }
67
68    /// Get a reference to the underlying graph.
69    pub fn graph(&self) -> &G {
70        &self.graph
71    }
72
73    /// Get the number of vertices in the underlying graph.
74    pub fn num_vertices(&self) -> usize {
75        self.graph.num_vertices()
76    }
77
78    /// Get the number of edges in the underlying graph.
79    pub fn num_edges(&self) -> usize {
80        self.graph.num_edges()
81    }
82
83    /// Check whether a partition is valid (all non-empty sets are dominating).
84    ///
85    /// Returns `Some(k)` where k is the number of non-empty dominating sets,
86    /// or `None` if any non-empty set fails the domination property.
87    fn evaluate_partition(&self, config: &[usize]) -> Option<usize> {
88        let n = self.graph.num_vertices();
89
90        // Configuration must assign each vertex to exactly one set.
91        if config.len() != n {
92            return None;
93        }
94
95        // Collect which vertices belong to each set
96        let mut sets: Vec<Vec<usize>> = vec![vec![]; n];
97        for (v, &set_idx) in config.iter().enumerate() {
98            // Each set index must be within bounds of the available sets.
99            if set_idx >= n {
100                return None;
101            }
102            sets[set_idx].push(v);
103        }
104
105        // Check each non-empty set is a dominating set
106        let mut count = 0;
107        for set in &sets {
108            if set.is_empty() {
109                continue;
110            }
111            count += 1;
112
113            // Build membership lookup
114            let mut in_set = vec![false; n];
115            for &v in set {
116                in_set[v] = true;
117            }
118
119            // Every vertex must be in the set or adjacent to someone in the set
120            for v in 0..n {
121                if in_set[v] {
122                    continue;
123                }
124                if !self.graph.neighbors(v).iter().any(|&u| in_set[u]) {
125                    return None;
126                }
127            }
128        }
129
130        Some(count)
131    }
132}
133
134impl<G> Problem for MaximumDomaticNumber<G>
135where
136    G: Graph + crate::variant::VariantParam,
137{
138    const NAME: &'static str = "MaximumDomaticNumber";
139    type Solution = Vec<usize>;
140    type Value = Max<i64>;
141
142    crate::problem_parameters![("num_vertices", num_vertices),];
143
144    fn variant() -> Vec<(&'static str, &'static str)> {
145        crate::variant_params![G]
146    }
147
148    fn evaluate(
149        &self,
150        config: &Self::Solution,
151    ) -> Result<Max<i64>, crate::traits::EvaluationError> {
152        let n = self.graph.num_vertices();
153        if config.len() != n {
154            return Err(crate::traits::EvaluationError::InvalidConfiguration(
155                "partition assignment length does not match the graph vertices".into(),
156            ));
157        }
158        if config.iter().any(|&part| part >= n) {
159            return Err(crate::traits::EvaluationError::InvalidConfiguration(
160                "partition assignment contains an out-of-range part".into(),
161            ));
162        }
163        Ok({
164            match self.evaluate_partition(config) {
165                Some(k) => Max(Some(i64::try_from(k).map_err(|_| {
166                    crate::traits::EvaluationError::IntegerOverflow(
167                        "converting domatic number to i64".into(),
168                    )
169                })?)),
170                None => Max(None),
171            }
172        })
173    }
174}
175
176impl<G> crate::solvers::BruteForceProblem for MaximumDomaticNumber<G>
177where
178    G: Graph + crate::variant::VariantParam,
179{
180    fn dimensions(&self) -> Vec<usize> {
181        let n = self.graph.num_vertices();
182        vec![n; n]
183    }
184}
185
186crate::impl_random_generate!(
187    MaximumDomaticNumber<SimpleGraph>,
188    crate::random::SimpleGraphRandomSpec,
189    |spec| { Ok(MaximumDomaticNumber::new(spec.graph()?)) }
190);
191
192crate::declare_variants! {
193    default MaximumDomaticNumber<SimpleGraph> => "2.695^num_vertices" random,
194}
195
196crate::register_brute_force! {
197    MaximumDomaticNumber<SimpleGraph>,
198}
199
200#[cfg(feature = "example-db")]
201pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
202    vec![crate::example_db::specs::ModelExampleSpec {
203        id: "maximum_domatic_number_simplegraph",
204        instance: Box::new(MaximumDomaticNumber::new(SimpleGraph::new(
205            6,
206            vec![
207                (0, 1),
208                (0, 2),
209                (0, 3),
210                (1, 4),
211                (2, 5),
212                (3, 4),
213                (3, 5),
214                (4, 5),
215            ],
216        ))),
217        optimal_config: serde_json::json!(vec![0, 1, 2, 0, 2, 1]),
218        optimal_value: serde_json::json!(3),
219    }]
220}
221
222#[cfg(test)]
223#[path = "../../unit_tests/models/graph/maximum_domatic_number.rs"]
224mod tests;
problemreductions/models/graph/maximum_domatic_number.rs

problemreductions/models/graph/
maximum_domatic_number.rs
