 |
tgen
|
|
tgen
|
Labeled weighted graph generator. More...
Classes | |
| struct | value |
| Labeled graph value. More... | |
Public Member Functions | |
| wgraph (int n, int m, bool is_directed=false, bool has_self_loops=false) | |
| Creates a graph generator for a fixed number of vertices and edges. | |
| wgraph & | add_edge (int u, int v) |
| Adds a preset edge that must appear in the generated graph. | |
| wgraph & | add_edges_from (const value &rhs) |
| Adds all edges from another graph as preset edges. | |
| value | gen () const |
| Generates a uniformly random graph satisfying the constraints. | |
| value | get_connected () const |
| Random connected undirected graph extending preset edges. | |
| value | get_acyclic () const |
| Random directed acyclic graph extending preset edges. | |
| Public Member Functions inherited from tgen::gen_base< wgraph< 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 m, int elongation, int spread, bool is_directed=false) |
| Random skewed connected graph (large diameter). | |
| static value | gen_bipartite (int n1, int n2, int m, bool connected=false) |
| Generates a random bipartite graph. | |
Labeled weighted graph generator.
Defines graphs on n vertices with exactly m edges after generation, subject to preset edges from tgen::wgraph::add_edge. A uniformly random completion (respecting simple / directed / self-loop rules) is produced by tgen::wgraph::gen.
There are other static generation methods:
There are also structured, non-uniform operations:
|
inline |
Creates a graph generator for a fixed number of vertices and edges.
| n | Number of vertices. |
| m | Target number of edges. |
| is_directed | If true, edges are directed and distinguish (u,v) from (v,u). |
| has_self_loops | If true, pairs (i,i) may be generated. |
O(1).
|
inline |
Adds a preset edge that must appear in the generated graph.
| u | Endpoint (head if directed). |
| v | Endpoint (tail if directed). |
The number of preset edges must not exceed m.
O(log m) amortized.
|
inline |
Adds all edges from another graph as preset edges.
| rhs | Graph to take edges from. |
O(rhs.m() log m).
|
inline |
Generates a uniformly random graph satisfying the constraints.
Preset edges are included first; remaining edges are sampled uniformly from admissible pairs until m distinct edges exist.
| std::runtime_error | if there are not m valid edges to generate. |
O(n + m log n).
|
inlinestatic |
Generates a random bipartite graph.
| n1 | Size of the left side. |
| n2 | Size of the right side. |
| m | Target edge count. |
| connected | If true, the graph is connected (requires m >= n1 + n2 - 1). |
The vertices on the left side are indexed in [0, n1), and those on right side in [n1, n1 + n2).
When connected is false, m cross edges are chosen uniformly without replacement from K_{n1, n2}.
When connected is true, a spanning tree is built first via a bipartite Prüfer sequence, then remaining cross edges are added by rejection sampling.
O(n1 + n2 + m log(n1 * n2)) expected.
|
inlinestatic |
Random skewed connected graph (large diameter).
| n | Vertex count. |
| m | Edge count. |
| elongation | Passed to tgen::wnext; controls how star-like or path-like the spanning tree is. |
| spread | Maximum walk length toward the root when sampling an extra edge. |
| is_directed | If true, orients every edge down spanning tree. |
First, builds a skewed spanning tree with tgen::wtree::gen_skewed(n, elongation). Then, the remaining edges (v, u) are generated with the following procedure. Vertex u is random, and vertex v is the result of walking tgen::next(2, spread) parent edges in the spanning tree.
If elongation is small (negative), the spanning tree tends to be star-like and the graph tends to have small diameter. If elongation is large (positive), the spanning tree tends to be path-like and vertices 0 and n - 1 tend to be far apart.
When is_directed is true, the result is a directed acyclic graph weakly connected with root 0.
O(n + m log n) if spread is O(1);
O(n log n + m log^2 n) otherwise.
|
inline |
Random directed acyclic graph extending preset edges.
Preset edges must be acyclic. Remaining edges respect a random topological order (randomized Kahn).
| std::runtime_error | preset edges form a cycle. |
O(n + m log n).
|
inline |
Random connected undirected graph extending preset edges.
First, edges are chosen to connect the connected components induced by the preset edges, uniformly at random. Then, remaining edges are chosen uniformly at random.
O(n + m log n).
1.14.0