lal::generate::all_arrangements Class Reference

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

#include <all_arrangements.hpp>

Public Member Functions
	all_arrangements (const lal::graphs::graph &g) noexcept
	Constructor with graph.
	all_arrangements (uint32_t n) noexcept
	Constructor with number of vertices.
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
	Returns the current arrangement and advances the generator.

Private Attributes
const uint32_t	m_n
	Number of vertices.
linear_arrangement	m_arr
	The arrangement generated by this class.
bool	m_reached_end = false
	Has the end of the iteration been reached?

Detailed Description

Exhaustive enumeration of arrangements of any graph.

This class generates all \(n!\) arrangements of an \(n\)-vertex tree. Unlike other generators (e.g. lal::generate::all_projective_arrangements), this class need not be instantiated with a tree but, rather, with a number of vertices due to the simple fact that the tree structure does not matter for the generation of these arrangements. However, constructing this class with a tree (or any graph), is allowed for the sake of consistency.

In order to use this class, you must first provide the number of vertices. 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 can also be instantiated with a graph. Neverthless, only its number of vertices is actually needed.

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

A possible usage of this class is the following:

all_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 (all_arrangements Gen(9); 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:

all_arrangements Gen(8);
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.

Constructor & Destructor Documentation

all_arrangements() [1/2]

lal::generate::all_arrangements::all_arrangements ( const lal::graphs::graph & g )

inlinenoexcept

Constructor with graph.

Parameters

g	Input graph. Only its number of vertices is used.

all_arrangements() [2/2]

lal::generate::all_arrangements::all_arrangements ( uint32_t n )

inlinenoexcept

Constructor with number of vertices.

Parameters

n	Number of vertices of the arrangements.

Member Function Documentation

get_arrangement()

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

inlinenoexcept

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).

next()

void lal::generate::all_arrangements::next ( )

inlinenoexcept

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_arrangements::yield_arrangement ( )

inlinenoexcept

Returns the current arrangement and advances the generator.

This method calls next() after retrieving a copy of the current arrangement.

Returns

The current arrangement.

Member Data Documentation

m_arr

linear_arrangement lal::generate::all_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_arrangements.hpp