rust_igraph/algorithms/operators/
union.rs

1//! Union of two graphs (ALGO-OP-004).
2//!
3//! Counterpart of `igraph_union()` from
4//! `references/igraph/src/operators/union.c:69-75`. Vertex sets are
5//! aligned by index — the result has
6//! `max(left.vcount(), right.vcount())` vertices. Edges are unioned by
7//! *maximum multiplicity*: for each (canonicalised) endpoint pair
8//! `(u, v)`, the result contains `max(count_left, count_right)` edges.
9//! For undirected inputs the canonicalised pair is `(min(u,v),
10//! max(u,v))`; for directed inputs the pair is taken as-is, so
11//! `(u, v)` and `(v, u)` are tallied separately.
12//!
13//! Phase-1 minimal slice: two-graph variant only. Multi-arg
14//! `union_many` and the edge-mapping outputs (`edge_map1` /
15//! `edge_map2`) ship later.
16
17use std::collections::BTreeMap;
18
19use crate::core::graph::EdgeId;
20use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
21
22/// Returns the union of `left` and `right`.
23///
24/// Vertex sets are aligned by index — the result has
25/// `max(left.vcount(), right.vcount())` vertices. For each endpoint
26/// pair `(u, v)`, the multiplicity in the result equals the larger of
27/// the multiplicities in the two inputs.
28///
29/// Both inputs must agree on directedness; an undirected edge
30/// `(u, v)` is canonicalised to `(min(u, v), max(u, v))` before
31/// counting, while directed edges are tallied as-is.
32///
33/// Output edges are emitted in lexicographic `(src, tgt)` order; two
34/// edges sharing the same canonicalised pair appear consecutively.
35///
36/// # Errors
37/// - [`IgraphError::InvalidArgument`] if directedness diverges.
38///
39/// # Examples
40///
41/// ```
42/// use rust_igraph::{Graph, union};
43///
44/// // Triangle ∪ path: edges {(0,1), (1,2), (2,0)} ∪ {(0,1), (1,3)}
45/// // → {(0,1), (1,2), (2,0), (1,3)} on 4 vertices.
46/// let mut a = Graph::with_vertices(3);
47/// a.add_edge(0, 1).unwrap();
48/// a.add_edge(1, 2).unwrap();
49/// a.add_edge(2, 0).unwrap();
50/// let mut b = Graph::with_vertices(4);
51/// b.add_edge(0, 1).unwrap();
52/// b.add_edge(1, 3).unwrap();
53///
54/// let u = union(&a, &b).unwrap();
55/// assert_eq!(u.vcount(), 4);
56/// assert_eq!(u.ecount(), 4);
57/// ```
58pub fn union(left: &Graph, right: &Graph) -> IgraphResult<Graph> {
59    if left.is_directed() != right.is_directed() {
60        return Err(IgraphError::InvalidArgument(
61            "union: cannot mix directed and undirected graphs".to_string(),
62        ));
63    }
64    let directed = left.is_directed();
65    let n = std::cmp::max(left.vcount(), right.vcount());
66
67    let canon = |u: VertexId, v: VertexId| -> (VertexId, VertexId) {
68        if directed || u <= v { (u, v) } else { (v, u) }
69    };
70
71    let mut count_left: BTreeMap<(VertexId, VertexId), u32> = BTreeMap::new();
72    let mut count_right: BTreeMap<(VertexId, VertexId), u32> = BTreeMap::new();
73
74    let m_l = u32::try_from(left.ecount())
75        .map_err(|_| IgraphError::Internal("ecount exceeds u32::MAX"))?;
76    for e in 0..m_l {
77        let (u, v) = left.edge(e as EdgeId)?;
78        *count_left.entry(canon(u, v)).or_insert(0) += 1;
79    }
80    let m_r = u32::try_from(right.ecount())
81        .map_err(|_| IgraphError::Internal("ecount exceeds u32::MAX"))?;
82    for e in 0..m_r {
83        let (u, v) = right.edge(e as EdgeId)?;
84        *count_right.entry(canon(u, v)).or_insert(0) += 1;
85    }
86
87    // Walk the merged key set in lex order and emit the per-pair
88    // multiplicity-max edges. Using BTreeMap keeps output edges
89    // deterministic (sorted by `(src, tgt)`).
90    let mut edges: Vec<(VertexId, VertexId)> = Vec::new();
91    let mut iter_l = count_left.iter().peekable();
92    let mut iter_r = count_right.iter().peekable();
93    loop {
94        let next = match (iter_l.peek(), iter_r.peek()) {
95            (None, None) => break,
96            (Some((kl, _)), None) => Some((**kl, true, false)),
97            (None, Some((kr, _))) => Some((**kr, false, true)),
98            (Some((kl, _)), Some((kr, _))) => match kl.cmp(kr) {
99                std::cmp::Ordering::Less => Some((**kl, true, false)),
100                std::cmp::Ordering::Greater => Some((**kr, false, true)),
101                std::cmp::Ordering::Equal => Some((**kl, true, true)),
102            },
103        };
104        let Some((k, take_l, take_r)) = next else {
105            break;
106        };
107        let cl = if take_l {
108            match iter_l.next() {
109                Some((_, v)) => *v,
110                None => 0,
111            }
112        } else {
113            0
114        };
115        let cr = if take_r {
116            match iter_r.next() {
117                Some((_, v)) => *v,
118                None => 0,
119            }
120        } else {
121            0
122        };
123        let m = std::cmp::max(cl, cr);
124        for _ in 0..m {
125            edges.push(k);
126        }
127    }
128
129    let mut out = Graph::new(n, directed)?;
130    out.add_edges(edges)?;
131    Ok(out)
132}
133
134/// Returns the union of multiple graphs.
135///
136/// Generalises [`union`] to an arbitrary number of inputs. The result
137/// has `max(g.vcount() for g in graphs)` vertices. For each endpoint
138/// pair `(u, v)`, the multiplicity in the result equals the maximum
139/// over all input graphs.
140///
141/// If `graphs` is empty, returns an empty directed graph (matching
142/// igraph C convention). All inputs must agree on directedness.
143///
144/// # Errors
145/// - [`IgraphError::InvalidArgument`] if directedness diverges.
146///
147/// # Examples
148///
149/// ```
150/// use rust_igraph::{Graph, union_many};
151///
152/// let mut a = Graph::with_vertices(3);
153/// a.add_edge(0, 1).unwrap();
154/// let mut b = Graph::with_vertices(4);
155/// b.add_edge(1, 2).unwrap();
156/// let mut c = Graph::with_vertices(2);
157/// c.add_edge(0, 1).unwrap();
158///
159/// let u = union_many(&[&a, &b, &c]).unwrap();
160/// assert_eq!(u.vcount(), 4);
161/// assert_eq!(u.ecount(), 2); // (0,1) and (1,2)
162/// ```
163pub fn union_many(graphs: &[&Graph]) -> IgraphResult<Graph> {
164    if graphs.is_empty() {
165        return Graph::new(0, true);
166    }
167
168    let directed = graphs[0].is_directed();
169    for g in &graphs[1..] {
170        if g.is_directed() != directed {
171            return Err(IgraphError::InvalidArgument(
172                "union_many: cannot mix directed and undirected graphs".to_string(),
173            ));
174        }
175    }
176
177    let n = graphs.iter().map(|g| g.vcount()).max().unwrap_or(0);
178
179    let canon = |u: VertexId, v: VertexId| -> (VertexId, VertexId) {
180        if directed || u <= v { (u, v) } else { (v, u) }
181    };
182
183    // Collect per-pair maximum multiplicity across all graphs
184    let mut max_mult: BTreeMap<(VertexId, VertexId), u32> = BTreeMap::new();
185
186    for g in graphs {
187        let mut counts: BTreeMap<(VertexId, VertexId), u32> = BTreeMap::new();
188        let m = g.ecount();
189        for eid in 0..m {
190            #[allow(clippy::cast_possible_truncation)]
191            let eid_u32 = eid as u32;
192            let (u, v) = g.edge(eid_u32)?;
193            *counts.entry(canon(u, v)).or_insert(0) += 1;
194        }
195        for (pair, cnt) in counts {
196            let entry = max_mult.entry(pair).or_insert(0);
197            if cnt > *entry {
198                *entry = cnt;
199            }
200        }
201    }
202
203    let mut edges: Vec<(VertexId, VertexId)> = Vec::new();
204    for (pair, mult) in &max_mult {
205        for _ in 0..*mult {
206            edges.push(*pair);
207        }
208    }
209
210    let mut out = Graph::new(n, directed)?;
211    out.add_edges(edges)?;
212    Ok(out)
213}
214
215#[cfg(test)]
216mod tests {
217    use super::*;
218
219    fn sorted_edges(g: &Graph) -> Vec<(VertexId, VertexId)> {
220        let m = u32::try_from(g.ecount()).unwrap();
221        let mut v: Vec<_> = (0..m).map(|e| g.edge(e).unwrap()).collect();
222        v.sort_unstable();
223        v
224    }
225
226    #[test]
227    fn empty_union_empty() {
228        let a = Graph::with_vertices(0);
229        let b = Graph::with_vertices(0);
230        let u = union(&a, &b).unwrap();
231        assert_eq!(u.vcount(), 0);
232        assert_eq!(u.ecount(), 0);
233        assert!(!u.is_directed());
234    }
235
236    #[test]
237    fn vcount_is_max_of_inputs() {
238        // a: 3 isolated vertices, b: 6 isolated vertices.
239        let a = Graph::with_vertices(3);
240        let b = Graph::with_vertices(6);
241        let u = union(&a, &b).unwrap();
242        assert_eq!(u.vcount(), 6);
243        assert_eq!(u.ecount(), 0);
244    }
245
246    #[test]
247    fn triangle_union_path_doc_example() {
248        let mut a = Graph::with_vertices(3);
249        a.add_edge(0, 1).unwrap();
250        a.add_edge(1, 2).unwrap();
251        a.add_edge(2, 0).unwrap();
252        let mut b = Graph::with_vertices(4);
253        b.add_edge(0, 1).unwrap();
254        b.add_edge(1, 3).unwrap();
255        let u = union(&a, &b).unwrap();
256        assert_eq!(u.vcount(), 4);
257        assert_eq!(u.ecount(), 4);
258        assert_eq!(sorted_edges(&u), vec![(0, 1), (0, 2), (1, 2), (1, 3)]);
259    }
260
261    #[test]
262    fn max_multiplicity_when_left_has_more() {
263        // left: 3× (0,1); right: 1× (0,1). Result: 3× (0,1).
264        let mut a = Graph::with_vertices(2);
265        a.add_edge(0, 1).unwrap();
266        a.add_edge(0, 1).unwrap();
267        a.add_edge(0, 1).unwrap();
268        let mut b = Graph::with_vertices(2);
269        b.add_edge(0, 1).unwrap();
270        let u = union(&a, &b).unwrap();
271        assert_eq!(u.ecount(), 3);
272    }
273
274    #[test]
275    fn max_multiplicity_when_right_has_more() {
276        // left: 1× (0,1); right: 5× (0,1). Result: 5× (0,1).
277        let mut a = Graph::with_vertices(2);
278        a.add_edge(0, 1).unwrap();
279        let mut b = Graph::with_vertices(2);
280        for _ in 0..5 {
281            b.add_edge(0, 1).unwrap();
282        }
283        let u = union(&a, &b).unwrap();
284        assert_eq!(u.ecount(), 5);
285    }
286
287    #[test]
288    fn disjoint_edge_sets_become_simple_union() {
289        // a: edges (0,1); b: edges (2,3) on 4 vertices.
290        let mut a = Graph::with_vertices(4);
291        a.add_edge(0, 1).unwrap();
292        let mut b = Graph::with_vertices(4);
293        b.add_edge(2, 3).unwrap();
294        let u = union(&a, &b).unwrap();
295        assert_eq!(sorted_edges(&u), vec![(0, 1), (2, 3)]);
296    }
297
298    #[test]
299    fn idempotent_with_self() {
300        // union(a, a) ≡ a (max-multiplicity: max(k, k) = k).
301        let mut a = Graph::with_vertices(4);
302        a.add_edge(0, 1).unwrap();
303        a.add_edge(1, 2).unwrap();
304        a.add_edge(0, 2).unwrap();
305        a.add_edge(0, 2).unwrap(); // multi-edge
306        let u = union(&a, &a).unwrap();
307        assert_eq!(u.vcount(), a.vcount());
308        assert_eq!(u.ecount(), a.ecount());
309        assert_eq!(sorted_edges(&u), sorted_edges(&a));
310    }
311
312    #[test]
313    fn directed_keeps_orientation_separate() {
314        // left: (0→1); right: (1→0). Both edges land in the result.
315        let mut a = Graph::new(2, true).unwrap();
316        a.add_edge(0, 1).unwrap();
317        let mut b = Graph::new(2, true).unwrap();
318        b.add_edge(1, 0).unwrap();
319        let u = union(&a, &b).unwrap();
320        assert!(u.is_directed());
321        assert_eq!(u.ecount(), 2);
322        assert_eq!(sorted_edges(&u), vec![(0, 1), (1, 0)]);
323    }
324
325    #[test]
326    fn directed_max_multiplicity_per_orientation() {
327        // left: 2× (0→1); right: 3× (1→0); both kept independently.
328        let mut a = Graph::new(2, true).unwrap();
329        a.add_edge(0, 1).unwrap();
330        a.add_edge(0, 1).unwrap();
331        let mut b = Graph::new(2, true).unwrap();
332        for _ in 0..3 {
333            b.add_edge(1, 0).unwrap();
334        }
335        let u = union(&a, &b).unwrap();
336        assert_eq!(u.ecount(), 5);
337        let s = sorted_edges(&u);
338        assert_eq!(s.iter().filter(|&&p| p == (0, 1)).count(), 2);
339        assert_eq!(s.iter().filter(|&&p| p == (1, 0)).count(), 3);
340    }
341
342    #[test]
343    fn loops_are_preserved() {
344        // left: 2× (0,0); right: 1× (0,0). Result: 2× (0,0).
345        let mut a = Graph::with_vertices(1);
346        a.add_edge(0, 0).unwrap();
347        a.add_edge(0, 0).unwrap();
348        let mut b = Graph::with_vertices(1);
349        b.add_edge(0, 0).unwrap();
350        let u = union(&a, &b).unwrap();
351        assert_eq!(u.ecount(), 2);
352        assert!(u.edge(0).unwrap() == (0, 0));
353    }
354
355    #[test]
356    fn unaligned_vertex_sizes_use_max() {
357        // a has 2 vertices, b has 5 vertices. Result must have 5 vertices.
358        let mut a = Graph::with_vertices(2);
359        a.add_edge(0, 1).unwrap();
360        let mut b = Graph::with_vertices(5);
361        b.add_edge(3, 4).unwrap();
362        let u = union(&a, &b).unwrap();
363        assert_eq!(u.vcount(), 5);
364        assert_eq!(sorted_edges(&u), vec![(0, 1), (3, 4)]);
365    }
366
367    #[test]
368    fn mixed_directedness_errors() {
369        let a = Graph::with_vertices(2);
370        let b = Graph::new(2, true).unwrap();
371        assert!(union(&a, &b).is_err());
372    }
373
374    #[test]
375    fn undirected_canonicalises_swapped_endpoints() {
376        // Both edges encode the same undirected pair (1,0) and (0,1).
377        let mut a = Graph::with_vertices(2);
378        a.add_edge(1, 0).unwrap();
379        let mut b = Graph::with_vertices(2);
380        b.add_edge(0, 1).unwrap();
381        let u = union(&a, &b).unwrap();
382        // max(1,1) = 1.
383        assert_eq!(u.ecount(), 1);
384        let endpoints = u.edge(0).unwrap();
385        assert!(endpoints == (0, 1) || endpoints == (1, 0));
386    }
387
388    #[test]
389    fn larger_left_vertex_count_preserved() {
390        // Mirror the previous test with sides swapped.
391        let mut a = Graph::with_vertices(5);
392        a.add_edge(3, 4).unwrap();
393        let mut b = Graph::with_vertices(2);
394        b.add_edge(0, 1).unwrap();
395        let u = union(&a, &b).unwrap();
396        assert_eq!(u.vcount(), 5);
397        assert_eq!(sorted_edges(&u), vec![(0, 1), (3, 4)]);
398    }
399
400    // --- union_many tests ---
401
402    #[test]
403    fn union_many_empty_list() {
404        let u = union_many(&[]).unwrap();
405        assert_eq!(u.vcount(), 0);
406        assert!(u.is_directed());
407    }
408
409    #[test]
410    fn union_many_single_graph() {
411        let mut a = Graph::with_vertices(3);
412        a.add_edge(0, 1).unwrap();
413        a.add_edge(1, 2).unwrap();
414        let u = union_many(&[&a]).unwrap();
415        assert_eq!(u.vcount(), 3);
416        assert_eq!(u.ecount(), 2);
417        assert_eq!(sorted_edges(&u), sorted_edges(&a));
418    }
419
420    #[test]
421    fn union_many_three_graphs() {
422        let mut a = Graph::with_vertices(3);
423        a.add_edge(0, 1).unwrap();
424        let mut b = Graph::with_vertices(4);
425        b.add_edge(1, 2).unwrap();
426        let mut c = Graph::with_vertices(5);
427        c.add_edge(3, 4).unwrap();
428
429        let u = union_many(&[&a, &b, &c]).unwrap();
430        assert_eq!(u.vcount(), 5);
431        assert_eq!(u.ecount(), 3);
432        assert_eq!(sorted_edges(&u), vec![(0, 1), (1, 2), (3, 4)]);
433    }
434
435    #[test]
436    fn union_many_max_multiplicity() {
437        let mut a = Graph::with_vertices(2);
438        a.add_edge(0, 1).unwrap();
439        a.add_edge(0, 1).unwrap();
440        let mut b = Graph::with_vertices(2);
441        b.add_edge(0, 1).unwrap();
442        b.add_edge(0, 1).unwrap();
443        b.add_edge(0, 1).unwrap();
444        let mut c = Graph::with_vertices(2);
445        c.add_edge(0, 1).unwrap();
446
447        let u = union_many(&[&a, &b, &c]).unwrap();
448        assert_eq!(u.ecount(), 3); // max(2, 3, 1) = 3
449    }
450
451    #[test]
452    fn union_many_mixed_directedness_fails() {
453        let a = Graph::with_vertices(2);
454        let b = Graph::new(2, true).unwrap();
455        assert!(union_many(&[&a, &b]).is_err());
456    }
457
458    #[test]
459    fn union_many_directed() {
460        let mut a = Graph::new(3, true).unwrap();
461        a.add_edge(0, 1).unwrap();
462        let mut b = Graph::new(3, true).unwrap();
463        b.add_edge(1, 0).unwrap();
464        let mut c = Graph::new(3, true).unwrap();
465        c.add_edge(1, 2).unwrap();
466
467        let u = union_many(&[&a, &b, &c]).unwrap();
468        assert!(u.is_directed());
469        assert_eq!(u.ecount(), 3);
470        assert_eq!(sorted_edges(&u), vec![(0, 1), (1, 0), (1, 2)]);
471    }
472}
rust_igraph/algorithms/operators/union.rs

rust_igraph/algorithms/operators/
union.rs
