rust_igraph/algorithms/properties/
sort_by_degree.rs

1//! Sort vertex IDs by degree (ALGO-PR-054).
2//!
3//! Counterpart of `igraph_sort_vertex_ids_by_degree()` from
4//! `references/igraph/src/properties/degrees.c:712`.
5//!
6//! Returns vertex IDs sorted by their degree in ascending or
7//! descending order.
8
9use crate::algorithms::properties::degree::DegreeMode;
10use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
11
12/// Sort order for vertex degree sorting.
13#[derive(Debug, Clone, Copy, PartialEq, Eq)]
14pub enum SortOrder {
15    /// Smallest degree first.
16    Ascending,
17    /// Largest degree first.
18    Descending,
19}
20
21/// Return vertex IDs sorted by their degree.
22///
23/// - `mode`: which degree to use (`Out`, `In`, or `All`). For
24///   undirected graphs all modes are equivalent.
25/// - `order`: ascending (smallest degree first) or descending.
26///
27/// Returns a `Vec<VertexId>` containing all vertex IDs in the
28/// requested order. Ties are broken by vertex ID (stable sort).
29///
30/// # Examples
31///
32/// ```
33/// use rust_igraph::{Graph, sort_vertices_by_degree, DegreeMode, SortOrder};
34///
35/// // Star: center vertex has degree 3, leaves have degree 1.
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 sorted = sort_vertices_by_degree(&g, DegreeMode::All, SortOrder::Descending).unwrap();
41/// assert_eq!(sorted[0], 0); // highest degree vertex first
42/// ```
43pub fn sort_vertices_by_degree(
44    graph: &Graph,
45    mode: DegreeMode,
46    order: SortOrder,
47) -> IgraphResult<Vec<VertexId>> {
48    let n = graph.vcount();
49
50    if n == 0 {
51        return Ok(Vec::new());
52    }
53
54    let n_usize = n as usize;
55    let ecount = graph.ecount();
56    let directed = graph.is_directed();
57
58    let mut deg = vec![0u32; n_usize];
59
60    if ecount > 0 {
61        let m_u32 =
62            u32::try_from(ecount).map_err(|_| IgraphError::Internal("ecount exceeds u32::MAX"))?;
63
64        for eid in 0..m_u32 {
65            let (from, to) = graph.edge(eid)?;
66            let f = from as usize;
67            let t = to as usize;
68
69            if directed {
70                match mode {
71                    DegreeMode::Out => {
72                        deg[f] += 1;
73                    }
74                    DegreeMode::In => {
75                        deg[t] += 1;
76                    }
77                    DegreeMode::All => {
78                        deg[f] += 1;
79                        deg[t] += 1;
80                    }
81                }
82            } else if from == to {
83                deg[f] += 2;
84            } else {
85                deg[f] += 1;
86                deg[t] += 1;
87            }
88        }
89    }
90
91    let mut ids: Vec<VertexId> = (0..n).collect();
92
93    match order {
94        SortOrder::Ascending => {
95            ids.sort_by(|&a, &b| deg[a as usize].cmp(&deg[b as usize]));
96        }
97        SortOrder::Descending => {
98            ids.sort_by(|&a, &b| deg[b as usize].cmp(&deg[a as usize]));
99        }
100    }
101
102    Ok(ids)
103}
104
105#[cfg(test)]
106mod tests {
107    use super::*;
108
109    #[test]
110    fn empty_graph() {
111        let g = Graph::with_vertices(0);
112        let s = sort_vertices_by_degree(&g, DegreeMode::All, SortOrder::Ascending).unwrap();
113        assert!(s.is_empty());
114    }
115
116    #[test]
117    fn no_edges_ascending() {
118        let g = Graph::with_vertices(5);
119        let s = sort_vertices_by_degree(&g, DegreeMode::All, SortOrder::Ascending).unwrap();
120        // All degree 0, stable sort → original order.
121        assert_eq!(s, vec![0, 1, 2, 3, 4]);
122    }
123
124    #[test]
125    fn star_descending() {
126        let mut g = Graph::with_vertices(4);
127        g.add_edge(0, 1).unwrap();
128        g.add_edge(0, 2).unwrap();
129        g.add_edge(0, 3).unwrap();
130        let s = sort_vertices_by_degree(&g, DegreeMode::All, SortOrder::Descending).unwrap();
131        // deg = [3, 1, 1, 1]. Descending: 0 first, then 1,2,3.
132        assert_eq!(s[0], 0);
133        assert_eq!(s.len(), 4);
134    }
135
136    #[test]
137    fn star_ascending() {
138        let mut g = Graph::with_vertices(4);
139        g.add_edge(0, 1).unwrap();
140        g.add_edge(0, 2).unwrap();
141        g.add_edge(0, 3).unwrap();
142        let s = sort_vertices_by_degree(&g, DegreeMode::All, SortOrder::Ascending).unwrap();
143        // deg = [3, 1, 1, 1]. Ascending: 1,2,3 first (degree 1), then 0 (degree 3).
144        assert_eq!(s[3], 0);
145    }
146
147    #[test]
148    fn path_5_ascending() {
149        let mut g = Graph::with_vertices(5);
150        for i in 0..4u32 {
151            g.add_edge(i, i + 1).unwrap();
152        }
153        let s = sort_vertices_by_degree(&g, DegreeMode::All, SortOrder::Ascending).unwrap();
154        // deg = [1, 2, 2, 2, 1]. Sorted ascending: 0,4 (deg 1), then 1,2,3 (deg 2).
155        assert!(s[0] == 0 || s[0] == 4);
156        assert!(s[1] == 0 || s[1] == 4);
157        assert!(s[0] != s[1]);
158    }
159
160    #[test]
161    fn directed_out_degree() {
162        // 0→1, 0→2, 1→2
163        let mut g = Graph::new(3, true).unwrap();
164        g.add_edge(0, 1).unwrap();
165        g.add_edge(0, 2).unwrap();
166        g.add_edge(1, 2).unwrap();
167        let s = sort_vertices_by_degree(&g, DegreeMode::Out, SortOrder::Descending).unwrap();
168        // out-deg = [2, 1, 0]. Desc: 0, 1, 2.
169        assert_eq!(s, vec![0, 1, 2]);
170    }
171
172    #[test]
173    fn directed_in_degree() {
174        // 0→1, 0→2, 1→2
175        let mut g = Graph::new(3, true).unwrap();
176        g.add_edge(0, 1).unwrap();
177        g.add_edge(0, 2).unwrap();
178        g.add_edge(1, 2).unwrap();
179        let s = sort_vertices_by_degree(&g, DegreeMode::In, SortOrder::Descending).unwrap();
180        // in-deg = [0, 1, 2]. Desc: 2, 1, 0.
181        assert_eq!(s, vec![2, 1, 0]);
182    }
183
184    #[test]
185    fn k4_stable_order() {
186        let mut g = Graph::with_vertices(4);
187        for u in 0..4u32 {
188            for v in (u + 1)..4 {
189                g.add_edge(u, v).unwrap();
190            }
191        }
192        let s = sort_vertices_by_degree(&g, DegreeMode::All, SortOrder::Ascending).unwrap();
193        // All same degree → stable sort preserves original order.
194        assert_eq!(s, vec![0, 1, 2, 3]);
195    }
196
197    #[test]
198    fn self_loop_counted() {
199        let mut g = Graph::with_vertices(3);
200        g.add_edge(0, 0).unwrap(); // self-loop: deg(0) += 2
201        g.add_edge(0, 1).unwrap(); // deg(0) += 1, deg(1) += 1
202        g.add_edge(1, 2).unwrap(); // deg(1) += 1, deg(2) += 1
203        let s = sort_vertices_by_degree(&g, DegreeMode::All, SortOrder::Descending).unwrap();
204        // deg = [3, 2, 1]. Desc: 0, 1, 2.
205        assert_eq!(s, vec![0, 1, 2]);
206    }
207}
rust_igraph/algorithms/properties/sort_by_degree.rs

rust_igraph/algorithms/properties/
sort_by_degree.rs
