tgen::wtree< VWeight, EWeight >::value

Labeled tree value. More...

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

Public Member Functions
	value (const std::vector< std::set< int > > &adj)
	Builds a tree from an adjacency list.
	value (int n, const std::vector< std::pair< int, int > > &edges)
	Builds a tree from a vertex count and an edge list.
	value (const typename wgraph< VWeight, EWeight >::value &g)
	Builds a tree from a graph via a Kruskal-like random spanning tree.
int	n () const
	Returns the number of vertices.
const std::vector< std::set< int > > &	adj () const
	Adjacency list.
const std::vector< std::pair< int, int > > &	edges () const
	Edge list.
const std::optional< std::vector< VWeight > > &	vertex_weights () const
	Optional vertex weights.
const std::optional< std::vector< EWeight > > &	edge_weights () const
	Optional edge weights.
template<typename NewVWeight = VWeight>
wtree< NewVWeight, EWeight >::value	set_vertex_weights (const std::vector< NewVWeight > &vertex_weights) const
	Attaches vertex weights.
template<typename NewEWeight = EWeight>
wtree< VWeight, NewEWeight >::value	set_edge_weights (const std::vector< NewEWeight > &edge_weights) const
	Attaches edge weights.
value &	edge_weighted ()
	Enables edge-weighted mode on an edgeless tree.
value &	add_1 ()
	Adds 1 for printing.
value &	print_n ()
	Prints the number of vertices before the tree.
value &	print_parents (int root=-1)
	Prints in parent format instead of edge list.
value &	shuffle_except (std::set< int > indices)
	Shuffles vertices except given vertices, and edge order.
value &	shuffle ()
	Shuffles vertices and edge order.
value &	link (const value &rhs, int new_u, int new_v, std::optional< EWeight > new_w=std::nullopt)
	Links two trees by an edge.
value &	glue (const value &rhs, std::set< std::pair< int, int > > index_pairs)
	Glues another tree at given vertex pairs.
value &	glue (const value &rhs, std::set< int > indices)
	Glues another tree at given vertices.
std::pair< int, std::vector< std::set< int > > >	to_std () const
	Converts the tree to a std types.
Public Member Functions inherited from tgen::gen_value_base< value >
bool	operator< (const value &rhs) const

Friends
std::ostream &	operator<< (std::ostream &out, const value &val)
	Prints the tree to an output stream.

Detailed Description

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

Labeled tree value.

Adjacency list tgen::wtree::value::adj is symmetric, and each undirected edge is listed once in the edge list tgen::wtree::value::edges, as (u, v) with u < v.

It can be printed through std::cout.

Definition at line 4383 of file tgen.h.

Constructor & Destructor Documentation

value() [1/3]

template<typename VWeight, typename EWeight>

tgen::wtree< VWeight, EWeight >::value::value ( const std::vector< std::set< int > > & adj )

inline

Builds a tree from an adjacency list.

Parameters

adj	Adjacency list; adj[u] contains every neighbor of u.

Adjacency list must be symmetric, and must form a tree.

Complexity

O(n).

Examples

// Builds a path on 3 vertices from an adjacency list.
std::vector<std::set<int>> a(3);
a[0] = {1};
a[1] = {0, 2};
a[2] = {1};
tgen::tree::value t(a);

Definition at line 4400 of file tgen.h.

value() [2/3]

template<typename VWeight, typename EWeight>

tgen::wtree< VWeight, EWeight >::value::value ( int n, const std::vector< std::pair< int, int > > & edges )

inline

Builds a tree from a vertex count and an edge list.

Parameters

n	Number of vertices.
edges	List of undirected edges.

Each edge (u, v) must be listed once with u < v, and must form a tree.

Complexity

O(n).

Examples

// Builds a path on 3 vertices from an edge list.
tgen::tree::value t(3, {{0, 1}, {1, 2}});

Definition at line 4420 of file tgen.h.

value() [3/3]

template<typename VWeight, typename EWeight>

tgen::wtree< VWeight, EWeight >::value::value

(

const typename wgraph< VWeight, EWeight >::value &

g

)

Builds a tree from a graph via a Kruskal-like random spanning tree.

Parameters

