Struct believer::generators::random_checks::generator::Generator

pub struct Generator<R: Rng = ThreadRng> { /* fields omitted */ }

A Generator helps generating checks for a code while respecting some global constraints.

Constraints are degrees and minimal girth. A Generator is consumed while generating checks. Take a look at all the setters methods (the one that have &mut self as argument and output) to see all the parameters that can be set.

Example

use believer::random_checks::Generator;
use rand::SeedableRng;
use rand_chacha::ChaCha8Rng;

// Create a check generator for 10 bits with the given random number generator.
let mut generator = Generator::with_n_bits(10)
    .with_random_number_generator(ChaCha8Rng::seed_from_u64(123));

// Set some parameters for the generator.
generator
    .set_maximal_bit_degree(3)
    .set_minimal_girth(6)
    .set_target_check_degree(4);

// Generate a check over the first 4 bits (this is in fact deterministic).
let first_check = generator.set_over_bits(vec![0, 1, 2, 3]).get_random_check();
assert_eq!(first_check, Some(vec![0, 1, 2, 3]));

// Use relative weight for the next check.
let distribution = vec![0.0, 0.0, 0.0, 0.0, 0.1, 0.1, 0.2, 0.2, 0.2, 0.2];
let second_check = generator
    .set_over_all_bits()
    .set_distribution(distribution)
    .get_random_check();
assert_eq!(second_check, Some(vec![6, 7, 8, 9]));

// By default, all generated checks of degree below target (4 in this example) are rejected.
// We can't generate a degree 4 check over only 3 bits.
let third_check = generator
    .set_uniform_distribution()
    .set_over_bits(vec![4, 5, 6])
    .get_random_check();
assert!(third_check.is_none());

// But, we can relax this constraint. In this case, the generator will try to create a degree 4
// (the target check degree) check. Since it not possible, a degree 3 check will be returns
// instead.
generator.allow_checks_of_degree_at_least(3);
let fourth_check = generator.get_random_check();
assert_eq!(fourth_check, Some(vec![4, 5, 6]));

// It is also possible that a check is rejected if it would create a cycle smaller than the
// minimal girth or if all the bits have reached the maximum degree. In the following example
// having bit 4 and 6 together in an other check would create a length 4 cycle.
let fifth_check = generator.set_over_bits(vec![0, 4, 6]).get_random_check();
assert!(fifth_check.is_none());

// However, it is possible to generate a degree 2 check.
let sixth_check = generator.allow_checks_of_degree_at_least(2).get_random_check();
assert_eq!(sixth_check, Some(vec![0, 4]));

Methods

impl Generator<ThreadRng>

pub fn new() -> Self

Creates a generator for empty code.

pub fn with_n_bits(n_bits: usize) -> Self

Creates a generator for n_bits without any restriction on the checks that are going to be generated and using the uniform distribution over all bits.

impl<R: Rng> Generator<R>

pub fn with_random_number_generator<S: Rng>(self, rng: S) -> Generator<S>

Create a copy of self with the given rng consuming self .

If not set, random numbers will be generate using rand::thread_rng. This method consume self and create a new Generator from it taking ownership of most of it's parameters. It is designed to be use during construction.

Example

use believer::random_checks::Generator;

// Some random number generator.
use rand::SeedableRng;
use rand_chacha::ChaCha8Rng;

let mut rng = ChaCha8Rng::seed_from_u64(123);
let generator = Generator::new().with_random_number_generator(rng);

pub fn set_minimal_girth(&mut self, minimal_girth: usize) -> &mut Self

Set the minimal girth of self.

The checks generated after this won't create any cycle smaller than the minimal girth. If this is set before generating the first checks, the generated checks will induce a code with girth at least minimal_girth.

pub fn set_maximal_bit_degree(&mut self, degree: usize) -> &mut Self

Set the maximal bit degree of self.

A given bit will not be part of any new check if it was generated in maximal_bit_degree previous checks. The default value is 1.

pub fn set_over_all_bits(&mut self) -> &mut Self

Set self to generate the following checks without any restriction on the bits.

This is the default behavior.

pub fn set_over_bits(&mut self, bits: Vec<usize>) -> &mut Self

Set self to generate the following checks using only the given bits.

