Quickcheck random_01 function only outputting 0 makes all QuickCheck Arbitrary Graphs (almost) complete #796
Description
While working on an implementation for a check if a graph is chordal I noticed something weird:
Looking at the random_01 function in src/quickcheck.rs, which is used to generate the "arbitrary" graphs for the quickchecks, I noticed that there seems to be something off.
When printing out all the values generated by random_01 I only get 0s. More precisely, I edited random_01 in src/quickcheck.rs to be as follows:
/// Return a random float in the range [0, 1.)
fn random_01<G: Gen>(g: &mut G) -> f64 {
// from rand
let bits = 53;
let scale = 1. / ((1u64 << bits) as f64);
let x: u64 = Arbitrary::arbitrary(g);
let output = (x >> (64 - bits)) as f64 * scale;
use std::println;
println!("x: {}, output: {}", x, output);
output
}And the output in my terminal looks something like this:
x: 60, output: 0
x: 47, output: 0
x: 19, output: 0
x: 92, output: 0
x: 51, output: 0
x: 17, output: 0
x: 38, output: 0
x: 6, output: 0
x: 7, output: 0
x: 23, output: 0
x: 93, output: 0
x: 80, output: 0
x: 35, output: 0
x: 18, output: 0
x: 13, output: 0
x: 8, output: 0
x: 48, output: 0
x: 0, output: 0
x: 29, output: 0
x: 4, output: 0
x: 63, output: 0
x: 24, output: 0
x: 94, output: 0
x: 3, output: 0
I guess the fact that values of x are between 0 and 100 is not intended. Since for these values, the output always seems to be 0. This possible range of values for x ( or more generally Arbitrary::arbitrary(g);) seems to be determined by the size of the generator g. This, in turn is 100 by default for QuickCheck, according to the docs here, see new(). (This new is never explicitly called as far as I can tell, however I guess it's implicitly called when using the quickcheck macro or similar functionality).
In particular, all (Graph) graphs generated by Arbitrary seem to be almost always complete graphs (with regard to their non loop edges). This is not desirable I would think.
Furthermore, this means that the size of the graph which is also controlled by Arbitrary::arbitrary(g);, is bounded at 100.
I am not sure, how to fix this since I have not yet fully understood the QuickCheck crate, but this does seem to be quite limiting to our QuickCheck quality. One way would be by using the rand crate to generate numbers between 0 and 1 instead of quickcheck. I would however think that this is not a great solution since this would probably imply creating a lot of random number generators for all the quickchecks.
Hence, probably it would be best to properly use the functionality exposed by QuickCheck to generate the random numbers we want.
Another question which arises is what the size of the tested graphs should be, since I would think that the original (intended) size of u64::MAX is not feasible.
As a side note, I ran the quickchecks with a workaround (somewhat) random number generator by just dividing the x from above by 100 as a f64 and 2 quickchecks seemed to crash after this change:
failures:
---- maximal_cliques_matches_ref_impl stdout ----
thread 'maximal_cliques_matches_ref_impl' panicked at tests/quickcheck.rs:1518:13:
assertion failed: cliques.len() == cliques_ref.len()
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
thread 'maximal_cliques_matches_ref_impl' panicked at tests/quickcheck.rs:1518:13:
assertion failed: cliques.len() == cliques_ref.len()
thread 'maximal_cliques_matches_ref_impl' panicked at tests/quickcheck.rs:1518:13:
assertion failed: cliques.len() == cliques_ref.len()
thread 'maximal_cliques_matches_ref_impl' panicked at tests/quickcheck.rs:1518:13:
assertion failed: cliques.len() == cliques_ref.len()
thread 'maximal_cliques_matches_ref_impl' panicked at .cargo/registry/src/index.crates.io-1949cf8c6b5b557f/quickcheck-0.8.5/src/tester.rs:176:28:
[quickcheck] TEST FAILED (runtime error). Arguments: (Graph { Ty: "Directed", node_count: 4, edge_count: 4, edges: (0, 3), (1, 3), (3, 1), (3, 3) })
Error: "assertion failed: cliques.len() == cliques_ref.len()"
---- test_steiner_tree stdout ----
thread 'test_steiner_tree' panicked at src/algo/steiner_tree.rs:29:11:
no entry found for key
thread 'test_steiner_tree' panicked at src/algo/steiner_tree.rs:29:11:
no entry found for key
thread 'test_steiner_tree' panicked at src/algo/steiner_tree.rs:29:11:
no entry found for key
thread 'test_steiner_tree' panicked at src/algo/steiner_tree.rs:29:11:
no entry found for key
thread 'test_steiner_tree' panicked at src/algo/steiner_tree.rs:29:11:
no entry found for key
thread 'test_steiner_tree' panicked at src/algo/steiner_tree.rs:29:11:
no entry found for key
thread 'test_steiner_tree' panicked at .cargo/registry/src/index.crates.io-1949cf8c6b5b557f/quickcheck-0.8.5/src/tester.rs:176:28:
[quickcheck] TEST FAILED (runtime error). Arguments: (Graph { Ty: "Undirected", node_count: 2, edge_count: 0, edge weights: {} })
Error: "no entry found for key"
failures:
maximal_cliques_matches_ref_impl
test_steiner_tree