graaf/op/
degree.rs

1//! Return a vertex's degree.
2//!
3//! A vertex's degree is the sum of its indegree and outdegree.
4//!
5//! # Examples
6//!
7//! ```
8//! use graaf::{
9//!     AddArc,
10//!     AdjacencyList,
11//!     Degree,
12//!     Empty,
13//! };
14//!
15//! let mut digraph = AdjacencyList::empty(3);
16//!
17//! digraph.add_arc(0, 1);
18//! digraph.add_arc(0, 2);
19//! digraph.add_arc(1, 2);
20//! digraph.add_arc(2, 0);
21//!
22//! assert_eq!(digraph.degree(0), 3);
23//! assert_eq!(digraph.degree(1), 2);
24//! assert_eq!(digraph.degree(2), 3);
25//! ```
26#![doc(alias = "semidegree")]
27#![doc(alias = "valence")]
28#![doc(alias = "valency")]
29
30use crate::{
31    Indegree,
32    Outdegree,
33    Vertices,
34};
35
36/// Vertex degree
37#[doc(alias = "Semidegree")]
38#[doc(alias = "Valence")]
39#[doc(alias = "Valency")]
40pub trait Degree {
41    /// Return a vertex's degree.
42    ///
43    /// # Arguments
44    ///
45    /// * `u`: The vertex.
46    ///
47    /// # Examples
48    ///
49    /// ```
50    /// use graaf::{
51    ///     AddArc,
52    ///     AdjacencyList,
53    ///     Degree,
54    ///     Empty,
55    /// };
56    ///
57    /// let mut digraph = AdjacencyList::empty(3);
58    ///
59    /// digraph.add_arc(0, 1);
60    /// digraph.add_arc(0, 2);
61    /// digraph.add_arc(1, 2);
62    /// digraph.add_arc(2, 0);
63    ///
64    /// assert_eq!(digraph.degree(0), 3);
65    /// assert_eq!(digraph.degree(1), 2);
66    /// assert_eq!(digraph.degree(2), 3);
67    /// ```
68    #[doc(alias = "semidegree")]
69    #[doc(alias = "valence")]
70    #[doc(alias = "valency")]
71    #[must_use]
72    fn degree(&self, u: usize) -> usize;
73
74    /// Return a digraph's maximum degree.
75    ///
76    /// # Examples
77    ///
78    /// The maximum degree of this digraph is `6`. The vertex with the maximum
79    /// degree is red.
80    ///
81    /// ![A digraph and its maximum degree](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/max_degree-0.88.4.svg?)
82    ///
83    /// ```
84    /// use graaf::{
85    ///     AddArc,
86    ///     AdjacencyList,
87    ///     Degree,
88    ///     Empty,
89    /// };
90    ///
91    /// let mut digraph = AdjacencyList::empty(4);
92    ///
93    /// digraph.add_arc(0, 1);
94    /// digraph.add_arc(0, 2);
95    /// digraph.add_arc(0, 3);
96    /// digraph.add_arc(1, 0);
97    /// digraph.add_arc(1, 2);
98    /// digraph.add_arc(2, 0);
99    /// digraph.add_arc(3, 0);
100    ///
101    /// assert_eq!(digraph.max_degree(), 6);
102    /// ```
103    #[must_use]
104    fn max_degree(&self) -> usize
105    where
106        Self: Vertices,
107    {
108        self.vertices().map(|u| self.degree(u)).max().unwrap_or(0)
109    }
110
111    /// Return a digraph's minimum degree.
112    ///
113    /// # Examples
114    ///
115    /// The minimum degree of this digraph is `2`. The vertex with the minimum
116    /// degree is red.
117    ///
118    /// ![A digraph and its minimum degree](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/min_degree-0.88.4.svg?)
119    ///
120    /// ```
121    /// use graaf::{
122    ///     AddArc,
123    ///     AdjacencyList,
124    ///     Degree,
125    ///     Empty,
126    /// };
127    ///
128    /// let mut digraph = AdjacencyList::empty(4);
129    ///
130    /// digraph.add_arc(0, 1);
131    /// digraph.add_arc(0, 2);
132    /// digraph.add_arc(0, 3);
133    /// digraph.add_arc(1, 0);
134    /// digraph.add_arc(1, 2);
135    /// digraph.add_arc(2, 0);
136    /// digraph.add_arc(3, 0);
137    ///
138    /// assert_eq!(digraph.min_degree(), 2);
139    /// ```
140    #[must_use]
141    fn min_degree(&self) -> usize
142    where
143        Self: Vertices,
144    {
145        self.vertices().map(|u| self.degree(u)).min().unwrap_or(0)
146    }
147}
148
149impl<D> Degree for D
150where
151    D: Indegree + Outdegree,
152{
153    fn degree(&self, u: usize) -> usize {
154        self.indegree(u) + self.outdegree(u)
155    }
156}
157
158/// `Degree` tests
159#[macro_export]
160macro_rules! test_degree {
161    ($fixture:path) => {
162        use $fixture::{
163            bang_jensen_34,
164            bang_jensen_94,
165            bang_jensen_196,
166            kattis_builddeps,
167            kattis_cantinaofbabel_1,
168            kattis_cantinaofbabel_2,
169            kattis_escapewallmaria_1,
170            kattis_escapewallmaria_2,
171            kattis_escapewallmaria_3,
172        };
173
174        #[test]
175        fn degree_bang_jensen_196() {
176            let digraph = bang_jensen_196();
177
178            assert!(digraph.degree(0) == 4);
179            assert!(digraph.degree(1) == 4);
180            assert!(digraph.degree(2) == 4);
181            assert!(digraph.degree(3) == 3);
182            assert!(digraph.degree(4) == 3);
183            assert!(digraph.degree(5) == 2);
184            assert!(digraph.degree(6) == 2);
185            assert!(digraph.degree(7) == 4);
186        }
187
188        #[test]
189        fn degree_bang_jensen_34() {
190            let digraph = bang_jensen_34();
191
192            assert!(digraph.degree(0) == 2);
193            assert!(digraph.degree(1) == 2);
194            assert!(digraph.degree(2) == 3);
195            assert!(digraph.degree(3) == 1);
196            assert!(digraph.degree(4) == 2);
197            assert!(digraph.degree(5) == 2);
198        }
199
200        #[test]
201        fn degree_bang_jensen_94() {
202            let digraph = bang_jensen_94();
203
204            assert!(digraph.degree(0) == 2);
205            assert!(digraph.degree(1) == 3);
206            assert!(digraph.degree(2) == 5);
207            assert!(digraph.degree(3) == 3);
208            assert!(digraph.degree(4) == 2);
209            assert!(digraph.degree(5) == 2);
210            assert!(digraph.degree(6) == 1);
211        }
212
213        #[test]
214        fn degree_kattis_builddeps() {
215            let digraph = kattis_builddeps();
216
217            assert!(digraph.degree(0) == 2);
218            assert!(digraph.degree(1) == 3);
219            assert!(digraph.degree(2) == 3);
220            assert!(digraph.degree(3) == 3);
221            assert!(digraph.degree(4) == 3);
222            assert!(digraph.degree(5) == 2);
223        }
224
225        #[test]
226        fn degree_kattis_cantinaofbabel_1() {
227            let digraph = kattis_cantinaofbabel_1();
228
229            assert!(digraph.degree(0) == 2);
230            assert!(digraph.degree(1) == 5);
231            assert!(digraph.degree(2) == 3);
232            assert!(digraph.degree(3) == 8);
233            assert!(digraph.degree(4) == 3);
234            assert!(digraph.degree(5) == 3);
235            assert!(digraph.degree(6) == 4);
236            assert!(digraph.degree(7) == 4);
237            assert!(digraph.degree(8) == 2);
238            assert!(digraph.degree(9) == 3);
239            assert!(digraph.degree(10) == 4);
240            assert!(digraph.degree(11) == 3);
241        }
242
243        #[test]
244        fn degree_kattis_cantinaofbabel_2() {
245            let digraph = kattis_cantinaofbabel_2();
246
247            assert!(digraph.degree(0) == 3);
248            assert!(digraph.degree(1) == 3);
249            assert!(digraph.degree(2) == 4);
250            assert!(digraph.degree(3) == 3);
251            assert!(digraph.degree(4) == 2);
252            assert!(digraph.degree(5) == 4);
253            assert!(digraph.degree(6) == 2);
254            assert!(digraph.degree(7) == 4);
255            assert!(digraph.degree(8) == 4);
256            assert!(digraph.degree(9) == 3);
257            assert!(digraph.degree(10) == 3);
258            assert!(digraph.degree(11) == 3);
259        }
260
261        #[test]
262        fn degree_kattis_escapewallmaria_1() {
263            let digraph = kattis_escapewallmaria_1();
264
265            assert!(digraph.degree(0) == 0);
266            assert!(digraph.degree(1) == 0);
267            assert!(digraph.degree(2) == 0);
268            assert!(digraph.degree(3) == 0);
269            assert!(digraph.degree(4) == 0);
270            assert!(digraph.degree(5) == 4);
271            assert!(digraph.degree(6) == 2);
272            assert!(digraph.degree(7) == 0);
273            assert!(digraph.degree(8) == 0);
274            assert!(digraph.degree(9) == 4);
275            assert!(digraph.degree(10) == 0);
276            assert!(digraph.degree(11) == 0);
277            assert!(digraph.degree(12) == 1);
278            assert!(digraph.degree(13) == 3);
279        }
280
281        #[test]
282        fn degree_kattis_escapewallmaria_2() {
283            let digraph = kattis_escapewallmaria_2();
284
285            assert!(digraph.degree(0) == 0);
286            assert!(digraph.degree(1) == 0);
287            assert!(digraph.degree(2) == 0);
288            assert!(digraph.degree(3) == 0);
289            assert!(digraph.degree(4) == 0);
290            assert!(digraph.degree(5) == 4);
291            assert!(digraph.degree(6) == 2);
292            assert!(digraph.degree(7) == 0);
293            assert!(digraph.degree(8) == 0);
294            assert!(digraph.degree(9) == 3);
295            assert!(digraph.degree(10) == 0);
296            assert!(digraph.degree(11) == 0);
297            assert!(digraph.degree(12) == 2);
298            assert!(digraph.degree(13) == 3);
299        }
300
301        #[test]
302        fn degree_kattis_escapewallmaria_3() {
303            let digraph = kattis_escapewallmaria_3();
304
305            assert!(digraph.degree(0) == 0);
306            assert!(digraph.degree(1) == 4);
307            assert!(digraph.degree(2) == 4);
308            assert!(digraph.degree(3) == 0);
309            assert!(digraph.degree(4) == 0);
310            assert!(digraph.degree(5) == 6);
311            assert!(digraph.degree(6) == 4);
312            assert!(digraph.degree(7) == 0);
313            assert!(digraph.degree(8) == 0);
314            assert!(digraph.degree(9) == 4);
315            assert!(digraph.degree(10) == 0);
316            assert!(digraph.degree(11) == 0);
317            assert!(digraph.degree(12) == 2);
318            assert!(digraph.degree(13) == 4);
319        }
320
321        #[test]
322        fn max_degree_bang_jensen_196() {
323            assert_eq!(bang_jensen_196().max_degree(), 4);
324        }
325
326        #[test]
327        fn max_degree_bang_jensen_34() {
328            assert_eq!(bang_jensen_34().max_degree(), 3);
329        }
330
331        #[test]
332        fn max_degree_bang_jensen_94() {
333            assert_eq!(bang_jensen_94().max_degree(), 5);
334        }
335
336        #[test]
337        fn max_degree_kattis_builddeps() {
338            assert_eq!(kattis_builddeps().max_degree(), 3);
339        }
340
341        #[test]
342        fn max_degree_kattis_cantinaofbabel_1() {
343            assert_eq!(kattis_cantinaofbabel_1().max_degree(), 8);
344        }
345
346        #[test]
347        fn max_degree_kattis_cantinaofbabel_2() {
348            assert_eq!(kattis_cantinaofbabel_2().max_degree(), 4);
349        }
350
351        #[test]
352        fn max_degree_kattis_escapewallmaria_1() {
353            assert_eq!(kattis_escapewallmaria_1().max_degree(), 4);
354        }
355
356        #[test]
357        fn max_degree_kattis_escapewallmaria_2() {
358            assert_eq!(kattis_escapewallmaria_2().max_degree(), 4);
359        }
360
361        #[test]
362        fn max_degree_kattis_escapewallmaria_3() {
363            assert_eq!(kattis_escapewallmaria_3().max_degree(), 6);
364        }
365
366        #[test]
367        fn min_degree_bang_jensen_196() {
368            assert_eq!(bang_jensen_196().min_degree(), 2);
369        }
370
371        #[test]
372        fn min_degree_bang_jensen_34() {
373            assert_eq!(bang_jensen_34().min_degree(), 1);
374        }
375
376        #[test]
377        fn min_degree_bang_jensen_94() {
378            assert_eq!(bang_jensen_94().min_degree(), 1);
379        }
380
381        #[test]
382        fn min_degree_kattis_builddeps() {
383            assert_eq!(kattis_builddeps().min_degree(), 2);
384        }
385
386        #[test]
387        fn min_degree_kattis_cantinaofbabel_1() {
388            assert_eq!(kattis_cantinaofbabel_1().min_degree(), 2);
389        }
390
391        #[test]
392        fn min_degree_kattis_cantinaofbabel_2() {
393            assert_eq!(kattis_cantinaofbabel_2().min_degree(), 2);
394        }
395
396        #[test]
397        fn min_degree_kattis_escapewallmaria_1() {
398            assert_eq!(kattis_escapewallmaria_1().min_degree(), 0);
399        }
400
401        #[test]
402        fn min_degree_kattis_escapewallmaria_2() {
403            assert_eq!(kattis_escapewallmaria_2().min_degree(), 0);
404        }
405
406        #[test]
407        fn min_degree_kattis_escapewallmaria_3() {
408            assert_eq!(kattis_escapewallmaria_3().min_degree(), 0);
409        }
410    };
411}
graaf/op/degree.rs

graaf/op/
degree.rs
