 |
tgen 1.5.0
|
|
tgen 1.5.0
|
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 & | print_1_based () |
| Sets that printed vertex ids are 1-based. | |
| 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. | |
| std::pair< int, std::vector< std::set< int > > > | to_std_1_based () const |
| Converts the tree to 1-based 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 |
|
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 tree. Other vertices are shifted accordingly. Passing this value itself as rhs glues a copy of its original contents.
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. Passing this value itself as rhs glues a copy of its original contents.
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. Passing this value itself as rhs links it to a copy of its original contents.
O(rhs.n * log n) amortized.
That is, the complexity depends mostly on the rhs tree.
|
inline |
|
inline |
Sets that printed vertex ids are 1-based.
This only affects streaming (std::cout and friends). Stored vertex ids stay 0-based. For a 1-based adjacency export, use to_std_1_based(). Weights are not affected.
O(1).
|
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 |
Shuffles vertices except given vertices, and edge order.
| indices | Vertex ids to keep fixed; every other vertex is relabeled by a random permutation. |
O(n).
|
inline |
Converts the tree to a std types.
Returns 0-based vertex ids. Unaffected by print_1_based(). For a 1-based export, use to_std_1_based().
|
inline |
Converts the tree to 1-based std types.
Vertex labels are increased by one; adj has size n + 1 with index 0 unused. Unaffected by print_1_based().
|
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