petgraph/
quickcheck.rs

1extern crate quickcheck;
2use self::quickcheck::{Arbitrary, Gen};
3
4use crate::graph::{node_index, IndexType};
5#[cfg(feature = "stable_graph")]
6use crate::stable_graph::StableGraph;
7use crate::{EdgeType, Graph};
8
9#[cfg(feature = "graphmap")]
10use crate::graphmap::{GraphMap, NodeTrait};
11use crate::visit::NodeIndexable;
12
13/// Return a random float in the range [0, 1.)
14fn 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"`
31impl<N, E, Ty, Ix> Arbitrary for Graph<N, E, Ty, Ix>
32where
33    N: Arbitrary,
34    E: Arbitrary,
35    Ty: EdgeType + Send + 'static,
36    Ix: IndexType + Send,
37{
38    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
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"`
99impl<N, E, Ty, Ix> Arbitrary for StableGraph<N, E, Ty, Ix>
100where
101    N: Arbitrary,
102    E: Arbitrary,
103    Ty: EdgeType + Send + 'static,
104    Ix: IndexType + Send,
105{
106    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
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")]
179impl<N, E, Ty> Arbitrary for GraphMap<N, E, Ty>
180where
181    N: NodeTrait + Arbitrary,
182    E: Arbitrary,
183    Ty: EdgeType + Clone + Send + 'static,
184{
185    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}
petgraph/quickcheck.rs

petgraph/
quickcheck.rs
