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(try_from = "MonochromaticTriangleData<G>")]
62#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
63pub struct MonochromaticTriangle<G> {
64    /// The underlying graph.
65    graph: G,
66    /// Precomputed list of triangles, each stored as three edge indices.
67    triangles: Vec<[usize; 3]>,
68    /// Ordered edge list (mirrors `graph.edges()` order).
69    edge_list: Vec<(usize, usize)>,
70}
71
72// The persisted triangle and edge lists are derived data; loading rebuilds them.
73#[derive(Deserialize)]
74#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
75struct MonochromaticTriangleData<G> {
76    graph: G,
77}
78
79impl<G> TryFrom<MonochromaticTriangleData<G>> for MonochromaticTriangle<G>
80where
81    G: Graph,
82{
83    type Error = crate::registry::ConstructionError;
84
85    fn try_from(data: MonochromaticTriangleData<G>) -> Result<Self, Self::Error> {
86        Ok(Self::new(data.graph))
87    }
88}
89
90impl<G: Graph> MonochromaticTriangle<G> {
91    /// Create a new Monochromatic Triangle instance.
92    pub fn new(graph: G) -> Self {
93        let edge_list = graph.edges();
94        // Build edge-to-index mapping: (min(u,v), max(u,v)) -> index
95        let mut edge_index: HashMap<(usize, usize), usize> = HashMap::new();
96        for (idx, &(u, v)) in edge_list.iter().enumerate() {
97            let key = if u < v { (u, v) } else { (v, u) };
98            edge_index.insert(key, idx);
99        }
100
101        // Find all triangles: for each triple (u, v, w) with u < v < w,
102        // check if all three edges exist.
103        let n = graph.num_vertices();
104        let mut triangles = Vec::new();
105        for u in 0..n {
106            for v in (u + 1)..n {
107                if !graph.has_edge(u, v) {
108                    continue;
109                }
110                for w in (v + 1)..n {
111                    if graph.has_edge(u, w) && graph.has_edge(v, w) {
112                        let e_uv = edge_index[&(u, v)];
113                        let e_uw = edge_index[&(u, w)];
114                        let e_vw = edge_index[&(v, w)];
115                        triangles.push([e_uv, e_uw, e_vw]);
116                    }
117                }
118            }
119        }
120
121        Self {
122            graph,
123            triangles,
124            edge_list,
125        }
126    }
127
128    /// Get a reference to the underlying graph.
129    pub fn graph(&self) -> &G {
130        &self.graph
131    }
132
133    /// Get the number of vertices in the underlying graph.
134    pub fn num_vertices(&self) -> usize {
135        self.graph.num_vertices()
136    }
137
138    /// Get the number of edges in the underlying graph.
139    pub fn num_edges(&self) -> usize {
140        self.graph.num_edges()
141    }
142
143    /// Get the precomputed list of triangles (as edge-index triples).
144    pub fn triangles(&self) -> &[[usize; 3]] {
145        &self.triangles
146    }
147
148    /// Get the number of triangles in the graph.
149    pub fn num_triangles(&self) -> usize {
150        self.triangles.len()
151    }
152
153    /// Get the ordered edge list.
154    pub fn edge_list(&self) -> &[(usize, usize)] {
155        &self.edge_list
156    }
157}
158
159impl<G> Problem for MonochromaticTriangle<G>
160where
161    G: Graph + VariantParam,
162{
163    const NAME: &'static str = "MonochromaticTriangle";
164    type Solution = Vec<bool>;
165    type Value = crate::types::Or;
166
167    crate::problem_parameters![
168        ("num_edges", num_edges),
169        ("num_triangles", num_triangles),
170        ("num_vertices", num_vertices),
171    ];
172
173    fn variant() -> Vec<(&'static str, &'static str)> {
174        crate::variant_params![G]
175    }
176
177    fn evaluate(
178        &self,
179        config: &Self::Solution,
180    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
181        Ok({
182            crate::types::Or({
183                if config.len() != self.edge_list.len() {
184                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
185                        "edge-coloring length does not match the graph".into(),
186                    ));
187                }
188
189                // Check each triangle: if all three edges have the same color,
190                // the coloring is invalid.
191                for tri in &self.triangles {
192                    let c0 = config[tri[0]];
193                    let c1 = config[tri[1]];
194                    let c2 = config[tri[2]];
195                    if c0 == c1 && c1 == c2 {
196                        return Ok(crate::types::Or(false));
197                    }
198                }
199
200                true
201            })
202        })
203    }
204}
205
206impl<G> crate::solvers::BruteForceProblem for MonochromaticTriangle<G>
207where
208    G: Graph + VariantParam,
209{
210    fn dimensions(&self) -> Vec<usize> {
211        vec![2; self.edge_list.len()]
212    }
213}
214
215crate::declare_variants! {
216    default MonochromaticTriangle<SimpleGraph> => "2^num_edges",
217}
218
219crate::register_brute_force! {
220    MonochromaticTriangle<SimpleGraph> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
221}
222
223#[cfg(feature = "example-db")]
224pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
225    // K4: 4 vertices, 6 edges, has a valid 2-coloring avoiding monochromatic triangles.
226    // Edges in order: (0,1),(0,2),(0,3),(1,2),(1,3),(2,3)
227    // Config [0,0,1,1,0,1]:
228    //   Triangle (0,1,2): edges 0,1,3 -> colors 0,0,1 -> not monochromatic
229    //   Triangle (0,1,3): edges 0,2,4 -> colors 0,1,0 -> not monochromatic
230    //   Triangle (0,2,3): edges 1,2,5 -> colors 0,1,1 -> not monochromatic
231    //   Triangle (1,2,3): edges 3,4,5 -> colors 1,0,1 -> not monochromatic
232    vec![crate::example_db::specs::ModelExampleSpec {
233        id: "monochromatic_triangle_simplegraph",
234        instance: Box::new(MonochromaticTriangle::new(SimpleGraph::new(
235            4,
236            vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)],
237        ))),
238        optimal_config: serde_json::json!(vec![false, false, true, true, false, true]),
239        optimal_value: serde_json::json!(true),
240    }]
241}
242
243#[cfg(test)]
244#[path = "../../unit_tests/models/graph/monochromatic_triangle.rs"]
245mod tests;
problemreductions/models/graph/monochromatic_triangle.rs

problemreductions/models/graph/
monochromatic_triangle.rs
