lal::generate::all_bipartite_arrangements Class Reference

Exhaustive enumeration of all bipartite arrangements of any bipartite graph. More...

#include <all_bipartite_arrangements.hpp>

Public Member Functions
template<class graph_t >
	all_bipartite_arrangements (const graph_t &g)
	Constructor with graph.
	all_bipartite_arrangements (const all_bipartite_arrangements &Gen) noexcept=default
	Default copy constructor.
	all_bipartite_arrangements (all_bipartite_arrangements &&Gen) noexcept=default
	Default move constructor.
	all_bipartite_arrangements (const properties::bipartite_graph_coloring &c) noexcept
	Constructor with coloring.
	all_bipartite_arrangements (properties::bipartite_graph_coloring &&c) noexcept
	Constructor with coloring.
	~all_bipartite_arrangements () noexcept=default
	Default destructor.
const linear_arrangement &	get_arrangement () const noexcept
	Returns the current linear arrangemnt.
bool	end () const noexcept
	Returns true if the end of the iteration was reached.
void	next () noexcept
	Generates the next arrangement.
void	reset () noexcept
	Sets the generator to its initial state.
linear_arrangement	yield_arrangement () noexcept
	Constructs the current arrangement.

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 () noexcept
	Initializes this class.
void	init_arrangement (const bool red_first) noexcept
	Initializes this class.

Private Attributes
bool	m_do_mirror
	Has the end of the iteration been reached for mirrored arrangements?
bool	m_reached_end_blue
	Has the end of the iteration been reached for blue vertices?
bool	m_reached_end_red
	Has the end of the iteration been reached for red vertices?
std::size_t	m_n_blue
	Number of blue vertices.
std::size_t	m_n_red
	Number of red vertices.
linear_arrangement	m_arr
	The arrangement generated by this class.
properties::bipartite_graph_coloring	m_coloring
	Coloring of the bipartite graph.

Detailed Description

Exhaustive enumeration of all bipartite arrangements of any bipartite graph.

This class generates all \(|V_1|!\cdot|V_2|!\) bipartite arrangements of a bipartite graph \(B=(V_1\cup V_2, E)\) (see page Types of arrangements for a definition of bipartite arrangements). Unlike other generators (e.g. lal::generate::all_projective_arrangements), this class can be instantiated with the coloring of the bipartite graph, from which the "blue" and "red" vertices are extracted. However, constructing this class with a graph is allowed for the sake of consistency; neverthless, only its number of vertices is actually needed. This is due to the simple fact that the graph structure does not matter for the enumeration of these arrangements.

In order to use this class, you must first provide the coloring of the graph. Arrangements are generated internally, i.e., arragements are encoded in the internal state of the generator. Said state is updated using method next(), which updates it to encode the next arrangement in the generation. In order to retrieve an arrangement, use method get_arrangement(). Upon initialisation, the generator encodes the first arrangement, which has to be retrieved using method get_arrangement().

This class is a wrapper over the C++'s std::next_permutation algorithm.

A possible usage of this class is the following:

lal::generate::all_bipartite_arrangements Gen(g); // t is any graph (tree included)
while (not Gen.end()) {
    const lal::linear_arrangement& arr = Gen.get_arrangement();
    // ...
    Gen.next();
}

When using get_arrangement() in combination with next(), it is important to bear in mind that, if the arrangement is declared as a constant reference, users should not call next() before using the retrieved arrangement. To alleviate this source of bugs, this class can also be used in a for loop:

for (lal::generate::all_bipartite_arrangements Gen(g); not Gen.end(); Gen.next()) {
    const lal::linear_arrangement arr = Gen.get_arrangement();
    // ...
}

This class also has method yield_arrangement() which is aimed at avoiding potential source of bugs:

lal::generate::all_bipartite_arrangements Gen(g);
while (not Gen.end()) {
    const lal::linear_arrangement& arr = Gen.yield_arrangement();
    // ...
}

Note that the arrangement is not declared as a constant reference since method yield_arrangement() returns the tree as a copy.

Furthermore, if the biparite coloring object (lal::properties::bipartite_graph_coloring) of the graph g already exists, then one can construct this class using said object.

lal::properties::bipartite_graph_coloring c = lal::properties::coloring(g);
lal::generate::all_bipartite_arrangements Gen(c);
while (not Gen.end()) {
    const lal::linear_arrangement& arr = Gen.yield_arrangement();
    // ...
}

Constructor & Destructor Documentation

all_bipartite_arrangements() [1/5]

template<class graph_t >

lal::generate::all_bipartite_arrangements::all_bipartite_arrangements ( const graph_t & g )

inline

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.

Precondition

The input graph g is bipartite.

all_bipartite_arrangements() [2/5]

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

defaultnoexcept

Default copy constructor.

Parameters

Gen	Exhaustive bipartite arrangement generator.

all_bipartite_arrangements() [3/5]

lal::generate::all_bipartite_arrangements::all_bipartite_arrangements ( all_bipartite_arrangements && Gen )

defaultnoexcept

Default move constructor.

Parameters

Gen	Exhaustive bipartite arrangement generator.

all_bipartite_arrangements() [4/5]

lal::generate::all_bipartite_arrangements::all_bipartite_arrangements ( const properties::bipartite_graph_coloring & c )

inlinenoexcept

Constructor with coloring.

Parameters

c	Input coloring of a bipartite graph.

all_bipartite_arrangements() [5/5]

lal::generate::all_bipartite_arrangements::all_bipartite_arrangements ( properties::bipartite_graph_coloring && c )

inlinenoexcept

Constructor with coloring.

Parameters

c	Input coloring of a bipartite graph.

Member Function Documentation

get_arrangement()

const linear_arrangement & lal::generate::all_bipartite_arrangements::get_arrangement ( ) const

inlinenodiscardnoexcept

Returns the current linear arrangemnt.

Recall that method next() should not be called until the arrangement has been processed if such an arrangement was declared as a constant reference.

Returns

A permutation of the vertices (a.k.a. a linear arrangement).

init()

void lal::generate::all_bipartite_arrangements::init ( )

privatenoexcept

Initializes this class.

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

init_arrangement()

void lal::generate::all_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.

next()

void lal::generate::all_bipartite_arrangements::next ( )

noexcept

Generates the next arrangement.

Modifies the internal state so that the next arrangement can be retrieved using method get_arrangement.

yield_arrangement()

linear_arrangement lal::generate::all_bipartite_arrangements::yield_arrangement ( )

inlinenodiscardnoexcept

Constructs the current arrangement.

Returns

The current arrangement.

Postcondition

This generator is moved to the next arrangement.

Member Data Documentation

m_arr

linear_arrangement lal::generate::all_bipartite_arrangements::m_arr

private

The arrangement generated by this class.

Actually, generated by the std::next_permutation algorithm.

---

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

• lal/generate/all_bipartite_arrangements.hpp