Labeled graph value. More...

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

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 &	add_1 ()
	Adds 1 for printing.
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.
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.

Detailed Description

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

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.

Definition at line 5157 of file tgen.h.

Constructor & Destructor Documentation

◆ value() [1/3]

template<typename VWeight, typename EWeight>

tgen::wgraph< VWeight, EWeight >::value::value	(	const std::vector< std::set< int > > &	adj,
		bool	is_directed = false )

inline

Builds a graph from an adjacency list.

Parameters

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.

Complexity

O(n + m).

Examples

// Triangle as undirected graph from adjacency.
std::vector<std::set<int>> a(3);
a[0] = {1, 2};
a[1] = {0, 2};
a[2] = {0, 1};
tgen::graph::value g(a);

Definition at line 5176 of file tgen.h.

◆ value() [2/3]

template<typename VWeight, typename EWeight>

tgen::wgraph< VWeight, EWeight >::value::value	(	int	n,
		const std::vector< std::pair< int, int > > &	edges = {},
		bool	is_directed = false )

inline

Builds a graph from number of vertices and edge list.

Parameters

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.

Complexity

O(n + m log n).

Examples

// 2 P_2.

tgen::graph::value g(4, {{0, 1}, {2, 3}});

Definition at line 5197 of file tgen.h.

◆ value() [3/3]

template<typename VWeight, typename EWeight>

tgen::wgraph< VWeight, EWeight >::value::value ( const typename wtree< VWeight, EWeight >::value & t )

inline

Builds an undirected graph from a tree.

Parameters

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.

Complexity

O(n).

Examples

auto t = tgen::tree(5).gen();

auto g = tgen::graph::value(t);

tgen::tree

wtree< int, int > tree

Unweighted labeled trees.

Definition tgen.h:4981

tgen::wtree::gen

value gen() const

Generates a uniformly random value from the set of valid trees.

Definition tgen.h:4883

Definition at line 5228 of file tgen.h.

Member Function Documentation

◆ add_1()

template<typename VWeight, typename EWeight>

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

inline

Adds 1 for printing.

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

Complexity

O(1).

Examples

// Stream edges with vertex indices shifted by one for output only.
auto g = tgen::graph::value(3, {{0, 1}, {1, 2}});
std::cout << g.add_1(); // Prints "1 2\n2 3\n".

Definition at line 5326 of file tgen.h.

◆ add_edge()

template<typename VWeight, typename EWeight>

value & tgen::wgraph< VWeight, EWeight >::value::add_edge	(	int	u,
		int	v,
		std::optional< EWeight >	w = std::nullopt )

inline

Adds an edge between two vertices.

Parameters

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.

Complexity

O(log n) amortized.

Examples

// Add a second edge; edge count becomes two.
tgen::graph::value g(3, {{0, 1}});
g.add_edge(1, 2);
std::cout << g.m() << std::endl; // Prints "2".

Definition at line 5441 of file tgen.h.

◆ add_vertices()

template<typename VWeight, typename EWeight>

value & tgen::wgraph< VWeight, EWeight >::value::add_vertices	(	int	k,
		std::optional< std::vector< VWeight > >	new_vertex_weights = std::nullopt )

inline

Adds new isolated vertices.

Parameters

k	Number of vertices to append.
new_vertex_weights	Optional weights for the new vertices (required if the graph already has vertex weights).

Complexity

O(k) amortized.

Examples

// Append one isolated vertex; total vertex count becomes three.
tgen::graph::value g(2, {{0, 1}});
g.add_vertices(1);
std::cout << g.n() << std::endl; // Prints "3".

Definition at line 5414 of file tgen.h.

◆ adj()

template<typename VWeight, typename EWeight>

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

inline

Adjacency list.

Returns: Constant reference to the adjacency list.

Examples

// Degree of vertex 1 in a P_3.
auto g = tgen::graph::value(3, {{0, 1}, {1, 2}});
std::cout << g.adj()[1].size() << std::endl; // Prints "2".

