1 extern crate quickcheck;
2 use self::quickcheck::{Arbitrary, Gen};
3
4 use crate::graph::{node_index, IndexType};
5 #[cfg(feature = "stable_graph")]
6 use crate::stable_graph::StableGraph;
7 use crate::{EdgeType, Graph};
8
9 #[cfg(feature = "graphmap")]
10 use crate::graphmap::{GraphMap, NodeTrait};
11 use crate::visit::NodeIndexable;
12
13 /// Return a random float in the range [0, 1.)
random_01<G: Gen>(g: &mut G) -> f6414 fn random_01<G: Gen>(g: &mut G) -> f64 {
15 // from rand
16 let bits = 53;
17 let scale = 1. / ((1u64 << bits) as f64);
18 let x = g.next_u64();
19 (x >> (64 - bits)) as f64 * scale
20 }
21
22 /// `Arbitrary` for `Graph` creates a graph by selecting a node count
23 /// and a probability for each possible edge to exist.
24 ///
25 /// The result will be simple graph or digraph, self loops
26 /// possible, no parallel edges.
27 ///
28 /// The exact properties of the produced graph is subject to change.
29 ///
30 /// Requires crate feature `"quickcheck"`
31 impl<N, E, Ty, Ix> Arbitrary for Graph<N, E, Ty, Ix>
32 where
33 N: Arbitrary,
34 E: Arbitrary,
35 Ty: EdgeType + Send + 'static,
36 Ix: IndexType + Send,
37 {
arbitrary<G: Gen>(g: &mut G) -> Self38 fn arbitrary<G: Gen>(g: &mut G) -> Self {
39 let nodes = usize::arbitrary(g);
40 if nodes == 0 {
41 return Graph::with_capacity(0, 0);
42 }
43 // use X² for edge probability (bias towards lower)
44 let edge_prob = random_01(g) * random_01(g);
45 let edges = ((nodes as f64).powi(2) * edge_prob) as usize;
46 let mut gr = Graph::with_capacity(nodes, edges);
47 for _ in 0..nodes {
48 gr.add_node(N::arbitrary(g));
49 }
50 for i in gr.node_indices() {
51 for j in gr.node_indices() {
52 if !gr.is_directed() && i > j {
53 continue;
54 }
55 let p: f64 = random_01(g);
56 if p <= edge_prob {
57 gr.add_edge(i, j, E::arbitrary(g));
58 }
59 }
60 }
61 gr
62 }
63
64 // shrink the graph by splitting it in two by a very
65 // simple algorithm, just even and odd node indices
shrink(&self) -> Box<dyn Iterator<Item = Self>>66 fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
67 let self_ = self.clone();
68 Box::new((0..2).filter_map(move |x| {
69 let gr = self_.filter_map(
70 |i, w| {
71 if i.index() % 2 == x {
72 Some(w.clone())
73 } else {
74 None
75 }
76 },
77 |_, w| Some(w.clone()),
78 );
79 // make sure we shrink
80 if gr.node_count() < self_.node_count() {
81 Some(gr)
82 } else {
83 None
84 }
85 }))
86 }
87 }
88
89 #[cfg(feature = "stable_graph")]
90 /// `Arbitrary` for `StableGraph` creates a graph by selecting a node count
91 /// and a probability for each possible edge to exist.
92 ///
93 /// The result will be simple graph or digraph, with possible
94 /// self loops, no parallel edges.
95 ///
96 /// The exact properties of the produced graph is subject to change.
97 ///
98 /// Requires crate features `"quickcheck"` and `"stable_graph"`
99 impl<N, E, Ty, Ix> Arbitrary for StableGraph<N, E, Ty, Ix>
100 where
101 N: Arbitrary,
102 E: Arbitrary,
103 Ty: EdgeType + Send + 'static,
104 Ix: IndexType + Send,
105 {
arbitrary<G: Gen>(g: &mut G) -> Self106 fn arbitrary<G: Gen>(g: &mut G) -> Self {
107 let nodes = usize::arbitrary(g);
108 if nodes == 0 {
109 return StableGraph::with_capacity(0, 0);
110 }
111 // use X² for edge probability (bias towards lower)
112 let edge_prob = random_01(g) * random_01(g);
113 let edges = ((nodes as f64).powi(2) * edge_prob) as usize;
114 let mut gr = StableGraph::with_capacity(nodes, edges);
115 for _ in 0..nodes {
116 gr.add_node(N::arbitrary(g));
117 }
118 for i in 0..gr.node_count() {
119 for j in 0..gr.node_count() {
120 let i = node_index(i);
121 let j = node_index(j);
122 if !gr.is_directed() && i > j {
123 continue;
124 }
125 let p: f64 = random_01(g);
126 if p <= edge_prob {
127 gr.add_edge(i, j, E::arbitrary(g));
128 }
129 }
130 }
131 if bool::arbitrary(g) {
132 // potentially remove nodes to make holes in nodes & edge sets
133 let n = u8::arbitrary(g) % (gr.node_count() as u8);
134 for _ in 0..n {
135 let ni = node_index(usize::arbitrary(g) % gr.node_bound());
136 if gr.node_weight(ni).is_some() {
137 gr.remove_node(ni);
138 }
139 }
140 }
141 gr
142 }
143
144 // shrink the graph by splitting it in two by a very
145 // simple algorithm, just even and odd node indices
shrink(&self) -> Box<dyn Iterator<Item = Self>>146 fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
147 let self_ = self.clone();
148 Box::new((0..2).filter_map(move |x| {
149 let gr = self_.filter_map(
150 |i, w| {
151 if i.index() % 2 == x {
152 Some(w.clone())
153 } else {
154 None
155 }
156 },
157 |_, w| Some(w.clone()),
158 );
159 // make sure we shrink
160 if gr.node_count() < self_.node_count() {
161 Some(gr)
162 } else {
163 None
164 }
165 }))
166 }
167 }
168
169 /// `Arbitrary` for `GraphMap` creates a graph by selecting a node count
170 /// and a probability for each possible edge to exist.
171 ///
172 /// The result will be simple graph or digraph, self loops
173 /// possible, no parallel edges.
174 ///
175 /// The exact properties of the produced graph is subject to change.
176 ///
177 /// Requires crate features `"quickcheck"` and `"graphmap"`
178 #[cfg(feature = "graphmap")]
179 impl<N, E, Ty> Arbitrary for GraphMap<N, E, Ty>
180 where
181 N: NodeTrait + Arbitrary,
182 E: Arbitrary,
183 Ty: EdgeType + Clone + Send + 'static,
184 {
arbitrary<G: Gen>(g: &mut G) -> Self185 fn arbitrary<G: Gen>(g: &mut G) -> Self {
186 let nodes = usize::arbitrary(g);
187 if nodes == 0 {
188 return GraphMap::with_capacity(0, 0);
189 }
190 let mut nodes = (0..nodes).map(|_| N::arbitrary(g)).collect::<Vec<_>>();
191 nodes.sort();
192 nodes.dedup();
193
194 // use X² for edge probability (bias towards lower)
195 let edge_prob = random_01(g) * random_01(g);
196 let edges = ((nodes.len() as f64).powi(2) * edge_prob) as usize;
197 let mut gr = GraphMap::with_capacity(nodes.len(), edges);
198 for &node in &nodes {
199 gr.add_node(node);
200 }
201 for (index, &i) in nodes.iter().enumerate() {
202 let js = if Ty::is_directed() {
203 &nodes[..]
204 } else {
205 &nodes[index..]
206 };
207 for &j in js {
208 let p: f64 = random_01(g);
209 if p <= edge_prob {
210 gr.add_edge(i, j, E::arbitrary(g));
211 }
212 }
213 }
214 gr
215 }
216 }
217