rust_igraph/algorithms/properties/
mutual.rs

1//! Mutual (reciprocal) edge detection (ALGO-PR-038).
2//!
3//! For directed graphs, an edge (A, B) is *mutual* if (B, A) also
4//! exists. For undirected graphs, all edges are mutual by definition.
5//!
6//! Counterpart of `igraph_is_mutual` and `igraph_has_mutual` from
7//! `references/igraph/src/properties/multiplicity.c`.
8
9use crate::core::{Graph, IgraphResult, VertexId};
10
11/// Check whether each edge in a directed graph is mutual (reciprocated).
12///
13/// An edge (A, B) is mutual if the reverse edge (B, A) also exists.
14/// Self-loops are considered mutual if `loops` is true.
15///
16/// For undirected graphs, all edges are considered mutual.
17///
18/// Returns a boolean vector with one entry per edge.
19///
20/// # Examples
21///
22/// ```
23/// use rust_igraph::{Graph, is_mutual};
24///
25/// let mut g = Graph::new(3, true).unwrap();
26/// g.add_edge(0, 1).unwrap(); // edge 0
27/// g.add_edge(1, 0).unwrap(); // edge 1
28/// g.add_edge(1, 2).unwrap(); // edge 2
29/// let mutual = is_mutual(&g, true).unwrap();
30/// assert_eq!(mutual, vec![true, true, false]);
31/// ```
32pub fn is_mutual(graph: &Graph, loops: bool) -> IgraphResult<Vec<bool>> {
33    let ecount = graph.ecount();
34
35    if !graph.is_directed() {
36        return Ok(vec![true; ecount]);
37    }
38
39    let n = graph.vcount() as usize;
40    let mut out_adj: Vec<Vec<VertexId>> = vec![Vec::new(); n];
41    for eid in 0..ecount {
42        #[allow(clippy::cast_possible_truncation)]
43        let (from, to) = graph.edge(eid as u32)?;
44        out_adj[from as usize].push(to);
45    }
46    for adj in &mut out_adj {
47        adj.sort_unstable();
48    }
49
50    let mut result = Vec::with_capacity(ecount);
51
52    for eid in 0..ecount {
53        #[allow(clippy::cast_possible_truncation)]
54        let (from, to) = graph.edge(eid as u32)?;
55
56        if from == to {
57            result.push(loops);
58        } else {
59            // Check if reverse edge exists: is `from` in out-neighbors of `to`?
60            let has_reverse = out_adj[to as usize].binary_search(&from).is_ok();
61            result.push(has_reverse);
62        }
63    }
64
65    Ok(result)
66}
67
68/// Check whether a directed graph has any mutual (reciprocal) edges.
69///
70/// For undirected graphs, returns true if there is at least one edge
71/// (all edges are mutual by definition).
72///
73/// Self-loops are considered mutual if `loops` is true.
74///
75/// # Examples
76///
77/// ```
78/// use rust_igraph::{Graph, has_mutual};
79///
80/// let mut g = Graph::new(3, true).unwrap();
81/// g.add_edge(0, 1).unwrap();
82/// g.add_edge(1, 2).unwrap();
83/// assert!(!has_mutual(&g, false).unwrap());
84///
85/// g.add_edge(1, 0).unwrap();
86/// assert!(has_mutual(&g, false).unwrap());
87/// ```
88pub fn has_mutual(graph: &Graph, loops: bool) -> IgraphResult<bool> {
89    let ecount = graph.ecount();
90
91    if !graph.is_directed() {
92        return Ok(ecount > 0);
93    }
94
95    let n = graph.vcount() as usize;
96    let mut out_adj: Vec<Vec<VertexId>> = vec![Vec::new(); n];
97    for eid in 0..ecount {
98        #[allow(clippy::cast_possible_truncation)]
99        let (from, to) = graph.edge(eid as u32)?;
100        out_adj[from as usize].push(to);
101    }
102    for adj in &mut out_adj {
103        adj.sort_unstable();
104    }
105
106    for eid in 0..ecount {
107        #[allow(clippy::cast_possible_truncation)]
108        let (from, to) = graph.edge(eid as u32)?;
109
110        if from == to {
111            if loops {
112                return Ok(true);
113            }
114        } else if out_adj[to as usize].binary_search(&from).is_ok() {
115            return Ok(true);
116        }
117    }
118
119    Ok(false)
120}
121
122/// Count the number of mutual edge pairs in a directed graph.
123///
124/// Each pair of reciprocal edges (A→B and B→A) is counted once.
125/// Self-loops are counted if `loops` is true.
126///
127/// For undirected graphs, returns the number of edges (all are mutual).
128///
129/// # Examples
130///
131/// ```
132/// use rust_igraph::{Graph, count_mutual};
133///
134/// let mut g = Graph::new(4, true).unwrap();
135/// g.add_edge(0, 1).unwrap();
136/// g.add_edge(1, 0).unwrap();
137/// g.add_edge(1, 2).unwrap();
138/// g.add_edge(2, 1).unwrap();
139/// g.add_edge(2, 3).unwrap();
140/// assert_eq!(count_mutual(&g, false).unwrap(), 2);
141/// ```
142pub fn count_mutual(graph: &Graph, loops: bool) -> IgraphResult<usize> {
143    let ecount = graph.ecount();
144
145    if !graph.is_directed() {
146        return Ok(ecount);
147    }
148
149    let n = graph.vcount() as usize;
150    let mut out_adj: Vec<Vec<VertexId>> = vec![Vec::new(); n];
151    for eid in 0..ecount {
152        #[allow(clippy::cast_possible_truncation)]
153        let (from, to) = graph.edge(eid as u32)?;
154        out_adj[from as usize].push(to);
155    }
156    for adj in &mut out_adj {
157        adj.sort_unstable();
158    }
159
160    let mut count: usize = 0;
161
162    for eid in 0..ecount {
163        #[allow(clippy::cast_possible_truncation)]
164        let (from, to) = graph.edge(eid as u32)?;
165
166        if from == to {
167            if loops {
168                count += 1;
169            }
170        } else if from < to && out_adj[to as usize].binary_search(&from).is_ok() {
171            count += 1;
172        }
173    }
174
175    Ok(count)
176}
177
178#[cfg(test)]
179mod tests {
180    use super::*;
181
182    #[test]
183    fn is_mutual_undirected() {
184        let mut g = Graph::with_vertices(3);
185        g.add_edge(0, 1).unwrap();
186        g.add_edge(1, 2).unwrap();
187        let result = is_mutual(&g, true).unwrap();
188        assert_eq!(result, vec![true, true]);
189    }
190
191    #[test]
192    fn is_mutual_directed_reciprocal() {
193        let mut g = Graph::new(3, true).unwrap();
194        g.add_edge(0, 1).unwrap();
195        g.add_edge(1, 0).unwrap();
196        g.add_edge(1, 2).unwrap();
197        let result = is_mutual(&g, true).unwrap();
198        assert_eq!(result, vec![true, true, false]);
199    }
200
201    #[test]
202    fn is_mutual_self_loop_true() {
203        let mut g = Graph::new(2, true).unwrap();
204        g.add_edge(0, 0).unwrap();
205        g.add_edge(0, 1).unwrap();
206        let result = is_mutual(&g, true).unwrap();
207        assert_eq!(result, vec![true, false]);
208    }
209
210    #[test]
211    fn is_mutual_self_loop_false() {
212        let mut g = Graph::new(2, true).unwrap();
213        g.add_edge(0, 0).unwrap();
214        g.add_edge(0, 1).unwrap();
215        let result = is_mutual(&g, false).unwrap();
216        assert_eq!(result, vec![false, false]);
217    }
218
219    #[test]
220    fn is_mutual_empty() {
221        let g = Graph::new(3, true).unwrap();
222        let result = is_mutual(&g, true).unwrap();
223        assert!(result.is_empty());
224    }
225
226    #[test]
227    fn has_mutual_no_mutual() {
228        let mut g = Graph::new(3, true).unwrap();
229        g.add_edge(0, 1).unwrap();
230        g.add_edge(1, 2).unwrap();
231        assert!(!has_mutual(&g, false).unwrap());
232    }
233
234    #[test]
235    fn has_mutual_with_mutual() {
236        let mut g = Graph::new(3, true).unwrap();
237        g.add_edge(0, 1).unwrap();
238        g.add_edge(1, 0).unwrap();
239        assert!(has_mutual(&g, false).unwrap());
240    }
241
242    #[test]
243    fn has_mutual_undirected_nonempty() {
244        let mut g = Graph::with_vertices(2);
245        g.add_edge(0, 1).unwrap();
246        assert!(has_mutual(&g, false).unwrap());
247    }
248
249    #[test]
250    fn has_mutual_undirected_empty() {
251        let g = Graph::with_vertices(3);
252        assert!(!has_mutual(&g, false).unwrap());
253    }
254
255    #[test]
256    fn has_mutual_self_loop_counted() {
257        let mut g = Graph::new(2, true).unwrap();
258        g.add_edge(0, 0).unwrap();
259        assert!(has_mutual(&g, true).unwrap());
260        assert!(!has_mutual(&g, false).unwrap());
261    }
262
263    #[test]
264    fn count_mutual_basic() {
265        let mut g = Graph::new(4, true).unwrap();
266        g.add_edge(0, 1).unwrap();
267        g.add_edge(1, 0).unwrap();
268        g.add_edge(1, 2).unwrap();
269        g.add_edge(2, 1).unwrap();
270        g.add_edge(2, 3).unwrap();
271        assert_eq!(count_mutual(&g, false).unwrap(), 2);
272    }
273
274    #[test]
275    fn count_mutual_none() {
276        let mut g = Graph::new(3, true).unwrap();
277        g.add_edge(0, 1).unwrap();
278        g.add_edge(1, 2).unwrap();
279        g.add_edge(2, 0).unwrap();
280        assert_eq!(count_mutual(&g, false).unwrap(), 0);
281    }
282
283    #[test]
284    fn count_mutual_all() {
285        let mut g = Graph::new(3, true).unwrap();
286        g.add_edge(0, 1).unwrap();
287        g.add_edge(1, 0).unwrap();
288        g.add_edge(1, 2).unwrap();
289        g.add_edge(2, 1).unwrap();
290        g.add_edge(0, 2).unwrap();
291        g.add_edge(2, 0).unwrap();
292        assert_eq!(count_mutual(&g, false).unwrap(), 3);
293    }
294
295    #[test]
296    fn count_mutual_undirected() {
297        let mut g = Graph::with_vertices(3);
298        g.add_edge(0, 1).unwrap();
299        g.add_edge(1, 2).unwrap();
300        assert_eq!(count_mutual(&g, false).unwrap(), 2);
301    }
302
303    #[test]
304    fn count_mutual_with_self_loops() {
305        let mut g = Graph::new(3, true).unwrap();
306        g.add_edge(0, 0).unwrap();
307        g.add_edge(0, 1).unwrap();
308        g.add_edge(1, 0).unwrap();
309        assert_eq!(count_mutual(&g, true).unwrap(), 2); // self-loop + (0,1)/(1,0) pair
310        assert_eq!(count_mutual(&g, false).unwrap(), 1); // only (0,1)/(1,0)
311    }
312}
rust_igraph/algorithms/properties/mutual.rs

rust_igraph/algorithms/properties/
mutual.rs
