Graphs

Generation of simple labeled graphs (undirected or directed). More...

Classes
struct	tgen::wgraph< VWeight, EWeight >
	Labeled weighted graph generator. More...
struct	tgen::wgraph< VWeight, EWeight >::value
	Labeled graph value. More...

Typedefs
template<typename VWeight>
using	tgen::vgraph = wgraph<VWeight, int>
	Vertex-weighted labeled graphs.
template<typename EWeight>
using	tgen::egraph = wgraph<int, EWeight>
	Edge-weighted labeled graphs.
using	tgen::graph = wgraph<int, int>
	Unweighted labeled graphs.

Functions
graph::value	tgen::K (int n)
	Complete undirected graph.
graph::value	tgen::P (int n, bool is_directed=false)
	Path graph.
graph::value	tgen::C (int n, bool is_directed=false)
	Cycle graph.
graph::value	tgen::S (int n)
	Star undirected graph.
graph::value	tgen::K (int n1, int n2)
	Complete bipartite undirected graph.

Detailed Description

Generation of simple labeled graphs (undirected or directed).

Vertices are labeled 0 through n-1. Isomorphism is not factored out: two different labeled graphs are distinct.

The template tgen::wgraph<VWeight, EWeight> is the general generator. It fixes n and a target edge count m, optional preset edges, and directed / self-loop mode. It only randomizes edges (which pairs of vertices are adjacent); vertex and edge weights are not sampled by the generator. Attach them on tgen::wgraph::value with tgen::wgraph::value::set_vertex_weights / tgen::wgraph::value::set_edge_weights when needed. Use tgen::wgraph::value::edge_weighted on an edgeless graph to enable weighted add_edge(u, v, w) calls before any edges exist.

Convenient aliases (same constructors and methods as tgen::wgraph):

• tgen::graph — unweighted, tgen::wgraph<int, int>;
• tgen::vgraph<VWeight> — vertex weight type VWeight, dummy edge weight int, i.e. tgen::wgraph<VWeight, int>;
• tgen::egraph<EWeight> — edge weight type EWeight, dummy vertex weight int, i.e. tgen::wgraph<int, EWeight>.

Examples

Prints a random simple graph on 5 vertices with 6 edges, including (0,1).

std::cout << tgen::graph(5, 6).add_edge(0, 1).gen();

0 1
3 4
1 3
1 4
2 4
0 2

Example generated graph

Random connected graph on 8 vertices with 10 edges, including edge (0,1).

std::cout << tgen::graph(8, 10).add_edge(0, 1).get_connected();

0 1
0 3
1 5
2 7
4 7
5 6
6 7
1 4
1 2
1 6

Example generated graph

Random DAG on 8 vertices with 12 directed edges.

std::cout << tgen::graph(8, 12, true).get_acyclic();

1 2
7 4
3 5
2 5
6 4
1 5
7 0
1 0
4 3
4 5
1 3
0 3

Example generated graph

Skewed connected graph on 10 vertices with 15 edges (elongation 100, spread 2).

std::cout << tgen::graph::gen_skewed(10, 15, 100, 2);

0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
1 3
6 8
7 9
5 7
4 6
2 4

Example generated graph

Triangle with string edge weights and a leading n/m line when printed.

std::cout << tgen::C(3).set_edge_weights<std::string>({"a", "b", "ab"}).print_nm();

3 3
0 1 a
0 2 b
1 2 ab

Example generated graph

Weighted directed graph built edge by edge with edge_weighted.

std::cout << tgen::egraph<int>::value(4, {}, true).edge_weighted().add_edge(0, 1, 10).add_edge(1, 2, 20).add_edge(2, 3, 30).print_nm();

4 3
0 1 10
1 2 20
2 3 30

Standard graphs (tgen::K, tgen::P, tgen::C, and tgen::S) are deterministic helpers that return tgen::wgraph::value.

For labeled trees (exactly n-1 undirected edges), see the Trees module and tgen::wtree.

Typedef Documentation

egraph

template<typename EWeight>

using tgen::egraph = wgraph<int, EWeight>

Edge-weighted labeled graphs.

Same as tgen::wgraph<int, EWeight> (vertex weight type is a dummy int).

Definition at line 6328 of file tgen.h.

graph

using tgen::graph = wgraph<int, int>

Unweighted labeled graphs.

Same as tgen::wgraph<int, int> (vertex and edge weight types are dummy int).

Definition at line 6331 of file tgen.h.

vgraph

template<typename VWeight>

using tgen::vgraph = wgraph<VWeight, int>

Vertex-weighted labeled graphs.

Same as tgen::wgraph<VWeight, int> (edge weight type is a dummy int).

Definition at line 6325 of file tgen.h.

Function Documentation

C()

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

inline

Cycle graph.

Parameters

n	Number of vertices.
is_directed	If true, edges are i -> (i+1) % n; otherwise the graph is undirected.

Precondition

n >= 3.

Complexity

O(n).

Examples

// Undirected cycle on five vertices.
std::cout << tgen::C(5);
 
// Directed cycle on five vertices.
std::cout << tgen::C(5, true);

Definition at line 6356 of file tgen.h.

K() [1/2]

graph::value tgen::K ( int n )

inline

Complete undirected graph.

Parameters

n	Number of vertices.

Complexity

O(n^2).

Examples

// Complete graph on four vertices (all pairs adjacent).
std::cout << tgen::K(4);

Definition at line 6339 of file tgen.h.

K() [2/2]

graph::value tgen::K ( int n1, int n2 )

inline

Complete bipartite undirected graph.

Parameters

n1	Number of vertices on the left side.
n2	Number of vertices on the right side.

The vertices on the left side are indexed in [0, n1), and those on right side in [n1, n1 + n2).

Complexity

O(n1 * n2).

Examples

// Complete bipartite graph between parts of size two and three.
std::cout << tgen::K(2, 3);

Definition at line 6369 of file tgen.h.

P()

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

inline

Path graph.

Parameters

n	Number of vertices.
is_directed	If true, edges are i -> i+1 for i in [0, n - 2); otherwise the graph is undirected.

The endpoints of the path are vertices 0 and n - 1.

Complexity

O(n).

Examples

// Undirected path on five vertices.
std::cout << tgen::P(5);
 
// Directed path on five vertices (0 -> 1 -> ... -> 4).
std::cout << tgen::P(5, true);

Definition at line 6345 of file tgen.h.

S()

graph::value tgen::S ( int n )

inline

Star undirected graph.

Parameters

n	Total number of vertices.

The center of the star is vertex 0.

Complexity

O(n).

Examples

// Star with four leaves.
std::cout << tgen::S(5);

Definition at line 6380 of file tgen.h.