graaf/op/
is_regular.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
//! Check whether a digraph is regular.
//!
//! A digraph is regular if all vertices have the same indegree and
//! outdegree.
//!
//! # Examples
//!
//! ```
//! use graaf::{
//!     AdjacencyList,
//!     Circuit,
//!     IsRegular,
//!     RemoveArc,
//! };
//!
//! let mut digraph = AdjacencyList::circuit(7);
//!
//! assert!(digraph.is_regular());
//!
//! digraph.remove_arc(6, 0);
//!
//! assert!(!digraph.is_regular());
//! ```

use crate::{
    Indegree,
    Outdegree,
    Vertices,
};

/// Check whether a digraph is regular.
///
/// # Implementing [`IsRegular`] for a custom type
///
/// Provide an implementation of [`is_regular`](IsRegular::is_regular) that
/// returns whether the digraph is regular OR implement [`Indegree`],
/// [`Vertices`], and [`Outdegree`].
///
/// ```
/// use {
///     graaf::{
///         Indegree,
///         IsRegular,
///         Outdegree,
///         Vertices,
///     },
///     std::collections::BTreeSet,
/// };
///
/// struct AdjacencyList {
///     arcs: Vec<BTreeSet<usize>>,
/// }
///
/// impl Indegree for AdjacencyList {
///     fn indegree(&self, v: usize) -> usize {
///         self.arcs.iter().filter(|set| set.contains(&v)).count()
///     }
/// }
///
/// impl Vertices for AdjacencyList {
///     fn vertices(&self) -> impl Iterator<Item = usize> {
///         0..self.arcs.len()
///     }
/// }
///
/// impl Outdegree for AdjacencyList {
///     fn outdegree(&self, u: usize) -> usize {
///         self.arcs[u].len()
///     }
/// }
///
/// let digraph = AdjacencyList {
///     arcs: vec![
///         BTreeSet::from([1, 2]),
///         BTreeSet::from([2, 0]),
///         BTreeSet::from([0, 1]),
///     ],
/// };
///
/// assert!(digraph.is_regular());
///
/// let digraph = AdjacencyList {
///     arcs: vec![
///         BTreeSet::from([1, 2]),
///         BTreeSet::from([0, 2]),
///         BTreeSet::from([0]),
///     ],
/// };
///
/// assert!(!digraph.is_regular());
/// ```
pub trait IsRegular {
    /// Check whether the digraph is regular.
    ///
    /// # Examples
    ///
    /// ```
    /// use graaf::{
    ///     AdjacencyList,
    ///     Circuit,
    ///     IsRegular,
    ///     RemoveArc,
    /// };
    ///
    /// let mut digraph = AdjacencyList::circuit(7);
    ///
    /// assert!(digraph.is_regular());
    ///
    /// digraph.remove_arc(6, 0);
    ///
    /// assert!(!digraph.is_regular());
    /// ```
    #[must_use]
    fn is_regular(&self) -> bool;
}

impl<D> IsRegular for D
where
    D: Indegree + Outdegree + Vertices,
{
    /// # Panics
    ///
    /// Panics if the digraph has no vertices.
    fn is_regular(&self) -> bool {
        let mut vertices = self.vertices();

        let order =
            vertices.next().expect("a digraph has at least one vertex");

        let indegree = self.indegree(order);
        let outdegree = self.outdegree(order);

        indegree == outdegree
            && vertices.all(|u| {
                self.indegree(u) == indegree && self.outdegree(u) == outdegree
            })
    }
}