rust_igraph/algorithms/layout/
bipartite.rs

1//! Bipartite layout (ALGO-LO-006).
2//!
3//! Places vertices of a bipartite graph in two rows, then optimizes
4//! horizontal positions via the Sugiyama crossing minimization.
5
6use crate::algorithms::layout::sugiyama::{SugiyamaParams, layout_sugiyama};
7use crate::core::Graph;
8use crate::core::{IgraphError, IgraphResult};
9
10/// Compute a bipartite layout.
11///
12/// Vertices are placed in two rows based on their boolean type. Horizontal
13/// positions are optimized to minimize edge crossings using the Sugiyama
14/// algorithm.
15///
16/// # Arguments
17///
18/// * `graph` — the input graph (need not actually be bipartite; any graph
19///   with a two-coloring works).
20/// * `types` — boolean slice of length `vcount`: `true` places the vertex
21///   in row 0 (top), `false` in row 1 (bottom).
22/// * `hgap` — preferred minimum horizontal gap between vertices in the
23///   same row.
24/// * `vgap` — vertical distance between the two rows.
25/// * `maxiter` — maximum crossing-minimization iterations (100 is typical).
26///
27/// Returns `[x, y]` positions for each vertex.
28///
29/// # Errors
30///
31/// Returns `InvalidArgument` if `types.len() != graph.vcount()` or if
32/// `hgap` is negative.
33///
34/// # Examples
35///
36/// ```
37/// use rust_igraph::{Graph, layout_bipartite};
38///
39/// // K_{2,3}: vertices 0,1 in one part, 2,3,4 in the other
40/// let mut g = Graph::with_vertices(5);
41/// for &u in &[0u32, 1] {
42///     for &v in &[2u32, 3, 4] {
43///         g.add_edge(u, v).unwrap();
44///     }
45/// }
46///
47/// let types = vec![true, true, false, false, false];
48/// let pos = layout_bipartite(&g, &types, 1.0, 1.0, 100).unwrap();
49/// assert_eq!(pos.len(), 5);
50/// // Top-row vertices share the same y
51/// assert!((pos[0][1] - pos[1][1]).abs() < 1e-10);
52/// // Bottom-row vertices share a different y
53/// assert!((pos[2][1] - pos[3][1]).abs() < 1e-10);
54/// assert!((pos[0][1] - pos[2][1]).abs() > 0.5);
55/// ```
56pub fn layout_bipartite(
57    graph: &Graph,
58    types: &[bool],
59    hgap: f64,
60    vgap: f64,
61    maxiter: u32,
62) -> IgraphResult<Vec<[f64; 2]>> {
63    let n = graph.vcount() as usize;
64
65    if types.len() != n {
66        return Err(IgraphError::InvalidArgument(format!(
67            "types length ({}) must equal vertex count ({})",
68            types.len(),
69            n
70        )));
71    }
72    if hgap < 0.0 {
73        return Err(IgraphError::InvalidArgument(
74            "hgap cannot be negative".into(),
75        ));
76    }
77
78    let layers: Vec<u32> = types.iter().map(|&t| u32::from(!t)).collect();
79
80    let params = SugiyamaParams {
81        hgap,
82        vgap,
83        maxiter,
84    };
85
86    let result = layout_sugiyama(graph, Some(&layers), &params)?;
87    Ok(result.positions)
88}
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93
94    #[test]
95    fn test_bipartite_k23() {
96        let mut g = Graph::with_vertices(5);
97        for &u in &[0u32, 1] {
98            for &v in &[2u32, 3, 4] {
99                g.add_edge(u, v).unwrap();
100            }
101        }
102        let types = vec![true, true, false, false, false];
103        let pos = layout_bipartite(&g, &types, 1.0, 1.0, 100).unwrap();
104        assert_eq!(pos.len(), 5);
105        assert!((pos[0][1] - pos[1][1]).abs() < 1e-10);
106        assert!((pos[2][1] - pos[3][1]).abs() < 1e-10);
107        assert!((pos[2][1] - pos[4][1]).abs() < 1e-10);
108        assert!((pos[0][1] - pos[2][1]).abs() > 0.5);
109    }
110
111    #[test]
112    fn test_bipartite_empty() {
113        let g = Graph::with_vertices(0);
114        let pos = layout_bipartite(&g, &[], 1.0, 1.0, 100).unwrap();
115        assert!(pos.is_empty());
116    }
117
118    #[test]
119    fn test_bipartite_single_vertex() {
120        let g = Graph::with_vertices(1);
121        let pos = layout_bipartite(&g, &[true], 1.0, 1.0, 100).unwrap();
122        assert_eq!(pos.len(), 1);
123    }
124
125    #[test]
126    fn test_bipartite_wrong_types_len() {
127        let g = Graph::with_vertices(3);
128        let result = layout_bipartite(&g, &[true, false], 1.0, 1.0, 100);
129        assert!(result.is_err());
130    }
131
132    #[test]
133    fn test_bipartite_negative_hgap() {
134        let g = Graph::with_vertices(2);
135        let result = layout_bipartite(&g, &[true, false], -1.0, 1.0, 100);
136        assert!(result.is_err());
137    }
138
139    #[test]
140    fn test_bipartite_all_same_type() {
141        let mut g = Graph::with_vertices(4);
142        g.add_edge(0, 1).unwrap();
143        g.add_edge(2, 3).unwrap();
144        let types = vec![true, true, true, true];
145        let pos = layout_bipartite(&g, &types, 1.0, 1.0, 100).unwrap();
146        assert_eq!(pos.len(), 4);
147        // All in same row
148        for i in 1..4 {
149            assert!((pos[i][1] - pos[0][1]).abs() < 1e-10);
150        }
151    }
152
153    #[test]
154    fn test_bipartite_no_edges() {
155        let g = Graph::with_vertices(4);
156        let types = vec![true, true, false, false];
157        let pos = layout_bipartite(&g, &types, 1.0, 1.0, 100).unwrap();
158        assert_eq!(pos.len(), 4);
159        // Two rows
160        assert!((pos[0][1] - pos[1][1]).abs() < 1e-10);
161        assert!((pos[2][1] - pos[3][1]).abs() < 1e-10);
162    }
163
164    #[test]
165    fn test_bipartite_separation() {
166        let mut g = Graph::with_vertices(4);
167        g.add_edge(0, 2).unwrap();
168        g.add_edge(1, 3).unwrap();
169        let types = vec![true, true, false, false];
170        let pos = layout_bipartite(&g, &types, 2.0, 3.0, 100).unwrap();
171        // Vertices in the same row should be at least hgap apart
172        let diff_x = (pos[0][0] - pos[1][0]).abs();
173        assert!(diff_x >= 2.0 - 1e-10, "hgap not respected: diff_x={diff_x}");
174        // Rows should be vgap apart
175        let diff_y = (pos[0][1] - pos[2][1]).abs();
176        assert!(
177            (diff_y - 3.0).abs() < 1e-10,
178            "vgap not respected: diff_y={diff_y}"
179        );
180    }
181}
rust_igraph/algorithms/layout/bipartite.rs

rust_igraph/algorithms/layout/
bipartite.rs
