lal::generate::rand_bipartite_arrangements Class Reference

Random generation of arrangements of any bipartite graph. More...

#include <rand_bipartite_arrangements.hpp>

Public Member Functions
template<class graph_t >
	rand_bipartite_arrangements (const graph_t &g, const uint64_t seed=0) noexcept
	Constructor with graph.
	rand_bipartite_arrangements (const rand_bipartite_arrangements &Gen) noexcept=default
	Default copy constructor.
	rand_bipartite_arrangements (rand_bipartite_arrangements &&Gen) noexcept=default
	Default move constructor.
	rand_bipartite_arrangements (const properties::bipartite_graph_coloring &c, const uint64_t seed=0) noexcept
	Constructor with coloring.
	rand_bipartite_arrangements (properties::bipartite_graph_coloring &&c, const uint64_t seed=0) noexcept
	Constructor with coloring.
const linear_arrangement &	get_arrangement () noexcept
	Returns a linear arrangement constructed uniformly at random.
const linear_arrangement &	yield_arrangement () noexcept
	Returns a linear arrangement constructed uniformly at random.

Properties
	:bipartite_graph_coloring::color_t blue = properties::bipartite_graph_coloring::blue
	Shortcut to blue color.
	:bipartite_graph_coloring::color_t red = properties::bipartite_graph_coloring::red
	Shortcut to red color.

Private Member Functions
void	init (const uint64_t seed) noexcept
	Initializes this class.
void	init_arrangement (const bool red_first) noexcept
	Initializes this class.

Private Attributes
std::size_t	m_n_blue
	Number of blue vertices.
std::size_t	m_n_red
	Number of red vertices.
std::mt19937	m_gen
	Random number generator.
std::bernoulli_distribution	m_red_or_blue
	Boolean values generator.
linear_arrangement	m_arr
	The arrangement generated by this class.
properties::bipartite_graph_coloring	m_coloring
	Coloring of the bipartite graph.
properties::bipartite_graph_coloring::color_t	m_what_in_left
	What color do we find in the left half?

Detailed Description

Random generation of arrangements of any bipartite graph.

This class generates bipartite linear arrangements uniformly at random (see page Types of arrangements for a definition of bipartite arrangements). This class can be instantiated with a (bipartite) graph, or with the coloring of one.

A possible usage of this class is the following:

// given a tree T (or any other bipartite graph)
lal::generate::rand_bipartite_arrangements Gen(T);
for (int i = 0; i < 100; ++i) {
    const lal::linear_arrangement& arr = Gen.get_arrangement();
    // ...
}

Equivalently,

// given a tree T (or any other bipartite graph)
lal::properties::bipartite_graph_coloring c = lal::properties::coloring(T);
lal::generate::rand_bipartite_arrangements Gen(c);
for (int i = 0; i < 100; ++i) {
    const lal::linear_arrangement& arr = Gen.yield_arrangement();
    // ...
}

Constructor & Destructor Documentation

rand_bipartite_arrangements() [1/5]

template<class graph_t >

lal::generate::rand_bipartite_arrangements::rand_bipartite_arrangements ( const graph_t & g, const uint64_t seed = 0 )

inlinenoexcept

Constructor with graph.

This constructor needs to calculate the bipartite coloring of the graph.

Template Parameters

graph_t

Graph type. A subclass of lal::graphs::graph.

Parameters

g	Input graph.
seed	Integer value to seed the random number generator.

Precondition

The input graph g is bipartite.

rand_bipartite_arrangements() [2/5]

lal::generate::rand_bipartite_arrangements::rand_bipartite_arrangements ( const rand_bipartite_arrangements & Gen )

defaultnoexcept

Default copy constructor.

Parameters

Gen	Exhaustive bipartite arrangement generator.

rand_bipartite_arrangements() [3/5]

lal::generate::rand_bipartite_arrangements::rand_bipartite_arrangements ( rand_bipartite_arrangements && Gen )

defaultnoexcept

Default move constructor.

Parameters

Gen	Exhaustive bipartite arrangement generator.

rand_bipartite_arrangements() [4/5]

lal::generate::rand_bipartite_arrangements::rand_bipartite_arrangements ( const properties::bipartite_graph_coloring & c, const uint64_t seed = 0 )

inlinenoexcept

Constructor with coloring.

Parameters

c	Input coloring of a bipartite graph.
seed	Integer value to seed the random number generator.

rand_bipartite_arrangements() [5/5]

lal::generate::rand_bipartite_arrangements::rand_bipartite_arrangements ( properties::bipartite_graph_coloring && c, const uint64_t seed = 0 )

inlinenoexcept

Constructor with coloring.

Parameters

c	Input coloring of a bipartite graph.
seed	Integer value to seed the random number generator.

Member Function Documentation

init()

void lal::generate::rand_bipartite_arrangements::init ( const uint64_t seed )

privatenoexcept

Initializes this class.

Initializes the arrangement (m_arr) and the number of blue and red vertices (m_n_blue and m_n_red).

Parameters

seed	Seed for the random number generator.

init_arrangement()

void lal::generate::rand_bipartite_arrangements::init_arrangement ( const bool red_first )

privatenoexcept

Initializes this class.

Initializes the arrangement by placing the red or blue vertices in the left side of the arrangement depending on the value of the parameter.

Parameters

red_first

Place red vertices first if true.

Member Data Documentation

m_arr

linear_arrangement lal::generate::rand_bipartite_arrangements::m_arr

private

The arrangement generated by this class.

Actually, generated by the std::next_permutation algorithm.

m_red_or_blue

std::bernoulli_distribution lal::generate::rand_bipartite_arrangements::m_red_or_blue

private

Boolean values generator.

To decide what color goes at the left half.

---

The documentation for this class was generated from the following file:

• lal/generate/rand_bipartite_arrangements.hpp