graaf/gen/
star.rs

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

graaf/gen/
star.rs
