problemreductions/rules/
monochromatictriangle_ilp.rs

1//! Reduction from MonochromaticTriangle to ILP.
2//!
3//! Use one binary variable per edge color. Every triangle must use both colors,
4//! encoded as the pair of inequalities `1 <= sum <= 2` over its three incident
5//! edge variables.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::graph::MonochromaticTriangle;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::topology::SimpleGraph;
12
13/// Result of reducing MonochromaticTriangle to ILP.
14#[derive(Debug, Clone)]
15pub struct ReductionMonochromaticTriangleToILP {
16    target: ILP<bool>,
17}
18
19impl ReductionResult for ReductionMonochromaticTriangleToILP {
20    type Source = MonochromaticTriangle<SimpleGraph>;
21    type Target = ILP<bool>;
22
23    fn target_problem(&self) -> &Self::Target {
24        &self.target
25    }
26
27    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
28        target_solution.to_vec()
29    }
30}
31
32#[reduction(
33    overhead = {
34        num_vars = "num_edges",
35        num_constraints = "2 * num_triangles",
36    }
37)]
38impl ReduceTo<ILP<bool>> for MonochromaticTriangle<SimpleGraph> {
39    type Result = ReductionMonochromaticTriangleToILP;
40
41    fn reduce_to(&self) -> Self::Result {
42        let mut constraints = Vec::with_capacity(2 * self.num_triangles());
43        for triangle in self.triangles() {
44            let terms: Vec<(usize, f64)> =
45                triangle.iter().map(|&edge_idx| (edge_idx, 1.0)).collect();
46            constraints.push(LinearConstraint::ge(terms.clone(), 1.0));
47            constraints.push(LinearConstraint::le(terms, 2.0));
48        }
49
50        ReductionMonochromaticTriangleToILP {
51            target: ILP::new(
52                self.num_edges(),
53                constraints,
54                vec![],
55                ObjectiveSense::Minimize,
56            ),
57        }
58    }
59}
60
61#[cfg(feature = "example-db")]
62pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
63    use crate::topology::SimpleGraph;
64
65    vec![crate::example_db::specs::RuleExampleSpec {
66        id: "monochromatictriangle_to_ilp",
67        build: || {
68            let source = MonochromaticTriangle::new(SimpleGraph::new(
69                4,
70                vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)],
71            ));
72            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
73        },
74    }]
75}
76
77#[cfg(test)]
78#[path = "../unit_tests/rules/monochromatictriangle_ilp.rs"]
79mod tests;
problemreductions/rules/monochromatictriangle_ilp.rs

problemreductions/rules/
monochromatictriangle_ilp.rs
