graaf/gen/
empty.rs

1//! Generate empty digraphs.
2//!
3//! An empty digraph has no arcs.
4//!
5//! # Examples
6//!
7//! ## Order 2
8//!
9//! Generate an empty digraph of order `2`.
10//!
11//! ![An empty digraph of order `2`](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/empty_2.svg)
12//!
13//! ```
14//! use graaf::{
15//!     AdjacencyList,
16//!     Arcs,
17//!     Empty,
18//! };
19//!
20//! assert!(AdjacencyList::empty(2).arcs().eq([]));
21//! ```
22//!
23//! ## Order 3
24//!
25//! Generate an empty digraph of order `3`.
26//!
27//! ![An empty digraph of order `3`](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/empty_3.svg)
28//!
29//! ```
30//! use graaf::{
31//!     AdjacencyList,
32//!     Arcs,
33//!     Empty,
34//! };
35//!
36//! assert!(AdjacencyList::empty(3).arcs().eq([]));
37//! ```
38//!
39//! ## Order 4
40//!
41//! Generate an empty digraph of order `4`.
42//!
43//! ![An empty digraph of order `4`](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/empty_4.svg)
44//!
45//! ```
46//! use graaf::{
47//!     AdjacencyList,
48//!     Arcs,
49//!     Empty,
50//! };
51//!
52//! assert!(AdjacencyList::empty(4).arcs().eq([]));
53//! ```
54#![doc(alias = "edgeless")]
55
56/// Empty digraphs
57#[doc(alias = "Edgeless")]
58pub trait Empty {
59    /// Generate an empty digraph.
60    ///
61    /// # Arguments
62    ///
63    /// * `order` - The number of vertices in the digraph.
64    ///
65    /// # Examples
66    ///
67    /// ## Order 2
68    ///
69    /// Generate an empty digraph of order `2`.
70    ///
71    /// ![An empty digraph of order `2`](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/empty_2.svg)
72    ///
73    /// ```
74    /// use graaf::{
75    ///     AdjacencyList,
76    ///     Arcs,
77    ///     Empty,
78    /// };
79    ///
80    /// assert!(AdjacencyList::empty(2).arcs().eq([]));
81    /// ```
82    ///
83    /// ## Order 3
84    ///
85    /// Generate an empty digraph of order `3`.
86    ///
87    /// ![An empty digraph of order `3`](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/empty_3.svg)
88    ///
89    /// ```
90    /// use graaf::{
91    ///     AdjacencyList,
92    ///     Arcs,
93    ///     Empty,
94    /// };
95    ///
96    /// assert!(AdjacencyList::empty(3).arcs().eq([]));
97    /// ```
98    ///
99    /// ## Order 4
100    ///
101    /// Generate an empty digraph of order `4`.
102    ///
103    /// ![An empty digraph of order `4`](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/empty_4.svg)
104    ///
105    /// ```
106    /// use graaf::{
107    ///     AdjacencyList,
108    ///     Arcs,
109    ///     Empty,
110    /// };
111    ///
112    /// assert!(AdjacencyList::empty(4).arcs().eq([]));
113    /// ```
114    #[doc(alias = "edgeless")]
115    #[must_use]
116    fn empty(order: usize) -> Self;
117
118    /// Generate a trivial digraph.
119    ///
120    /// A trivial digraph has one vertex and no arcs.
121    ///
122    /// # Examples
123    ///
124    /// ```
125    /// use graaf::{
126    ///     AdjacencyList,
127    ///     Arcs,
128    ///     Empty,
129    /// };
130    ///
131    /// assert!(AdjacencyList::trivial().arcs().eq([]));
132    /// ```
133    #[doc(alias = "singleton")]
134    #[must_use]
135    fn trivial() -> Self
136    where
137        Self: Sized,
138    {
139        Self::empty(1)
140    }
141}
142
143/// `Empty` tests
144#[macro_export]
145macro_rules! test_empty {
146    ($type:ty) => {
147        #[test]
148        #[should_panic(expected = "a digraph has at least one vertex")]
149        fn empty_0() {
150            drop(<$type>::empty(0));
151        }
152
153        #[test]
154        fn empty_1() {
155            let digraph = <$type>::empty(1);
156
157            assert_eq!(digraph.order(), 1);
158            assert!(digraph.arcs().eq([]));
159        }
160
161        #[test]
162        fn empty_1_complement() {
163            let digraph = <$type>::empty(1).complement();
164
165            assert_eq!(digraph.order(), 1);
166            assert!(digraph.arcs().eq([]));
167        }
168
169        #[test]
170        fn empty_2() {
171            let digraph = <$type>::empty(2);
172
173            assert_eq!(digraph.order(), 2);
174            assert!(digraph.arcs().eq([]));
175        }
176
177        #[test]
178        fn empty_2_complement() {
179            let digraph = <$type>::empty(2).complement();
180
181            assert_eq!(digraph.order(), 2);
182            assert!(digraph.arcs().eq([(0, 1), (1, 0)]));
183        }
184
185        #[test]
186        fn empty_3() {
187            let digraph = <$type>::empty(3);
188
189            assert_eq!(digraph.order(), 3);
190            assert!(digraph.arcs().eq([]));
191        }
192
193        #[test]
194        fn empty_3_complement() {
195            let digraph = <$type>::empty(3).complement();
196
197            assert_eq!(digraph.order(), 3);
198
199            assert!(digraph.arcs().eq([
200                (0, 1),
201                (0, 2),
202                (1, 0),
203                (1, 2),
204                (2, 0),
205                (2, 1)
206            ]));
207        }
208
209        #[test]
210        fn empty_trivial() {
211            let digraph = <$type>::trivial();
212
213            assert_eq!(digraph.order(), 1);
214            assert!(digraph.arcs().eq([]));
215        }
216    };
217}
218
219/// `Empty` proptests with `Complement`
220#[macro_export]
221macro_rules! proptest_empty_complement {
222    ($type:ty) => {
223        use {
224            proptest::proptest,
225            $crate::Complement,
226        };
227
228        proptest! {
229            #[test]
230            fn empty_complement_size(order in 1..5_usize) {
231                assert_eq!(
232                    <$type>::empty(order).complement().size(),
233                    order * (order - 1)
234                );
235            }
236        }
237    };
238}
239
240/// `Empty` proptests with `Complement` and `Complete`
241#[macro_export]
242macro_rules! proptest_empty_complete {
243    ($type:ty) => {
244        use {
245            proptest::proptest,
246            $crate::{
247                Complement,
248                Complete,
249            },
250        };
251
252        proptest! {
253            #[test]
254            fn empty_complement_equals_complete(order in 1..5_usize) {
255                assert_eq!(
256                    <$type>::empty(order).complement(),
257                    <$type>::complete(order)
258                );
259            }
260        }
261    };
262}
263
264/// `Empty` proptests
265#[macro_export]
266macro_rules! proptest_empty {
267    ($type:ty) => {
268        use {
269            proptest::proptest,
270            $crate::{
271                Degree,
272                IsBalanced,
273                IsIsolated,
274                IsOriented,
275                IsPendant,
276                IsSpanningSubdigraph,
277                IsSubdigraph,
278                IsSuperdigraph,
279                IsSymmetric,
280                OutdegreeSequence,
281                Sinks,
282                Sources,
283            },
284        };
285
286        proptest! {
287            #[test]
288            fn empty_arcs(order in 1..5_usize) {
289                assert!(<$type>::empty(order).arcs().eq([]));
290            }
291
292            #[test]
293            fn empty_degree(order in 1..5_usize) {
294                let digraph = <$type>::empty(order);
295
296                assert!(digraph.vertices().all(|u| digraph.degree(u) == 0));
297            }
298
299            #[test]
300            fn empty_degree_sequence(order in 1..5_usize) {
301                assert!(<$type>::empty(order).degree_sequence().all(|d| d == 0));
302            }
303
304            #[test]
305            fn empty_degree_sum_equals_2size(order in 1..5_usize) {
306                let digraph = <$type>::empty(order);
307
308                assert_eq!(
309                    digraph
310                        .vertices()
311                        .fold(0, |acc, u| acc + digraph.degree(u)),
312                    2 * digraph.size()
313                );
314            }
315
316            #[test]
317            fn empty_even_number_odd_degrees(order in 1..5_usize) {
318                let digraph = <$type>::empty(order);
319
320                assert_eq!(
321                    digraph
322                        .vertices()
323                        .filter(|&u| digraph.degree(u) % 2 == 1)
324                        .count()
325                        % 2,
326                    0
327                );
328            }
329
330            #[test]
331            fn empty_has_arc(order in 1..5_usize) {
332                let digraph = <$type>::empty(order);
333
334                assert!(digraph.vertices().all(|u| {
335                    digraph.vertices().all(|v| !digraph.has_arc(u, v))
336                }));
337            }
338
339            #[test]
340            fn empty_has_edge(order in 1..5_usize) {
341                let digraph = <$type>::empty(order);
342
343                assert!(digraph.vertices().all(|u| {
344                    digraph.vertices().all(|v| !digraph.has_edge(u, v))
345                }));
346            }
347
348            #[test]
349            fn empty_indegree(order in 1..5_usize) {
350                let digraph = <$type>::empty(order);
351
352                assert!(digraph.vertices().all(|u| digraph.indegree(u) == 0));
353            }
354
355            #[test]
356            fn empty_indegree_sequence(order in 1..5_usize) {
357                assert!(<$type>::empty(order)
358                    .indegree_sequence()
359                    .all(|d| d == 0));
360            }
361
362            #[test]
363            fn empty_is_balanced(order in 1..5_usize) {
364                assert!(<$type>::empty(order).is_balanced());
365            }
366
367            #[test]
368            fn empty_is_complete(order in 1..5_usize) {
369                assert!((order == 1) == <$type>::empty(order).is_complete());
370            }
371
372            #[test]
373            fn empty_is_isolated(order in 1..5_usize) {
374                let digraph = <$type>::empty(order);
375
376                assert!(digraph.vertices().all(|u| digraph.is_isolated(u)));
377            }
378
379            #[test]
380            fn empty_is_oriented(order in 1..5_usize) {
381                assert!(<$type>::empty(order).is_oriented());
382            }
383
384            #[test]
385            fn empty_is_pendant(order in 1..5_usize) {
386                let digraph = <$type>::empty(order);
387
388                assert!(digraph.vertices().all(|u| !digraph.is_pendant(u)));
389            }
390
391            #[test]
392            fn empty_is_regular(order in 1..5_usize) {
393                assert!(<$type>::empty(order).is_regular());
394            }
395
396            #[test]
397            fn empty_is_semicomplete(order in 1..5_usize) {
398                assert!((order == 1) == <$type>::empty(order).is_semicomplete());
399            }
400
401            #[test]
402            fn empty_is_simple(order in 1..5_usize) {
403                assert!(<$type>::empty(order).is_simple());
404            }
405
406            #[test]
407            fn empty_is_sink(order in 1..5_usize) {
408                let digraph = <$type>::empty(order);
409
410                assert!(digraph.vertices().all(|u| digraph.is_sink(u)));
411            }
412
413            #[test]
414            fn empty_is_source(order in 1..5_usize) {
415                let digraph = <$type>::empty(order);
416
417                assert!(digraph.vertices().all(|u| digraph.is_source(u)));
418            }
419
420            #[test]
421            fn empty_is_spanning_subdigraph(order in 1..5_usize) {
422                let digraph = <$type>::empty(order);
423
424                assert!(digraph.is_spanning_subdigraph(&digraph));
425            }
426
427            #[test]
428            fn empty_is_subdigraph(order in 1..5_usize) {
429                let digraph = <$type>::empty(order);
430
431                assert!(digraph.is_subdigraph(&digraph));
432            }
433
434            #[test]
435            fn empty_is_superdigraph(order in 1..5_usize) {
436                let digraph = <$type>::empty(order);
437
438                assert!(digraph.is_superdigraph(&digraph));
439            }
440
441            #[test]
442            fn empty_is_symmetric(order in 1..5_usize) {
443                assert!(<$type>::empty(order).is_symmetric());
444            }
445
446            #[test]
447            fn empty_is_tournament(order in 1..5_usize) {
448                assert!((order == 1) == <$type>::empty(order).is_tournament());
449            }
450
451            #[test]
452            fn empty_max_degree(order in 1..5_usize) {
453                assert_eq!(<$type>::empty(order).max_degree(), 0);
454            }
455
456            #[test]
457            fn empty_max_indegree(order in 1..5_usize) {
458                assert_eq!(<$type>::empty(order).max_indegree(), 0);
459            }
460
461            #[test]
462            fn empty_max_outdegree(order in 1..5_usize) {
463                assert_eq!(<$type>::empty(order).max_outdegree(), 0);
464            }
465
466            #[test]
467            fn empty_min_degree(order in 1..5_usize) {
468                assert_eq!(<$type>::empty(order).min_degree(), 0);
469            }
470
471            #[test]
472            fn empty_min_indegree(order in 1..5_usize) {
473                assert_eq!(<$type>::empty(order).min_indegree(), 0);
474            }
475
476            #[test]
477            fn empty_min_outdegree(order in 1..5_usize) {
478                assert_eq!(<$type>::empty(order).min_outdegree(), 0);
479            }
480
481            #[test]
482            fn empty_outdegree(order in 1..5_usize) {
483                let digraph = <$type>::empty(order);
484
485                assert!(digraph.vertices().all(|u| digraph.outdegree(u) == 0));
486            }
487
488            #[test]
489            fn empty_outdegree_sequence(order in 1..5_usize) {
490                assert!(<$type>::empty(order)
491                    .outdegree_sequence()
492                    .all(|d| d == 0));
493            }
494
495            #[test]
496            fn empty_semidegree_sequence(order in 1..5_usize) {
497                assert!(<$type>::empty(order)
498                    .semidegree_sequence()
499                    .all(|d| d == (0, 0)));
500            }
501
502            #[test]
503            fn empty_sinks(order in 1..5_usize) {
504                assert!(<$type>::empty(order).sinks().eq(0..order));
505            }
506
507            #[test]
508            fn empty_size(order in 1..5_usize) {
509                assert_eq!(<$type>::empty(order).size(), 0);
510            }
511
512            #[test]
513            fn empty_sources(order in 1..5_usize) {
514                assert!(<$type>::empty(order).sources().eq(0..order));
515            }
516        }
517    };
518}
graaf/gen/empty.rs

graaf/gen/
empty.rs