g	Undirected connected graph.

Shuffles the edges of g and greedily adds them while avoiding cycles, in the spirit of Kruskal's algorithm. The result is a random spanning tree.

Vertex and edge weights are copied when the weight types match.

Note

This operation is not uniformly random.

Complexity

O(n + m alpha(n)).

Examples

auto g = tgen::graph(10, 20).gen();
auto t = tgen::tree::value(g);

Definition at line 6276 of file tgen.h.

Member Function Documentation

add_1()

template<typename VWeight, typename EWeight>

value & tgen::wtree< VWeight, EWeight >::value::add_1 ( )

inline

Adds 1 for printing.

This makes it so, when given to std::cout, the tree will be printed with labels 1-based. Weights are not affected.

Complexity

O(1).

Examples

// Shifts printed vertex indices by one (internal ids stay 0-based).
auto t = tgen::tree::value(3, {{0, 1}, {1, 2}});
std::cout << t.add_1(); // Prints "1 2\n2 3\n".

Definition at line 4524 of file tgen.h.

adj()

template<typename VWeight, typename EWeight>

const std::vector< std::set< int > > & tgen::wtree< VWeight, EWeight >::value::adj ( ) const

inline

Adjacency list.

Returns

Constant reference to the adjacency list.

Edges appear in both directions in adj.

Examples

// Prints the degree of vertex 1 in a 3-vertex path.
auto t = tgen::tree::value(3, {{0, 1}, {1, 2}});
std::cout << t.adj()[1].size() << std::endl; // Prints "2".

Definition at line 4467 of file tgen.h.

edge_weighted()

template<typename VWeight, typename EWeight>

value & tgen::wtree< VWeight, EWeight >::value::edge_weighted ( )

inline

Enables edge-weighted mode on an edgeless tree.

After this call, add_edge(u, v, w) accepts a weight for each new edge.

Precondition

The tree has no edges.

Returns

*this (mutating).

Complexity

O(1).

Examples

// Build a weighted tree edge by edge.
tgen::etree<int>::value t(4, {});
t.edge_weighted();
t.add_edge(0, 1, 5);
t.add_edge(1, 2, 6);
t.add_edge(2, 3, 7);
std::cout << t;

Definition at line 4511 of file tgen.h.

edge_weights()

template<typename VWeight, typename EWeight>

const std::optional< std::vector< EWeight > > & tgen::wtree< VWeight, EWeight >::value::edge_weights ( ) const

inline

Optional edge weights.

Returns

Constant reference to the optional edge-weight vector, aligned with edges();

Index i corresponds to edges()[i]. Absent when the tree has no edge weights.

Examples

// Prints weight of first edge.
auto t = tgen::tree::value(3, {{0, 1}, {1, 2}}).set_edge_weights({30, 40});
std::cout << (*t.edge_weights())[0] << std::endl; // Prints "30".

Definition at line 4478 of file tgen.h.

edges()

template<typename VWeight, typename EWeight>

const std::vector< std::pair< int, int > > & tgen::wtree< VWeight, EWeight >::value::edges ( ) const

inline

Edge list.

Returns

Constant reference to the edge list.

Each edge (u, v) appears only once, with u < v. The order matches optional edge weights when present.

Examples

// Prints every edge of a path on 4 vertices.
for (const auto &[u, v] : tgen::tree::value(4, {{0, 1}, {1, 2}, {2, 3}}).edges())
    std::cout << u << " " << v << "\n";

Definition at line 4470 of file tgen.h.

glue() [1/2]

template<typename VWeight, typename EWeight>

value & tgen::wtree< VWeight, EWeight >::value::glue ( const value & rhs, std::set< int > indices )

inline

Glues another tree at given vertices.

Parameters

rhs	Other tree to be glued.
indices	Set of vertex labels: for each i in indices, vertex i is glued to vertex i in rhs.

Gluing one vertex to another means they are considered to be the same vertex, maintaining the label it had in this graph. Other vertices are shifted accordingly.

Complexity

O(rhs.n * log n) amortized.

That is, the complexity depends mostly on the rhs tree.

Examples

