graaf/op/
is_spanning_subdigraph.rs

1//! Check whether a digraph is another digraph's spanning subdigraph.
2//!
3//! A digraph `H` is a spanning subdigraph of a digraph `D` if the vertex set
4//! of `H` equals the vertex set of `D` and the arc set of `H` is a subset of
5//! the arc set of `D`.
6//!
7//! # Examples
8//!
9//! ```
10//! use graaf::{
11//!     AddArc,
12//!     AdjacencyList,
13//!     Circuit,
14//!     Empty,
15//!     IsSpanningSubdigraph,
16//! };
17//!
18//! let mut h = AdjacencyList::empty(3);
19//!
20//! h.add_arc(0, 1);
21//!
22//! let d = AdjacencyList::circuit(3);
23//!
24//! assert!(h.is_spanning_subdigraph(&d));
25//! ```
26//!
27//! Every digraph is its own spanning subdigraph.
28//!
29//! ```
30//! use graaf::{
31//!     AdjacencyList,
32//!     IsSpanningSubdigraph,
33//!     RandomTournament,
34//! };
35//!
36//! let tournament = AdjacencyList::random_tournament(4, 0);
37//!
38//! assert!(tournament.is_spanning_subdigraph(&tournament));
39//! ```
40//!
41//! A digraph `H` with arcs not in the arc set of a digraph `D` isn't a
42//! spanning subdigraph of `D`.
43//!
44//! ```
45//! use graaf::{
46//!     AddArc,
47//!     AdjacencyList,
48//!     Empty,
49//!     IsSpanningSubdigraph,
50//! };
51//!
52//! let mut h = AdjacencyList::empty(2);
53//!
54//! h.add_arc(0, 1);
55//! h.add_arc(1, 0);
56//!
57//! let mut d = AdjacencyList::empty(2);
58//!
59//! d.add_arc(0, 1);
60//!
61//! assert!(!h.is_spanning_subdigraph(&d));
62//! ```
63//!
64//! A digraph `H` with vertices not in the vertex set of a digraph `D` isn't a
65//! spanning subdigraph of `D`.
66//!
67//! ```
68//! use graaf::{
69//!     AddArc,
70//!     AdjacencyList,
71//!     Empty,
72//!     IsSpanningSubdigraph,
73//! };
74//!
75//! let mut h = AdjacencyList::empty(2);
76//!
77//! h.add_arc(0, 1);
78//!
79//! let d = AdjacencyList::empty(2);
80//!
81//! assert!(!h.is_spanning_subdigraph(&d));
82//! ```
83//!
84//! A digraph `H` with arcs whose end-vertices aren't in the vertex set of `H`
85//! isn't a spanning subdigraph of a digraph `D`.
86//!
87//! ```
88//! use graaf::{
89//!     AddArc,
90//!     AdjacencyList,
91//!     Empty,
92//!     IsSpanningSubdigraph,
93//! };
94//!
95//! // The arc (0, 2) has end-vertex `2` which isn't in the vertex set of `H`.
96//!
97//! let mut h = AdjacencyList::empty(3);
98//!
99//! h.add_arc(0, 1);
100//! h.add_arc(0, 2);
101//! h.add_arc(1, 0);
102//!
103//! let mut d = AdjacencyList::empty(3);
104//!
105//! d.add_arc(0, 1);
106//! d.add_arc(1, 0);
107//!
108//! assert!(!h.is_spanning_subdigraph(&d));
109//! ```
110//!
111//! A digraph `H` isn't a spanning subdigraph of a digraph `D` if the vertex
112//! set of `H` isn't equal to the vertex set of `D`.
113//!
114//! ```
115//! use graaf::{
116//!     AddArc,
117//!     AdjacencyList,
118//!     Empty,
119//!     IsSpanningSubdigraph,
120//! };
121//!
122//! let h = AdjacencyList::empty(2);
123//! let d = AdjacencyList::empty(3);
124//!
125//! assert!(!h.is_spanning_subdigraph(&d));
126//! ```
127
128use crate::{
129    Arcs,
130    HasArc,
131    Vertices,
132};
133
134/// Check whether a digraph is another digraph's spanning subdigraph.
135pub trait IsSpanningSubdigraph {
136    /// Check whether the digraph is another digraph's spanning subdigraph.
137    ///
138    /// # Arguments
139    ///
140    /// * `d`: The digraph to compare against.
141    ///
142    /// # Examples
143    ///
144    /// ```
145    /// use graaf::{
146    ///     AddArc,
147    ///     AdjacencyList,
148    ///     Circuit,
149    ///     Empty,
150    ///     IsSpanningSubdigraph,
151    /// };
152    ///
153    /// let mut h = AdjacencyList::empty(3);
154    ///
155    /// h.add_arc(0, 1);
156    ///
157    /// let d = AdjacencyList::circuit(3);
158    ///
159    /// assert!(h.is_spanning_subdigraph(&d));
160    /// ```
161    ///
162    /// Every digraph is a spanning subdigraph of itself.
163    ///
164    /// ```
165    /// use graaf::{
166    ///     AdjacencyList,
167    ///     IsSpanningSubdigraph,
168    ///     RandomTournament,
169    /// };
170    ///
171    /// let tournament = AdjacencyList::random_tournament(4, 0);
172    ///
173    /// assert!(tournament.is_spanning_subdigraph(&tournament));
174    /// ```
175    ///
176    /// A digraph `H` with arcs not in the arc set of a digraph `D` isn't a
177    /// spanning subdigraph of `D`.
178    ///
179    /// ```
180    /// use graaf::{
181    ///     AddArc,
182    ///     AdjacencyList,
183    ///     Empty,
184    ///     IsSpanningSubdigraph,
185    /// };
186    ///
187    /// let mut h = AdjacencyList::empty(2);
188    ///
189    /// h.add_arc(0, 1);
190    /// h.add_arc(1, 0);
191    ///
192    /// let mut d = AdjacencyList::empty(2);
193    ///
194    /// d.add_arc(0, 1);
195    ///
196    /// assert!(!h.is_spanning_subdigraph(&d));
197    /// ```
198    ///
199    /// A digraph `H` with vertices not in the vertex set of a digraph `D` is
200    /// not a spanning subdigraph of `D`.
201    ///
202    /// ```
203    /// use graaf::{
204    ///     AddArc,
205    ///     AdjacencyList,
206    ///     Empty,
207    ///     IsSpanningSubdigraph,
208    /// };
209    ///
210    /// let mut h = AdjacencyList::empty(2);
211    ///
212    /// h.add_arc(0, 1);
213    ///
214    /// let d = AdjacencyList::empty(2);
215    ///
216    /// assert!(!h.is_spanning_subdigraph(&d));
217    /// ```
218    ///
219    /// A digraph `H` with arcs whose end-vertices aren't in the vertex set of
220    /// `H` isn't a spanning subdigraph of a digraph `D`.
221    ///
222    /// ```
223    /// use graaf::{
224    ///     AddArc,
225    ///     AdjacencyList,
226    ///     Empty,
227    ///     IsSpanningSubdigraph,
228    /// };
229    ///
230    /// // The arc (0, 2) has end-vertex `2` which isn't in the vertex set
231    /// // of `H`.
232    ///
233    /// let mut h = AdjacencyList::empty(3);
234    ///
235    /// h.add_arc(0, 1);
236    /// h.add_arc(0, 2);
237    /// h.add_arc(1, 0);
238    ///
239    /// let mut d = AdjacencyList::empty(3);
240    ///
241    /// d.add_arc(0, 1);
242    /// d.add_arc(1, 0);
243    ///
244    /// assert!(!h.is_spanning_subdigraph(&d));
245    /// ```
246    ///
247    /// A digraph `H` isn't a spanning subdigraph of a digraph `D` if the
248    /// vertex set of `H` isn't equal to the vertex set of `D`.
249    ///
250    /// ```
251    /// use graaf::{
252    ///     AddArc,
253    ///     AdjacencyList,
254    ///     Empty,
255    ///     IsSpanningSubdigraph,
256    /// };
257    ///
258    /// let h = AdjacencyList::empty(2);
259    /// let d = AdjacencyList::empty(3);
260    ///
261    /// assert!(!h.is_spanning_subdigraph(&d));
262    /// ```
263    #[must_use]
264    fn is_spanning_subdigraph(&self, d: &Self) -> bool;
265}
266
267impl<D> IsSpanningSubdigraph for D
268where
269    D: Arcs + HasArc + Vertices,
270{
271    fn is_spanning_subdigraph(&self, d: &Self) -> bool {
272        self.vertices().eq(d.vertices())
273            && self.arcs().all(|(u, v)| d.has_arc(u, v))
274    }
275}
graaf/op/is_spanning_subdigraph.rs

graaf/op/
is_spanning_subdigraph.rs
