petgraph/
quickcheck.rs

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

petgraph/
quickcheck.rs
