graaf/op/
outdegree_sequence.rs

1//! Iterate a digraph's outdegree sequence.
2//!
3//! # Examples
4//!
5//! ```
6//! use graaf::{
7//!     AddArc,
8//!     AdjacencyList,
9//!     Empty,
10//!     OutdegreeSequence,
11//! };
12//!
13//! let mut digraph = AdjacencyList::empty(3);
14//!
15//! digraph.add_arc(0, 1);
16//! digraph.add_arc(0, 2);
17//! digraph.add_arc(1, 2);
18//! digraph.add_arc(2, 0);
19//!
20//! assert!(digraph.outdegree_sequence().eq([2, 1, 1]));
21//! ```
22
23use crate::{
24    Outdegree,
25    Vertices,
26};
27
28/// Digraph outdegree sequence
29pub trait OutdegreeSequence {
30    /// Iterate the digraph's outdegree sequence.
31    ///
32    /// # Examples
33    ///
34    /// ```
35    /// use graaf::{
36    ///     AddArc,
37    ///     AdjacencyList,
38    ///     Empty,
39    ///     OutdegreeSequence,
40    /// };
41    ///
42    /// let mut digraph = AdjacencyList::empty(3);
43    ///
44    /// digraph.add_arc(0, 1);
45    /// digraph.add_arc(0, 2);
46    /// digraph.add_arc(1, 2);
47    /// digraph.add_arc(2, 0);
48    ///
49    /// assert!(digraph.outdegree_sequence().eq([2, 1, 1]));
50    /// ```
51    #[must_use]
52    fn outdegree_sequence(&self) -> impl Iterator<Item = usize>;
53}
54
55impl<D> OutdegreeSequence for D
56where
57    D: Outdegree + Vertices,
58{
59    fn outdegree_sequence(&self) -> impl Iterator<Item = usize> {
60        self.vertices().map(move |v| self.outdegree(v))
61    }
62}
63
64/// `OutdegreeSequence` tests
65#[macro_export]
66macro_rules! test_outdegree_sequence {
67    ($fixture:path) => {
68        use $fixture::{
69            bang_jensen_34,
70            bang_jensen_94,
71            bang_jensen_196,
72            kattis_builddeps,
73            kattis_cantinaofbabel_1,
74            kattis_cantinaofbabel_2,
75            kattis_escapewallmaria_1,
76            kattis_escapewallmaria_2,
77            kattis_escapewallmaria_3,
78        };
79
80        #[test]
81        fn outdegree_sequence_bang_jensen_196() {
82            assert!(
83                bang_jensen_196()
84                    .outdegree_sequence()
85                    .eq([3, 3, 1, 2, 1, 1, 1, 1])
86            );
87        }
88
89        #[test]
90        fn outdegree_sequence_bang_jensen_34() {
91            assert!(
92                bang_jensen_34().outdegree_sequence().eq([1, 1, 3, 0, 0, 1])
93            );
94        }
95
96        #[test]
97        fn outdegree_sequence_bang_jensen_94() {
98            assert!(
99                bang_jensen_94()
100                    .outdegree_sequence()
101                    .eq([2, 1, 4, 1, 1, 0, 0])
102            );
103        }
104
105        #[test]
106        fn outdegree_sequence_kattis_builddeps() {
107            assert!(
108                kattis_builddeps()
109                    .outdegree_sequence()
110                    .eq([2, 0, 3, 1, 1, 1])
111            );
112        }
113
114        #[test]
115        fn outdegree_sequence_kattis_cantinaofbabel_1() {
116            assert!(
117                kattis_cantinaofbabel_1()
118                    .outdegree_sequence()
119                    .eq([1, 3, 1, 6, 1, 1, 2, 1, 2, 2, 1, 1])
120            );
121        }
122
123        #[test]
124        fn outdegree_sequence_kattis_cantinaofbabel_2() {
125            assert!(
126                kattis_cantinaofbabel_2()
127                    .outdegree_sequence()
128                    .eq([1, 2, 3, 1, 1, 2, 1, 1, 3, 1, 2, 1])
129            );
130        }
131
132        #[test]
133        fn outdegree_sequence_kattis_escapewallmaria_1() {
134            assert!(
135                kattis_escapewallmaria_1()
136                    .outdegree_sequence()
137                    .eq([0, 0, 0, 0, 0, 2, 1, 0, 0, 2, 0, 0, 0, 2, 0, 0])
138            );
139        }
140
141        #[test]
142        fn outdegree_sequence_kattis_escapewallmaria_2() {
143            assert!(
144                kattis_escapewallmaria_2()
145                    .outdegree_sequence()
146                    .eq([0, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 1, 2, 0, 0])
147            );
148        }
149
150        #[test]
151        fn outdegree_sequence_kattis_escapewallmaria_3() {
152            assert!(
153                kattis_escapewallmaria_3()
154                    .outdegree_sequence()
155                    .eq([0, 2, 2, 0, 0, 3, 2, 0, 0, 2, 0, 0, 1, 2, 0, 0])
156            );
157        }
158    };
159}
graaf/op/outdegree_sequence.rs

graaf/op/
outdegree_sequence.rs
