lal::generate::all_projective_arrangements Class Reference

Exhaustive enumeration of projective arrangements of a rooted tree. More...

#include <all_projective_arrangements.hpp>

Public Member Functions
	all_projective_arrangements (const graphs::rooted_tree &T) noexcept
	Constructor with rooted tree.
	all_projective_arrangements (const graphs::free_tree &T, const node root) noexcept
	Constructor with free tree and a root vertex.
	all_projective_arrangements (const all_projective_arrangements &Gen) noexcept=default
	Default copy constructor.
	all_projective_arrangements (all_projective_arrangements &&Gen) noexcept=default
	Default move constructor.
	~all_projective_arrangements () noexcept=default
	Default destructor.
bool	end () const noexcept
	Returns whether there are more arrangements to generate.
linear_arrangement	get_arrangement () const noexcept
	Constructs the current arrangement.
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 Member Functions
void	initialize_intervals_tree () noexcept
	Initialize the interval every node of the tree, starting at r.
void	initialize_interval_node (const node u) noexcept
	Initialize the interval of node u.

Private Attributes
const graphs::rooted_tree &	m_rT
	Constant reference to rooted tree.
detail::array< detail::array< node > >	m_intervals
	The interval of every node of the tree.
bool	m_reached_end = false
	Has the end of the generation been reached?

Detailed Description

Exhaustive enumeration of projective arrangements of a rooted tree.

This class does not take into account the symmetries between arrangements produced by swapping leaves of the tree connected to the same parent. That is, the arrangements produced can be seen as arrangements of labelled trees. Therefore, this class will generate \(n!\) arrangements for a star tree of \(n\) vertices.

See Types of arrangements for the definition of projective arrangements.

In order to use this class, you must first provide the tree object in the constructor. Arrangements are generated internally, i.e., they 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 implements the algorithm outlined in [25] and [24].

A possible usage of this class is the following:

lal::generate::all_projective_arrangements Gen(t); // t is a rooted tree
while (not Gen.end()) {
    const lal::linear_arrangement& arr = Gen.get_arrangement();
    // ...
    Gen.next();
}

Alternatively, this class can be used in a for loop:

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

This class also has method yield_arrangement() which is aimed at simplifying this class' usage:

lal::generate::all_projective_arrangements Gen(t); // t is a rooted tree
while (not Gen.end()) {
    const lal::linear_arrangement arr = Gen.yield_arrangement();
    // ...
}

Constructor & Destructor Documentation

all_projective_arrangements() [1/4]

lal::generate::all_projective_arrangements::all_projective_arrangements ( const graphs::rooted_tree & T )

noexcept

Constructor with rooted tree.

Parameters

T	Rooted tree

Precondition

The object T is a valid rooted tree (see graphs::rooted_tree::is_rooted_tree).

all_projective_arrangements() [2/4]

lal::generate::all_projective_arrangements::all_projective_arrangements ( const graphs::free_tree & T, const node root )

inlinenoexcept

Constructor with free tree and a root vertex.

Parameters

T	Free tree
root	Root vertex

Precondition

The object T is a valid tree (see graphs::rooted_tree::is_rooted_tree).

all_projective_arrangements() [3/4]

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

defaultnoexcept

Default copy constructor.

Parameters

Gen	Exhaustive projective arrangement generator.

all_projective_arrangements() [4/4]

lal::generate::all_projective_arrangements::all_projective_arrangements ( all_projective_arrangements && Gen )

defaultnoexcept

Default move constructor.

Parameters

Gen	Exhaustive projective arrangement generator.

Member Function Documentation

end()

bool lal::generate::all_projective_arrangements::end ( ) const

inlinenodiscardnoexcept

Returns whether there are more arrangements to generate.

Returns

True if there are still more arrangements to generate. Returns false if all arrangements have been generated.

get_arrangement()

linear_arrangement lal::generate::all_projective_arrangements::get_arrangement ( ) const

nodiscardnoexcept

Constructs the current arrangement.

Returns

The arrangement generated with method next().

Precondition

Method next must have been called at least once.

next()

void lal::generate::all_projective_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_projective_arrangements::yield_arrangement ( )

inlinenodiscardnoexcept

Returns the current arrangement and advances the generator.

Returns

The current arrangement.

Postcondition

This generator is moved to the next arrangement.

---

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

• lal/generate/all_projective_arrangements.hpp