problemreductions/models/graph/
monochromatic_triangle.rs

1//! Monochromatic Triangle problem implementation.
2//!
3//! Given a graph G = (V, E), determine whether the edges of G can be 2-colored
4//! (each edge assigned color 0 or 1) so that no triangle is monochromatic,
5//! i.e., no three mutually adjacent vertices have all three connecting edges
6//! the same color.
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
9use crate::topology::{Graph, SimpleGraph};
10use crate::traits::Problem;
11use crate::variant::VariantParam;
12use serde::{Deserialize, Serialize};
13use std::collections::HashMap;
14
15inventory::submit! {
16    ProblemSchemaEntry {
17        name: "MonochromaticTriangle",
18        display_name: "Monochromatic Triangle",
19        aliases: &[],
20        dimensions: &[
21            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
22        ],
23        category: crate::registry::ProblemCategory::Graph,
24        module_path: module_path!(),
25        description: "2-color edges so that no triangle is monochromatic",
26        fields: &[
27            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
28        ],
29    }
30}
31
32/// The Monochromatic Triangle problem.
33///
34/// Given a graph G = (V, E), determine whether the edges of G can be 2-colored
35/// so that no triangle (three mutually adjacent vertices) has all three edges
36/// the same color.
37///
38/// Each configuration entry corresponds to an edge (in the order returned by
39/// `graph.edges()`), with value 0 or 1 representing the two colors.
40///
41/// # Type Parameters
42///
43/// * `G` - Graph type (e.g., SimpleGraph)
44///
45/// # Example
46///
47/// ```
48/// use problemreductions::models::graph::MonochromaticTriangle;
49/// use problemreductions::topology::SimpleGraph;
50/// use problemreductions::{Problem, BruteForce};
51///
52/// // K4: complete graph on 4 vertices
53/// let graph = SimpleGraph::new(4, vec![(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)]);
54/// let problem = MonochromaticTriangle::new(graph);
55///
56/// let solver = BruteForce::new();
57/// let solution = solver.solve(&problem).unwrap();
58/// assert!(solution.is_some());
59/// ```
60#[derive(Debug, Clone, Serialize, Deserialize)]
61#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
62pub struct MonochromaticTriangle<G> {
63    /// The underlying graph.
64    graph: G,
65    /// Precomputed list of triangles, each stored as three edge indices.
66    triangles: Vec<[usize; 3]>,
67    /// Ordered edge list (mirrors `graph.edges()` order).
68    edge_list: Vec<(usize, usize)>,
69}
70
71impl<G: Graph> MonochromaticTriangle<G> {
72    /// Create a new Monochromatic Triangle instance.
73    pub fn new(graph: G) -> Self {
74        let edge_list = graph.edges();
75        // Build edge-to-index mapping: (min(u,v), max(u,v)) -> index
76        let mut edge_index: HashMap<(usize, usize), usize> = HashMap::new();
77        for (idx, &(u, v)) in edge_list.iter().enumerate() {
78            let key = if u < v { (u, v) } else { (v, u) };
79            edge_index.insert(key, idx);
80        }
81
82        // Find all triangles: for each triple (u, v, w) with u < v < w,
83        // check if all three edges exist.
84        let n = graph.num_vertices();
85        let mut triangles = Vec::new();
86        for u in 0..n {
87            for v in (u + 1)..n {
88                if !graph.has_edge(u, v) {
89                    continue;
90                }
91                for w in (v + 1)..n {
92                    if graph.has_edge(u, w) && graph.has_edge(v, w) {
93                        let e_uv = edge_index[&(u, v)];
94                        let e_uw = edge_index[&(u, w)];
95                        let e_vw = edge_index[&(v, w)];
96                        triangles.push([e_uv, e_uw, e_vw]);
97                    }
98                }
99            }
100        }
101
102        Self {
103            graph,
104            triangles,
105            edge_list,
106        }
107    }
108
109    /// Get a reference to the underlying graph.
110    pub fn graph(&self) -> &G {
111        &self.graph
112    }
113
114    /// Get the number of vertices in the underlying graph.
115    pub fn num_vertices(&self) -> usize {
116        self.graph.num_vertices()
117    }
118
119    /// Get the number of edges in the underlying graph.
120    pub fn num_edges(&self) -> usize {
121        self.graph.num_edges()
122    }
123
124    /// Get the precomputed list of triangles (as edge-index triples).
125    pub fn triangles(&self) -> &[[usize; 3]] {
126        &self.triangles
127    }
128
129    /// Get the number of triangles in the graph.
130    pub fn num_triangles(&self) -> usize {
131        self.triangles.len()
132    }
133
134    /// Get the ordered edge list.
135    pub fn edge_list(&self) -> &[(usize, usize)] {
136        &self.edge_list
137    }
138}
139
140impl<G> Problem for MonochromaticTriangle<G>
141where
142    G: Graph + VariantParam,
143{
144    const NAME: &'static str = "MonochromaticTriangle";
145    type Solution = Vec<bool>;
146    type Value = crate::types::Or;
147
148    crate::problem_parameters![
149        ("num_edges", num_edges),
150        ("num_triangles", num_triangles),
151        ("num_vertices", num_vertices),
152    ];
153
154    fn variant() -> Vec<(&'static str, &'static str)> {
155        crate::variant_params![G]
156    }
157
158    fn evaluate(
159        &self,
160        config: &Self::Solution,
161    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
162        Ok({
163            crate::types::Or({
164                if config.len() != self.edge_list.len() {
165                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
166                        "edge-coloring length does not match the graph".into(),
167                    ));
168                }
169
170                // Check each triangle: if all three edges have the same color,
171                // the coloring is invalid.
172                for tri in &self.triangles {
173                    let c0 = config[tri[0]];
174                    let c1 = config[tri[1]];
175                    let c2 = config[tri[2]];
176                    if c0 == c1 && c1 == c2 {
177                        return Ok(crate::types::Or(false));
178                    }
179                }
180
181                true
182            })
183        })
184    }
185}
186
187impl<G> crate::solvers::BruteForceProblem for MonochromaticTriangle<G>
188where
189    G: Graph + VariantParam,
190{
191    fn dimensions(&self) -> Vec<usize> {
192        vec![2; self.edge_list.len()]
193    }
194}
195
196crate::declare_variants! {
197    default MonochromaticTriangle<SimpleGraph> => "2^num_edges",
198}
199
200crate::register_brute_force! {
201    MonochromaticTriangle<SimpleGraph> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
202}
203
204#[cfg(feature = "example-db")]
205pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
206    // K4: 4 vertices, 6 edges, has a valid 2-coloring avoiding monochromatic triangles.
207    // Edges in order: (0,1),(0,2),(0,3),(1,2),(1,3),(2,3)
208    // Config [0,0,1,1,0,1]:
209    //   Triangle (0,1,2): edges 0,1,3 -> colors 0,0,1 -> not monochromatic
210    //   Triangle (0,1,3): edges 0,2,4 -> colors 0,1,0 -> not monochromatic
211    //   Triangle (0,2,3): edges 1,2,5 -> colors 0,1,1 -> not monochromatic
212    //   Triangle (1,2,3): edges 3,4,5 -> colors 1,0,1 -> not monochromatic
213    vec![crate::example_db::specs::ModelExampleSpec {
214        id: "monochromatic_triangle_simplegraph",
215        instance: Box::new(MonochromaticTriangle::new(SimpleGraph::new(
216            4,
217            vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)],
218        ))),
219        optimal_config: serde_json::json!(vec![false, false, true, true, false, true]),
220        optimal_value: serde_json::json!(true),
221    }]
222}
223
224#[cfg(test)]
225#[path = "../../unit_tests/models/graph/monochromatic_triangle.rs"]
226mod tests;
problemreductions/models/graph/monochromatic_triangle.rs

problemreductions/models/graph/
monochromatic_triangle.rs
