rust_igraph/algorithms/constructors/
weighted_biadjacency.rs

1//! Bipartite graph from a weighted biadjacency matrix (ALGO-CN-038).
2//!
3//! Counterpart of `igraph_weighted_biadjacency()` in
4//! `references/igraph/src/misc/bipartite.c:770-830`.
5//!
6//! Creates a bipartite graph from an `n1 × n2` weighted matrix where
7//! non-zero entries become edges whose weight is the entry value.
8
9use crate::algorithms::games::bipartite::BipartiteMode;
10use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
11
12/// Result of [`weighted_biadjacency`].
13#[derive(Debug, Clone)]
14pub struct WeightedBiadjacencyResult {
15    /// The constructed bipartite graph on `n1 + n2` vertices.
16    pub graph: Graph,
17    /// Per-vertex type: `false` = partition 1 (rows), `true` = partition 2 (columns).
18    pub types: Vec<bool>,
19    /// Per-edge weight corresponding to the matrix entry that produced it.
20    pub weights: Vec<f64>,
21}
22
23/// Build a bipartite graph from a weighted biadjacency matrix.
24///
25/// The matrix has `n1` rows and `n2` columns. The resulting graph has
26/// `n1 + n2` vertices: vertices `[0, n1)` correspond to rows (partition 1)
27/// and vertices `[n1, n1+n2)` correspond to columns (partition 2).
28///
29/// Each non-zero entry in the matrix produces one edge (or two mutual
30/// edges when `directed = true` and `mode = All`) whose weight equals
31/// the matrix entry value.
32///
33/// # Parameters
34///
35/// * `matrix` — row-major `n1 × n2` weighted biadjacency matrix (all rows
36///   must have equal length `n2`).
37/// * `directed` — whether the resulting graph is directed.
38/// * `mode` — edge direction policy (only meaningful when `directed = true`):
39///   - [`BipartiteMode::Out`] — arcs from rows to columns.
40///   - [`BipartiteMode::In`] — arcs from columns to rows.
41///   - [`BipartiteMode::All`] — mutual arcs in both directions.
42///
43/// # Errors
44///
45/// * [`IgraphError::InvalidArgument`] — ragged matrix or vertex count overflow.
46///
47/// # Examples
48///
49/// ```
50/// use rust_igraph::{weighted_biadjacency, BipartiteMode};
51///
52/// let matrix: &[&[f64]] = &[
53///     &[1.5, 0.0],
54///     &[0.0, 2.5],
55/// ];
56/// let r = weighted_biadjacency(matrix, false, BipartiteMode::All).unwrap();
57/// assert_eq!(r.graph.vcount(), 4);
58/// assert_eq!(r.graph.ecount(), 2);
59/// assert_eq!(r.weights, vec![1.5, 2.5]);
60/// assert_eq!(r.types, vec![false, false, true, true]);
61/// ```
62pub fn weighted_biadjacency(
63    matrix: &[&[f64]],
64    directed: bool,
65    mode: BipartiteMode,
66) -> IgraphResult<WeightedBiadjacencyResult> {
67    let n1 = matrix.len();
68    let n2 = if n1 == 0 { 0 } else { matrix[0].len() };
69
70    for (row_idx, row) in matrix.iter().enumerate() {
71        if row.len() != n2 {
72            return Err(IgraphError::InvalidArgument(format!(
73                "weighted_biadjacency: row {row_idx} has length {} but expected {n2}",
74                row.len()
75            )));
76        }
77    }
78
79    let total = n1.checked_add(n2).ok_or_else(|| {
80        IgraphError::InvalidArgument(
81            "weighted_biadjacency: total vertex count overflows usize".to_string(),
82        )
83    })?;
84    let total_u32 = u32::try_from(total).map_err(|_| {
85        IgraphError::InvalidArgument(
86            "weighted_biadjacency: total vertex count exceeds u32::MAX".to_string(),
87        )
88    })?;
89    let n1_u32 = u32::try_from(n1).map_err(|_| {
90        IgraphError::InvalidArgument("weighted_biadjacency: n1 exceeds u32::MAX".to_string())
91    })?;
92    let n2_u32 = u32::try_from(n2).map_err(|_| {
93        IgraphError::InvalidArgument("weighted_biadjacency: n2 exceeds u32::MAX".to_string())
94    })?;
95
96    let mut edges: Vec<(VertexId, VertexId)> = Vec::new();
97    let mut weights: Vec<f64> = Vec::new();
98
99    for j in 0..n2_u32 {
100        for i in 0..n1_u32 {
101            let weight = matrix[i as usize][j as usize];
102            if weight == 0.0 {
103                continue;
104            }
105
106            let (from, to) = if mode == BipartiteMode::In {
107                (n1_u32 + j, i)
108            } else {
109                (i, n1_u32 + j)
110            };
111
112            if mode != BipartiteMode::All || !directed {
113                edges.push((from, to));
114                weights.push(weight);
115            } else {
116                edges.push((from, to));
117                weights.push(weight);
118                edges.push((to, from));
119                weights.push(weight);
120            }
121        }
122    }
123
124    let mut graph = Graph::new(total_u32, directed)?;
125    if !edges.is_empty() {
126        graph.add_edges(edges)?;
127    }
128
129    let mut types = vec![false; total];
130    for t in types.iter_mut().skip(n1) {
131        *t = true;
132    }
133
134    Ok(WeightedBiadjacencyResult {
135        graph,
136        types,
137        weights,
138    })
139}
140
141#[cfg(test)]
142#[allow(clippy::float_cmp)]
143mod tests {
144    use super::*;
145
146    #[test]
147    fn empty_matrix() {
148        let matrix: &[&[f64]] = &[];
149        let r = weighted_biadjacency(matrix, false, BipartiteMode::All).unwrap();
150        assert_eq!(r.graph.vcount(), 0);
151        assert_eq!(r.graph.ecount(), 0);
152        assert!(r.weights.is_empty());
153        assert!(r.types.is_empty());
154    }
155
156    #[test]
157    fn single_nonzero() {
158        let matrix: &[&[f64]] = &[&[3.5]];
159        let r = weighted_biadjacency(matrix, false, BipartiteMode::All).unwrap();
160        assert_eq!(r.graph.vcount(), 2);
161        assert_eq!(r.graph.ecount(), 1);
162        assert_eq!(r.weights, vec![3.5]);
163        assert_eq!(r.types, vec![false, true]);
164    }
165
166    #[test]
167    fn single_zero() {
168        let matrix: &[&[f64]] = &[&[0.0]];
169        let r = weighted_biadjacency(matrix, false, BipartiteMode::All).unwrap();
170        assert_eq!(r.graph.vcount(), 2);
171        assert_eq!(r.graph.ecount(), 0);
172        assert!(r.weights.is_empty());
173    }
174
175    #[test]
176    fn two_by_two() {
177        let matrix: &[&[f64]] = &[&[1.5, 0.0], &[0.0, 2.5]];
178        let r = weighted_biadjacency(matrix, false, BipartiteMode::All).unwrap();
179        assert_eq!(r.graph.vcount(), 4);
180        assert_eq!(r.graph.ecount(), 2);
181        assert_eq!(r.weights, vec![1.5, 2.5]);
182        assert_eq!(r.types, vec![false, false, true, true]);
183    }
184
185    #[test]
186    fn negative_weight() {
187        let matrix: &[&[f64]] = &[&[-2.0]];
188        let r = weighted_biadjacency(matrix, false, BipartiteMode::All).unwrap();
189        assert_eq!(r.graph.ecount(), 1);
190        assert_eq!(r.weights, vec![-2.0]);
191    }
192
193    #[test]
194    fn directed_out() {
195        let matrix: &[&[f64]] = &[&[1.0, 2.0]];
196        let r = weighted_biadjacency(matrix, true, BipartiteMode::Out).unwrap();
197        assert!(r.graph.is_directed());
198        assert_eq!(r.graph.ecount(), 2);
199        for eid in 0..r.graph.ecount() {
200            #[allow(clippy::cast_possible_truncation)]
201            let (s, t) = r.graph.edge(eid as u32).unwrap();
202            assert!(!r.types[s as usize], "source should be row");
203            assert!(r.types[t as usize], "target should be col");
204        }
205        assert_eq!(r.weights, vec![1.0, 2.0]);
206    }
207
208    #[test]
209    fn directed_in() {
210        let matrix: &[&[f64]] = &[&[1.0, 2.0]];
211        let r = weighted_biadjacency(matrix, true, BipartiteMode::In).unwrap();
212        assert!(r.graph.is_directed());
213        assert_eq!(r.graph.ecount(), 2);
214        for eid in 0..r.graph.ecount() {
215            #[allow(clippy::cast_possible_truncation)]
216            let (s, t) = r.graph.edge(eid as u32).unwrap();
217            assert!(r.types[s as usize], "source should be col");
218            assert!(!r.types[t as usize], "target should be row");
219        }
220    }
221
222    #[test]
223    fn directed_all_mutual() {
224        let matrix: &[&[f64]] = &[&[5.0]];
225        let r = weighted_biadjacency(matrix, true, BipartiteMode::All).unwrap();
226        assert!(r.graph.is_directed());
227        assert_eq!(r.graph.ecount(), 2);
228        assert_eq!(r.weights, vec![5.0, 5.0]);
229    }
230
231    #[test]
232    fn undirected_ignores_mode() {
233        let matrix: &[&[f64]] = &[&[1.0]];
234        let r_out = weighted_biadjacency(matrix, false, BipartiteMode::Out).unwrap();
235        let r_all = weighted_biadjacency(matrix, false, BipartiteMode::All).unwrap();
236        assert_eq!(r_out.graph.ecount(), 1);
237        assert_eq!(r_all.graph.ecount(), 1);
238    }
239
240    #[test]
241    fn ragged_matrix_rejected() {
242        let matrix: &[&[f64]] = &[&[1.0, 2.0], &[3.0]];
243        let result = weighted_biadjacency(matrix, false, BipartiteMode::All);
244        assert!(result.is_err());
245    }
246
247    #[test]
248    fn larger_matrix() {
249        let matrix: &[&[f64]] = &[&[1.0, 0.0, 3.0], &[0.0, 2.0, 0.0], &[4.0, 0.0, 0.0]];
250        let r = weighted_biadjacency(matrix, false, BipartiteMode::All).unwrap();
251        assert_eq!(r.graph.vcount(), 6); // 3 + 3
252        assert_eq!(r.graph.ecount(), 4); // 4 non-zero entries
253        assert_eq!(r.weights.len(), 4);
254        assert_eq!(r.types, vec![false, false, false, true, true, true]);
255    }
256}
rust_igraph/algorithms/constructors/weighted_biadjacency.rs

rust_igraph/algorithms/constructors/
weighted_biadjacency.rs
