tgen::wtree< VWeight, EWeight >

Labeled weighted tree generator. More...

Inheritance diagram for tgen::wtree< VWeight, EWeight >:

Classes
struct	value
	Labeled tree value. More...

Public Member Functions
	wtree (int n)
	Creates a tree generator with specified number of vertices.
wtree &	add_edge (int u, int v)
	Restricts generator s.t. some edge is present.
value	gen () const
	Generates a uniformly random value from the set of valid trees.
Public Member Functions inherited from tgen::gen_base< wtree< VWeight, EWeight > >
auto	gen_list (int size, Args &&...args) const
	Generates a list of several generation calls.
auto	gen_until (Pred predicate, int max_tries, Args &&...args) const
	Generates a random value from the valid set until a condition is met.
auto	distinct (Args &&...args) const
	Creates distinct generator for current generator.

Static Public Member Functions
static value	gen_skewed (int n, int elongation)
	Random skewed tree (large diameter).
static value	gen_kruskal (int n)
	Kruskal-like random labeled tree.

Detailed Description

template<typename VWeight, typename EWeight>
struct tgen::wtree< VWeight, EWeight >

Labeled weighted tree generator.

Defines a set of trees on n vertices, subject to preset edges. A uniformly random tgen::wtree::value from that set (satisfying the constraints) is produced by tgen::wtree::gen.

There are also structured, non-uniform static generation methods:

• For random skewed trees (with large diameter): tgen::wtree::gen_skewed.

Definition at line 4356 of file tgen.h.

Constructor & Destructor Documentation

wtree()

template<typename VWeight, typename EWeight>

tgen::wtree< VWeight, EWeight >::wtree ( int n )

inline

Creates a tree generator with specified number of vertices.

Parameters

n	Number of vertices.

Complexity

O(1).

Examples

// Tree generator on 10 vertices.
auto tree_gen = tgen::tree(10);

Definition at line 4362 of file tgen.h.

Member Function Documentation

add_edge()

template<typename VWeight, typename EWeight>

wtree & tgen::wtree< VWeight, EWeight >::add_edge ( int u, int v )

inline

Restricts generator s.t. some edge is present.

Parameters

u	First endpoint.
v	Second endpoint.

Preset edges must not form a cycle.

Complexity

O(log n).

Examples

// Tree generator on 5 vertices with edge (0,1) forced.
auto tree_gen = tgen::tree(5).add_edge(0, 1);

Definition at line 4368 of file tgen.h.

gen()

template<typename VWeight, typename EWeight>

value tgen::wtree< VWeight, EWeight >::gen ( ) const

inline

Generates a uniformly random value from the set of valid trees.

Returns

A uniformly random tgen::tree::value from the set of valid trees, given the added restrictions.

Complexity

O(n).

Examples

// Prints a uniformly random labeled tree on 4 vertices.
std::cout <<  tgen::tree(4).gen();

Definition at line 4883 of file tgen.h.

gen_kruskal()

template<typename VWeight, typename EWeight>

value tgen::wtree< VWeight, EWeight >::gen_kruskal ( int n )

inlinestatic

Kruskal-like random labeled tree.

Parameters

n	Vertex count.

Returns

A tgen::wtree::value on n vertices.

Repeatedly samples a random vertex pair and adds it when it connects two different components (union-find), until the graph is a tree.

Note

This operation is not uniformly random.

Complexity

O(n log(n) alpha(n)) expected time.

Examples

std::cout << tgen::tree::gen_kruskal(10);

Definition at line 4950 of file tgen.h.

gen_skewed()

template<typename VWeight, typename EWeight>

value tgen::wtree< VWeight, EWeight >::gen_skewed ( int n, int elongation )

inlinestatic

Random skewed tree (large diameter).

Parameters

n	Vertex count.
elongation	Passed to tgen::wnext; controls how star-like or path-like the tree is.

Returns

A random skewed tgen::wtree::value on n vertices.

For each i from 1 to n-1, the parent of i is tgen::wnext(i, elongation), in [0, i).

If elongation is small (negative), you will likely get a star.
If elongation is large (positive), you will likely get a path.

Note

This operation is not uniformly random.

Complexity

O(n).

Examples

// Prints a random skewed tree on 50 vertices, likely similar to a path.
std::cout << tgen::tree::gen_skewed(50, 10);

Definition at line 4940 of file tgen.h.

---

The documentation for this struct was generated from the following files:

• /home/runner/work/tgen/tgen/single_include/tgen.h
• tree.dox