problemreductions/models/graph/
maximum_achromatic_number.rs

1//! Maximum Achromatic Number problem implementation.
2//!
3//! Given a graph G = (V, E), find a proper coloring that uses the maximum
4//! number of colors such that the coloring is also complete: for every pair
5//! of distinct colors, there exists an edge connecting a vertex of one color
6//! to a vertex of the other.
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
9use crate::topology::{Graph, SimpleGraph};
10use crate::traits::Problem;
11use crate::types::Max;
12use serde::{Deserialize, Serialize};
13use std::collections::HashSet;
14
15inventory::submit! {
16    ProblemSchemaEntry {
17        name: "MaximumAchromaticNumber",
18        display_name: "Maximum Achromatic Number",
19        aliases: &[],
20        dimensions: &[
21            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
22        ],
23        category: crate::registry::ProblemCategory::Graph,
24        module_path: module_path!(),
25        description: "Find a complete proper coloring maximizing the number of colors",
26        fields: &[
27            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
28        ],
29    }
30}
31
32/// The Maximum Achromatic Number problem.
33///
34/// Given a graph G = (V, E), find a proper coloring of the vertices using the
35/// maximum number of colors such that the coloring is *complete*: for every
36/// pair of distinct colors used, there exists at least one edge between a
37/// vertex of one color and a vertex of the other.
38///
39/// Variables: one per vertex, each selecting a color class (0..n-1).
40///
41/// # Type Parameters
42///
43/// * `G` - The graph type (e.g., `SimpleGraph`)
44///
45/// # Example
46///
47/// ```
48/// use problemreductions::models::graph::MaximumAchromaticNumber;
49/// use problemreductions::topology::SimpleGraph;
50/// use problemreductions::{Problem, BruteForce};
51///
52/// // C6: achromatic number is 3
53/// let graph = SimpleGraph::new(6, vec![(0,1),(1,2),(2,3),(3,4),(4,5),(5,0)]);
54/// let problem = MaximumAchromaticNumber::new(graph);
55///
56/// let solver = BruteForce::new();
57/// let solution = solver.solve(&problem).unwrap().unwrap();
58/// let value = problem.evaluate(&solution).unwrap();
59/// assert_eq!(value, problemreductions::types::Max(Some(3)));
60/// ```
61#[derive(Debug, Clone, Serialize, Deserialize)]
62pub struct MaximumAchromaticNumber<G> {
63    /// The underlying graph.
64    graph: G,
65}
66
67impl<G: Graph> MaximumAchromaticNumber<G> {
68    /// Create a MaximumAchromaticNumber problem from a graph.
69    pub fn new(graph: G) -> Self {
70        Self { graph }
71    }
72
73    /// Get a reference to the underlying graph.
74    pub fn graph(&self) -> &G {
75        &self.graph
76    }
77
78    /// Get the number of vertices in the underlying graph.
79    pub fn num_vertices(&self) -> usize {
80        self.graph.num_vertices()
81    }
82
83    /// Get the number of edges in the underlying graph.
84    pub fn num_edges(&self) -> usize {
85        self.graph.num_edges()
86    }
87
88    /// Check whether a configuration is a proper coloring.
89    ///
90    /// A proper coloring assigns colors to vertices such that no two adjacent
91    /// vertices share the same color.
92    pub fn is_proper_coloring(&self, config: &[usize]) -> bool {
93        for (u, v) in self.graph.edges() {
94            if config[u] == config[v] {
95                return false;
96            }
97        }
98        true
99    }
100
101    /// Check whether a proper coloring is complete.
102    ///
103    /// A coloring is complete if for every pair of distinct colors used,
104    /// there exists an edge between a vertex of one color and a vertex
105    /// of the other.
106    pub fn is_complete_coloring(&self, config: &[usize]) -> bool {
107        let used_colors: HashSet<usize> = config.iter().copied().collect();
108        let colors: Vec<usize> = used_colors.into_iter().collect();
109
110        for i in 0..colors.len() {
111            for j in (i + 1)..colors.len() {
112                let c1 = colors[i];
113                let c2 = colors[j];
114                let has_edge = self.graph.edges().iter().any(|&(u, v)| {
115                    (config[u] == c1 && config[v] == c2) || (config[u] == c2 && config[v] == c1)
116                });
117                if !has_edge {
118                    return false;
119                }
120            }
121        }
122        true
123    }
124}
125
126impl<G> Problem for MaximumAchromaticNumber<G>
127where
128    G: Graph + crate::variant::VariantParam,
129{
130    const NAME: &'static str = "MaximumAchromaticNumber";
131    type Solution = Vec<usize>;
132    type Value = Max<i64>;
133
134    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
135
136    fn variant() -> Vec<(&'static str, &'static str)> {
137        crate::variant_params![G]
138    }
139
140    fn evaluate(
141        &self,
142        config: &Self::Solution,
143    ) -> Result<Max<i64>, crate::traits::EvaluationError> {
144        Ok({
145            if config.len() != self.graph.num_vertices() {
146                return Err(crate::traits::EvaluationError::InvalidConfiguration(
147                    "color assignment length does not match the graph vertices".into(),
148                ));
149            }
150            if self.graph.num_vertices() == 0 {
151                return Ok(Max(Some(0)));
152            }
153            if !self.is_proper_coloring(config) {
154                return Ok(Max(None));
155            }
156            if !self.is_complete_coloring(config) {
157                return Ok(Max(None));
158            }
159            let distinct_colors: HashSet<usize> = config.iter().copied().collect();
160            Max(Some(i64::try_from(distinct_colors.len()).map_err(
161                |_| {
162                    crate::traits::EvaluationError::IntegerOverflow(
163                        "converting achromatic color count to i64".to_string(),
164                    )
165                },
166            )?))
167        })
168    }
169}
170
171impl<G> crate::solvers::BruteForceProblem for MaximumAchromaticNumber<G>
172where
173    G: Graph + crate::variant::VariantParam,
174{
175    fn dimensions(&self) -> Vec<usize> {
176        vec![self.graph.num_vertices(); self.graph.num_vertices()]
177    }
178}
179
180crate::impl_random_generate!(
181    MaximumAchromaticNumber<SimpleGraph>,
182    crate::random::SimpleGraphRandomSpec,
183    |spec| { Ok(MaximumAchromaticNumber::new(spec.graph()?)) }
184);
185
186crate::declare_variants! {
187    default MaximumAchromaticNumber<SimpleGraph> => "num_vertices^num_vertices" random,
188}
189
190crate::register_brute_force! {
191    MaximumAchromaticNumber<SimpleGraph>,
192}
193
194#[cfg(feature = "example-db")]
195pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
196    // C6: 6-cycle, achromatic number = 3
197    // Coloring [0, 1, 2, 0, 1, 2] uses 3 colors and is both proper and complete.
198    vec![crate::example_db::specs::ModelExampleSpec {
199        id: "maximum_achromatic_number_simplegraph",
200        instance: Box::new(MaximumAchromaticNumber::new(SimpleGraph::new(
201            6,
202            vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)],
203        ))),
204        optimal_config: serde_json::json!(vec![0, 1, 2, 0, 1, 2]),
205        optimal_value: serde_json::json!(3),
206    }]
207}
208
209#[cfg(test)]
210#[path = "../../unit_tests/models/graph/maximum_achromatic_number.rs"]
211mod tests;
problemreductions/models/graph/maximum_achromatic_number.rs

problemreductions/models/graph/
maximum_achromatic_number.rs