// Glues two 3-vertex paths at vertex 0.
tgen::tree::value a(3, {{0, 1}, {1, 2}});
tgen::tree::value b(3, {{0, 1}, {1, 2}});
a.glue(b, {0});
std::cout << a.n() << std::endl; // Prints "5".

Definition at line 4746 of file tgen.h.

glue() [2/2]

template<typename VWeight, typename EWeight>

value & tgen::wtree< VWeight, EWeight >::value::glue ( const value & rhs, std::set< std::pair< int, int > > index_pairs )

inline

Glues another tree at given vertex pairs.

Parameters

rhs	Other tree to be glued.
index_pairs	Set of (l, r) pairs: vertex l is glued to vertex r in rhs.

Gluing one vertex to another means they are considered to be the same vertex, maintaining the label it had in this tree. Other vertices are shifted accordingly.

Complexity

O(rhs.n * log n) amortized.

That is, the complexity depends mostly on the rhs tree.

Examples

// Glues two trees by identifying vertex 1 (left) with vertex 0 (right).
tgen::tree::value left(4, {{0, 1}, {1, 2}, {2, 3}});
tgen::tree::value right(3, {{0, 1}, {1, 2}});
left.glue(right, {{1, 0}});
std::cout << left;

Definition at line 4686 of file tgen.h.

link()

template<typename VWeight, typename EWeight>

value & tgen::wtree< VWeight, EWeight >::value::link ( const value & rhs, int new_u, int new_v, std::optional< EWeight > new_w = std::nullopt )

inline

Links two trees by an edge.

Parameters

rhs	Second tree.
new_u	Endpoint in this tree.
new_v	Endpoint in rhs before relabeling.
new_w	Optional weight of the connecting edge.

Vertices on rhs are shifted by the current n. Weight usage must be consistent.

Complexity

O(rhs.n * log n) amortized.

That is, the complexity depends mostly on the rhs tree.

Examples

// Links two 2-vertex paths with one new edge; prints total vertex count.
tgen::tree::value a(2, {{0, 1}});
tgen::tree::value b(2, {{0, 1}});
a.link(b, 0, 0);
std::cout << a.n() << std::endl; // Prints "4".

Definition at line 4659 of file tgen.h.

n()

template<typename VWeight, typename EWeight>

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

inline

Returns the number of vertices.

Returns

The number of vertices.

Examples

// Prints the vertex count of a path on 5 vertices.
auto t = tgen::tree::value(5, {{0, 1}, {1, 2}, {2, 3}, {3, 4}});
std::cout << t.n() << std::endl; // Prints "5".

Definition at line 4464 of file tgen.h.

print_n()

template<typename VWeight, typename EWeight>

value & tgen::wtree< VWeight, EWeight >::value::print_n ( )

inline

Prints the number of vertices before the tree.

Complexity

O(1).

Examples

// Stream with a leading line giving the vertex count.
auto t = tgen::tree::value(3, {{0, 1}, {1, 2}});
std::cout << t.print_n(); // Prints "3\n0 1\n1 2\n".

Definition at line 4531 of file tgen.h.

print_parents()

template<typename VWeight, typename EWeight>

value & tgen::wtree< VWeight, EWeight >::value::print_parents ( int root = -1 )

inline

Prints in parent format instead of edge list.

Parameters

root	Root choice: -1 uses vertex 0 and omits its parent; n picks a random root; otherwise an explicit root in [0, n).

Incompatible with edge weights.

Complexity

O(1).

Examples

// Prints in parent format (root -1: vertex 0 root, its parent is omitted).
auto t = tgen::tree::value(3, {{0, 1}, {1, 2}});
std::cout << t.print_parents(); // Prints "0 1\n".

Definition at line 4540 of file tgen.h.

set_edge_weights()

template<typename VWeight, typename EWeight>

template<typename NewEWeight = EWeight>

wtree< VWeight, NewEWeight >::value tgen::wtree< VWeight, EWeight >::value::set_edge_weights ( const std::vector< NewEWeight > & edge_weights ) const

inline

Attaches edge weights.

Parameters

edge_weights

One weight per edge, in the same order as edges().

Returns

A copy of this tree with edge_weights attached. The weight type is deduced.

