package: rust-petgraph
kcrypd has requested an update for quickcheck to 1.0 in bug
https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=1001656
I am also looking at moving rand to 0.8. quickcheck previously had rand as part
of it's public API,
so it makes sense to update quickcheck at the same time as rand. I made an
attempt at porting the quickcheck
feature in petgraph for quickcheck 1.0 but while I got it to compile, all the
relavent tests failed,
so i'm not uploading it in it's current state.
I've uploaded the new version of rust-quickcheck to experimental and attatched
the patch I attempted to
prepares for rust-petgraph in case anyone else wants to take a crack at porting
it. Otherwise unless
someone raises an objetion I intend to drop the quickcheck feature from this
package when I update
rand/quickcheck in unstable.
Index: petgraph/Cargo.toml
===================================================================
--- petgraph.orig/Cargo.toml
+++ petgraph/Cargo.toml
@@ -42,7 +42,7 @@ default-features = false
version = "1.0.2"
[dependencies.quickcheck]
-version = "0.8"
+version = "1"
optional = true
default-features = false
Index: petgraph/tests/quickcheck.rs
===================================================================
--- petgraph.orig/tests/quickcheck.rs
+++ petgraph/tests/quickcheck.rs
@@ -11,7 +11,7 @@ extern crate odds;
mod utils;
-use utils::Small;
+//use utils::Small;
use odds::prelude::*;
use std::collections::HashSet;
@@ -34,6 +34,8 @@ use petgraph::visit::{EdgeRef, IntoEdgeR
use petgraph::visit::{Reversed, Topo};
use petgraph::EdgeType;
+use quickcheck::Gen;
+
fn mst_graph<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>) -> Graph<N, E, Undirected, Ix>
where
Ty: EdgeType,
@@ -46,7 +48,7 @@ where
use std::fmt;
-quickcheck! {
+/*quickcheck! {
fn mst_directed(g: Small<Graph<(), u32>>) -> bool {
// filter out isolated nodes
let no_singles = g.filter_map(
@@ -60,7 +62,7 @@ quickcheck! {
assert!(!is_cyclic_undirected(&mst));
true
}
-}
+}*/
quickcheck! {
fn mst_undirected(g: Graph<(), u32, Undirected>) -> bool {
@@ -78,13 +80,13 @@ quickcheck! {
}
}
-quickcheck! {
+/*quickcheck! {
fn reverse_undirected(g: Small<UnGraph<(), ()>>) -> bool {
let mut h = (*g).clone();
h.reverse();
is_isomorphic(&g, &h)
}
-}
+}*/
fn assert_graph_consistent<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>)
where
@@ -248,7 +250,7 @@ fn stable_graph_retain_edges() {
quickcheck::quickcheck(prop as fn(StableGraph<_, _, Undirected>) -> bool);
}
-#[test]
+/*#[test]
fn isomorphism_1() {
// using small weights so that duplicates are likely
fn prop<Ty: EdgeType>(g: Small<Graph<i8, i8, Ty>>) -> bool {
@@ -287,9 +289,9 @@ fn isomorphism_1() {
}
quickcheck::quickcheck(prop::<Undirected> as fn(_) -> bool);
quickcheck::quickcheck(prop::<Directed> as fn(_) -> bool);
-}
+}*/
-#[test]
+/*#[test]
fn isomorphism_modify() {
// using small weights so that duplicates are likely
fn prop<Ty: EdgeType>(g: Small<Graph<i16, i8, Ty>>, node: u8, edge: u8) -> bool {
@@ -322,7 +324,7 @@ fn isomorphism_modify() {
}
quickcheck::quickcheck(prop::<Undirected> as fn(_, _, _) -> bool);
quickcheck::quickcheck(prop::<Directed> as fn(_, _, _) -> bool);
-}
+}*/
#[test]
fn graph_remove_edge() {
@@ -564,29 +566,52 @@ fn graph_condensation_acyclic() {
#[derive(Debug, Clone)]
struct DAG<N: Default + Clone + Send + 'static>(Graph<N, ()>);
+// unfortunately quickcheck doesn't let us access the rng directly anymore
+fn u64_from_gen(g: &mut Gen) -> u64 {
+ let mut arr: [u8; 256] = [0; 256];
+ for (val, elem) in arr.iter_mut().enumerate() {
+ *elem = val as u8;
+ }
+ let mut result : u64 = 0;
+ for _ in 0..8 {
+ result *= 256;
+ result += *g.choose(&arr).unwrap() as u64;
+ }
+ return result;
+}
+
+/// Return a random float in the range [0, 1.)
+fn random_01(g: &mut Gen) -> f64 {
+ // from rand
+ let bits = 53;
+ let scale = 1. / ((1u64 << bits) as f64);
+ let x = u64_from_gen(g);
+ (x >> (64 - bits)) as f64 * scale
+}
+
impl<N: Default + Clone + Send + 'static> quickcheck::Arbitrary for DAG<N> {
- fn arbitrary<G: quickcheck::Gen>(g: &mut G) -> Self {
+ fn arbitrary(g: &mut Gen) -> Self {
let nodes = usize::arbitrary(g);
if nodes == 0 {
return DAG(Graph::with_capacity(0, 0));
}
- let split = g.gen_range(0., 1.);
+ let split = random_01(g);
let max_width = f64::sqrt(nodes as f64) as usize;
let tall = (max_width as f64 * split) as usize;
let fat = max_width - tall;
- let edge_prob = 1. - (1. - g.gen_range(0., 1.)) * (1. - g.gen_range(0., 1.));
+ let edge_prob = 1. - (1. - random_01(g)) * (1. - random_01(g));
let edges = ((nodes as f64).powi(2) * edge_prob) as usize;
let mut gr = Graph::with_capacity(nodes, edges);
let mut nodes = 0;
for _ in 0..tall {
- let cur_nodes = g.gen_range(0, fat);
+ let cur_nodes = ((u64_from_gen(g) as u128) * (fat as u128) / 18446744073709551616) as usize;
for _ in 0..cur_nodes {
gr.add_node(N::default());
}
for j in 0..nodes {
for k in 0..cur_nodes {
- if g.gen_range(0., 1.) < edge_prob {
+ if random_01(g) < edge_prob {
gr.add_edge(NodeIndex::new(j), NodeIndex::new(k + nodes), ());
}
}
@@ -928,7 +953,7 @@ quickcheck! {
assert!(edges_eq!(gr1, gr2));
}
- fn stable_di_graph_filter_map_remove(gr1: Small<StableDiGraph<i32, i32>>,
+ /*fn stable_di_graph_filter_map_remove(gr1: Small<StableDiGraph<i32, i32>>,
nodes: Vec<usize>,
edges: Vec<usize>) -> ()
{
@@ -963,5 +988,5 @@ quickcheck! {
for i in edges {
assert!(gr2.edge_weight(edge_index(i)).is_none());
}
- }
+ }*/
}
Index: petgraph/src/quickcheck.rs
===================================================================
--- petgraph.orig/src/quickcheck.rs
+++ petgraph/src/quickcheck.rs
@@ -10,12 +10,26 @@ use crate::{EdgeType, Graph};
use crate::graphmap::{GraphMap, NodeTrait};
use crate::visit::NodeIndexable;
+// unfortunately quickcheck doesn't let us access the rng directly anymore
+fn u64_from_gen(g: &mut Gen) -> u64 {
+ let mut arr: [u8; 256] = [0; 256];
+ for (val, elem) in arr.iter_mut().enumerate() {
+ *elem = val as u8;
+ }
+ let mut result : u64 = 0;
+ for _ in 0..8 {
+ result *= 256;
+ result += *g.choose(&arr).unwrap() as u64;
+ }
+ return result;
+}
+
/// Return a random float in the range [0, 1.)
-fn random_01<G: Gen>(g: &mut G) -> f64 {
+fn random_01(g: &mut Gen) -> f64 {
// from rand
let bits = 53;
let scale = 1. / ((1u64 << bits) as f64);
- let x = g.next_u64();
+ let x = u64_from_gen(g);
(x >> (64 - bits)) as f64 * scale
}
@@ -35,7 +49,7 @@ where
Ty: EdgeType + Send + 'static,
Ix: IndexType + Send,
{
- fn arbitrary<G: Gen>(g: &mut G) -> Self {
+ fn arbitrary(g: &mut Gen) -> Self {
let nodes = usize::arbitrary(g);
if nodes == 0 {
return Graph::with_capacity(0, 0);
@@ -103,7 +117,7 @@ where
Ty: EdgeType + Send + 'static,
Ix: IndexType + Send,
{
- fn arbitrary<G: Gen>(g: &mut G) -> Self {
+ fn arbitrary(g: &mut Gen) -> Self {
let nodes = usize::arbitrary(g);
if nodes == 0 {
return StableGraph::with_capacity(0, 0);
@@ -182,7 +196,7 @@ where
E: Arbitrary,
Ty: EdgeType + Clone + Send + 'static,
{
- fn arbitrary<G: Gen>(g: &mut G) -> Self {
+ fn arbitrary(g: &mut Gen) -> Self {
let nodes = usize::arbitrary(g);
if nodes == 0 {
return GraphMap::with_capacity(0, 0);
Index: petgraph/tests/utils/qc.rs
===================================================================
--- petgraph.orig/tests/utils/qc.rs
+++ petgraph/tests/utils/qc.rs
@@ -1,7 +1,7 @@
-use quickcheck::{Arbitrary, Gen, StdGen};
+use quickcheck::{Arbitrary, Gen};
use std::ops::Deref;
-#[derive(Copy, Clone, Debug)]
+/*#[derive(Copy, Clone, Debug)]
/// quickcheck Arbitrary adaptor - half the size of `T` on average
pub struct Small<T>(pub T);
@@ -24,4 +24,4 @@ where
fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
Box::new((**self).shrink().map(Small))
}
-}
+}*/
