11842754306

Committed 14 Nov 2024 05:53PM UTC coverage: 53.619% (+0.1%) from 53.511%

Build # 11842754306

Build Type

push

github

Committed by

vigna

Commit Message

ErdosRenyi is now sorted

Run Details

8 of 9 new or added lines in 1 file covered. (88.89%)

1 existing line in 1 file now uncovered.

2378 of 4435 relevant lines covered (53.62%)

23493306.62 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

88.46

/src/graphs/random/er.rs

/*
 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

use std::vec::IntoIter;

use lender::{Lend, Lender, Lending};
use rand::{rngs::SmallRng, Rng, SeedableRng};

use crate::{
    prelude::{NodeLabelsLender, SequentialGraph, SequentialLabeling},
    traits::{SortedIterator, SortedLender},
};

/// Provides a sequential implementation of Erdös-Rényi random graphs.
///
/// The Erdös-Rényi random graph model is a simple model for generating random
/// graphs. It is parameterized by the number of nodes `n` and the probability
/// `p` of an arc between any two nodes. In this implementation, loops are never
/// included.
///
/// Note that the time required to iterate over the graph is quadratic in `n`,
/// so if you plan to reuse it you should store the result in a more efficient
/// structure, such as a [`VecGraph`](crate::graphs::prelude::VecGraph). The
/// same applies if you need random access.
#[derive(Debug, Clone)]
pub struct ErdosRenyi {
    n: usize,
    p: f64,
    seed: u64,
}

impl ErdosRenyi {
    /// Creates a new Erdös-Rényi random graph, given the number of
    /// nodes, the probability of an edge between any two nodes, and a
    /// seed for the [pseudorandom number generator](SmallRng).
    pub fn new(n: usize, p: f64, seed: u64) -> Self {
        assert!((0.0..=1.0).contains(&p), "p must be in [0..1]");
        Self { n, p, seed }
    }
}

impl SequentialLabeling for ErdosRenyi {
    type Label = usize;
    type Lender<'a> = Iter;
    fn num_nodes(&self) -> usize {
        self.n
    }

    fn iter_from(&self, from: usize) -> Iter {
        let mut rng = SmallRng::seed_from_u64(self.seed);
        for _ in 0..from * (self.n - 1) {
            rng.gen_bool(self.p);
        }
        Iter {
            n: self.n,
            p: self.p,
            x: from,
            rng,
        }
    }
}

unsafe impl SortedLender for Iter {}
unsafe impl SortedIterator for <Succ as IntoIterator>::IntoIter {}

#[derive(Debug, Clone)]
pub struct Iter {
    n: usize,
    p: f64,
    x: usize,
    rng: SmallRng,
}

impl<'succ> NodeLabelsLender<'succ> for Iter {
    type Label = usize;
    type IntoIterator = Succ;
}

impl<'succ> Lending<'succ> for Iter {
    type Lend = (usize, <Self as NodeLabelsLender<'succ>>::IntoIterator);
}

pub struct Succ(Vec<usize>);
pub struct SuccIntoIter(IntoIter<usize>);

impl Iterator for SuccIntoIter {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.next()
    }
}

impl IntoIterator for Succ {
    type Item = usize;
    type IntoIter = SuccIntoIter;

    fn into_iter(self) -> Self::IntoIter {
        let iter = self.0.into_iter();
        SuccIntoIter(iter)
    }
}

impl Lender for Iter {
    #[inline(always)]
    fn next(&mut self) -> Option<Lend<'_, Self>> {
        if self.x >= self.n {
            return None;
        }

        let result = Some((
            self.x,
            Succ(
                (0..self.n)
                    .filter(|&y| y != self.x && self.rng.gen_bool(self.p))
                    .collect::<Vec<_>>(),
            ),
        ));
        self.x += 1;
        result
    }
}

impl SequentialGraph for ErdosRenyi {}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::transform;

    #[test]
    fn test_er() {
        let g = ErdosRenyi::new(10, 0.3, 0);
        for from in 0..10 {
            let mut it0 = g.iter_from(from);
            let mut it1 = g.iter();
            for _ in 0..from {
                it1.next();
            }
            while let (Some((x, s)), Some((y, t))) = (it0.next(), it1.next()) {
                assert_eq!(x, y);
                assert_eq!(s.0, t.0);
            }
            assert!(it0.next().is_none());
            assert!(it1.next().is_none());
        }
    }

    #[test]
    fn test_sorted() {
        // This is just to test that we implemented correctly
        // the SortedIterator and SortedLender traits.
        let er = ErdosRenyi::new(100, 0.1, 0);
        transform::simplify_sorted(er, 100).unwrap();
    }
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Sebastiano Vigna
3	*
4	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
5	*/
6
7	use std::vec::IntoIter;
8
9	use lender::{Lend, Lender, Lending};
10	use rand::{rngs::SmallRng, Rng, SeedableRng};
11
12	use crate::{
13	prelude::{NodeLabelsLender, SequentialGraph, SequentialLabeling},
14	traits::{SortedIterator, SortedLender},
15	};
16
17	/// Provides a sequential implementation of Erdös-Rényi random graphs.
18	///
19	/// The Erdös-Rényi random graph model is a simple model for generating random
20	/// graphs. It is parameterized by the number of nodes `n` and the probability
21	/// `p` of an arc between any two nodes. In this implementation, loops are never
22	/// included.
23	///
24	/// Note that the time required to iterate over the graph is quadratic in `n`,
25	/// so if you plan to reuse it you should store the result in a more efficient
26	/// structure, such as a [`VecGraph`](crate::graphs::prelude::VecGraph). The
27	/// same applies if you need random access.
28	#[derive(Debug, Clone)]
29	pub struct ErdosRenyi {
30	n: usize,
31	p: f64,
32	seed: u64,
33	}
34
35	impl ErdosRenyi {
36	/// Creates a new Erdös-Rényi random graph, given the number of
37	/// nodes, the probability of an edge between any two nodes, and a
38	/// seed for the [pseudorandom number generator](SmallRng).
39	pub fn new(n: usize, p: f64, seed: u64) -> Self {	6✔
40	assert!((0.0..=1.0).contains(&p), "p must be in [0..1]");	6✔
41	Self { n, p, seed }
42	}
43	}
44
45	impl SequentialLabeling for ErdosRenyi {
46	type Label = usize;
47	type Lender<'a> = Iter;
48	fn num_nodes(&self) -> usize {	62,210✔
49	self.n	62,210✔
50	}
51
52	fn iter_from(&self, from: usize) -> Iter {	124,437✔
53	let mut rng = SmallRng::seed_from_u64(self.seed);	124,437✔
54	for _ in 0..from * (self.n - 1) {	124,842✔
55	rng.gen_bool(self.p);	405✔
56	}
57	Iter {
58	n: self.n,	124,437✔
59	p: self.p,	124,437✔
60	x: from,
61	rng,
62	}
63	}
64	}
65
66	unsafe impl SortedLender for Iter {}
67	unsafe impl SortedIterator for <Succ as IntoIterator>::IntoIter {}
68
69	#[derive(Debug, Clone)]
70	pub struct Iter {
71	n: usize,
72	p: f64,
73	x: usize,
74	rng: SmallRng,
75	}
76
77	impl<'succ> NodeLabelsLender<'succ> for Iter {
78	type Label = usize;
79	type IntoIterator = Succ;
80	}
81
82	impl<'succ> Lending<'succ> for Iter {
83	type Lend = (usize, <Self as NodeLabelsLender<'succ>>::IntoIterator);
84	}
85
86	pub struct Succ(Vec<usize>);
87	pub struct SuccIntoIter(IntoIter<usize>);
88
89	impl Iterator for SuccIntoIter {
90	type Item = usize;
91
92	fn next(&mut self) -> Option<Self::Item> {	131,011,101✔
93	self.0.next()	131,011,101✔
94	}
95	}
96
97	impl IntoIterator for Succ {
98	type Item = usize;
99	type IntoIter = SuccIntoIter;
100
101	fn into_iter(self) -> Self::IntoIter {	12,441,700✔
102	let iter = self.0.into_iter();	12,441,700✔
103	SuccIntoIter(iter)	12,441,700✔
104	}
105	}
106
107	impl Lender for Iter {
108	#[inline(always)]
109	fn next(&mut self) -> Option<Lend<'_, Self>> {	12,503,808✔
110	if self.x >= self.n {	12,503,808✔
111	return None;	62,208✔
112	}
113
114	let result = Some((	12,441,600✔
115	self.x,	12,441,600✔
116	Succ(	12,441,600✔
117	(0..self.n)	12,441,600✔
118	.filter(\|&y\| y != self.x && self.rng.gen_bool(self.p))	2,147,483,647✔
NEW 119	.collect::<Vec<_>>(),	×
120	),
121	));
122	self.x += 1;	×
123	result	×
124	}
125	}
126
127	impl SequentialGraph for ErdosRenyi {}
128
129	#[cfg(test)]
130	mod tests {
131	use super::*;
132	use crate::transform;
133
134	#[test]
135	fn test_er() {
136	let g = ErdosRenyi::new(10, 0.3, 0);
137	for from in 0..10 {
138	let mut it0 = g.iter_from(from);
139	let mut it1 = g.iter();
140	for _ in 0..from {
141	it1.next();
142	}
143	while let (Some((x, s)), Some((y, t))) = (it0.next(), it1.next()) {
144	assert_eq!(x, y);
145	assert_eq!(s.0, t.0);
146	}
147	assert!(it0.next().is_none());
148	assert!(it1.next().is_none());
149	}
150	}
151
152	#[test]
153	fn test_sorted() {
154	// This is just to test that we implemented correctly
155	// the SortedIterator and SortedLender traits.
156	let er = ErdosRenyi::new(100, 0.1, 0);
157	transform::simplify_sorted(er, 100).unwrap();
158	}
159	}

vigna / webgraph-rs / 11842754306

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous