bigs/

sampler.rs

use crate::builder::Builder;
use crate::graph::{Edge, Graph};
use rand::seq::SliceRandom;
use rand::Rng;
use std::collections::VecDeque;

/// A sampler for regular bipartite graph.
///
/// This is the main struct of this crate.
/// The [`builder`](Sampler::builder) method is used to build a sampler
/// and  the [`sample_with`](Sampler::sample_with) method is used
/// to sample a random [`Graph`](Graph).
///
/// A sampler is specified by 4 parameters:
///     - variable's degree: the same for all variables,
///     - constraint's degree: the same for all contraints,
///     - number of variables,
///     - number of contraints.
///
/// To make sure that the graphs are regular,
/// the number of variables times their degree need to equal
/// the number of contraints times their degree.
/// If this is not satified, the builder will panic during construction.
///
/// # Example
///
/// This can be used to generate a random graph with 5 variables of degree 3
/// and 3 constraints of degree 5.
/// ```
/// # use bigs::Sampler;
/// use rand::thread_rng;
///
/// let sampler = Sampler::builder()
///     .number_of_variables(5)
///     .variable_degree(3)
///     .number_of_constraints(3)
///     .constraint_degree(5)
///     .build()
///     .unwrap();
///
/// let graph = sampler.sample_with(&mut thread_rng());
///
/// assert_eq!(graph.number_of_variables(), 5);
/// for variable in graph.variables() {
///     assert_eq!(variable.degree(), 3);
/// }
///
/// assert_eq!(graph.number_of_constraints(), 3);
/// for constraint in graph.constraints() {
///     assert_eq!(constraint.degree(), 5);
///     }
/// ```
///
/// However, this will return an error since the parameters do not define
/// a regular graph.
///
/// ```
/// # use bigs::Sampler;
/// let sampler = Sampler::builder()
///     .number_of_variables(5)
///     .variable_degree(3)
///     .number_of_constraints(3)
///     .constraint_degree(3)
///     .build();
///
/// assert!(sampler.is_err());
/// ```
///
/// # Reproductibility
///
/// If you use the same random number generator,
/// the graphs should be the same.
///
/// ```
/// # use bigs::Sampler;
/// use rand::SeedableRng;
/// use rand::rngs::SmallRng; // require the small_rng feature
///
/// let sampler = Sampler::builder()
///     .number_of_variables(5)
///     .variable_degree(3)
///     .number_of_constraints(3)
///     .constraint_degree(5)
///     .build()
///     .unwrap();
///
/// // Create two rngs with the same seed.
/// let mut rng = SmallRng::seed_from_u64(123);
/// let mut other_rng = SmallRng::seed_from_u64(123);
///
/// let graph = sampler.sample_with(&mut rng);
/// let other_graph = sampler.sample_with(&mut other_rng);
///
/// assert_eq!(graph, other_graph);
/// ```
#[derive(Debug)]
pub struct Sampler {
    pub(crate) variable_degree: usize,
    pub(crate) constraint_degree: usize,
    pub(crate) number_of_variables: usize,
    pub(crate) number_of_constraints: usize,
}

impl Sampler {
    /// Instanciates a builder for samplers.
    pub fn builder() -> Builder {
        Builder::default()
    }

    /// Samples a random graph with the sampler parameters.
    pub fn sample_with<R: Rng>(&self, rng: &mut R) -> Graph {
        Sample::from_sampler_and_rng(self, rng).generate()
    }

    /// Returns the number of variables in the graphs
    /// that will be generated by the sampler.
    pub fn number_of_variables(&self) -> usize {
        self.number_of_variables
    }

    /// Returns the number of constraints in the graphs
    /// that will be generated by the sampler.
    pub fn number_of_constraints(&self) -> usize {
        self.number_of_constraints
    }

    /// Returns the number of edges in the graphs
    /// that will be generated by the sampler.
    pub fn number_of_edges(&self) -> usize {
        self.number_of_variables * self.variable_degree
    }

    /// Returns the variable's degree in the graphs
    /// that will be generated by the sampler.
    pub fn variable_degree(&self) -> usize {
        self.variable_degree
    }

    /// Returns the contraint's degree in the graphs
    /// that will be generated by the sampler.
    pub fn constraint_degree(&self) -> usize {
        self.constraint_degree
    }
}

struct Sample<'s> {
    sampler: &'s Sampler,
    candidate_edges: VecDeque<Edge>,
}

impl<'s> Sample<'s> {
    fn from_sampler_and_rng<R: Rng>(sampler: &'s Sampler, rng: &mut R) -> Self {
        Self {
            sampler,
            candidate_edges: Self::candidate_edges(sampler, rng),
        }
    }

    fn candidate_edges<R: Rng>(sampler: &Sampler, rng: &mut R) -> VecDeque<Edge> {
        Self::candidate_variables(sampler, rng)
            .zip(Self::candidate_constraints(sampler, rng))
            .map(|(variable, constraint)| Edge {
                variable,
                constraint,
            })
            .collect()
    }

    fn candidate_variables<R: Rng>(sampler: &Sampler, rng: &mut R) -> impl Iterator<Item = usize> {
        let mut variables = (0..sampler.number_of_variables())
            .flat_map(|variable| std::iter::repeat(variable).take(sampler.variable_degree()))
            .collect::<Vec<usize>>();
        variables.shuffle(rng);
        variables.into_iter()
    }

    fn candidate_constraints<R: Rng>(
        sampler: &Sampler,
        rng: &mut R,
    ) -> impl Iterator<Item = usize> {
        let mut constraints = (0..sampler.number_of_constraints())
            .flat_map(|constraint| std::iter::repeat(constraint).take(sampler.constraint_degree()))
            .collect::<Vec<usize>>();
        constraints.shuffle(rng);
        constraints.into_iter()
    }

    fn generate(mut self) -> Graph {
        let mut graph = Graph::from_sampler(self.sampler);
        while let Some(edge) = self.candidate_edges.pop_front() {
            if graph.contains_edge(edge) {
                self.try_to_swap_edge_and_insert(&mut graph, edge);
            } else {
                graph.insert_edge(edge);
            }
        }
        graph
    }

    fn try_to_swap_edge_and_insert(&mut self, graph: &mut Graph, edge: Edge) {
        if let Some(edge_to_swap) = Self::find_edge_to_swap(edge, &graph) {
            graph.remove_edge(edge_to_swap);
            let (first_swapped_edge, second_swapped_edge) = Self::swap(edge, edge_to_swap);
            graph.insert_edge(first_swapped_edge);
            graph.insert_edge(second_swapped_edge);
        } else {
            self.candidate_edges.push_back(edge);
        }
    }

    fn find_edge_to_swap(target_edge: Edge, graph: &Graph) -> Option<Edge> {
        graph.edges().find(|edge| {
            let (first_swapped_edge, second_swapped_edge) = Self::swap(*edge, target_edge);
            !graph.contains_edge(first_swapped_edge) && !graph.contains_edge(second_swapped_edge)
        })
    }

    fn swap(first_edge: Edge, second_edge: Edge) -> (Edge, Edge) {
        (
            Edge {
                variable: first_edge.variable,
                constraint: second_edge.constraint,
            },
            Edge {
                variable: second_edge.variable,
                constraint: first_edge.constraint,
            },
        )
    }
}