rust_igraph/algorithms/operators/
join.rs

1//! Graph join operator (ALGO-OP-014).
2//!
3//! Creates the join of two disjoint graphs (disjoint union plus all
4//! cross-edges between the two vertex sets).
5
6use crate::core::error::IgraphError;
7use crate::core::{Graph, IgraphResult, VertexId};
8
9/// Creates the join of two graphs.
10///
11/// The join first takes the disjoint union of `left` and `right`, then adds
12/// all edges between the vertices originating from `left` and those from
13/// `right`. This produces a graph with `|V1| + |V2|` vertices and
14/// `|E1| + |E2| + |V1|*|V2|` edges (for undirected), or
15/// `|E1| + |E2| + 2*|V1|*|V2|` edges (for directed, since both directions
16/// are added).
17///
18/// Both graphs must have the same directedness.
19///
20/// # Arguments
21///
22/// * `left` — the first graph.
23/// * `right` — the second graph.
24///
25/// # Errors
26///
27/// Returns `InvalidArgument` if the graphs differ in directedness.
28///
29/// # Examples
30///
31/// ```
32/// use rust_igraph::{Graph, join};
33///
34/// let g1 = Graph::with_vertices(2); // 2 isolated vertices
35/// let g2 = Graph::with_vertices(3); // 3 isolated vertices
36///
37/// let j = join(&g1, &g2).unwrap();
38/// assert_eq!(j.vcount(), 5);
39/// // 0 original edges + 2*3 = 6 cross-edges
40/// assert_eq!(j.ecount(), 6);
41/// ```
42pub fn join(left: &Graph, right: &Graph) -> IgraphResult<Graph> {
43    if left.is_directed() != right.is_directed() {
44        return Err(IgraphError::InvalidArgument(
45            "cannot join directed and undirected graphs".to_string(),
46        ));
47    }
48
49    let n1 = left.vcount();
50    let n2 = right.vcount();
51    let directed = left.is_directed();
52    let n = n1
53        .checked_add(n2)
54        .ok_or_else(|| IgraphError::InvalidArgument("vertex count overflow in join".to_string()))?;
55
56    let e1 = left.ecount();
57    let e2 = right.ecount();
58
59    // Calculate cross-edges count
60    let cross_count = if directed {
61        2 * (n1 as usize) * (n2 as usize)
62    } else {
63        (n1 as usize) * (n2 as usize)
64    };
65
66    let mut edges: Vec<(VertexId, VertexId)> = Vec::with_capacity(e1 + e2 + cross_count);
67
68    // Copy left's edges
69    for eid in 0..e1 {
70        #[allow(clippy::cast_possible_truncation)]
71        let eid_u32 = eid as u32;
72        edges.push(left.edge(eid_u32)?);
73    }
74
75    // Copy right's edges, shifted by n1
76    for eid in 0..e2 {
77        #[allow(clippy::cast_possible_truncation)]
78        let eid_u32 = eid as u32;
79        let (src, tgt) = right.edge(eid_u32)?;
80        edges.push((src + n1, tgt + n1));
81    }
82
83    // Add all cross-edges
84    for i in 0..n1 {
85        for j in 0..n2 {
86            edges.push((i, j + n1));
87            if directed {
88                edges.push((j + n1, i));
89            }
90        }
91    }
92
93    let mut result = Graph::new(n, directed)?;
94    result.add_edges(edges)?;
95    Ok(result)
96}
97
98#[cfg(test)]
99mod tests {
100    use super::*;
101
102    #[test]
103    fn test_basic_undirected() {
104        let g1 = Graph::with_vertices(2);
105        let g2 = Graph::with_vertices(3);
106
107        let j = join(&g1, &g2).unwrap();
108        assert_eq!(j.vcount(), 5);
109        assert_eq!(j.ecount(), 6); // 2*3
110    }
111
112    #[test]
113    fn test_with_existing_edges() {
114        let mut g1 = Graph::with_vertices(2);
115        g1.add_edge(0, 1).unwrap();
116
117        let mut g2 = Graph::with_vertices(2);
118        g2.add_edge(0, 1).unwrap();
119
120        let j = join(&g1, &g2).unwrap();
121        assert_eq!(j.vcount(), 4);
122        // 1 + 1 + 2*2 = 6
123        assert_eq!(j.ecount(), 6);
124    }
125
126    #[test]
127    fn test_directed() {
128        let g1 = Graph::new(2, true).unwrap();
129        let g2 = Graph::new(3, true).unwrap();
130
131        let j = join(&g1, &g2).unwrap();
132        assert!(j.is_directed());
133        assert_eq!(j.vcount(), 5);
134        // 0 + 0 + 2*2*3 = 12 cross-edges (both directions)
135        assert_eq!(j.ecount(), 12);
136    }
137
138    #[test]
139    fn test_empty_left() {
140        let g1 = Graph::with_vertices(0);
141        let g2 = Graph::with_vertices(3);
142
143        let j = join(&g1, &g2).unwrap();
144        assert_eq!(j.vcount(), 3);
145        assert_eq!(j.ecount(), 0); // no cross-edges since |V1|=0
146    }
147
148    #[test]
149    fn test_empty_right() {
150        let g1 = Graph::with_vertices(3);
151        let g2 = Graph::with_vertices(0);
152
153        let j = join(&g1, &g2).unwrap();
154        assert_eq!(j.vcount(), 3);
155        assert_eq!(j.ecount(), 0);
156    }
157
158    #[test]
159    fn test_single_vertices() {
160        let g1 = Graph::with_vertices(1);
161        let g2 = Graph::with_vertices(1);
162
163        let j = join(&g1, &g2).unwrap();
164        assert_eq!(j.vcount(), 2);
165        assert_eq!(j.ecount(), 1); // one edge between vertex 0 and 1
166    }
167
168    #[test]
169    fn test_mixed_directedness_error() {
170        let g1 = Graph::new(2, true).unwrap();
171        let g2 = Graph::with_vertices(2);
172        assert!(join(&g1, &g2).is_err());
173    }
174
175    #[test]
176    fn test_vertex_ids_preserved() {
177        let mut g1 = Graph::with_vertices(2);
178        g1.add_edge(0, 1).unwrap();
179
180        let mut g2 = Graph::with_vertices(2);
181        g2.add_edge(0, 1).unwrap();
182
183        let j = join(&g1, &g2).unwrap();
184        // First edge is from g1: (0,1)
185        assert_eq!(j.edge(0).unwrap(), (0, 1));
186        // Second edge is from g2 shifted: (2,3)
187        assert_eq!(j.edge(1).unwrap(), (2, 3));
188    }
189}
rust_igraph/algorithms/operators/join.rs

rust_igraph/algorithms/operators/
join.rs