pub fn set_without_bits(&mut self, bits: Vec<usize>) -> &mut Self

Set self to generate the following checks without the given bits.

This won't reset the target bits.

Example

use believer::random_checks::Generator;

let mut generator = Generator::with_n_bits(10);

// This limit the following checks over bits 2, 3, 4, ..., 9.
generator.set_without_bits(vec![0, 1]);

// This limit the following checks over bits 7, 8 and 9 since 0 and 1 are already removed.
generator.set_without_bits(vec![2, 3, 4, 5, 6]);

// This limit the following checks over bits 0 and 1.
generator.set_over_bits(vec![0, 1, 2]).set_without_bits(vec![2]);

pub fn set_distribution(&mut self, distribution: Vec<f64>) -> &mut Self

Set self to generate bits in checks according to the given distribution.

The distribution does not need to be normalize. It will be normalize to sum to 1 except if the sum is 0. If not set, the uniform distribution is used.

Panic

Panics if the distribution lenght is not the same as the number of bits in self. Also panics if there are some negative probabilities.

Example

use believer::random_checks::Generator;
let mut generator = Generator::with_n_bits(5);

// It is more like that the first 3 bits are selected in the following checks.
generator.set_distribution(vec![0.3, 0.3, 0.3, 0.05, 0.05]);

// It can be set with relative weights.
generator.set_distribution(vec![30.0, 30.0, 30.0, 5.0, 5.0]);

// If we limit the bits to a subset, the distribution is updated in consequence. In the
// following, the distribution is updated to [0.75, 0.0, 0.0, 12.5, 12.5].
generator.set_without_bits(vec![1, 2]);

pub fn set_uniform_distribution(&mut self) -> &mut Self

Set self to generate bits in checks according to the uniform distribution.

This is the default behavior.

pub fn set_target_check_degree(&mut self, degree: usize) -> &mut Self

Set the target check degree of self.

By default, the target degree is 2 and a check will be rejected if, due to other constraints, it can't be generated with the target degree. This can be change using self.allow_checks_of_degree_at_least(degree) or self.allow_only_full_degree_check().

Example

use believer::random_checks::Generator;

let mut generator = Generator::with_n_bits(5);
generator.set_target_check_degree(4);

// Can't generator a degree 4 check over only bit 0 and 1.
assert_eq!(generator.set_over_bits(vec![0, 1]).get_random_check(), None);

pub fn allow_checks_of_degree_at_least(&mut self, degree: usize) -> &mut Self

Set self to allow all checks of degree at least degree.

By default, self only accept check of target degree (which is 2 by default).

Example

use believer::random_checks::Generator;

let mut generator = Generator::with_n_bits(5);

// Can't generator a degree 2 (default) check over only bit 0.
generator.set_over_bits(vec![0]);
assert_eq!(generator.get_random_check(), None);

// It is possible to allow check of degree 1 checks.
generator.allow_checks_of_degree_at_least(1);
assert_eq!(generator.get_random_check(), Some(vec![0]));

pub fn allow_only_check_of_target_degree(&mut self) -> &mut Self

Set self to allow only check of target degree (2 by default).

This is the default behavior.

Example

use believer::random_checks::Generator;

let mut generator = Generator::with_n_bits(5);
generator.set_target_check_degree(4);

// Not necessary, this is the default.
generator.allow_only_check_of_target_degree();

// A degree 3 check is not allowed.
generator.set_over_bits(vec![0, 1, 2]);
assert_eq!(generator.get_random_check(), None);

// It is possible to generate a check of degree 4 over 5 bits.
generator.set_over_all_bits();
assert!(generator.get_random_check().is_some());

pub fn get_bits_adjacent_to(&self, bit: usize) -> Vec<usize>

Returns the list of bits adjacent to bit given the minimal girth of the generator.

Two bits are adjacent if connecting them to the same check will create a cycle smaller than the minimal girth.

pub fn get_n_bits(&self) -> usize

Returns the number of bits in the code that self is generating checks for.

pub fn get_random_check(&mut self) -> Option<Vec<usize>>

Generates a random check.

The behavior of this function can be change using the setter methods.

Example

use believer::random_checks::Generator;
let mut generator = Generator::with_n_bits(10);
let check = generator.get_random_check();