rust_igraph/algorithms/constructors/
create_bipartite.rs

1//! Bipartite graph constructor with validation (ALGO-CN-036).
2//!
3//! Counterpart of `igraph_create_bipartite()` in
4//! `references/igraph/src/misc/bipartite.c:556-590`.
5//!
6//! Creates a graph from a type vector and edge list, verifying that
7//! every edge connects vertices of different types (the bipartite
8//! invariant).
9
10use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
11
12/// Create a bipartite graph from a type vector and edge list.
13///
14/// Validates that every edge connects vertices of different types
15/// (one endpoint in each partition). The type vector length defines
16/// the vertex count.
17///
18/// # Parameters
19///
20/// * `types` — per-vertex partition: `false` = partition 0, `true` = partition 1.
21/// * `edges` — pairs `(from, to)` of vertex IDs.
22/// * `directed` — whether the resulting graph is directed.
23///
24/// # Errors
25///
26/// * [`IgraphError::InvalidArgument`] — a vertex ID in `edges` is out of
27///   range, or an edge connects two vertices of the same type.
28///
29/// # Examples
30///
31/// ```
32/// use rust_igraph::create_bipartite;
33///
34/// // Simple K_{2,2} bipartite graph.
35/// let types = vec![false, false, true, true];
36/// let edges = vec![(0, 2), (0, 3), (1, 2), (1, 3)];
37/// let g = create_bipartite(&types, &edges, false).unwrap();
38/// assert_eq!(g.vcount(), 4);
39/// assert_eq!(g.ecount(), 4);
40///
41/// // Rejects same-type edges.
42/// let bad_edges = vec![(0, 1)]; // both false
43/// assert!(create_bipartite(&types, &bad_edges, false).is_err());
44/// ```
45pub fn create_bipartite(
46    types: &[bool],
47    edges: &[(VertexId, VertexId)],
48    directed: bool,
49) -> IgraphResult<Graph> {
50    let n = u32::try_from(types.len()).map_err(|_| {
51        IgraphError::InvalidArgument("create_bipartite: vertex count exceeds u32::MAX".to_string())
52    })?;
53
54    for (i, &(from, to)) in edges.iter().enumerate() {
55        if from >= n {
56            return Err(IgraphError::InvalidArgument(format!(
57                "create_bipartite: edge {i} source vertex {from} out of range (n={n})"
58            )));
59        }
60        if to >= n {
61            return Err(IgraphError::InvalidArgument(format!(
62                "create_bipartite: edge {i} target vertex {to} out of range (n={n})"
63            )));
64        }
65        let t_from = types[from as usize];
66        let t_to = types[to as usize];
67        if t_from == t_to {
68            return Err(IgraphError::InvalidArgument(format!(
69                "create_bipartite: edge {i} ({from}, {to}) connects vertices of the same type"
70            )));
71        }
72    }
73
74    let mut graph = Graph::new(n, directed)?;
75    if !edges.is_empty() {
76        graph.add_edges(edges.to_vec())?;
77    }
78
79    Ok(graph)
80}
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85
86    #[test]
87    fn empty_graph() {
88        let g = create_bipartite(&[], &[], false).unwrap();
89        assert_eq!(g.vcount(), 0);
90        assert_eq!(g.ecount(), 0);
91    }
92
93    #[test]
94    fn no_edges() {
95        let types = vec![false, true, false, true];
96        let g = create_bipartite(&types, &[], false).unwrap();
97        assert_eq!(g.vcount(), 4);
98        assert_eq!(g.ecount(), 0);
99    }
100
101    #[test]
102    fn k22_undirected() {
103        let types = vec![false, false, true, true];
104        let edges = vec![(0, 2), (0, 3), (1, 2), (1, 3)];
105        let g = create_bipartite(&types, &edges, false).unwrap();
106        assert_eq!(g.vcount(), 4);
107        assert_eq!(g.ecount(), 4);
108        assert!(!g.is_directed());
109    }
110
111    #[test]
112    fn k22_directed() {
113        let types = vec![false, false, true, true];
114        let edges = vec![(0, 2), (0, 3), (1, 2), (1, 3)];
115        let g = create_bipartite(&types, &edges, true).unwrap();
116        assert_eq!(g.vcount(), 4);
117        assert_eq!(g.ecount(), 4);
118        assert!(g.is_directed());
119    }
120
121    #[test]
122    fn rejects_same_type_edge_both_false() {
123        let types = vec![false, false, true];
124        let edges = vec![(0, 1)];
125        let result = create_bipartite(&types, &edges, false);
126        assert!(result.is_err());
127    }
128
129    #[test]
130    fn rejects_same_type_edge_both_true() {
131        let types = vec![false, true, true];
132        let edges = vec![(1, 2)];
133        let result = create_bipartite(&types, &edges, false);
134        assert!(result.is_err());
135    }
136
137    #[test]
138    fn rejects_out_of_range_source() {
139        let types = vec![false, true];
140        let edges = vec![(5, 1)];
141        let result = create_bipartite(&types, &edges, false);
142        assert!(result.is_err());
143    }
144
145    #[test]
146    fn rejects_out_of_range_target() {
147        let types = vec![false, true];
148        let edges = vec![(0, 5)];
149        let result = create_bipartite(&types, &edges, false);
150        assert!(result.is_err());
151    }
152
153    #[test]
154    fn single_edge() {
155        let types = vec![false, true];
156        let edges = vec![(0, 1)];
157        let g = create_bipartite(&types, &edges, false).unwrap();
158        assert_eq!(g.vcount(), 2);
159        assert_eq!(g.ecount(), 1);
160    }
161
162    #[test]
163    fn mixed_type_ordering() {
164        // Types don't need to be contiguous
165        let types = vec![true, false, true, false];
166        let edges = vec![(0, 1), (0, 3), (2, 1), (2, 3)];
167        let g = create_bipartite(&types, &edges, false).unwrap();
168        assert_eq!(g.vcount(), 4);
169        assert_eq!(g.ecount(), 4);
170    }
171
172    #[test]
173    fn valid_directed_reverse_edges() {
174        let types = vec![false, true];
175        let edges = vec![(1, 0)]; // true -> false is valid
176        let g = create_bipartite(&types, &edges, true).unwrap();
177        assert_eq!(g.ecount(), 1);
178    }
179}
rust_igraph/algorithms/constructors/create_bipartite.rs

rust_igraph/algorithms/constructors/
create_bipartite.rs
