problemreductions/rules/
minimumcoveringbycliques_minimumintersectiongraphbasis.rs

1//! Reduction from MinimumCoveringByCliques to MinimumIntersectionGraphBasis.
2//!
3//! The instance mapping is the identity on the underlying graph. Witness
4//! extraction converts an intersection representation back into an edge-clique
5//! cover by labeling each edge with any shared universe element.
6
7use crate::models::graph::{MinimumCoveringByCliques, MinimumIntersectionGraphBasis};
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11use crate::traits::Problem;
12use std::collections::BTreeMap;
13
14#[derive(Debug, Clone)]
15pub struct ReductionMinimumCoveringByCliquesToMinimumIntersectionGraphBasis {
16    target: MinimumIntersectionGraphBasis<SimpleGraph>,
17}
18
19fn invalid_source_solution(num_edges: usize) -> Vec<usize> {
20    if num_edges == 0 {
21        // Deliberately wrong length so source `evaluate` returns `Min(None)`.
22        vec![0]
23    } else {
24        vec![0; num_edges - 1]
25    }
26}
27
28fn extract_edge_clique_cover(graph: &SimpleGraph, target_solution: &[usize]) -> Option<Vec<usize>> {
29    let n = graph.num_vertices();
30    let m = graph.num_edges();
31
32    if m == 0 {
33        return target_solution.is_empty().then(Vec::new);
34    }
35
36    if target_solution.len() != n * m {
37        return None;
38    }
39
40    let mut label_map = BTreeMap::new();
41    let mut next_label = 0usize;
42    let mut source_solution = Vec::with_capacity(m);
43
44    for (u, v) in graph.edges() {
45        let shared_label = (0..m).find(|&slot| {
46            target_solution[u * m + slot] == 1 && target_solution[v * m + slot] == 1
47        })?;
48        let compressed = *label_map.entry(shared_label).or_insert_with(|| {
49            let label = next_label;
50            next_label += 1;
51            label
52        });
53        source_solution.push(compressed);
54    }
55
56    Some(source_solution)
57}
58
59#[cfg(any(test, feature = "example-db"))]
60fn intersection_basis_config(graph: &SimpleGraph, subsets: &[&[usize]]) -> Vec<usize> {
61    let n = graph.num_vertices();
62    let m = graph.num_edges();
63
64    assert_eq!(subsets.len(), n, "one subset per vertex");
65
66    if m == 0 {
67        assert!(
68            subsets.iter().all(|subset| subset.is_empty()),
69            "empty graphs have empty subsets in canonical configs"
70        );
71        return Vec::new();
72    }
73
74    let mut config = vec![0; n * m];
75    for (vertex, subset) in subsets.iter().enumerate() {
76        for &slot in *subset {
77            assert!(slot < m, "intersection-basis slot out of range");
78            config[vertex * m + slot] = 1;
79        }
80    }
81    config
82}
83
84impl ReductionResult for ReductionMinimumCoveringByCliquesToMinimumIntersectionGraphBasis {
85    type Source = MinimumCoveringByCliques<SimpleGraph>;
86    type Target = MinimumIntersectionGraphBasis<SimpleGraph>;
87
88    fn target_problem(&self) -> &Self::Target {
89        &self.target
90    }
91
92    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
93        if !self.target.evaluate(target_solution).is_valid() {
94            return invalid_source_solution(self.target.num_edges());
95        }
96
97        extract_edge_clique_cover(self.target.graph(), target_solution)
98            .unwrap_or_else(|| invalid_source_solution(self.target.num_edges()))
99    }
100}
101
102#[reduction(
103    overhead = {
104        num_vertices = "num_vertices",
105        num_edges = "num_edges",
106    }
107)]
108impl ReduceTo<MinimumIntersectionGraphBasis<SimpleGraph>>
109    for MinimumCoveringByCliques<SimpleGraph>
110{
111    type Result = ReductionMinimumCoveringByCliquesToMinimumIntersectionGraphBasis;
112
113    fn reduce_to(&self) -> Self::Result {
114        Self::Result {
115            target: MinimumIntersectionGraphBasis::new(self.graph().clone()),
116        }
117    }
118}
119
120#[cfg(feature = "example-db")]
121pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
122    use crate::export::SolutionPair;
123
124    vec![crate::example_db::specs::RuleExampleSpec {
125        id: "minimumcoveringbycliques_to_minimumintersectiongraphbasis",
126        build: || {
127            let source = MinimumCoveringByCliques::new(SimpleGraph::new(
128                4,
129                vec![(0, 1), (0, 2), (1, 2), (2, 3)],
130            ));
131            let target_config =
132                intersection_basis_config(source.graph(), &[&[0], &[0], &[0, 1], &[1]]);
133
134            crate::example_db::specs::rule_example_with_witness::<
135                _,
136                MinimumIntersectionGraphBasis<SimpleGraph>,
137            >(
138                source,
139                SolutionPair {
140                    source_config: vec![0, 0, 0, 1],
141                    target_config,
142                },
143            )
144        },
145    }]
146}
147
148#[cfg(test)]
149#[path = "../unit_tests/rules/minimumcoveringbycliques_minimumintersectiongraphbasis.rs"]
150mod tests;
problemreductions/rules/minimumcoveringbycliques_minimumintersectiongraphbasis.rs

problemreductions/rules/
minimumcoveringbycliques_minimumintersectiongraphbasis.rs
