lal::generate::all_projective_arrangements Class Reference

Exhaustive enumeration of projective arrangements of a labeled 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, node root) noexcept
	Constructor with free tree and a root vertex.
	all_projective_arrangements (const all_projective_arrangements &Gen)=default
	Default copy constructor.
	all_projective_arrangements (all_projective_arrangements &&Gen)=default
	Default move constructor.
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	initialise_intervals_tree () noexcept
	Initialise the interval every node of the tree, starting at r.
void	initialise_interval_node (node u) noexcept
	Initialise the interval of node u.

Private Attributes
const graphs::rooted_tree &	m_rT
	Constant reference to rooted tree.
std::vector< std::vector< 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 labeled rooted tree.

Generates all projective arrangements of a given rooted tree.

The arrangements generated do not take into account the symmetrical 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.

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 [15] and [14].

A possible usage of this class is the following:

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

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

default

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 )

default

Default move constructor.

Parameters

Gen	Exhaustive projective arrangement generator.

Member Function Documentation

end()

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

inlinenoexcept

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

noexcept

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

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.

---

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

• lal/generate/all_projective_arrangements.hpp