Definition at line 5267 of file tgen.h.

◆ disjoint_union()

template<typename VWeight, typename EWeight>

value & tgen::wgraph< VWeight, EWeight >::value::disjoint_union ( const value & rhs )

inline

Disjoint union with another graph.

Complexity

O(rhs.n + rhs.m log n) amortized.

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

Examples

// Disjoint union of two P_2.
tgen::graph::value a(2, {{0, 1}});
tgen::graph::value b(2, {{0, 1}});
a.disjoint_union(b);
std::cout << a.n() << std::endl; // Prints "4".

Definition at line 5579 of file tgen.h.

◆ edge_weighted()

template<typename VWeight, typename EWeight>

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

inline

Enables edge-weighted mode on an edgeless graph.

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

Precondition: The graph has no edges (m() == 0).

Complexity

O(1).

Examples

// Build a weighted directed graph edge by edge.
tgen::egraph<int>::value g(3, {}, true);
g.edge_weighted();
g.add_edge(0, 1, 10);
g.add_edge(1, 2, 20);
std::cout << g; // Prints "0 1 10\n1 2 20\n".

Definition at line 5313 of file tgen.h.

◆ edge_weights()

template<typename VWeight, typename EWeight>

const std::optional< std::vector< EWeight > > & tgen::wgraph< 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

// First edge weight aligned with the edge list order.
auto g = tgen::graph::value(3, {{0, 1}, {1, 2}}).set_edge_weights({30, 40});
std::cout << (*g.edge_weights())[0] << std::endl; // Prints "30".

Definition at line 5281 of file tgen.h.

◆ edges()

template<typename VWeight, typename EWeight>

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

inline

Edge list.

Returns: Constant reference to the edge list.

Examples

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

Definition at line 5273 of file tgen.h.

◆ glue() [1/2]

template<typename VWeight, typename EWeight>

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

inline

Glues another graph at given vertices.

Parameters

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.

Complexity

O(rhs.n + rhs.m log n) amortized.

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

Examples

// Glues to C_3 at vertex 0.

std::cout << tgen::C(3).glue(tgen::C(3), {0}).n() << std::endl; // Prints "5".

tgen::C

graph::value C(int n, bool is_directed=false)

Cycle graph.

Definition tgen.h:6356

tgen::wgraph::value::n

int n() const

Number of vertices.

Definition tgen.h:5258

Definition at line 5566 of file tgen.h.

◆ glue() [2/2]

template<typename VWeight, typename EWeight>

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

inline

Glues another graph at given vertex pairs.

Parameters

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.

Complexity

O(rhs.n + rhs.m log n) amortized.

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

Examples

// Glues the edge of a P_3 onto the certer of another P_3.

auto g = tgen::P(3).glue(tgen::P(3), {{0, 1}});

tgen::P

graph::value P(int n, bool is_directed=false)

Path graph.

Definition tgen.h:6345

Definition at line 5502 of file tgen.h.

◆ is_directed()

template<typename VWeight, typename EWeight>

bool tgen::wgraph< VWeight, EWeight >::value::is_directed ( ) const

inline

If the graph is directed.

Returns: True if edges are directed.

Examples

// Directed flag: same edge list, undirected vs directed semantics.
auto u = tgen::graph::value(3, {{0, 1}}, false);
auto d = tgen::graph::value(3, {{0, 1}}, true);
std::cout << u.is_directed() << d.is_directed() << std::endl; // Prints "01".

Definition at line 5264 of file tgen.h.

◆ link()

template<typename VWeight, typename EWeight>

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

inline

Links two graphs by an new edge.

Parameters

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. Weight usage must be consistent.

Complexity

O(rhs.n + rhs.m log n) amortized.

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

Examples

// Connect two single-edge graphs with one new bridge edge; four vertices total.
tgen::graph::value a(2, {{0, 1}});
tgen::graph::value b(2, {{0, 1}});
a.link(b, 0, 0);
std::cout << a.n() << std::endl; // Prints "4".

