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 extract_edge_clique_cover(
20    graph: &SimpleGraph,
21    target_solution: &[Vec<bool>],
22) -> Option<Vec<usize>> {
23    let n = graph.num_vertices();
24    let m = graph.num_edges();
25
26    if target_solution.len() != n || target_solution.iter().any(|row| row.len() != m) {
27        return None;
28    }
29
30    if m == 0 {
31        return Some(Vec::new());
32    }
33
34    let mut label_map = BTreeMap::new();
35    let mut next_label = 0usize;
36    let mut source_solution = Vec::with_capacity(m);
37
38    for (u, v) in graph.edges() {
39        let shared_label =
40            (0..m).find(|&slot| target_solution[u][slot] && target_solution[v][slot])?;
41        let compressed = *label_map.entry(shared_label).or_insert_with(|| {
42            let label = next_label;
43            next_label += 1;
44            label
45        });
46        source_solution.push(compressed);
47    }
48
49    Some(source_solution)
50}
51
52#[cfg(any(test, feature = "example-db"))]
53fn intersection_basis_config(graph: &SimpleGraph, subsets: &[&[usize]]) -> Vec<Vec<bool>> {
54    let n = graph.num_vertices();
55    let m = graph.num_edges();
56
57    assert_eq!(subsets.len(), n, "one subset per vertex");
58
59    if m == 0 {
60        assert!(
61            subsets.iter().all(|subset| subset.is_empty()),
62            "empty graphs have empty subsets in canonical configs"
63        );
64        return vec![Vec::new(); n];
65    }
66
67    let mut config = vec![vec![false; m]; n];
68    for (vertex, subset) in subsets.iter().enumerate() {
69        for &slot in *subset {
70            assert!(slot < m, "intersection-basis slot out of range");
71            config[vertex][slot] = true;
72        }
73    }
74    config
75}
76
77impl ReductionResult for ReductionMinimumCoveringByCliquesToMinimumIntersectionGraphBasis {
78    type Source = MinimumCoveringByCliques<SimpleGraph>;
79    type Target = MinimumIntersectionGraphBasis<SimpleGraph>;
80
81    fn target_problem(&self) -> &Self::Target {
82        &self.target
83    }
84
85    fn extract_solution(
86        &self,
87        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
88    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
89        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
90
91        Ok({
92            if !self.target.evaluate(target_solution)?.is_valid() {
93                return Err(crate::rules::ExtractionError::invalid(
94                    "target configuration is not a valid intersection graph basis",
95                ));
96            }
97
98            extract_edge_clique_cover(self.target.graph(), target_solution).ok_or_else(|| {
99                crate::rules::ExtractionError::invalid(
100                    "target basis does not assign a shared label to every source edge",
101                )
102            })?
103        })
104    }
105}
106
107#[reduction(
108    transform = exact {
109        num_vertices = "num_vertices",
110        num_edges = "num_edges",
111    }
112)]
113impl ReduceTo<MinimumIntersectionGraphBasis<SimpleGraph>>
114    for MinimumCoveringByCliques<SimpleGraph>
115{
116    type Result = ReductionMinimumCoveringByCliquesToMinimumIntersectionGraphBasis;
117
118    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
119        Ok(Self::Result {
120            target: MinimumIntersectionGraphBasis::new(self.graph().clone()),
121        })
122    }
123}
124
125#[cfg(feature = "example-db")]
126pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
127    use crate::export::SolutionPair;
128
129    vec![crate::example_db::specs::RuleExampleSpec {
130        id: "minimumcoveringbycliques_to_minimumintersectiongraphbasis",
131        build: || {
132            let source = MinimumCoveringByCliques::new(SimpleGraph::new(
133                4,
134                vec![(0, 1), (0, 2), (1, 2), (2, 3)],
135            ));
136            let target_config =
137                intersection_basis_config(source.graph(), &[&[0], &[0], &[0, 1], &[1]]);
138
139            crate::example_db::specs::rule_example_with_witness::<
140                _,
141                MinimumIntersectionGraphBasis<SimpleGraph>,
142            >(
143                source,
144                SolutionPair {
145                    source_config: serde_json::json!(vec![0, 0, 0, 1]),
146                    target_config: serde_json::to_value(target_config)
147                        .expect("solution serialization must succeed"),
148                },
149            )
150        },
151    }]
152}
153
154#[cfg(test)]
155#[path = "../unit_tests/rules/minimumcoveringbycliques_minimumintersectiongraphbasis.rs"]
156mod tests;
problemreductions/rules/minimumcoveringbycliques_minimumintersectiongraphbasis.rs

problemreductions/rules/
minimumcoveringbycliques_minimumintersectiongraphbasis.rs
