 |
tgen 1.5.0
|
|
tgen 1.5.0
|
Labeled graph value. More...
Public Member Functions | |
| value (const std::vector< std::set< int > > &adj, bool is_directed=false) | |
| Builds a graph from an adjacency list. | |
| value (int n, const std::vector< std::pair< int, int > > &edges={}, bool is_directed=false) | |
| Builds a graph from number of vertices and edge list. | |
| value (const typename wtree< VWeight, EWeight >::value &t) | |
| Builds an undirected graph from a tree. | |
| int | n () const |
| Number of vertices. | |
| int | m () const |
| Number of edges. | |
| bool | is_directed () const |
| If the graph is directed. | |
| 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> | |
| wgraph< NewVWeight, EWeight >::value | set_vertex_weights (const std::vector< NewVWeight > &vertex_weights) const |
| Attaches vertex weights. | |
| template<typename NewEWeight = EWeight> | |
| wgraph< 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 graph. | |
| value & | print_1_based () |
| Sets that printed vertex ids are 1-based. | |
| value & | print_nm () |
| Prints number of vertices and edges before edge list. | |
| value & | shuffle_except (std::set< int > indices) |
| Shuffles vertices except given vertices, and edge order. | |
| value & | shuffle () |
| Shuffles all vertices and edge order. | |
| value & | add_vertices (int k, std::optional< std::vector< VWeight > > new_vertex_weights=std::nullopt) |
| Adds new isolated vertices. | |
| value & | add_edge (int u, int v, std::optional< EWeight > w=std::nullopt) |
| Adds an edge between two vertices. | |
| value & | link (const value &rhs, int new_u, int new_v, std::optional< EWeight > new_w=std::nullopt) |
| Links two graphs by an new edge. | |
| value & | glue (const value &rhs, std::set< std::pair< int, int > > index_pairs) |
| Glues another graph at given vertex pairs. | |
| value & | glue (const value &rhs, std::set< int > indices) |
| Glues another graph at given vertices. | |
| value & | disjoint_union (const value &rhs) |
| Disjoint union with another graph. | |
| value & | random_subgraph (int num_edges) |
| Random subgraph with a fixed number of edges. | |
| value & | random_connected_subgraph (int num_edges) |
| Random subgraph with a fixed number of edges that keeps components connected. | |
| value | operator! () const |
| Graph complement of unweighted graph. | |
| value | operator+ (const value &rhs) const |
| Concatenates two graphs (disjoint union). | |
| std::tuple< int, int, std::vector< std::set< int > > > | to_std () const |
| Converts the graph to std types. | |
| std::tuple< int, int, std::vector< std::set< int > > > | to_std_1_based () const |
| Converts the graph 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 graph to an output stream. | |
Labeled graph value.
Adjacency lists are symmetric for undirected graphs; the edge list tgen::wgraph::value::edges lists each undirected edge once as (u, v) with u <= v. Directed graphs list each directed edge once.
It can be printed through std::cout.
|
inline |
Builds a graph from an adjacency list.
| adj | Adjacency list; adj[u] contains every neighbor of u (out-neighbors if directed). |
| is_directed | If false, adj must be symmetric and each undirected edge must appear in both directions. |
O(n + m).
|
inline |
Builds a graph from number of vertices and edge list.
| n | Number of vertices. |
| edges | List of edges. |
| is_directed | If the graph is directed. |
For undirected graphs, each edge (u, v) should appear once with u <= v.
O(n + m log n).
|
inline |
Builds an undirected graph from a tree.
| t | Tree to convert. |
The result has the same vertices and edges as t, with is_directed() == false. Vertex and edge weights are copied when the weight types match.
O(n).
|
inline |
Adds an edge between two vertices.
| u | First endpoint (tail if directed). |
| v | Second endpoint (head if directed). |
| w | Optional edge weight (required iff the graph already has edge weights). |
If the edge is already present, does nothing. Invalid endpoints or incompatible weights are rejected before modifying the graph.
O(log n) amortized.
|
inline |
Adds new isolated vertices.
| k | Nonnegative number of vertices to append; the resulting count must fit in int. |
| new_vertex_weights | Optional weights for the new vertices (required if the graph already has vertex weights). |
Invalid counts or weights are rejected before modifying the graph.
O(k) amortized.
|
inline |
|
inline |
Disjoint union with another graph.
O(rhs.n + rhs.m log n) amortized.
That is, the complexity depends mostly on the rhs graph.
|
inline |
Enables edge-weighted mode on an edgeless graph.
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 |
|
inline |
Glues another graph at given vertices.
| rhs | Other graph 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. Passing this value itself as rhs glues a copy of its original contents.
O(rhs.n + rhs.m log n) amortized.
That is, the complexity depends mostly on the rhs graph.
|
inline |
Glues another graph at given vertex pairs.
| rhs | Other graph 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 graph. Other vertices are shifted accordingly. Passing this value itself as rhs glues a copy of its original contents.
O(rhs.n + rhs.m log n) amortized.
That is, the complexity depends mostly on the rhs graph.
|
inline |
If the graph is directed.
|
inline |
Links two graphs by an new edge.
| rhs | Second graph. |
| new_u | Endpoint in this graph. |
| new_v | Endpoint in rhs before relabeling. |
| new_w | Optional weight of the connecting edge. |
Vertices on rhs are shifted by the current n. Both graphs must have the same directedness. Weight usage must be consistent. Passing this value itself as rhs links it to a copy of its original contents.
O(rhs.n + rhs.m log n) amortized.
That is, the complexity depends mostly on the rhs graph.
|
inline |
|
inline |
|
inline |
Graph complement of unweighted graph.
Immutable style: returns a copy with the complement with the same n, is_directed, and printing flags; does not modify *this.
Self loops are maintained.
O(n^2).
|
inline |
Concatenates two graphs (disjoint union).
Immutable style: returns a copy with the disjoint union; does not modify *this.
O(n + m log n) for the combined size.
|
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 |
Random subgraph with a fixed number of edges that keeps components connected.
| num_edges | Number of edges to keep (subset of current edges). Must be nonnegative. |
First, picks a random spanning forest via randomized Prim on each connected component (so the number of connected components does not increase). Then, extra edges are chosen uniformly at random.
Requires at least n - c edges, where c is the number of connected components in the current graph.
O(n + m).
|
inline |
Random subgraph with a fixed number of edges.
| num_edges | Number of edges to keep (subset of current edges). Must be nonnegative. |
The edges are chosen uniformly as a subset of the current edges. Edge-weighted mode is preserved even when num_edges is zero.
O(n + m).
|
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 + m).
|
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 + m).
|
inline |
Shuffles all vertices and edge order.
Shuffles all vertices and edge order. Equivalent to shuffle_except({}).
O(n + m).
|
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 + m).
|
inline |
Converts the graph to 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 graph 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 this graph has no vertex weights.
|
friend |
Prints the graph to an output stream.
| out | Output stream. |
| val | Graph to write. |
Optional n m line when print_nm is set, optional vertex-weight line, then edges (with optional edge weights).
O(n + m).
1.14.0