graaf/op/
outdegree.rs

1//! Return a vertex's outdegree.
2//!
3//! The outdegree is the digraph's size incident out of a vertex.
4//!
5//! # Examples
6//!
7//! ```
8//! use graaf::{
9//!     AddArc,
10//!     AdjacencyList,
11//!     Empty,
12//!     Outdegree,
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, 0);
20//!
21//! assert_eq!(digraph.outdegree(0), 2);
22//! assert_eq!(digraph.outdegree(1), 1);
23//! assert_eq!(digraph.outdegree(2), 0);
24//! ```
25#![doc(alias = "out_degree")]
26
27use crate::Vertices;
28
29/// Vertex outdegree
30pub trait Outdegree {
31    /// Return the vertex's outdegree.
32    ///
33    /// # Arguments
34    ///
35    /// * `u`: The vertex.
36    ///
37    /// # Examples
38    ///
39    /// ```
40    /// use graaf::{
41    ///     AddArc,
42    ///     AdjacencyList,
43    ///     Empty,
44    ///     Outdegree,
45    /// };
46    ///
47    /// let mut digraph = AdjacencyList::empty(3);
48    ///
49    /// digraph.add_arc(0, 1);
50    /// digraph.add_arc(0, 2);
51    /// digraph.add_arc(1, 0);
52    /// digraph.add_arc(2, 1);
53    ///
54    /// assert_eq!(digraph.outdegree(0), 2);
55    /// assert_eq!(digraph.outdegree(1), 1);
56    /// assert_eq!(digraph.outdegree(2), 1);
57    /// ```
58    #[doc(alias = "out_degree")]
59    #[must_use]
60    fn outdegree(&self, u: usize) -> usize;
61
62    /// Check whether a vertex is a digraph's sink.
63    ///
64    /// A sink is a vertex without out-neighbors.
65    ///
66    /// # Arguments
67    ///
68    /// * `u`: The vertex.
69    ///
70    /// # Examples
71    ///
72    /// ```
73    /// use graaf::{
74    ///     AddArc,
75    ///     AdjacencyList,
76    ///     Empty,
77    ///     Outdegree,
78    /// };
79    ///
80    /// let mut digraph = AdjacencyList::empty(3);
81    ///
82    /// digraph.add_arc(0, 1);
83    /// digraph.add_arc(0, 2);
84    /// digraph.add_arc(1, 0);
85    ///
86    /// assert!(!digraph.is_sink(0));
87    /// assert!(!digraph.is_sink(1));
88    /// assert!(digraph.is_sink(2));
89    /// ```
90    #[must_use]
91    fn is_sink(&self, u: usize) -> bool {
92        self.outdegree(u) == 0
93    }
94
95    /// Return the digraph's maximum outdegree.
96    ///
97    /// # Examples
98    ///
99    /// The maximum outdegree of this digraph is `3`. The vertex with the
100    /// maximum outdegree is red.
101    ///
102    /// ![A digraph and its maximum outdegree](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/max_outdegree-0.88.5.svg?)
103    ///
104    /// ```
105    /// use graaf::{
106    ///     AddArc,
107    ///     AdjacencyList,
108    ///     Empty,
109    ///     Outdegree,
110    /// };
111    ///
112    /// let mut digraph = AdjacencyList::empty(4);
113    ///
114    /// digraph.add_arc(0, 1);
115    /// digraph.add_arc(0, 2);
116    /// digraph.add_arc(0, 3);
117    /// digraph.add_arc(1, 0);
118    /// digraph.add_arc(1, 2);
119    /// digraph.add_arc(2, 0);
120    /// digraph.add_arc(3, 0);
121    ///
122    /// assert_eq!(digraph.max_outdegree(), 3);
123    /// ```
124    #[must_use]
125    fn max_outdegree(&self) -> usize
126    where
127        Self: Vertices,
128    {
129        self.vertices()
130            .map(|u| self.outdegree(u))
131            .max()
132            .unwrap_or(0)
133    }
134
135    /// Return the digraph's minimum outdegree.
136    ///
137    /// # Examples
138    ///
139    /// The minimum outdegree of this digraph is `1`. The vertices with the
140    /// minimum outdegree are red.
141    ///
142    /// ![A digraph and its minimum outdegree](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/min_outdegree-0.88.5.svg?)
143    ///
144    /// ```
145    /// use graaf::{
146    ///     AddArc,
147    ///     AdjacencyList,
148    ///     Empty,
149    ///     Outdegree,
150    /// };
151    ///
152    /// let mut digraph = AdjacencyList::empty(4);
153    ///
154    /// digraph.add_arc(0, 1);
155    /// digraph.add_arc(0, 2);
156    /// digraph.add_arc(0, 3);
157    /// digraph.add_arc(1, 0);
158    /// digraph.add_arc(1, 2);
159    /// digraph.add_arc(2, 0);
160    /// digraph.add_arc(3, 0);
161    ///
162    /// assert_eq!(digraph.min_outdegree(), 1);
163    /// ```
164    #[must_use]
165    fn min_outdegree(&self) -> usize
166    where
167        Self: Vertices,
168    {
169        self.vertices()
170            .map(|u| self.outdegree(u))
171            .min()
172            .unwrap_or(0)
173    }
174}
175
176/// `Outdegree` tests
177#[macro_export]
178macro_rules! test_outdegree {
179    ($type:ty, $fixture:path) => {
180        use $fixture::{
181            bang_jensen_34,
182            bang_jensen_94,
183            bang_jensen_196,
184            kattis_builddeps,
185            kattis_cantinaofbabel_1,
186            kattis_cantinaofbabel_2,
187            kattis_escapewallmaria_1,
188            kattis_escapewallmaria_2,
189            kattis_escapewallmaria_3,
190        };
191
192        #[test]
193        #[should_panic(expected = "u = 1 isn't in the digraph")]
194        fn is_sink_out_of_bounds() {
195            let _ = <$type>::trivial().is_sink(1);
196        }
197
198        #[test]
199        fn max_outdegree_bang_jensen_196() {
200            assert_eq!(bang_jensen_196().max_outdegree(), 3);
201        }
202
203        #[test]
204        fn max_outdegree_bang_jensen_34() {
205            assert_eq!(bang_jensen_34().max_outdegree(), 3);
206        }
207
208        #[test]
209        fn max_outdegree_bang_jensen_94() {
210            assert_eq!(bang_jensen_94().max_outdegree(), 4);
211        }
212
213        #[test]
214        fn max_outdegree_kattis_builddeps() {
215            assert_eq!(kattis_builddeps().max_outdegree(), 3);
216        }
217
218        #[test]
219        fn max_outdegree_kattis_cantinaofbabel_1() {
220            assert_eq!(kattis_cantinaofbabel_1().max_outdegree(), 6);
221        }
222
223        #[test]
224        fn max_outdegree_kattis_cantinaofbabel_2() {
225            assert_eq!(kattis_cantinaofbabel_2().max_outdegree(), 3);
226        }
227
228        #[test]
229        fn max_outdegree_kattis_escapewallmaria_1() {
230            assert_eq!(kattis_escapewallmaria_1().max_outdegree(), 2);
231        }
232
233        #[test]
234        fn max_outdegree_kattis_escapewallmaria_2() {
235            assert_eq!(kattis_escapewallmaria_2().max_outdegree(), 2);
236        }
237
238        #[test]
239        fn max_outdegree_kattis_escapewallmaria_3() {
240            assert_eq!(kattis_escapewallmaria_3().max_outdegree(), 3);
241        }
242
243        #[test]
244        fn min_outdegree_bang_jensen_196() {
245            assert_eq!(bang_jensen_196().min_outdegree(), 1);
246        }
247
248        #[test]
249        fn min_outdegree_bang_jensen_34() {
250            assert_eq!(bang_jensen_34().min_outdegree(), 0);
251        }
252
253        #[test]
254        fn min_outdegree_bang_jensen_94() {
255            assert_eq!(bang_jensen_94().min_outdegree(), 0);
256        }
257
258        #[test]
259        fn min_outdegree_kattis_builddeps() {
260            assert_eq!(kattis_builddeps().min_outdegree(), 0);
261        }
262
263        #[test]
264        fn min_outdegree_kattis_cantinaofbabel_1() {
265            assert_eq!(kattis_cantinaofbabel_1().min_outdegree(), 1);
266        }
267
268        #[test]
269        fn min_outdegree_kattis_cantinaofbabel_2() {
270            assert_eq!(kattis_cantinaofbabel_2().min_outdegree(), 1);
271        }
272
273        #[test]
274        fn min_outdegree_kattis_escapewallmaria_1() {
275            assert_eq!(kattis_escapewallmaria_1().min_outdegree(), 0);
276        }
277
278        #[test]
279        fn min_outdegree_kattis_escapewallmaria_2() {
280            assert_eq!(kattis_escapewallmaria_2().min_outdegree(), 0);
281        }
282
283        #[test]
284        fn min_outdegree_kattis_escapewallmaria_3() {
285            assert_eq!(kattis_escapewallmaria_3().min_outdegree(), 0);
286        }
287
288        #[test]
289        fn outdegree_bang_jensen_196() {
290            let digraph = bang_jensen_196();
291
292            assert_eq!(digraph.outdegree(0), 3);
293            assert_eq!(digraph.outdegree(1), 3);
294            assert_eq!(digraph.outdegree(2), 1);
295            assert_eq!(digraph.outdegree(3), 2);
296            assert_eq!(digraph.outdegree(4), 1);
297            assert_eq!(digraph.outdegree(5), 1);
298            assert_eq!(digraph.outdegree(6), 1);
299            assert_eq!(digraph.outdegree(7), 1);
300        }
301
302        #[test]
303        fn outdegree_bang_jensen_34() {
304            let digraph = bang_jensen_34();
305
306            assert_eq!(digraph.outdegree(0), 1);
307            assert_eq!(digraph.outdegree(1), 1);
308            assert_eq!(digraph.outdegree(2), 3);
309            assert_eq!(digraph.outdegree(3), 0);
310            assert_eq!(digraph.outdegree(4), 0);
311            assert_eq!(digraph.outdegree(5), 1);
312        }
313
314        #[test]
315        fn outdegree_bang_jensen_94() {
316            let digraph = bang_jensen_94();
317
318            assert_eq!(digraph.outdegree(0), 2);
319            assert_eq!(digraph.outdegree(1), 1);
320            assert_eq!(digraph.outdegree(2), 4);
321            assert_eq!(digraph.outdegree(3), 1);
322            assert_eq!(digraph.outdegree(4), 1);
323            assert_eq!(digraph.outdegree(5), 0);
324            assert_eq!(digraph.outdegree(6), 0);
325        }
326
327        #[test]
328        fn outdegree_kattis_builddeps() {
329            let digraph = kattis_builddeps();
330
331            assert_eq!(digraph.outdegree(0), 2);
332            assert_eq!(digraph.outdegree(1), 0);
333            assert_eq!(digraph.outdegree(2), 3);
334            assert_eq!(digraph.outdegree(3), 1);
335            assert_eq!(digraph.outdegree(4), 1);
336            assert_eq!(digraph.outdegree(5), 1);
337        }
338
339        #[test]
340        fn outdegree_kattis_cantinaofbabel_1() {
341            let digraph = kattis_cantinaofbabel_1();
342
343            assert_eq!(digraph.outdegree(0), 1);
344            assert_eq!(digraph.outdegree(1), 3);
345            assert_eq!(digraph.outdegree(2), 1);
346            assert_eq!(digraph.outdegree(3), 6);
347            assert_eq!(digraph.outdegree(4), 1);
348            assert_eq!(digraph.outdegree(5), 1);
349            assert_eq!(digraph.outdegree(6), 2);
350            assert_eq!(digraph.outdegree(7), 1);
351            assert_eq!(digraph.outdegree(8), 2);
352            assert_eq!(digraph.outdegree(9), 2);
353            assert_eq!(digraph.outdegree(10), 1);
354            assert_eq!(digraph.outdegree(11), 1);
355        }
356
357        #[test]
358        fn outdegree_kattis_cantinaofbabel_2() {
359            let digraph = kattis_cantinaofbabel_2();
360
361            assert_eq!(digraph.outdegree(0), 1);
362            assert_eq!(digraph.outdegree(1), 2);
363            assert_eq!(digraph.outdegree(2), 3);
364            assert_eq!(digraph.outdegree(3), 1);
365            assert_eq!(digraph.outdegree(4), 1);
366            assert_eq!(digraph.outdegree(5), 2);
367            assert_eq!(digraph.outdegree(6), 1);
368            assert_eq!(digraph.outdegree(7), 1);
369            assert_eq!(digraph.outdegree(8), 3);
370            assert_eq!(digraph.outdegree(9), 1);
371            assert_eq!(digraph.outdegree(10), 2);
372            assert_eq!(digraph.outdegree(11), 1);
373        }
374
375        #[test]
376        fn outdegree_kattis_escapewallmaria_1() {
377            let digraph = kattis_escapewallmaria_1();
378
379            assert_eq!(digraph.outdegree(0), 0);
380            assert_eq!(digraph.outdegree(1), 0);
381            assert_eq!(digraph.outdegree(2), 0);
382            assert_eq!(digraph.outdegree(3), 0);
383            assert_eq!(digraph.outdegree(4), 0);
384            assert_eq!(digraph.outdegree(5), 2);
385            assert_eq!(digraph.outdegree(6), 1);
386            assert_eq!(digraph.outdegree(7), 0);
387            assert_eq!(digraph.outdegree(8), 0);
388            assert_eq!(digraph.outdegree(9), 2);
389            assert_eq!(digraph.outdegree(10), 0);
390            assert_eq!(digraph.outdegree(11), 0);
391            assert_eq!(digraph.outdegree(12), 0);
392            assert_eq!(digraph.outdegree(13), 2);
393            assert_eq!(digraph.outdegree(14), 0);
394            assert_eq!(digraph.outdegree(15), 0);
395        }
396
397        #[test]
398        fn outdegree_kattis_escapewallmaria_2() {
399            let digraph = kattis_escapewallmaria_2();
400
401            assert_eq!(digraph.outdegree(0), 0);
402            assert_eq!(digraph.outdegree(1), 0);
403            assert_eq!(digraph.outdegree(2), 0);
404            assert_eq!(digraph.outdegree(3), 0);
405            assert_eq!(digraph.outdegree(4), 0);
406            assert_eq!(digraph.outdegree(5), 2);
407            assert_eq!(digraph.outdegree(6), 1);
408            assert_eq!(digraph.outdegree(7), 0);
409            assert_eq!(digraph.outdegree(8), 0);
410            assert_eq!(digraph.outdegree(9), 1);
411            assert_eq!(digraph.outdegree(10), 0);
412            assert_eq!(digraph.outdegree(11), 0);
413            assert_eq!(digraph.outdegree(12), 1);
414            assert_eq!(digraph.outdegree(13), 2);
415            assert_eq!(digraph.outdegree(14), 0);
416            assert_eq!(digraph.outdegree(15), 0);
417        }
418
419        #[test]
420        fn outdegree_kattis_escapewallmaria_3() {
421            let digraph = kattis_escapewallmaria_3();
422
423            assert_eq!(digraph.outdegree(0), 0);
424            assert_eq!(digraph.outdegree(1), 2);
425            assert_eq!(digraph.outdegree(2), 2);
426            assert_eq!(digraph.outdegree(3), 0);
427            assert_eq!(digraph.outdegree(4), 0);
428            assert_eq!(digraph.outdegree(5), 3);
429            assert_eq!(digraph.outdegree(6), 2);
430            assert_eq!(digraph.outdegree(7), 0);
431            assert_eq!(digraph.outdegree(8), 0);
432            assert_eq!(digraph.outdegree(9), 2);
433            assert_eq!(digraph.outdegree(10), 0);
434            assert_eq!(digraph.outdegree(11), 0);
435            assert_eq!(digraph.outdegree(12), 1);
436            assert_eq!(digraph.outdegree(13), 2);
437            assert_eq!(digraph.outdegree(14), 0);
438            assert_eq!(digraph.outdegree(15), 0);
439        }
440
441        #[test]
442        #[should_panic(expected = "u = 1 isn't in the digraph")]
443        fn outdegree_out_of_bounds() {
444            let _ = <$type>::trivial().outdegree(1);
445        }
446    };
447}
448
449#[cfg(test)]
450mod tests {
451    use {
452        super::*,
453        std::collections::BTreeSet,
454    };
455
456    #[test]
457    fn is_sink() {
458        struct AdjacencyList {
459            arcs: Vec<BTreeSet<usize>>,
460        }
461
462        impl Outdegree for AdjacencyList {
463            fn outdegree(&self, u: usize) -> usize {
464                self.arcs.get(u).map_or(0, BTreeSet::len)
465            }
466        }
467
468        let digraph = AdjacencyList {
469            arcs: vec![
470                BTreeSet::from([1, 2]),
471                BTreeSet::new(),
472                BTreeSet::new(),
473                BTreeSet::from([0]),
474            ],
475        };
476
477        assert!(!digraph.is_sink(0));
478        assert!(digraph.is_sink(1));
479        assert!(digraph.is_sink(2));
480        assert!(!digraph.is_sink(3));
481    }
482}
graaf/op/outdegree.rs

graaf/op/
outdegree.rs