Immutable style: returns a copy with weights set (weight type deduced); does not modify *this.

Complexity

O(n).

Examples

// Returns a copy with edge weights; prints edges with weights.
auto t = tgen::tree::value(3, {{0, 1}, {1, 2}});
auto w = t.set_edge_weights({9, 10});
std::cout << w; // Prints "0 1 9\n1 2 10\n".

Definition at line 4499 of file tgen.h.

set_vertex_weights()

template<typename VWeight, typename EWeight>

template<typename NewVWeight = VWeight>

wtree< NewVWeight, EWeight >::value tgen::wtree< VWeight, EWeight >::value::set_vertex_weights ( const std::vector< NewVWeight > & vertex_weights ) const

inline

Attaches vertex weights.

Parameters

vertex_weights

One weight per vertex (n values).

Returns

A copy of this tree with vertex_weights attached. The weight type is deduced.

Immutable style: returns a copy with weights set (weight type deduced); does not modify *this.

Complexity

O(n).

Examples

// Returns a copy with vertex weights; prints weight line then edges.
auto t = tgen::tree::value(3, {{0, 1}, {1, 2}});
auto w = t.set_vertex_weights({1, 2, 3});
std::cout << w; // Prints "1 2 3\n0 1\n1 2\n".

Definition at line 4485 of file tgen.h.

shuffle()

template<typename VWeight, typename EWeight>

value & tgen::wtree< VWeight, EWeight >::value::shuffle ( )

inline

Shuffles vertices and edge order.

Shuffles all vertices and edge order. Equivalent to shuffle_except({}).

Complexity

O(n).

Examples

// Randomly relabels all vertices and shuffles edge order.
auto t = tgen::tree(8).gen();
std::cout << t.shuffle();

Definition at line 4621 of file tgen.h.

shuffle_except()

template<typename VWeight, typename EWeight>

value & tgen::wtree< VWeight, EWeight >::value::shuffle_except ( std::set< int > indices )

inline

Shuffles vertices except given vertices, and edge order.

Parameters

indices

Vertex ids to keep fixed; every other vertex is relabeled by a random permutation.

Complexity

O(n).

Examples

// Keeps vertex 0 fixed, randomly relabels the rest and shuffles edge order.
auto t = tgen::tree(8).gen();
std::cout << t.shuffle_except({0});

Definition at line 4552 of file tgen.h.

to_std()

template<typename VWeight, typename EWeight>

std::pair< int, std::vector< std::set< int > > > tgen::wtree< VWeight, EWeight >::value::to_std ( ) const

inline

Converts the tree to a std types.

Returns

(n, adj) as a std::pair.

Examples

// Converts to (n, adjacency list) and prints n and adjacency list.
auto [n, adj] = tgen::tree::value(3, {{0, 1}, {1, 2}}).to_std();
std::cout << n << std::endl << tgen::print(adj) << std::endl; // Prints "3\n1\n0 2\n1\n".

Definition at line 4846 of file tgen.h.

vertex_weights()

template<typename VWeight, typename EWeight>

const std::optional< std::vector< VWeight > > & tgen::wtree< VWeight, EWeight >::value::vertex_weights ( ) const

inline

Optional vertex weights.

Returns

Constant reference to the optional vertex-weight vector.

Absent when the tree has no edge weights.

Examples

// Prints weight of vertex 0.
auto t = tgen::tree::value(2, {{0, 1}}).set_vertex_weights({7, 8});
std::cout << (*t.vertex_weights())[0] << std::endl; // Prints "7".

Definition at line 4473 of file tgen.h.

Friends And Related Symbol Documentation

operator<<

template<typename VWeight, typename EWeight>

std::ostream & operator<< ( std::ostream & out, const value & val )

friend

Prints the tree to an output stream.

Parameters

out	Output stream.
val	Tree to write.

Optional n line when print_n is set, optional vertex-weight line, then edges (with optional edge weights), or parent format when print_parents is set.

Complexity

O(n).

Examples

// Prints a small tree to standard output.
std::cout << tgen::tree::value(3, {{0, 1}, {1, 2}}); // Prints "0 1\n1 2\n".

Definition at line 4758 of file tgen.h.

---

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

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