1 use petgraph::{graph::DiGraph, graphmap::NodeTrait};
2 use quickcheck::{Arbitrary, Gen, StdGen};
3 use std::ops::Deref;
4 
5 #[derive(Copy, Clone, Debug)]
6 /// quickcheck Arbitrary adaptor - half the size of `T` on average
7 pub struct Small<T>(pub T);
8 
9 impl<T> Deref for Small<T> {
10     type Target = T;
deref(&self) -> &T11     fn deref(&self) -> &T {
12         &self.0
13     }
14 }
15 
16 impl<T> Arbitrary for Small<T>
17 where
18     T: Arbitrary,
19 {
arbitrary<G: Gen>(g: &mut G) -> Self20     fn arbitrary<G: Gen>(g: &mut G) -> Self {
21         let sz = g.size() / 2;
22         Small(T::arbitrary(&mut StdGen::new(g, sz)))
23     }
24 
shrink(&self) -> Box<dyn Iterator<Item = Self>>25     fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
26         Box::new((**self).shrink().map(Small))
27     }
28 }
29 
30 #[cfg(feature = "stable_graph")]
31 /// A directed graph where each pair of nodes has exactly one edge between them, and no loops.
32 #[derive(Clone, Debug)]
33 pub struct Tournament<N, E>(pub DiGraph<N, E>);
34 
35 /// `Arbitrary` for `Tournament` creates a graph with arbitrary node count, and exactly one edge of
36 /// arbitrary direction between each pair of nodes, and no loops. The average node count is reduced,
37 /// to mitigate the high edge count.
38 impl<N, E> Arbitrary for Tournament<N, E>
39 where
40     N: NodeTrait + Arbitrary,
41     E: Arbitrary,
42 {
arbitrary<G: Gen>(g: &mut G) -> Self43     fn arbitrary<G: Gen>(g: &mut G) -> Self {
44         let nodes = usize::arbitrary(g) / 4;
45         if nodes == 0 {
46             return Tournament(DiGraph::with_capacity(0, 0));
47         }
48 
49         let mut gr = DiGraph::new();
50         for _ in 0..nodes {
51             gr.add_node(N::arbitrary(g));
52         }
53         for i in gr.node_indices() {
54             for j in gr.node_indices() {
55                 if i >= j {
56                     continue;
57                 }
58                 let (source, target) = if bool::arbitrary(g) { (i, j) } else { (j, i) };
59                 gr.add_edge(source, target, E::arbitrary(g));
60             }
61         }
62         Tournament(gr)
63     }
64 
shrink(&self) -> Box<dyn Iterator<Item = Self>>65     fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
66         let Tournament(gr) = self;
67         Box::new(gr.shrink().map(Tournament))
68     }
69 }
70