graaf/op/
sinks.rs

1//! Iterate a digraph's sinks.
2//!
3//! A sink is a vertex without out-neighbors.
4//!
5//! # Examples
6//!
7//! ```
8//! use graaf::{
9//!     AddArc,
10//!     AdjacencyList,
11//!     Empty,
12//!     Sinks,
13//! };
14//!
15//! let mut digraph = AdjacencyList::empty(4);
16//!
17//! digraph.add_arc(0, 1);
18//! digraph.add_arc(0, 2);
19//! digraph.add_arc(1, 2);
20//!
21//! assert!(digraph.sinks().eq([2, 3]));
22//! ```
23
24use crate::{
25    Outdegree,
26    Vertices,
27};
28
29/// Digraph sinks
30pub trait Sinks {
31    /// Iterate a digraph's sinks.
32    ///
33    /// # Examples
34    ///
35    /// ```
36    /// use graaf::{
37    ///     AddArc,
38    ///     AdjacencyList,
39    ///     Empty,
40    ///     Sinks,
41    /// };
42    ///
43    /// let mut digraph = AdjacencyList::empty(4);
44    ///
45    /// digraph.add_arc(0, 1);
46    /// digraph.add_arc(0, 2);
47    /// digraph.add_arc(1, 2);
48    ///
49    /// assert!(digraph.sinks().eq([2, 3]));
50    /// ```
51    #[must_use]
52    fn sinks(&self) -> impl Iterator<Item = usize>;
53}
54
55impl<D> Sinks for D
56where
57    D: Outdegree + Vertices,
58{
59    fn sinks(&self) -> impl Iterator<Item = usize> {
60        self.vertices().filter(move |&u| self.is_sink(u))
61    }
62}
63
64/// `Sinks` tests
65#[macro_export]
66macro_rules! test_sinks {
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 sinks_bang_jensen_196() {
82            assert!(bang_jensen_196().sinks().eq([]));
83        }
84
85        #[test]
86        fn sinks_bang_jensen_34() {
87            assert!(bang_jensen_34().sinks().eq([3, 4]));
88        }
89
90        #[test]
91        fn sinks_bang_jensen_94() {
92            assert!(bang_jensen_94().sinks().eq([5, 6]));
93        }
94
95        #[test]
96        fn sinks_kattis_builddeps() {
97            assert!(kattis_builddeps().sinks().eq([1]));
98        }
99
100        #[test]
101        fn sinks_kattis_cantinaofbabel_1() {
102            assert!(kattis_cantinaofbabel_1().sinks().eq([]));
103        }
104
105        #[test]
106        fn sinks_kattis_cantinaofbabel_2() {
107            assert!(kattis_cantinaofbabel_2().sinks().eq([]));
108        }
109
110        #[test]
111        fn sinks_kattis_escapewallmaria_1() {
112            assert!(
113                kattis_escapewallmaria_1()
114                    .sinks()
115                    .eq([0, 1, 2, 3, 4, 7, 8, 10, 11, 12, 14, 15])
116            );
117        }
118
119        #[test]
120        fn sinks_kattis_escapewallmaria_2() {
121            assert!(
122                kattis_escapewallmaria_2()
123                    .sinks()
124                    .eq([0, 1, 2, 3, 4, 7, 8, 10, 11, 14, 15])
125            );
126        }
127
128        #[test]
129        fn sinks_kattis_escapewallmaria_3() {
130            assert!(
131                kattis_escapewallmaria_3()
132                    .sinks()
133                    .eq([0, 3, 4, 7, 8, 10, 11, 14, 15])
134            );
135        }
136    };
137}
graaf/op/sinks.rs

graaf/op/
sinks.rs
