graaf/gen/cycle.rs
1//! Generate cycle digraphs.
2//!
3//! A cycle is a digraph with a single bidirectional cycle.
4//!
5//! # Examples
6//!
7//! ## Order 2
8//!
9//! Generate a cycle digraph of order `2`.
10//!
11//! 
12//!
13//! ```
14//! use graaf::{
15//! AdjacencyList,
16//! Arcs,
17//! Cycle,
18//! };
19//!
20//! assert!(AdjacencyList::cycle(2).arcs().eq([(0, 1), (1, 0)]));
21//! ```
22//!
23//! ## Order 3
24//!
25//! Generate a cycle digraph of order `3`.
26//!
27//! 
28//!
29//! ```
30//! use graaf::{
31//! AdjacencyList,
32//! Arcs,
33//! Cycle,
34//! };
35//!
36//! assert!(AdjacencyList::cycle(3).arcs().eq([
37//! (0, 1),
38//! (0, 2),
39//! (1, 0),
40//! (1, 2),
41//! (2, 0),
42//! (2, 1)
43//! ]));
44//! ```
45//!
46//! ## Order 4
47//!
48//! Generate a cycle digraph of order `4`.
49//!
50//! 
51//!
52//! ```
53//! use graaf::{
54//! AdjacencyList,
55//! Arcs,
56//! Cycle,
57//! };
58//!
59//! assert!(AdjacencyList::cycle(4).arcs().eq([
60//! (0, 1),
61//! (0, 3),
62//! (1, 0),
63//! (1, 2),
64//! (2, 1),
65//! (2, 3),
66//! (3, 0),
67//! (3, 2)
68//! ]));
69//! ```
70
71/// Cycle digraphs
72pub trait Cycle {
73 /// Generate a cycle digraph.
74 ///
75 /// # Arguments
76 ///
77 /// * `order` - The number of vertices in the digraph.
78 ///
79 /// # Examples
80 ///
81 /// ## Order 2
82 ///
83 /// Generate a cycle digraph of order `2`.
84 ///
85 /// 
86 ///
87 /// ```
88 /// use graaf::{
89 /// AdjacencyList,
90 /// Arcs,
91 /// Cycle,
92 /// };
93 ///
94 /// assert!(AdjacencyList::cycle(2).arcs().eq([(0, 1), (1, 0)]));
95 /// ```
96 ///
97 /// ## Order 3
98 ///
99 /// Generate a cycle digraph of order `3`.
100 ///
101 /// 
102 ///
103 /// ```
104 /// use graaf::{
105 /// AdjacencyList,
106 /// Arcs,
107 /// Cycle,
108 /// };
109 ///
110 /// assert!(AdjacencyList::cycle(3).arcs().eq([
111 /// (0, 1),
112 /// (0, 2),
113 /// (1, 0),
114 /// (1, 2),
115 /// (2, 0),
116 /// (2, 1)
117 /// ]));
118 /// ```
119 ///
120 /// ## Order 4
121 ///
122 /// Generate a cycle digraph of order `4`.
123 ///
124 /// 
125 ///
126 /// ```
127 /// use graaf::{
128 /// AdjacencyList,
129 /// Arcs,
130 /// Cycle,
131 /// };
132 ///
133 /// assert!(AdjacencyList::cycle(4).arcs().eq([
134 /// (0, 1),
135 /// (0, 3),
136 /// (1, 0),
137 /// (1, 2),
138 /// (2, 1),
139 /// (2, 3),
140 /// (3, 0),
141 /// (3, 2)
142 /// ]));
143 /// ```
144 #[must_use]
145 fn cycle(order: usize) -> Self;
146}
147
148/// `Cycle` tests
149#[macro_export]
150macro_rules! test_cycle {
151 ($type:ty) => {
152 #[test]
153 #[should_panic(expected = "a digraph has at least one vertex")]
154 fn cycle_0() {
155 drop(<$type>::cycle(0));
156 }
157
158 #[test]
159 fn cycle_1() {
160 let digraph = <$type>::cycle(1);
161
162 assert_eq!(digraph.order(), 1);
163 assert!(digraph.arcs().eq([]));
164 }
165
166 #[test]
167 fn cycle_1_complement() {
168 let digraph = <$type>::cycle(1).complement();
169
170 assert_eq!(digraph.order(), 1);
171 assert!(digraph.arcs().eq([]));
172 }
173
174 #[test]
175 fn cycle_2() {
176 let digraph = <$type>::cycle(2);
177
178 assert_eq!(digraph.order(), 2);
179 assert!(digraph.arcs().eq([(0, 1), (1, 0)]));
180 }
181
182 #[test]
183 fn cycle_2_complement() {
184 let digraph = <$type>::cycle(2).complement();
185
186 assert_eq!(digraph.order(), 2);
187 assert!(digraph.arcs().eq([]));
188 }
189
190 #[test]
191 fn cycle_3() {
192 let digraph = <$type>::cycle(3);
193
194 assert_eq!(digraph.order(), 3);
195
196 assert!(digraph.arcs().eq([
197 (0, 1),
198 (0, 2),
199 (1, 0),
200 (1, 2),
201 (2, 0),
202 (2, 1)
203 ]));
204 }
205
206 #[test]
207 fn cycle_3_complement() {
208 let digraph = <$type>::cycle(3).complement();
209
210 assert_eq!(digraph.order(), 3);
211 assert!(digraph.arcs().eq([]));
212 }
213 };
214}
215
216/// `Cycle` proptests
217#[macro_export]
218macro_rules! proptest_cycle {
219 ($type:ty) => {
220 use {
221 proptest::proptest,
222 $crate::{
223 Degree,
224 IsBalanced,
225 IsIsolated,
226 IsOriented,
227 IsPendant,
228 IsSpanningSubdigraph,
229 IsSubdigraph,
230 IsSuperdigraph,
231 IsSymmetric,
232 OutdegreeSequence,
233 Sinks,
234 Sources,
235 },
236 };
237
238 proptest! {
239 #[test]
240 fn cycle_complement_size(order in 1..5_usize) {
241 assert_eq!(
242 <$type>::cycle(order).complement().size(),
243 order * order.saturating_sub(3)
244 );
245 }
246
247 #[test]
248 fn cycle_degree(order in 1..5_usize) {
249 let digraph = <$type>::cycle(order);
250
251 assert!(digraph.vertices().all(|u| {
252 digraph.degree(u)
253 == match order {
254 1 => 0,
255 2 => 2,
256 _ => 4,
257 }
258 }));
259 }
260
261 #[test]
262 fn cycle_degree_sequence(order in 1..5_usize) {
263 assert!(<$type>::cycle(order)
264 .degree_sequence()
265 .all(|d| match order {
266 1 => d == 0,
267 2 => d == 2,
268 _ => d == 4,
269 }));
270 }
271
272 #[test]
273 fn cycle_degree_sum_equals_2size(order in 1..5_usize) {
274 let digraph = <$type>::cycle(order);
275
276 assert_eq!(
277 digraph
278 .vertices()
279 .fold(0, |acc, u| acc + digraph.degree(u)),
280 2 * digraph.size()
281 );
282 }
283
284 #[test]
285 fn cycle_even_number_odd_degrees(order in 1..5_usize) {
286 let digraph = <$type>::cycle(order);
287
288 assert_eq!(
289 digraph
290 .vertices()
291 .filter(|&u| digraph.degree(u) % 2 == 1)
292 .count()
293 % 2,
294 0
295 );
296 }
297
298 #[test]
299 fn cycle_indegree(order in 1..5_usize) {
300 let digraph = <$type>::cycle(order);
301
302 assert!(digraph.vertices().all(|u| {
303 digraph.indegree(u)
304 == match order {
305 1 => 0,
306 2 => 1,
307 _ => 2,
308 }
309 }));
310 }
311
312 #[test]
313 fn cycle_indegree_sequence(order in 1..5_usize) {
314 assert!(<$type>::cycle(order).indegree_sequence().all(|d| d
315 == match order {
316 1 => 0,
317 2 => 1,
318 _ => 2,
319 }));
320 }
321
322 #[test]
323 fn cycle_is_balanced(order in 1..5_usize) {
324 assert!(<$type>::cycle(order).is_balanced());
325 }
326
327 #[test]
328 fn cycle_is_complete(order in 1..5_usize) {
329 assert!((order < 4) == <$type>::cycle(order).is_complete());
330 }
331
332 #[test]
333 fn cycle_is_isolated(order in 1..5_usize) {
334 let digraph = <$type>::cycle(order);
335
336 assert!(digraph
337 .vertices()
338 .all(|u| (order == 1) == digraph.is_isolated(u)));
339 }
340
341 #[test]
342 fn cycle_is_oriented(order in 1..5_usize) {
343 assert!((order == 1) == <$type>::cycle(order).is_oriented());
344 }
345
346 #[test]
347 fn cycle_is_pendant(order in 1..5_usize) {
348 let digraph = <$type>::cycle(order);
349
350 assert!(digraph.vertices().all(|u| !digraph.is_pendant(u)));
351 }
352
353 #[test]
354 fn cycle_is_regular(order in 1..5_usize) {
355 assert!(<$type>::cycle(order).is_regular());
356 }
357
358 #[test]
359 fn cycle_is_semicomplete(order in 1..5_usize) {
360 assert!((order < 4) == <$type>::cycle(order).is_semicomplete());
361 }
362
363 #[test]
364 fn cycle_is_simple(order in 1..5_usize) {
365 assert!(<$type>::cycle(order).is_simple());
366 }
367
368 #[test]
369 fn cycle_is_sink(order in 1..5_usize) {
370 let digraph = <$type>::cycle(order);
371
372 assert!(digraph
373 .vertices()
374 .all(|u| (order == 1) == digraph.is_sink(u)));
375 }
376
377 #[test]
378 fn cycle_is_source(order in 1..5_usize) {
379 let digraph = <$type>::cycle(order);
380
381 assert!(digraph
382 .vertices()
383 .all(|u| (order == 1) == digraph.is_source(u)));
384 }
385
386 #[test]
387 fn cycle_is_spanning_subdigraph(order in 1..5_usize) {
388 let digraph = <$type>::cycle(order);
389
390 assert!(digraph.is_spanning_subdigraph(&digraph));
391 }
392
393 #[test]
394 fn cycle_is_subdigraph(order in 1..5_usize) {
395 let digraph = <$type>::cycle(order);
396
397 assert!(digraph.is_subdigraph(&digraph));
398 }
399
400 #[test]
401 fn cycle_is_superdigraph(order in 1..5_usize) {
402 let digraph = <$type>::cycle(order);
403
404 assert!(digraph.is_superdigraph(&digraph));
405 }
406
407 #[test]
408 fn cycle_is_symmetric(order in 1..5_usize) {
409 assert!(<$type>::cycle(order).is_symmetric());
410 }
411
412 #[test]
413 fn cycle_is_tournament(order in 1..5_usize) {
414 assert!((order == 1) == <$type>::cycle(order).is_tournament());
415 }
416
417 #[test]
418 fn cycle_max_degree(order in 1..5_usize) {
419 assert_eq!(
420 <$type>::cycle(order).max_degree(),
421 match order {
422 1 => 0,
423 2 => 2,
424 _ => 4,
425 }
426 );
427 }
428
429 #[test]
430 fn cycle_max_indegree(order in 1..5_usize) {
431 assert_eq!(
432 <$type>::cycle(order).max_indegree(),
433 match order {
434 1 => 0,
435 2 => 1,
436 _ => 2,
437 }
438 );
439 }
440
441 #[test]
442 fn cycle_max_outdegree(order in 1..5_usize) {
443 assert_eq!(
444 <$type>::cycle(order).max_outdegree(),
445 match order {
446 1 => 0,
447 2 => 1,
448 _ => 2,
449 }
450 );
451 }
452
453 #[test]
454 fn cycle_min_degree(order in 1..5_usize) {
455 assert_eq!(
456 <$type>::cycle(order).min_degree(),
457 match order {
458 1 => 0,
459 2 => 2,
460 _ => 4,
461 }
462 );
463 }
464
465 #[test]
466 fn cycle_min_indegree(order in 1..5_usize) {
467 assert_eq!(
468 <$type>::cycle(order).min_indegree(),
469 match order {
470 1 => 0,
471 2 => 1,
472 _ => 2,
473 }
474 );
475 }
476
477 #[test]
478 fn cycle_min_outdegree(order in 1..5_usize) {
479 assert_eq!(
480 <$type>::cycle(order).min_outdegree(),
481 match order {
482 1 => 0,
483 2 => 1,
484 _ => 2,
485 }
486 );
487 }
488
489 #[test]
490 fn cycle_outdegree(order in 1..5_usize) {
491 let digraph = <$type>::cycle(order);
492
493 assert!(digraph.vertices().all(|u| {
494 digraph.outdegree(u)
495 == match order {
496 1 => 0,
497 2 => 1,
498 _ => 2,
499 }
500 }));
501 }
502
503 #[test]
504 fn cycle_outdegree_sequence(order in 1..5_usize) {
505 assert!(<$type>::cycle(order).outdegree_sequence().all(|d| d
506 == match order {
507 1 => 0,
508 2 => 1,
509 _ => 2,
510 }));
511 }
512
513 #[test]
514 fn cycle_semidegree_sequence(order in 1..5_usize) {
515 assert!(<$type>::cycle(order).semidegree_sequence().all(|d| d
516 == match order {
517 1 => (0, 0),
518 2 => (1, 1),
519 _ => (2, 2),
520 }));
521 }
522
523 #[test]
524 fn cycle_sinks(order in 1..5_usize) {
525 assert!(if order == 1 {
526 <$type>::cycle(order).sinks().eq([0])
527 } else {
528 <$type>::cycle(order).sinks().eq([])
529 });
530 }
531
532 #[test]
533 fn cycle_size(order in 1..5_usize) {
534 assert_eq!(
535 <$type>::cycle(order).size(),
536 match order {
537 1 => 0,
538 2 => 2,
539 _ => order * 2
540 }
541 );
542 }
543
544 #[test]
545 fn cycle_sources(order in 1..5_usize) {
546 assert!(if order == 1 {
547 <$type>::cycle(order).sources().eq([0])
548 } else {
549 <$type>::cycle(order).sources().eq([])
550 });
551 }
552 }
553 };
554}