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

problemreductions/rules/
minimumcoveringbycliques_minimumintersectiongraphbasis.rs
