graaf/op/
sources.rs

1//! Iterate a digraph's sources.
2//!
3//! A source is a vertex without in-neighbors.
4//!
5//! # Examples
6//!
7//! ```
8//! use graaf::{
9//!     AddArc,
10//!     AdjacencyList,
11//!     Empty,
12//!     Sources,
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.sources().eq([0, 3]));
22//! ```
23
24/// Digraph sources
25pub trait Sources {
26    /// Iterate the sources in the digraph.
27    ///
28    /// # Examples
29    ///
30    /// ```
31    /// use graaf::{
32    ///     AddArc,
33    ///     AdjacencyList,
34    ///     Empty,
35    ///     Sources,
36    /// };
37    ///
38    /// let mut digraph = AdjacencyList::empty(4);
39    ///
40    /// digraph.add_arc(0, 1);
41    /// digraph.add_arc(0, 2);
42    /// digraph.add_arc(1, 2);
43    ///
44    /// assert!(digraph.sources().eq([0, 3]));
45    /// ```
46    #[must_use]
47    fn sources(&self) -> impl Iterator<Item = usize>;
48}
49
50/// `Sources` tests
51#[macro_export]
52macro_rules! test_sources {
53    ($fixture:path) => {
54        use $fixture::{
55            bang_jensen_34,
56            bang_jensen_94,
57            bang_jensen_196,
58            kattis_builddeps,
59            kattis_cantinaofbabel_1,
60            kattis_cantinaofbabel_2,
61            kattis_escapewallmaria_1,
62            kattis_escapewallmaria_2,
63            kattis_escapewallmaria_3,
64        };
65
66        #[test]
67        fn sources_bang_jensen_196() {
68            assert!(bang_jensen_196().sources().eq([]));
69        }
70
71        #[test]
72        fn sources_bang_jensen_34() {
73            assert!(bang_jensen_34().sources().eq([2]));
74        }
75
76        #[test]
77        fn sources_bang_jensen_94() {
78            assert!(bang_jensen_94().sources().eq([0]));
79        }
80
81        #[test]
82        fn sources_kattis_builddeps() {
83            assert!(kattis_builddeps().sources().eq([0, 2]));
84        }
85
86        #[test]
87        fn sources_kattis_cantinaofbabel_1() {
88            assert!(kattis_cantinaofbabel_1().sources().eq([8]));
89        }
90
91        #[test]
92        fn sources_kattis_cantinaofbabel_2() {
93            assert!(kattis_cantinaofbabel_2().sources().eq([]));
94        }
95
96        #[test]
97        fn sources_kattis_escapewallmaria_1() {
98            assert!(
99                kattis_escapewallmaria_1()
100                    .sources()
101                    .eq([0, 1, 2, 3, 4, 7, 8, 10, 11, 14, 15])
102            );
103        }
104
105        #[test]
106        fn sources_kattis_escapewallmaria_2() {
107            assert!(
108                kattis_escapewallmaria_2()
109                    .sources()
110                    .eq([0, 1, 2, 3, 4, 7, 8, 10, 11, 14, 15])
111            );
112        }
113
114        #[test]
115        fn sources_kattis_escapewallmaria_3() {
116            assert!(
117                kattis_escapewallmaria_3()
118                    .sources()
119                    .eq([0, 3, 4, 7, 8, 10, 11, 14, 15])
120            );
121        }
122    };
123}
graaf/op/sources.rs

graaf/op/
sources.rs
