rust_igraph/algorithms/properties/
degree.rs

1//! Degree sequence and extremal degree queries (ALGO-PR-036).
2//!
3//! Batch computation of vertex degrees and max/min degree queries.
4//! Counterpart of `igraph_degree`, `igraph_maxdegree`, `igraph_strength`
5//! (the unweighted part).
6
7use crate::core::{Graph, IgraphResult, VertexId};
8
9/// Direction mode for degree computation in directed graphs.
10#[derive(Debug, Clone, Copy, PartialEq, Eq)]
11pub enum DegreeMode {
12    /// Out-degree (number of outgoing edges).
13    Out,
14    /// In-degree (number of incoming edges).
15    In,
16    /// Total degree (out + in; for undirected graphs, same as either).
17    All,
18}
19
20/// Returns the degree sequence of the graph.
21///
22/// For undirected graphs, `mode` is ignored. For directed graphs:
23/// - `Out`: count outgoing edges per vertex.
24/// - `In`: count incoming edges per vertex.
25/// - `All`: count all incident edges per vertex.
26///
27/// Self-loops contribute 2 to a vertex's degree in `All` mode for
28/// undirected graphs (matching igraph C `IGRAPH_LOOPS_TWICE` convention),
29/// and 1 each to in-degree and out-degree for directed graphs.
30///
31/// # Examples
32///
33/// ```
34/// use rust_igraph::{Graph, degree_sequence, DegreeMode};
35///
36/// let mut g = Graph::with_vertices(4);
37/// g.add_edge(0, 1).unwrap();
38/// g.add_edge(0, 2).unwrap();
39/// g.add_edge(0, 3).unwrap();
40/// let deg = degree_sequence(&g, DegreeMode::All).unwrap();
41/// assert_eq!(deg, vec![3, 1, 1, 1]);
42///
43/// // Directed graph
44/// let mut g = Graph::new(3, true).unwrap();
45/// g.add_edge(0, 1).unwrap();
46/// g.add_edge(0, 2).unwrap();
47/// g.add_edge(1, 2).unwrap();
48/// let out_deg = degree_sequence(&g, DegreeMode::Out).unwrap();
49/// assert_eq!(out_deg, vec![2, 1, 0]);
50/// let in_deg = degree_sequence(&g, DegreeMode::In).unwrap();
51/// assert_eq!(in_deg, vec![0, 1, 2]);
52/// ```
53pub fn degree_sequence(graph: &Graph, mode: DegreeMode) -> IgraphResult<Vec<u32>> {
54    let n = graph.vcount() as usize;
55    let ecount = graph.ecount();
56    let mut degrees = vec![0u32; n];
57
58    for eid in 0..ecount {
59        #[allow(clippy::cast_possible_truncation)]
60        let (src, tgt) = graph.edge(eid as u32)?;
61
62        if graph.is_directed() {
63            match mode {
64                DegreeMode::Out => {
65                    degrees[src as usize] += 1;
66                }
67                DegreeMode::In => {
68                    degrees[tgt as usize] += 1;
69                }
70                DegreeMode::All => {
71                    degrees[src as usize] += 1;
72                    if src != tgt {
73                        degrees[tgt as usize] += 1;
74                    }
75                }
76            }
77        } else {
78            degrees[src as usize] += 1;
79            degrees[tgt as usize] += 1;
80        }
81    }
82
83    Ok(degrees)
84}
85
86/// Returns the maximum degree in the graph.
87///
88/// Returns 0 for empty graphs (no vertices). For directed graphs,
89/// uses the specified `mode`.
90///
91/// # Examples
92///
93/// ```
94/// use rust_igraph::{Graph, max_degree, DegreeMode};
95///
96/// let mut g = Graph::with_vertices(4);
97/// g.add_edge(0, 1).unwrap();
98/// g.add_edge(0, 2).unwrap();
99/// g.add_edge(0, 3).unwrap();
100/// assert_eq!(max_degree(&g, DegreeMode::All).unwrap(), 3);
101/// ```
102pub fn max_degree(graph: &Graph, mode: DegreeMode) -> IgraphResult<u32> {
103    let degrees = degree_sequence(graph, mode)?;
104    Ok(degrees.into_iter().max().unwrap_or(0))
105}
106
107/// Returns the minimum degree in the graph.
108///
109/// Returns 0 for empty graphs (no vertices). For directed graphs,
110/// uses the specified `mode`.
111///
112/// # Examples
113///
114/// ```
115/// use rust_igraph::{Graph, min_degree, DegreeMode};
116///
117/// let mut g = Graph::with_vertices(4);
118/// g.add_edge(0, 1).unwrap();
119/// g.add_edge(0, 2).unwrap();
120/// g.add_edge(0, 3).unwrap();
121/// assert_eq!(min_degree(&g, DegreeMode::All).unwrap(), 1);
122/// ```
123pub fn min_degree(graph: &Graph, mode: DegreeMode) -> IgraphResult<u32> {
124    let degrees = degree_sequence(graph, mode)?;
125    Ok(degrees.into_iter().min().unwrap_or(0))
126}
127
128/// Returns the vertex (or one of the vertices) with the maximum degree.
129///
130/// Returns `None` for an empty graph.
131///
132/// # Examples
133///
134/// ```
135/// use rust_igraph::{Graph, max_degree_vertex, DegreeMode};
136///
137/// let mut g = Graph::with_vertices(4);
138/// g.add_edge(0, 1).unwrap();
139/// g.add_edge(0, 2).unwrap();
140/// g.add_edge(0, 3).unwrap();
141/// assert_eq!(max_degree_vertex(&g, DegreeMode::All).unwrap(), Some(0));
142/// ```
143pub fn max_degree_vertex(graph: &Graph, mode: DegreeMode) -> IgraphResult<Option<VertexId>> {
144    let degrees = degree_sequence(graph, mode)?;
145    Ok(degrees
146        .iter()
147        .enumerate()
148        .max_by_key(|(_, d)| *d)
149        .map(|(i, _)| {
150            #[allow(clippy::cast_possible_truncation)]
151            let v = i as u32;
152            v
153        }))
154}
155
156#[cfg(test)]
157mod tests {
158    use super::*;
159
160    #[test]
161    fn test_empty_graph() {
162        let g = Graph::with_vertices(0);
163        let deg = degree_sequence(&g, DegreeMode::All).unwrap();
164        assert!(deg.is_empty());
165        assert_eq!(max_degree(&g, DegreeMode::All).unwrap(), 0);
166        assert_eq!(min_degree(&g, DegreeMode::All).unwrap(), 0);
167    }
168
169    #[test]
170    fn test_isolated_vertices() {
171        let g = Graph::with_vertices(5);
172        let deg = degree_sequence(&g, DegreeMode::All).unwrap();
173        assert_eq!(deg, vec![0, 0, 0, 0, 0]);
174    }
175
176    #[test]
177    fn test_undirected_path() {
178        let mut g = Graph::with_vertices(4);
179        g.add_edge(0, 1).unwrap();
180        g.add_edge(1, 2).unwrap();
181        g.add_edge(2, 3).unwrap();
182        let deg = degree_sequence(&g, DegreeMode::All).unwrap();
183        assert_eq!(deg, vec![1, 2, 2, 1]);
184    }
185
186    #[test]
187    fn test_undirected_star() {
188        let mut g = Graph::with_vertices(5);
189        for i in 1..5u32 {
190            g.add_edge(0, i).unwrap();
191        }
192        let deg = degree_sequence(&g, DegreeMode::All).unwrap();
193        assert_eq!(deg, vec![4, 1, 1, 1, 1]);
194        assert_eq!(max_degree(&g, DegreeMode::All).unwrap(), 4);
195        assert_eq!(min_degree(&g, DegreeMode::All).unwrap(), 1);
196    }
197
198    #[test]
199    fn test_directed_out() {
200        let mut g = Graph::new(3, true).unwrap();
201        g.add_edge(0, 1).unwrap();
202        g.add_edge(0, 2).unwrap();
203        g.add_edge(1, 2).unwrap();
204        let deg = degree_sequence(&g, DegreeMode::Out).unwrap();
205        assert_eq!(deg, vec![2, 1, 0]);
206    }
207
208    #[test]
209    fn test_directed_in() {
210        let mut g = Graph::new(3, true).unwrap();
211        g.add_edge(0, 1).unwrap();
212        g.add_edge(0, 2).unwrap();
213        g.add_edge(1, 2).unwrap();
214        let deg = degree_sequence(&g, DegreeMode::In).unwrap();
215        assert_eq!(deg, vec![0, 1, 2]);
216    }
217
218    #[test]
219    fn test_directed_all() {
220        let mut g = Graph::new(3, true).unwrap();
221        g.add_edge(0, 1).unwrap();
222        g.add_edge(0, 2).unwrap();
223        g.add_edge(1, 2).unwrap();
224        let deg = degree_sequence(&g, DegreeMode::All).unwrap();
225        assert_eq!(deg, vec![2, 2, 2]);
226    }
227
228    #[test]
229    fn test_self_loop_undirected() {
230        let mut g = Graph::with_vertices(2);
231        g.add_edge(0, 0).unwrap();
232        g.add_edge(0, 1).unwrap();
233        let deg = degree_sequence(&g, DegreeMode::All).unwrap();
234        // Self-loop contributes 2 to vertex 0
235        assert_eq!(deg, vec![3, 1]);
236    }
237
238    #[test]
239    fn test_self_loop_directed_out() {
240        let mut g = Graph::new(2, true).unwrap();
241        g.add_edge(0, 0).unwrap();
242        g.add_edge(0, 1).unwrap();
243        let deg = degree_sequence(&g, DegreeMode::Out).unwrap();
244        assert_eq!(deg, vec![2, 0]);
245    }
246
247    #[test]
248    fn test_self_loop_directed_in() {
249        let mut g = Graph::new(2, true).unwrap();
250        g.add_edge(0, 0).unwrap();
251        g.add_edge(0, 1).unwrap();
252        let deg = degree_sequence(&g, DegreeMode::In).unwrap();
253        assert_eq!(deg, vec![1, 1]);
254    }
255
256    #[test]
257    fn test_self_loop_directed_all() {
258        let mut g = Graph::new(2, true).unwrap();
259        g.add_edge(0, 0).unwrap();
260        g.add_edge(0, 1).unwrap();
261        let deg = degree_sequence(&g, DegreeMode::All).unwrap();
262        // Self-loop: src == tgt, only counts once in All mode
263        assert_eq!(deg, vec![2, 1]);
264    }
265
266    #[test]
267    fn test_max_degree_vertex_basic() {
268        let mut g = Graph::with_vertices(4);
269        g.add_edge(0, 1).unwrap();
270        g.add_edge(0, 2).unwrap();
271        g.add_edge(0, 3).unwrap();
272        assert_eq!(max_degree_vertex(&g, DegreeMode::All).unwrap(), Some(0));
273    }
274
275    #[test]
276    fn test_max_degree_vertex_empty() {
277        let g = Graph::with_vertices(0);
278        assert_eq!(max_degree_vertex(&g, DegreeMode::All).unwrap(), None);
279    }
280
281    #[test]
282    fn test_complete_graph() {
283        let mut g = Graph::with_vertices(5);
284        for i in 0..5u32 {
285            for j in (i + 1)..5 {
286                g.add_edge(i, j).unwrap();
287            }
288        }
289        let deg = degree_sequence(&g, DegreeMode::All).unwrap();
290        assert!(deg.iter().all(|&d| d == 4));
291        assert_eq!(max_degree(&g, DegreeMode::All).unwrap(), 4);
292        assert_eq!(min_degree(&g, DegreeMode::All).unwrap(), 4);
293    }
294
295    #[test]
296    fn test_multi_edges() {
297        let mut g = Graph::with_vertices(2);
298        g.add_edge(0, 1).unwrap();
299        g.add_edge(0, 1).unwrap();
300        g.add_edge(0, 1).unwrap();
301        let deg = degree_sequence(&g, DegreeMode::All).unwrap();
302        assert_eq!(deg, vec![3, 3]);
303    }
304}
rust_igraph/algorithms/properties/degree.rs

rust_igraph/algorithms/properties/
degree.rs
