graaf/gen/
circuit.rs

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