Definition at line 5475 of file tgen.h.

◆ m()

template<typename VWeight, typename EWeight>

int tgen::wgraph< VWeight, EWeight >::value::m ( ) const

inline

Number of edges.

Returns: The number of edges (size of edges()).

Examples

// Edge count of a path on four vertices.
auto g = tgen::graph::value(4, {{0, 1}, {1, 2}, {2, 3}});
std::cout << g.m() << std::endl; // Prints "3".

Definition at line 5261 of file tgen.h.

◆ n()

template<typename VWeight, typename EWeight>

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

inline

Number of vertices.

Returns: The number of vertices.

Examples

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

Definition at line 5258 of file tgen.h.

◆ operator!()

template<typename VWeight, typename EWeight>

value tgen::wgraph< VWeight, EWeight >::value::operator! ( ) const

inline

Graph complement of unweighted graph.

Returns: Complement 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.

Complexity

O(n^2).

Examples

// Complement of a path on 4 vertices has three edges (the missing chords).
tgen::graph::value p = tgen::P(4);
std::cout << (!p).m() << std::endl; // Prints "3".

Definition at line 5708 of file tgen.h.

◆ operator+()

template<typename VWeight, typename EWeight>

value tgen::wgraph< VWeight, EWeight >::value::operator+ ( const value & rhs ) const

inline

Concatenates two graphs (disjoint union).

Immutable style: returns a copy with the disjoint union; does not modify *this.

Complexity

O(n + m log n) for the combined size.

Examples

// Concatenate two disjoint edges; total vertex count is four.
tgen::graph::value a(2, {{0, 1}});
tgen::graph::value b(2, {{0, 1}});
std::cout << (a + b).n() << std::endl; // Prints "4".

Definition at line 5742 of file tgen.h.

◆ print_nm()

template<typename VWeight, typename EWeight>

value & tgen::wgraph< VWeight, EWeight >::value::print_nm ( )

inline

Prints number of vertices and edges before edge list.

Complexity

O(1).

Examples

// Stream with a leading line giving vertex count and edge count.
auto g = tgen::graph::value(3, {{0, 1}, {1, 2}});
std::cout << g.print_nm(); // Prints "3 2\n0 1\n1 2\n".

Definition at line 5333 of file tgen.h.

◆ random_connected_subgraph()

template<typename VWeight, typename EWeight>

value & tgen::wgraph< VWeight, EWeight >::value::random_connected_subgraph ( int num_edges )

inline

Random subgraph with a fixed number of edges that keeps components connected.

Parameters

num_edges Number of edges to keep (subset of current edges).

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.

Note: This operation is not uniformly random.

Complexity

O(n + m).

Examples

// Random connected eight-edge subgraph of the complete graph on six vertices.
tgen::graph::value g = tgen::K(6);
std::cout << g.random_connected_subgraph(8).m() << std::endl; // Prints "8".

Definition at line 5618 of file tgen.h.

◆ random_subgraph()

template<typename VWeight, typename EWeight>

value & tgen::wgraph< VWeight, EWeight >::value::random_subgraph ( int num_edges )

inline

Random subgraph with a fixed number of edges.

Parameters

num_edges Number of edges to keep (subset of current edges).

The edges are chosen uniformly as a subset of the current edges.

Complexity

O(n + m).

Examples

// Random four-edge subgraph of the complete graph on five vertices.
tgen::graph::value g = tgen::K(5);
std::cout << g.random_subgraph(4).m() << std::endl; // Prints "4".

Definition at line 5585 of file tgen.h.

◆ set_edge_weights()

template<typename VWeight, typename EWeight>

template<typename NewEWeight = EWeight>

wgraph< VWeight, NewEWeight >::value tgen::wgraph< 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 graph 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 + m).

Examples

// Copy with edge weights; stream shows each edge with its weight.
auto g = tgen::graph::value(3, {{0, 1}, {1, 2}});
auto w = g.set_edge_weights({9, 10});
std::cout << w; // Prints "0 1 9\n1 2 10\n".

