rust_igraph/algorithms/properties/
adjacency.rs

1//! Graph adjacency matrix (ALGO-PR-042).
2//!
3//! Returns the adjacency matrix in dense form. Supports directed/undirected
4//! graphs, optional edge weights, triangle selection (upper/lower/both)
5//! for undirected graphs, and configurable self-loop handling.
6//!
7//! Counterpart of `igraph_get_adjacency` from
8//! `references/igraph/src/misc/conversion.c`.
9
10use crate::core::{Graph, IgraphError, IgraphResult};
11
12/// Which triangle of the adjacency matrix to fill (undirected graphs only).
13#[derive(Debug, Clone, Copy, PartialEq, Eq)]
14pub enum AdjacencyType {
15    /// Upper-right triangle only.
16    Upper,
17    /// Lower-left triangle only.
18    Lower,
19    /// Both triangles — full symmetric matrix.
20    Both,
21}
22
23/// How to count self-loop edges in the adjacency matrix diagonal.
24#[derive(Debug, Clone, Copy, PartialEq, Eq)]
25pub enum LoopHandling {
26    /// Ignore loops — diagonal is always zero.
27    NoLoops,
28    /// Count each loop once.
29    Once,
30    /// Count each loop twice for undirected graphs (once for directed).
31    Twice,
32}
33
34/// Compute the adjacency matrix of a graph.
35///
36/// Returns an n×n matrix stored as `Vec<Vec<f64>>` in row-major order.
37///
38/// - `adj_type`: which triangle to fill (ignored for directed graphs).
39/// - `weights`: optional edge weights. If `None`, each edge counts as 1.
40/// - `loops`: how to handle self-loop edges on the diagonal.
41///
42/// # Examples
43///
44/// ```
45/// use rust_igraph::{Graph, get_adjacency, AdjacencyType, LoopHandling};
46///
47/// // Triangle 0-1-2
48/// let mut g = Graph::with_vertices(3);
49/// g.add_edge(0, 1).unwrap();
50/// g.add_edge(1, 2).unwrap();
51/// g.add_edge(0, 2).unwrap();
52/// let adj = get_adjacency(&g, AdjacencyType::Both, None, LoopHandling::Once).unwrap();
53/// assert!((adj[0][1] - 1.0).abs() < 1e-10);
54/// assert!((adj[1][0] - 1.0).abs() < 1e-10);
55/// assert!((adj[0][2] - 1.0).abs() < 1e-10);
56/// ```
57pub fn get_adjacency(
58    graph: &Graph,
59    adj_type: AdjacencyType,
60    weights: Option<&[f64]>,
61    loops: LoopHandling,
62) -> IgraphResult<Vec<Vec<f64>>> {
63    let n = graph.vcount() as usize;
64    let ecount = graph.ecount();
65
66    if let Some(w) = weights {
67        if w.len() != ecount {
68            return Err(IgraphError::InvalidArgument(format!(
69                "get_adjacency: weight vector length ({}) does not match edge count ({ecount})",
70                w.len()
71            )));
72        }
73    }
74
75    let mut res = vec![vec![0.0_f64; n]; n];
76    let directed = graph.is_directed();
77
78    if directed {
79        for eid in 0..ecount {
80            #[allow(clippy::cast_possible_truncation)]
81            let (from, to) = graph.edge(eid as u32)?;
82            let f = from as usize;
83            let t = to as usize;
84            let w = weights.map_or(1.0, |ws| ws[eid]);
85
86            if f != t || loops != LoopHandling::NoLoops {
87                res[f][t] += w;
88            }
89        }
90    } else {
91        match adj_type {
92            AdjacencyType::Upper => {
93                for eid in 0..ecount {
94                    #[allow(clippy::cast_possible_truncation)]
95                    let (from, to) = graph.edge(eid as u32)?;
96                    let f = from as usize;
97                    let t = to as usize;
98                    let w = weights.map_or(1.0, |ws| ws[eid]);
99
100                    if t < f {
101                        res[t][f] += w;
102                    } else {
103                        res[f][t] += w;
104                    }
105                    if f == t && loops == LoopHandling::Twice {
106                        res[t][t] += w;
107                    }
108                }
109            }
110            AdjacencyType::Lower => {
111                for eid in 0..ecount {
112                    #[allow(clippy::cast_possible_truncation)]
113                    let (from, to) = graph.edge(eid as u32)?;
114                    let f = from as usize;
115                    let t = to as usize;
116                    let w = weights.map_or(1.0, |ws| ws[eid]);
117
118                    if t < f {
119                        res[f][t] += w;
120                    } else {
121                        res[t][f] += w;
122                    }
123                    if f == t && loops == LoopHandling::Twice {
124                        res[t][t] += w;
125                    }
126                }
127            }
128            AdjacencyType::Both => {
129                for eid in 0..ecount {
130                    #[allow(clippy::cast_possible_truncation)]
131                    let (from, to) = graph.edge(eid as u32)?;
132                    let f = from as usize;
133                    let t = to as usize;
134                    let w = weights.map_or(1.0, |ws| ws[eid]);
135
136                    res[f][t] += w;
137                    if f == t {
138                        if loops == LoopHandling::Twice {
139                            res[t][f] += w;
140                        }
141                    } else {
142                        res[t][f] += w;
143                    }
144                }
145            }
146        }
147    }
148
149    // Erase diagonal if NoLoops
150    if loops == LoopHandling::NoLoops {
151        for (i, row) in res.iter_mut().enumerate() {
152            row[i] = 0.0;
153        }
154    }
155
156    Ok(res)
157}
158
159#[cfg(test)]
160mod tests {
161    use super::*;
162
163    fn approx_eq(a: f64, b: f64) -> bool {
164        (a - b).abs() < 1e-10
165    }
166
167    #[test]
168    fn empty_graph() {
169        let g = Graph::with_vertices(0);
170        let adj = get_adjacency(&g, AdjacencyType::Both, None, LoopHandling::Once).unwrap();
171        assert!(adj.is_empty());
172    }
173
174    #[test]
175    fn single_vertex_no_edges() {
176        let g = Graph::with_vertices(1);
177        let adj = get_adjacency(&g, AdjacencyType::Both, None, LoopHandling::Once).unwrap();
178        assert_eq!(adj.len(), 1);
179        assert!(approx_eq(adj[0][0], 0.0));
180    }
181
182    #[test]
183    fn undirected_single_edge_both() {
184        let mut g = Graph::with_vertices(2);
185        g.add_edge(0, 1).unwrap();
186        let adj = get_adjacency(&g, AdjacencyType::Both, None, LoopHandling::Once).unwrap();
187        assert!(approx_eq(adj[0][1], 1.0));
188        assert!(approx_eq(adj[1][0], 1.0));
189        assert!(approx_eq(adj[0][0], 0.0));
190        assert!(approx_eq(adj[1][1], 0.0));
191    }
192
193    #[test]
194    fn undirected_single_edge_upper() {
195        let mut g = Graph::with_vertices(2);
196        g.add_edge(0, 1).unwrap();
197        let adj = get_adjacency(&g, AdjacencyType::Upper, None, LoopHandling::Once).unwrap();
198        assert!(approx_eq(adj[0][1], 1.0));
199        assert!(approx_eq(adj[1][0], 0.0));
200    }
201
202    #[test]
203    fn undirected_single_edge_lower() {
204        let mut g = Graph::with_vertices(2);
205        g.add_edge(0, 1).unwrap();
206        let adj = get_adjacency(&g, AdjacencyType::Lower, None, LoopHandling::Once).unwrap();
207        assert!(approx_eq(adj[0][1], 0.0));
208        assert!(approx_eq(adj[1][0], 1.0));
209    }
210
211    #[test]
212    fn undirected_triangle_both() {
213        let mut g = Graph::with_vertices(3);
214        g.add_edge(0, 1).unwrap();
215        g.add_edge(1, 2).unwrap();
216        g.add_edge(0, 2).unwrap();
217        let adj = get_adjacency(&g, AdjacencyType::Both, None, LoopHandling::Once).unwrap();
218        // Symmetric
219        for (i, row) in adj.iter().enumerate() {
220            for (j, &val) in row.iter().enumerate() {
221                assert!(approx_eq(val, adj[j][i]));
222            }
223        }
224        assert!(approx_eq(adj[0][1], 1.0));
225        assert!(approx_eq(adj[1][2], 1.0));
226        assert!(approx_eq(adj[0][2], 1.0));
227    }
228
229    #[test]
230    fn directed_basic() {
231        let mut g = Graph::new(3, true).unwrap();
232        g.add_edge(0, 1).unwrap();
233        g.add_edge(1, 2).unwrap();
234        let adj = get_adjacency(&g, AdjacencyType::Both, None, LoopHandling::Once).unwrap();
235        assert!(approx_eq(adj[0][1], 1.0));
236        assert!(approx_eq(adj[1][0], 0.0)); // no reverse edge
237        assert!(approx_eq(adj[1][2], 1.0));
238        assert!(approx_eq(adj[2][1], 0.0));
239    }
240
241    #[test]
242    fn self_loop_no_loops() {
243        let mut g = Graph::with_vertices(2);
244        g.add_edge(0, 0).unwrap();
245        g.add_edge(0, 1).unwrap();
246        let adj = get_adjacency(&g, AdjacencyType::Both, None, LoopHandling::NoLoops).unwrap();
247        assert!(approx_eq(adj[0][0], 0.0));
248        assert!(approx_eq(adj[0][1], 1.0));
249    }
250
251    #[test]
252    fn self_loop_once() {
253        let mut g = Graph::with_vertices(2);
254        g.add_edge(0, 0).unwrap();
255        g.add_edge(0, 1).unwrap();
256        let adj = get_adjacency(&g, AdjacencyType::Both, None, LoopHandling::Once).unwrap();
257        assert!(approx_eq(adj[0][0], 1.0));
258    }
259
260    #[test]
261    fn self_loop_twice_undirected() {
262        let mut g = Graph::with_vertices(2);
263        g.add_edge(0, 0).unwrap();
264        g.add_edge(0, 1).unwrap();
265        let adj = get_adjacency(&g, AdjacencyType::Both, None, LoopHandling::Twice).unwrap();
266        assert!(approx_eq(adj[0][0], 2.0));
267    }
268
269    #[test]
270    fn self_loop_twice_directed() {
271        let mut g = Graph::new(2, true).unwrap();
272        g.add_edge(0, 0).unwrap();
273        g.add_edge(0, 1).unwrap();
274        let adj = get_adjacency(&g, AdjacencyType::Both, None, LoopHandling::Twice).unwrap();
275        // Directed: loops counted once even with Twice
276        assert!(approx_eq(adj[0][0], 1.0));
277    }
278
279    #[test]
280    fn weighted() {
281        let mut g = Graph::with_vertices(3);
282        g.add_edge(0, 1).unwrap();
283        g.add_edge(1, 2).unwrap();
284        let weights = vec![2.5, 3.0];
285        let adj =
286            get_adjacency(&g, AdjacencyType::Both, Some(&weights), LoopHandling::Once).unwrap();
287        assert!(approx_eq(adj[0][1], 2.5));
288        assert!(approx_eq(adj[1][0], 2.5));
289        assert!(approx_eq(adj[1][2], 3.0));
290        assert!(approx_eq(adj[2][1], 3.0));
291    }
292
293    #[test]
294    fn multi_edge() {
295        let mut g = Graph::with_vertices(2);
296        g.add_edge(0, 1).unwrap();
297        g.add_edge(0, 1).unwrap();
298        let adj = get_adjacency(&g, AdjacencyType::Both, None, LoopHandling::Once).unwrap();
299        assert!(approx_eq(adj[0][1], 2.0));
300        assert!(approx_eq(adj[1][0], 2.0));
301    }
302
303    #[test]
304    fn weight_mismatch() {
305        let mut g = Graph::with_vertices(2);
306        g.add_edge(0, 1).unwrap();
307        let result = get_adjacency(
308            &g,
309            AdjacencyType::Both,
310            Some(&[1.0, 2.0]),
311            LoopHandling::Once,
312        );
313        assert!(result.is_err());
314    }
315
316    #[test]
317    fn upper_reversed_edge_order() {
318        // Edge stored as (1, 0) internally — ensure upper still places in [0][1]
319        let mut g = Graph::with_vertices(3);
320        g.add_edge(2, 0).unwrap();
321        let adj = get_adjacency(&g, AdjacencyType::Upper, None, LoopHandling::Once).unwrap();
322        assert!(approx_eq(adj[0][2], 1.0));
323        assert!(approx_eq(adj[2][0], 0.0));
324    }
325
326    #[test]
327    fn lower_reversed_edge_order() {
328        let mut g = Graph::with_vertices(3);
329        g.add_edge(0, 2).unwrap();
330        let adj = get_adjacency(&g, AdjacencyType::Lower, None, LoopHandling::Once).unwrap();
331        assert!(approx_eq(adj[2][0], 1.0));
332        assert!(approx_eq(adj[0][2], 0.0));
333    }
334}
rust_igraph/algorithms/properties/adjacency.rs

rust_igraph/algorithms/properties/
adjacency.rs
