Trees

Generation of labeled unrooted trees. More...

Classes
struct	tgen::wtree< VWeight, EWeight >
	Labeled weighted tree generator. More...
struct	tgen::wtree< VWeight, EWeight >::value
	Labeled tree value. More...

Typedefs
template<typename VWeight>
using	tgen::vtree = wtree<VWeight, int>
	Vertex-weighted labeled trees.
template<typename EWeight>
using	tgen::etree = wtree<int, EWeight>
	Edge-weighted labeled trees.
using	tgen::tree = wtree<int, int>
	Unweighted labeled trees.

Detailed Description

Generation of labeled unrooted trees.

Vertices are labeled 0 through n-1. Isomorphism is not factored out: two different labeled trees are distinct.

The template tgen::wtree<VWeight, EWeight> is the general generator. It only randomizes the tree shape (edges); vertex and edge weights are not sampled by the generator. Attach them on tgen::wtree::value with tgen::wtree::value::set_vertex_weights / tgen::wtree::value::set_edge_weights when needed. Use tgen::wtree::value::edge_weighted on an edgeless tree to enable weighted add_edge(u, v, w) calls before any edges exist.

Convenient aliases (same constructors and methods as tgen::wtree):

• tgen::tree — unweighted, tgen::wtree<int, int>;
• tgen::vtree<VWeight> — vertex weight type VWeight, dummy edge weight int, i.e. tgen::wtree<VWeight, int>;
• tgen::etree<EWeight> — edge weight type EWeight, dummy vertex weight int, i.e. tgen::wtree<int, EWeight>.

Examples

Prints a random labeled tree on 10 vertices with edges (0,1) and (2,3) forced.

std::cout << tgen::tree(10).add_edge(0, 1).add_edge(2, 3).gen();

0 1
2 3
3 1
4 9
5 0
6 7
8 1
1 7
7 9

Example generated tree

Prints a skewed random tree on 10 vertices (elongation 3).

std::cout << tgen::tree::gen_skewed(10, 3);

1 0
2 1
3 2
4 3
5 2
6 5
7 6
8 6
9 7

Example generated tree

Tree on 4 vertices with string vertex weights attached after generation.

std::cout << tgen::tree(4).gen().set_vertex_weights<std::string>({"a", "ab", "b", "abc"});

a ab b abc
0 1
0 3
2 3

Example generated tree

Path tree on 4 vertices with edge weights attached incrementally via edge_weighted.

std::cout << tgen::etree<int>::value(4, {}).edge_weighted().add_edge(0, 1, 5).add_edge(1, 2, 6).add_edge(2, 3, 7).print_n();

4
0 1 5
1 2 6
2 3 7

For labeled graphs (fixed n, m, optional direction and self-loops), see the Graphs module and tgen::wgraph.

Typedef Documentation

etree

template<typename EWeight>

using tgen::etree = wtree<int, EWeight>

Edge-weighted labeled trees.

Same as tgen::wtree<int, EWeight> (vertex weight type is a dummy int).

Definition at line 4978 of file tgen.h.

tree

using tgen::tree = wtree<int, int>

Unweighted labeled trees.

Same as tgen::wtree<int, int> (vertex and edge weight types are a dummy int).

Definition at line 4981 of file tgen.h.

vtree

template<typename VWeight>

using tgen::vtree = wtree<VWeight, int>

Vertex-weighted labeled trees.

Same as tgen::wtree<VWeight, int> (edge weight type is a dummy int).

Definition at line 4975 of file tgen.h.