 |
tgen
|
|
tgen
|
Labeled tree value. More...
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. | |
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.
|
inline |
Builds a tree from an adjacency list.
| adj | Adjacency list; adj[u] contains every neighbor of u. |
Adjacency list must be symmetric, and must form a tree.
O(n).
|
inline |
Builds a tree from a vertex count and an edge list.
| 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.
O(n).
| 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.
| 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.
O(n + m alpha(n)).
|
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.
O(1).
|
inline |
|
inline |
Enables edge-weighted mode on an edgeless tree.
After this call, add_edge(u, v, w) accepts a weight for each new edge.
O(1).
|
inline |
Optional edge weights.
Index i corresponds to edges()[i]. Absent when the tree has no edge weights.
|
inline |
Edge list.
Each edge (u, v) appears only once, with u < v. The order matches optional edge weights when present.
|
inline |
Glues another tree at given vertices.
| 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.
O(rhs.n * log n) amortized.
That is, the complexity depends mostly on the rhs tree.
|
inline |
Glues another tree at given vertex pairs.
| 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.
O(rhs.n * log n) amortized.
That is, the complexity depends mostly on the rhs tree.
|
inline |
Links two trees by an edge.
| 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.
O(rhs.n * log n) amortized.
That is, the complexity depends mostly on the rhs tree.
|
inline |
|
inline |
|
inline |
Prints in parent format instead of edge list.
| 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.
O(1).
|
inline |
Attaches edge weights.
| edge_weights | One weight per edge, in the same order as edges(). |
Immutable style: returns a copy with weights set (weight type deduced); does not modify *this.
O(n).
|
inline |
Attaches vertex weights.
| vertex_weights | One weight per vertex (n values). |
Immutable style: returns a copy with weights set (weight type deduced); does not modify *this.
O(n).
|
inline |
Shuffles vertices and edge order.
Shuffles all vertices and edge order. Equivalent to shuffle_except({}).
O(n).
|
inline |
|
inline |
Converts the tree to a std types.
|
inline |
Optional vertex weights.
Absent when the tree has no edge weights.
|
friend |
Prints the tree to an output stream.
| 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.
O(n).
1.14.0