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 (const uint64_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
	Constructs the current arrangement.

Private Attributes
const uint64_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:

lal::generate::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 (lal::generate::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:

lal::generate::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 ( const uint64_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

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

◆ next()

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

Public Member Functions

Private Attributes