gen_graph.h - GaisaiYuno/data-generation GitHub Wiki

类

graph（图）

​init()：初始化。

​print()：输出，不带边权。

​printw(l,r)：输出带权边，权值在 [l,r] 之间。

​shuffle()：打乱边。

​add_edge(p)：添加边 p（p 是一个 std::pair，其 first 和 second 元素代表了边的两个节点）。

add_edge(x,y)：添加边 (x,y)。

​check(p)：检查边 p 是否存在。

函数

random_tree(n)：生成一棵 n 个节点的树。

random_graph(n,m,is_connect,has_same_edge,has_loop)：生成一张 n 个节点，m 条边的图，is_connect, has_same_edge, has_loop 分别代表是否连通，是否有重边，是否有自环。

random_edge(n,has_loop)：生成一条端点在 [1,n] 之间的边，has_loop 代表是否有自环。

chain(n)：生成一条有 n 个节点的链。

jhgraph(n,nd)：生成一个 n 节点菊花图，中心节点为 nd。

random_dag(n,m,has_same_loop)：生成一张 n 个节点，m 条边的 DAG （有向无环图），has_same_edge 代表是否有重边。

举例

#include <bits/stdc++.h>
#include "random.h"
#include "gen_graph.h" 
using namespace std;
int main(){
	int n=10,m=30;
	graph g;
	g=chain(n);
	g.add_edge(make_pair(1,n));
	g.print(); //生成一个环
	g=random_graph(n,m);
	g.shuffle();
	g.printw(0,1e9); //生成一张边权在 [0,1e9] 之间的连通、无重边、无自环的图，并打乱输出
	g=random_graph(n,m,1,1,1);
	g.shuffle();
	g.printw(0,1e9); //生成一张边权在 [0,1e9] 之间的连通、有重边、有自环的图，并打乱输出
	return 0;
}