rust_igraph/algorithms/constructors/
full_bipartite.rs

1//! Complete bipartite graph constructor (ALGO-CN-035).
2//!
3//! Counterpart of `igraph_full_bipartite()` in
4//! `references/igraph/src/misc/bipartite.c:448-528`.
5//!
6//! A *complete bipartite graph* K_{n1, n2} has two partitions of sizes
7//! `n1` and `n2` with every possible edge between the two partitions
8//! (no edges within a partition).
9//!
10//! Vertices `[0, n1)` form partition 1 and vertices `[n1, n1+n2)` form
11//! partition 2.
12//!
13//! Direction is governed by [`BipartiteMode`]:
14//!
15//! * [`BipartiteMode::Out`] — arcs flow from partition 1 to partition 2.
16//! * [`BipartiteMode::In`]  — arcs flow from partition 2 to partition 1.
17//! * [`BipartiteMode::All`] — undirected, or directed with mutual arcs.
18//!
19//! Edge counts:
20//!
21//! * Undirected / directed `Out` / directed `In`: `n1 × n2`.
22//! * Directed `All`: `2 × n1 × n2`.
23
24pub use crate::algorithms::games::bipartite::BipartiteMode;
25use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
26
27/// Bundled return type of [`full_bipartite`].
28#[derive(Debug, Clone)]
29pub struct FullBipartite {
30    /// The constructed graph.
31    pub graph: Graph,
32    /// Per-vertex type: `false` = partition 1, `true` = partition 2.
33    pub types: Vec<bool>,
34}
35
36/// Build the complete bipartite graph K_{n1, n2}.
37///
38/// `n1` vertices in partition 1, `n2` vertices in partition 2.
39/// The result graph has `n1 + n2` vertices and `n1 × n2` edges
40/// (or `2 × n1 × n2` arcs when directed mutual).
41///
42/// # Errors
43///
44/// * [`IgraphError::InvalidArgument`] — vertex count `n1 + n2`
45///   overflows `u32`, or the edge count overflows `usize`.
46///
47/// # Examples
48///
49/// ```
50/// use rust_igraph::{full_bipartite, BipartiteMode};
51///
52/// // K_{2,3} undirected: 5 vertices, 6 edges.
53/// let r = full_bipartite(2, 3, false, BipartiteMode::All).unwrap();
54/// assert_eq!(r.graph.vcount(), 5);
55/// assert_eq!(r.graph.ecount(), 6);
56/// assert_eq!(r.types, vec![false, false, true, true, true]);
57///
58/// // K_{2,3} directed out: 5 vertices, 6 arcs.
59/// let d = full_bipartite(2, 3, true, BipartiteMode::Out).unwrap();
60/// assert_eq!(d.graph.ecount(), 6);
61/// assert!(d.graph.is_directed());
62///
63/// // K_{2,3} directed mutual: 12 arcs.
64/// let m = full_bipartite(2, 3, true, BipartiteMode::All).unwrap();
65/// assert_eq!(m.graph.ecount(), 12);
66/// ```
67pub fn full_bipartite(
68    n1: u32,
69    n2: u32,
70    directed: bool,
71    mode: BipartiteMode,
72) -> IgraphResult<FullBipartite> {
73    let total = n1.checked_add(n2).ok_or_else(|| {
74        IgraphError::InvalidArgument(format!(
75            "full_bipartite: total vertex count {n1} + {n2} overflows u32"
76        ))
77    })?;
78
79    if total == 0 {
80        let graph = Graph::new(0, directed)?;
81        return Ok(FullBipartite {
82            graph,
83            types: Vec::new(),
84        });
85    }
86
87    let n1_us = n1 as usize;
88    let n2_us = n2 as usize;
89    let base_edges = n1_us.checked_mul(n2_us).ok_or_else(|| {
90        IgraphError::InvalidArgument("full_bipartite: edge count overflows usize".to_string())
91    })?;
92    let num_edges = if directed && mode == BipartiteMode::All {
93        base_edges.checked_mul(2).ok_or_else(|| {
94            IgraphError::InvalidArgument(
95                "full_bipartite: mutual edge count overflows usize".to_string(),
96            )
97        })?
98    } else {
99        base_edges
100    };
101
102    let mut edges: Vec<(VertexId, VertexId)> = Vec::with_capacity(num_edges);
103
104    match mode {
105        BipartiteMode::Out | BipartiteMode::All if !directed => {
106            for i in 0..n1 {
107                for j in 0..n2 {
108                    edges.push((i, n1 + j));
109                }
110            }
111        }
112        BipartiteMode::Out => {
113            for i in 0..n1 {
114                for j in 0..n2 {
115                    edges.push((i, n1 + j));
116                }
117            }
118        }
119        BipartiteMode::In => {
120            for i in 0..n1 {
121                for j in 0..n2 {
122                    edges.push((n1 + j, i));
123                }
124            }
125        }
126        BipartiteMode::All => {
127            for i in 0..n1 {
128                for j in 0..n2 {
129                    edges.push((i, n1 + j));
130                    edges.push((n1 + j, i));
131                }
132            }
133        }
134    }
135
136    let mut graph = Graph::new(total, directed)?;
137    graph.add_edges(edges)?;
138
139    let mut types = vec![false; total as usize];
140    for i in n1..total {
141        types[i as usize] = true;
142    }
143
144    Ok(FullBipartite { graph, types })
145}
146
147#[cfg(test)]
148mod tests {
149    use super::*;
150
151    #[test]
152    fn empty_graph() {
153        let r = full_bipartite(0, 0, false, BipartiteMode::All).unwrap();
154        assert_eq!(r.graph.vcount(), 0);
155        assert_eq!(r.graph.ecount(), 0);
156        assert!(r.types.is_empty());
157    }
158
159    #[test]
160    fn one_partition_empty() {
161        let r = full_bipartite(3, 0, false, BipartiteMode::All).unwrap();
162        assert_eq!(r.graph.vcount(), 3);
163        assert_eq!(r.graph.ecount(), 0);
164        assert_eq!(r.types, vec![false, false, false]);
165    }
166
167    #[test]
168    fn other_partition_empty() {
169        let r = full_bipartite(0, 4, false, BipartiteMode::All).unwrap();
170        assert_eq!(r.graph.vcount(), 4);
171        assert_eq!(r.graph.ecount(), 0);
172        assert_eq!(r.types, vec![true, true, true, true]);
173    }
174
175    #[test]
176    fn k23_undirected() {
177        let r = full_bipartite(2, 3, false, BipartiteMode::All).unwrap();
178        assert_eq!(r.graph.vcount(), 5);
179        assert_eq!(r.graph.ecount(), 6);
180        assert!(!r.graph.is_directed());
181        assert_eq!(r.types, vec![false, false, true, true, true]);
182    }
183
184    #[test]
185    fn k11_undirected() {
186        let r = full_bipartite(1, 1, false, BipartiteMode::All).unwrap();
187        assert_eq!(r.graph.vcount(), 2);
188        assert_eq!(r.graph.ecount(), 1);
189        assert_eq!(r.types, vec![false, true]);
190    }
191
192    #[test]
193    fn k33_undirected() {
194        let r = full_bipartite(3, 3, false, BipartiteMode::All).unwrap();
195        assert_eq!(r.graph.vcount(), 6);
196        assert_eq!(r.graph.ecount(), 9);
197    }
198
199    #[test]
200    fn directed_out() {
201        let r = full_bipartite(2, 3, true, BipartiteMode::Out).unwrap();
202        assert!(r.graph.is_directed());
203        assert_eq!(r.graph.ecount(), 6);
204        // All edges go from partition 1 → partition 2
205        for eid in 0..r.graph.ecount() {
206            #[allow(clippy::cast_possible_truncation)]
207            let e = eid as u32;
208            let (s, t) = r.graph.edge(e).unwrap();
209            assert!(!r.types[s as usize], "source should be partition 1");
210            assert!(r.types[t as usize], "target should be partition 2");
211        }
212    }
213
214    #[test]
215    fn directed_in() {
216        let r = full_bipartite(2, 3, true, BipartiteMode::In).unwrap();
217        assert!(r.graph.is_directed());
218        assert_eq!(r.graph.ecount(), 6);
219        // All edges go from partition 2 → partition 1
220        for eid in 0..r.graph.ecount() {
221            #[allow(clippy::cast_possible_truncation)]
222            let e = eid as u32;
223            let (s, t) = r.graph.edge(e).unwrap();
224            assert!(r.types[s as usize], "source should be partition 2");
225            assert!(!r.types[t as usize], "target should be partition 1");
226        }
227    }
228
229    #[test]
230    fn directed_mutual() {
231        let r = full_bipartite(2, 3, true, BipartiteMode::All).unwrap();
232        assert!(r.graph.is_directed());
233        assert_eq!(r.graph.ecount(), 12); // 2 × 2 × 3
234    }
235
236    #[test]
237    fn types_correctness() {
238        let r = full_bipartite(4, 2, false, BipartiteMode::All).unwrap();
239        assert_eq!(r.types, vec![false, false, false, false, true, true]);
240    }
241
242    #[test]
243    fn bipartite_structure_no_within_partition_edges() {
244        let r = full_bipartite(3, 4, false, BipartiteMode::All).unwrap();
245        for eid in 0..r.graph.ecount() {
246            #[allow(clippy::cast_possible_truncation)]
247            let e = eid as u32;
248            let (s, t) = r.graph.edge(e).unwrap();
249            assert_ne!(
250                r.types[s as usize], r.types[t as usize],
251                "edge ({s}, {t}) connects same partition"
252            );
253        }
254    }
255
256    #[test]
257    fn overflow_vertex_count_errors() {
258        let result = full_bipartite(u32::MAX, 1, false, BipartiteMode::All);
259        assert!(result.is_err());
260    }
261}
rust_igraph/algorithms/constructors/full_bipartite.rs

rust_igraph/algorithms/constructors/
full_bipartite.rs
