problemreductions/rules/
bmf_bicliquecover.rs

1//! Reduction from BMF (exact Boolean Matrix Factorization) to BicliqueCover.
2//!
3//! Classical equivalence (Monson, Pullman, Rees 1995): an m x n boolean
4//! matrix `A` is the biadjacency matrix of the bipartite graph `G_A`, and
5//! each rank-1 factor of `A = B ⊙ C` is exactly a (complete) biclique of
6//! `G_A` — its left side is `{i : B[i][r] = 1}` and its right side is
7//! `{j : C[r][j] = 1}`. Hence an exact rank-`k` factorization corresponds
8//! to a cover of `E(G_A)` by `k` sub-bicliques of `G_A`, and the total
9//! factor weight `|B|_1 + |C|_1` equals the total biclique size (the
10//! number of vertex memberships summed over all bicliques).
11//!
12//! Variable-layout mapping: BMF stores `B` row-major followed by `C`
13//! row-major, while BicliqueCover stores vertex memberships vertex-major.
14//! `extract_solution` transposes the right-vertex half so the extracted
15//! BMF config matches `B` and `C`.
16
17use crate::models::algebraic::BMF;
18use crate::models::graph::BicliqueCover;
19use crate::reduction;
20use crate::rules::traits::{ReduceTo, ReductionResult};
21use crate::topology::BipartiteGraph;
22
23/// Convert one vertex-membership row per biclique into BMF factors.
24pub(crate) fn config_bc_to_bmf(
25    bc: &[Vec<bool>],
26    m: usize,
27    n: usize,
28    k: usize,
29) -> (Vec<Vec<bool>>, Vec<Vec<bool>>) {
30    let mut b = vec![vec![false; k]; m];
31    let mut c = vec![vec![false; n]; k];
32    for i in 0..m {
33        for l in 0..k {
34            b[i][l] = bc[l][i];
35        }
36    }
37    for l in 0..k {
38        for j in 0..n {
39            c[l][j] = bc[l][m + j];
40        }
41    }
42    (b, c)
43}
44
45/// Inverse of [`config_bc_to_bmf`].
46pub(crate) fn config_bmf_to_bc(
47    bmf: &(Vec<Vec<bool>>, Vec<Vec<bool>>),
48    m: usize,
49    n: usize,
50    k: usize,
51) -> Vec<Vec<bool>> {
52    let (b, c) = bmf;
53    let mut bc = vec![vec![false; m + n]; k];
54    for i in 0..m {
55        for l in 0..k {
56            bc[l][i] = b[i][l];
57        }
58    }
59    for l in 0..k {
60        for j in 0..n {
61            bc[l][m + j] = c[l][j];
62        }
63    }
64    bc
65}
66
67/// Result of reducing BMF to BicliqueCover.
68#[derive(Debug, Clone)]
69pub struct ReductionBMFToBicliqueCover {
70    target: BicliqueCover,
71    m: usize,
72    n: usize,
73    k: usize,
74}
75
76impl ReductionResult for ReductionBMFToBicliqueCover {
77    type Source = BMF;
78    type Target = BicliqueCover;
79
80    fn target_problem(&self) -> &BicliqueCover {
81        &self.target
82    }
83
84    /// Map a BicliqueCover config (vertex-major) back to a BMF config (B row-major, then C row-major).
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(config_bc_to_bmf(target_solution, self.m, self.n, self.k))
92    }
93}
94
95#[reduction(
96    transform = exact {
97        num_vertices = "rows + cols",
98        num_edges = "rows * cols",
99        rank = "rank",
100    },
101    unavailable = {
102        left_size = "the exact target parameter is not represented by this reduction's symbolic transform",
103        right_size = "the exact target parameter is not represented by this reduction's symbolic transform",
104    }
105)]
106impl ReduceTo<BicliqueCover> for BMF {
107    type Result = ReductionBMFToBicliqueCover;
108
109    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
110        let m = self.rows();
111        let n = self.cols();
112        let k = self.rank();
113        let mut edges = Vec::new();
114        for (i, row) in self.matrix().iter().enumerate() {
115            for (j, &val) in row.iter().enumerate() {
116                if val {
117                    edges.push((i, j));
118                }
119            }
120        }
121        let target = BicliqueCover::new(BipartiteGraph::new(m, n, edges), k);
122        Ok(ReductionBMFToBicliqueCover { target, m, n, k })
123    }
124}
125
126#[cfg(feature = "example-db")]
127pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
128    use crate::export::SolutionPair;
129
130    vec![crate::example_db::specs::RuleExampleSpec {
131        id: "bmf_to_bicliquecover",
132        build: || {
133            // 2x2 all-ones, rank 1 — a single biclique covering both sides exactly.
134            let source = BMF::new(vec![vec![true, true], vec![true, true]], 1);
135            crate::example_db::specs::rule_example_with_witness::<_, BicliqueCover>(
136                source,
137                SolutionPair {
138                    source_config: serde_json::json!((
139                        vec![vec![true], vec![true]],
140                        vec![vec![true, true]]
141                    )),
142                    target_config: serde_json::json!(vec![vec![true, true, true, true]]),
143                },
144            )
145        },
146    }]
147}
148
149#[cfg(test)]
150#[path = "../unit_tests/rules/bmf_bicliquecover.rs"]
151mod tests;
problemreductions/rules/bmf_bicliquecover.rs

problemreductions/rules/
bmf_bicliquecover.rs
