lal::generate::all_planar_arrangements Class Reference

Exhaustive enumeration of planar arrangements of a labeled free tree. More...

#include <all_planar_arrangements.hpp>

Public Member Functions
	all_planar_arrangements (const graphs::free_tree &T) noexcept
	Constructor with constant reference to a free tree. More...
	all_planar_arrangements (const graphs::rooted_tree &T) noexcept
	Constructor with rooted tree. More...
	all_planar_arrangements (const all_planar_arrangements &Gen)=default
	Default copy constructor. More...
	all_planar_arrangements (all_planar_arrangements &&Gen)=default
	Default move constructor. More...
	~all_planar_arrangements () noexcept=default
	Default destructor.
bool	end () const noexcept
	Returns whether there are more arrangements to generate. More...
linear_arrangement	get_arrangement () const noexcept
	Constructs the current arrangement. More...
void	next () noexcept
	Generates the next arrangement. More...
void	reset () noexcept
	Sets the generator to its initial state.
linear_arrangement	yield_arrangement () noexcept
	Constructs the current arrangement. More...

Private Member Functions
void	initialise_intervals_tree () noexcept
	Initiales the interval of every node of the tree.
void	initialise_interval_node (node v, node parent) noexcept
	Initialise the interval of node v, whose parent vertex is parent.

Private Attributes
graphs::free_tree	m_T_copy
	A copy of a free tree. More...
const graphs::free_tree &	m_T
	Constant reference to free tree.
node	m_root
	Vertex at which we root the tree.
detail::data_array< std::vector< node > >	m_intervals
	The interval of every node of the tree.
detail::data_array< char >	m_memory_bit_sort
	Array for the bit sort algorithm.
bool	m_reached_end = false
	Has the end of the generation been reached?

Detailed Description

Exhaustive enumeration of planar arrangements of a labeled free tree.

Generates all planar arrangements of a given free tree.

The arrangements generated do not take into account the symmetrical arrangements produced by swapping leaves of the tree connected to the same vertex. 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 in [4].

A possible usage of this class is the following:

all_planar_arrangements Gen(t); // t is a free 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_planar_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_planar_arrangements Gen(t); // t is a free tree
while (not Gen.end()) {
    const lal::linear_arrangement arr = Gen.yield_arrangement();
    // ...
}

Constructor & Destructor Documentation

all_planar_arrangements() [1/4]

lal::generate::all_planar_arrangements::all_planar_arrangements ( const graphs::free_tree &  T )

noexcept

Constructor with constant reference to a free tree.

Parameters

T	Input free tree

Precondition

The object T is a valid tree (see graphs::free_tree::is_tree).

all_planar_arrangements() [2/4]

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

noexcept

Constructor with rooted tree.

This constructor transforms the input rooted tree into a free tree.

Parameters

T	Input rooted tree

Precondition

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

all_planar_arrangements() [3/4]

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

default

Default copy constructor.

Parameters

Gen	Exhaustive planar arrangement generator.

all_planar_arrangements() [4/4]

lal::generate::all_planar_arrangements::all_planar_arrangements ( all_planar_arrangements &&  Gen )

default

Default move constructor.

Parameters

Gen	Exhaustive planar arrangement generator.

Member Function Documentation

end()

bool lal::generate::all_planar_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_planar_arrangements::get_arrangement ( ) const

noexcept

Constructs the current arrangement.

Returns

Returns the arrangement generated with method next().

Precondition

Method next must have been called at least once.

next()

void lal::generate::all_planar_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_planar_arrangements::yield_arrangement ( )

inlinenoexcept

Constructs the current arrangement.

Returns

The current arrangement.

Postcondition

This generator is moved to the next arrangement.

Member Data Documentation

m_T_copy

graphs::free_tree lal::generate::all_planar_arrangements::m_T_copy

private

A copy of a free tree.

Used only when this class is constructed with a rooted tree.

---

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

• lal/generate/all_planar_arrangements.hpp