Definition at line 5302 of file tgen.h.

◆ set_vertex_weights()

template<typename VWeight, typename EWeight>

template<typename NewVWeight = VWeight>

wgraph< NewVWeight, EWeight >::value tgen::wgraph< 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 graph 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 + m).

Examples

// Copy with vertex weights; stream shows weight line then edges.
auto g = tgen::graph::value(3, {{0, 1}, {1, 2}});
auto w = g.set_vertex_weights({1, 2, 3});
std::cout << w; // Prints "1 2 3\n0 1\n1 2\n".

Definition at line 5288 of file tgen.h.

◆ shuffle()

template<typename VWeight, typename EWeight>

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

inline

Shuffles all vertices and edge order.

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

Complexity

O(n + m).

Examples

// Random relabel of P_5.

std::cout << tgen::P(5).shuffle();

Definition at line 5409 of file tgen.h.

◆ shuffle_except()

template<typename VWeight, typename EWeight>

value & tgen::wgraph< 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 + m).

Examples

// Random relabel of P_5 maintaining 0 as one of its extreme points.

std::cout << tgen::P(5).shuffle_except({0});

Definition at line 5343 of file tgen.h.

◆ to_std()

template<typename VWeight, typename EWeight>

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

inline

Converts the graph to std types.

Returns: (n, m, adj) as std::tuple.

Examples

// Tuple holds vertex count, edge count, and adjacency lists.
auto [n, m, adj] = tgen::graph::value(3, {{0, 1}, {1, 2}}).to_std();
std::cout << n << " " << m << std::endl; // Prints "3 2".

Definition at line 5797 of file tgen.h.

◆ vertex_weights()

template<typename VWeight, typename EWeight>

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

inline

Optional vertex weights.

Returns: Constant reference to the optional vertex-weight vector.

Absent when this graph has no vertex weights.

Examples

// First vertex weight after attaching integer weights.
auto g = tgen::graph::value(2, {{0, 1}}).set_vertex_weights({7, 8});
std::cout << (*g.vertex_weights())[0] << std::endl; // Prints "7".

Definition at line 5276 of file tgen.h.

◆ operator<<

template<typename VWeight, typename EWeight>

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

friend

Prints the graph to an output stream.

Parameters

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).

Complexity

O(n + m).

Examples

// Prints a three-vertex path as edge lines.

std::cout << tgen::graph::value(3, {{0, 1}, {1, 2}}).print_nm();

tgen::wgraph::value::print_nm

value & print_nm()

Prints number of vertices and edges before edge list.

Definition tgen.h:5333

2
1
2

Definition at line 5766 of file tgen.h.

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

/home/runner/work/tgen/tgen/single_include/tgen.h
graph.dox

Public Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

◆ value() [1/3]

Complexity

Examples

◆ value() [2/3]

Complexity

Examples

◆ value() [3/3]

Complexity

Examples

Member Function Documentation

◆ add_1()

Complexity

Examples

◆ add_edge()

Complexity

Examples

◆ add_vertices()

Complexity

Examples

◆ adj()

Examples

◆ disjoint_union()

Complexity

Examples

◆ edge_weighted()

Complexity

Examples

◆ edge_weights()

Examples

◆ edges()

Examples

◆ glue() [1/2]

Complexity

Examples

◆ glue() [2/2]

Complexity

Examples

◆ is_directed()

Examples

◆ link()

Complexity

Examples

◆ m()

Examples

◆ n()

Examples

◆ operator!()

Complexity

Examples

◆ operator+()

Complexity

Examples

◆ print_nm()

Complexity

Examples

◆ random_connected_subgraph()

Complexity

Examples

◆ random_subgraph()

Complexity

Examples

◆ set_edge_weights()

Complexity

Examples

◆ set_vertex_weights()

Complexity

Examples

◆ shuffle()

Complexity

Examples

◆ shuffle_except()

Complexity

Examples

◆ to_std()

Examples

◆ vertex_weights()