rust_igraph/algorithms/properties/
joint_degree_distribution.rs

1//! Joint degree distribution (ALGO-PR-045).
2//!
3//! Counterpart of `igraph_joint_degree_distribution()` in
4//! `references/igraph/src/misc/mixing.c:852-927`.
5//!
6//! Computes `P_ij`: the (possibly normalized) count of connected ordered
7//! vertex pairs having degrees i and j.
8
9use crate::algorithms::properties::degree::{DegreeMode, degree_sequence};
10use crate::core::{Graph, IgraphResult};
11
12/// Compute the joint degree distribution matrix.
13///
14/// Returns a matrix `P` where `P[i][j]` counts (or gives the probability of)
15/// a randomly chosen ordered pair of connected vertices having degrees `i`
16/// and `j`.
17///
18/// For undirected graphs, `from_mode` and `to_mode` are forced to
19/// [`DegreeMode::All`] and each edge contributes to both `P[d(u)][d(v)]`
20/// and `P[d(v)][d(u)]`.
21///
22/// For directed graphs with `directed_neighbors = true`, only `u → v` arcs
23/// are counted (incrementing `P[deg_from(u)][deg_to(v)]`). With
24/// `directed_neighbors = false`, each edge also contributes in reverse.
25///
26/// # Parameters
27///
28/// * `graph` — the input graph.
29/// * `from_mode` — degree mode for sources (Out/In/All). Ignored for
30///   undirected graphs.
31/// * `to_mode` — degree mode for targets. Ignored for undirected graphs.
32/// * `directed_neighbors` — whether to treat connections as directed.
33///   Ignored for undirected graphs.
34/// * `normalized` — if `true`, scale matrix so entries sum to 1.0.
35/// * `max_from_degree` — if `Some(k)`, clip row count to `k+1`.
36/// * `max_to_degree` — if `Some(k)`, clip column count to `k+1`.
37///
38/// # Examples
39///
40/// ```
41/// use rust_igraph::{Graph, joint_degree_distribution, DegreeMode};
42///
43/// let mut g = Graph::with_vertices(4);
44/// g.add_edge(0, 1).unwrap();
45/// g.add_edge(1, 2).unwrap();
46/// g.add_edge(2, 3).unwrap();
47/// // Path graph: degrees are [1, 2, 2, 1]
48/// let p = joint_degree_distribution(
49///     &g, DegreeMode::All, DegreeMode::All, false, false, None, None,
50/// ).unwrap();
51/// // P[1][2] counts edges connecting degree-1 and degree-2 vertices
52/// assert!(p[1][2] > 0.0);
53/// ```
54#[allow(clippy::too_many_arguments)]
55pub fn joint_degree_distribution(
56    graph: &Graph,
57    from_mode: DegreeMode,
58    to_mode: DegreeMode,
59    directed_neighbors: bool,
60    normalized: bool,
61    max_from_degree: Option<u32>,
62    max_to_degree: Option<u32>,
63) -> IgraphResult<Vec<Vec<f64>>> {
64    let vcount = graph.vcount();
65    let ecount = graph.ecount();
66
67    // For undirected graphs, force modes.
68    let (fm, tm, dir_neigh) = if graph.is_directed() {
69        (from_mode, to_mode, directed_neighbors)
70    } else {
71        (DegreeMode::All, DegreeMode::All, false)
72    };
73
74    // Compute degree vectors.
75    let deg_from = degree_sequence(graph, fm)?;
76    let deg_to = if std::mem::discriminant(&fm) == std::mem::discriminant(&tm) {
77        deg_from.clone()
78    } else {
79        degree_sequence(graph, tm)?
80    };
81
82    // Determine matrix dimensions.
83    let nrow = if let Some(max) = max_from_degree {
84        max as usize + 1
85    } else if vcount == 0 {
86        0
87    } else {
88        *deg_from.iter().max().unwrap_or(&0) as usize + 1
89    };
90
91    let ncol = if let Some(max) = max_to_degree {
92        max as usize + 1
93    } else if vcount == 0 {
94        0
95    } else {
96        *deg_to.iter().max().unwrap_or(&0) as usize + 1
97    };
98
99    let mut matrix = vec![vec![0.0_f64; ncol]; nrow];
100    let mut sum = 0.0_f64;
101
102    for eid in 0..ecount {
103        #[allow(clippy::cast_possible_truncation)]
104        let (src, tgt) = graph.edge(eid as u32)?;
105
106        let from_type = deg_from[src as usize] as usize;
107        let to_type = deg_to[tgt as usize] as usize;
108
109        if from_type < nrow && to_type < ncol {
110            matrix[from_type][to_type] += 1.0;
111            sum += 1.0;
112        }
113
114        if !dir_neigh {
115            let rev_from = deg_from[tgt as usize] as usize;
116            let rev_to = deg_to[src as usize] as usize;
117            if rev_from < nrow && rev_to < ncol {
118                matrix[rev_from][rev_to] += 1.0;
119                sum += 1.0;
120            }
121        }
122    }
123
124    if normalized && ecount > 0 && sum > 0.0 {
125        let inv = 1.0 / sum;
126        for row in &mut matrix {
127            for val in row.iter_mut() {
128                *val *= inv;
129            }
130        }
131    }
132
133    Ok(matrix)
134}
135
136#[cfg(test)]
137#[allow(clippy::float_cmp)]
138mod tests {
139    use super::*;
140    use crate::core::Graph;
141
142    #[test]
143    fn empty_graph() {
144        let g = Graph::new(0, false).unwrap();
145        let p = joint_degree_distribution(
146            &g,
147            DegreeMode::All,
148            DegreeMode::All,
149            false,
150            false,
151            None,
152            None,
153        )
154        .unwrap();
155        assert!(p.is_empty());
156    }
157
158    #[test]
159    fn no_edges() {
160        let g = Graph::new(5, false).unwrap();
161        let p = joint_degree_distribution(
162            &g,
163            DegreeMode::All,
164            DegreeMode::All,
165            false,
166            false,
167            None,
168            None,
169        )
170        .unwrap();
171        // Max degree is 0, so matrix is 1×1 with value 0.
172        assert_eq!(p.len(), 1);
173        assert_eq!(p[0][0], 0.0);
174    }
175
176    #[test]
177    fn single_edge_undirected() {
178        let mut g = Graph::new(2, false).unwrap();
179        g.add_edges(vec![(0, 1)]).unwrap();
180        let p = joint_degree_distribution(
181            &g,
182            DegreeMode::All,
183            DegreeMode::All,
184            false,
185            false,
186            None,
187            None,
188        )
189        .unwrap();
190        // Both vertices have degree 1. Undirected → counts both directions.
191        assert_eq!(p.len(), 2); // rows 0..1
192        assert_eq!(p[1][1], 2.0); // (deg1→deg1) counted twice
193    }
194
195    #[test]
196    fn single_edge_normalized() {
197        let mut g = Graph::new(2, false).unwrap();
198        g.add_edges(vec![(0, 1)]).unwrap();
199        let p = joint_degree_distribution(
200            &g,
201            DegreeMode::All,
202            DegreeMode::All,
203            false,
204            true,
205            None,
206            None,
207        )
208        .unwrap();
209        assert_eq!(p[1][1], 1.0); // normalized: all mass at (1,1)
210    }
211
212    #[test]
213    fn path_graph() {
214        // 0-1-2-3: degrees [1,2,2,1]
215        let mut g = Graph::new(4, false).unwrap();
216        g.add_edges(vec![(0, 1), (1, 2), (2, 3)]).unwrap();
217        let p = joint_degree_distribution(
218            &g,
219            DegreeMode::All,
220            DegreeMode::All,
221            false,
222            false,
223            None,
224            None,
225        )
226        .unwrap();
227        // Edge (0,1): forward p[1][2]+=1, reverse p[2][1]+=1
228        // Edge (1,2): forward p[2][2]+=1, reverse p[2][2]+=1
229        // Edge (2,3): forward p[2][1]+=1, reverse p[1][2]+=1
230        assert_eq!(p[1][2], 2.0);
231        assert_eq!(p[2][1], 2.0);
232        assert_eq!(p[2][2], 2.0);
233    }
234
235    #[test]
236    fn directed_out_in() {
237        // 0→1→2: out-degrees [1,1,0], in-degrees [0,1,1]
238        let mut g = Graph::new(3, true).unwrap();
239        g.add_edges(vec![(0, 1), (1, 2)]).unwrap();
240        let p =
241            joint_degree_distribution(&g, DegreeMode::Out, DegreeMode::In, true, false, None, None)
242                .unwrap();
243        // Edge 0→1: from_deg=out(0)=1, to_deg=in(1)=1 → p[1][1] += 1
244        // Edge 1→2: from_deg=out(1)=1, to_deg=in(2)=1 → p[1][1] += 1
245        assert_eq!(p[1][1], 2.0);
246    }
247
248    #[test]
249    fn max_degree_clips() {
250        let mut g = Graph::new(4, false).unwrap();
251        g.add_edges(vec![(0, 1), (1, 2), (2, 3)]).unwrap();
252        let p = joint_degree_distribution(
253            &g,
254            DegreeMode::All,
255            DegreeMode::All,
256            false,
257            false,
258            Some(1),
259            Some(1),
260        )
261        .unwrap();
262        // Matrix is 2×2 (indices 0..=1)
263        assert_eq!(p.len(), 2);
264        assert_eq!(p[0].len(), 2);
265        // Only p[1][1] from edges between deg-1 vertices: edges (0,1) and (2,3)
266        // where both endpoints have deg≤1... actually vertex 1 has deg 2 which is clipped
267        // edge (0,1): from_deg=1, to_deg=2 → 2 >= nrow=2, skipped in forward
268        //            reverse: from_deg=2, to_deg=1 → 2 >= nrow=2, skipped
269        // edge (1,2): both deg=2, both >= nrow=2, skipped both ways
270        // edge (2,3): from_deg=2, to_deg=1 → 2 >= nrow=2, skipped forward
271        //            reverse: from_deg=1, to_deg=2 → 2 >= ncol=2, skipped
272        // So p[1][1] = 0 — only deg-1-to-deg-1 direct connections exist (none in this graph)
273        assert_eq!(p[1][1], 0.0);
274    }
275
276    #[test]
277    fn triangle_undirected() {
278        let mut g = Graph::new(3, false).unwrap();
279        g.add_edges(vec![(0, 1), (1, 2), (2, 0)]).unwrap();
280        let p = joint_degree_distribution(
281            &g,
282            DegreeMode::All,
283            DegreeMode::All,
284            false,
285            false,
286            None,
287            None,
288        )
289        .unwrap();
290        // All vertices have degree 2. Each of 3 edges counted twice → p[2][2] = 6
291        assert_eq!(p[2][2], 6.0);
292    }
293
294    #[test]
295    fn triangle_normalized() {
296        let mut g = Graph::new(3, false).unwrap();
297        g.add_edges(vec![(0, 1), (1, 2), (2, 0)]).unwrap();
298        let p = joint_degree_distribution(
299            &g,
300            DegreeMode::All,
301            DegreeMode::All,
302            false,
303            true,
304            None,
305            None,
306        )
307        .unwrap();
308        assert_eq!(p[2][2], 1.0);
309    }
310
311    #[test]
312    fn directed_not_directed_neighbors() {
313        // 0→1: with directed_neighbors=false, counts both directions
314        let mut g = Graph::new(2, true).unwrap();
315        g.add_edges(vec![(0, 1)]).unwrap();
316        let p = joint_degree_distribution(
317            &g,
318            DegreeMode::Out,
319            DegreeMode::In,
320            false,
321            false,
322            None,
323            None,
324        )
325        .unwrap();
326        // out-degrees: [1, 0], in-degrees: [0, 1]
327        // Forward: p[out(0)=1][in(1)=1] += 1 → p[1][1] = 1
328        // Reverse: p[out(1)=0][in(0)=0] += 1 → p[0][0] = 1
329        assert_eq!(p[1][1], 1.0);
330        assert_eq!(p[0][0], 1.0);
331    }
332
333    #[test]
334    fn self_loop_undirected() {
335        let mut g = Graph::new(2, false).unwrap();
336        g.add_edges(vec![(0, 0), (0, 1)]).unwrap();
337        let p = joint_degree_distribution(
338            &g,
339            DegreeMode::All,
340            DegreeMode::All,
341            false,
342            false,
343            None,
344            None,
345        )
346        .unwrap();
347        // degrees: vertex 0 has degree 3 (loop=2 + edge=1), vertex 1 has degree 1
348        // edge (0,0): both endpoints are vertex 0 with deg 3
349        //   forward: p[3][3] += 1, reverse: p[3][3] += 1 → 2
350        // edge (0,1): deg 3 and deg 1
351        //   forward: p[3][1] += 1, reverse: p[1][3] += 1
352        assert_eq!(p[3][3], 2.0);
353        assert_eq!(p[3][1], 1.0);
354        assert_eq!(p[1][3], 1.0);
355    }
356}
rust_igraph/algorithms/properties/joint_degree_distribution.rs

rust_igraph/algorithms/properties/
joint_degree_distribution.rs
