Random Graph Generator
(library/random/graph-generator.hpp)

• View this file on GitHub
• Last update: 2024-09-10 10:42:34+08:00
• Include: #include "library/random/graph-generator.hpp"

使用方法

int n;
bool is_tree, weighted;
long long low, high;
int OFFSET = 0; // 0-based
GraphGenerator::generate(n, is_tree, weighted, low, high).print(OFFSET);

References

https://nyaannyaan.github.io/library/random_graph/gen.hpp

Depends on

• random_t (library/random/random.hpp)
• library/random/splitmix64.hpp

Code

#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <set>
#include <cassert>
#include "random.hpp"

namespace felix {

namespace GraphGenerator {

struct Graph {
	struct Edge {
		int u, v;
		long long w;
		Edge(int x, int y, long long z = 1) : u(x), v(y), w(z) {}
	};

	int n, m = 0;
	bool weighted;
	std::vector<Edge> edges;
	std::vector<std::vector<int>> g;

	Graph(int _n = 0, bool _weighted = false) : n(_n), weighted(_weighted), g(_n) {}

	void add_edge(int u, int v, long long w = -1) {
		g[u].push_back(edges.size());
		edges.emplace_back(u, v, w);
		m += 1;
	}

	void add_undirected_edge(int u, int v, long long w = -1) {
		int x = std::min(u, v);
		int y = std::max(u, v);
		add_edge(x, y, w);
	}

	std::vector<std::vector<Edge>> adjacency_list(bool directed = false) {
		std::vector<std::vector<Edge>> h(n);
		for(auto& [u, v, w] : edges) {
			h[u].emplace_back(u, v, w);
			if(!directed) {
				h[v].emplace_back(v, u, w);
			}
		}
		return h;
	}

	std::vector<std::vector<long long>> adjacency_matrix(bool directed = false) {
		std::vector<std::vector<long long>> h(n, std::vector<long long>(n));
		for(auto& [u, v, w] : edges) {
			h[u][v] = w;
			if(!directed) {
				h[v][u] = w;
			}
		}
		return h;
	}

	void print_matrix(bool directed = false) {
		auto h = adjacency_matrix(directed);
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				std::cout << h[i][j] << " \n"[j == n - 1];
			}
		}
	}

	void print(int OFFSET = 0) {
		std::cout << n << " " << m << "\n";
		for(auto& [u, v, w] : edges) {
			std::cout << u + OFFSET << " " << v + OFFSET;
			if(weighted) {
				std::cout << " " << w;
			}
			std::cout << "\n";
		}
	}
};

long long w_low = 1, w_high = 1;

void set_weight(bool weighted, long long low, long long high) {
	if(!weighted) {
		low = high = 1;
	}
	w_low = low;
	w_high = high;
}

void add_edge(Graph& g, int u, int v) {
	long long w = rnd.next(w_low, w_high);
	g.add_undirected_edge(u, v, w);
}

Graph tree(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	auto order = rnd.perm(n);
	for(int i = 1; i < n; i++) {
		add_edge(g, order[rnd.next(0, i - 1)], order[i]);
	}
	assert(g.m == n - 1);
	return g;
}

Graph path(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	auto order = rnd.perm(n);
	for(int i = 0; i < n - 1; i++) {
		add_edge(g, order[i], order[i + 1]);
	}
	assert(g.m == n - 1);
	return g;
}

Graph star(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	auto order = rnd.perm(n);
	for(int i = 1; i < n; i++) {
		add_edge(g, order[0], order[i]);
	}
	assert(g.m == n - 1);
	return g;
}

Graph perfect(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			add_edge(g, i, j);
		}
	}
	return g;
}

Graph simple(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	auto order = rnd.perm(n);
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			if(rnd.next(0, 1)) {
				add_edge(g, i, j);
			}
		}
	}
	return g;
}

Graph namori(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	add_edge(g, 0, rnd.next(1, n - 1));
	for(int i = 1; i < n; i++) {
		add_edge(g, i, rnd.next(0, i - 1));
	}
	return g;
}

Graph sparse(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	if(n == 0) {
		return g;
	}
	int m = rnd.next(0, n - 1);
	std::set<std::pair<int, int>> edges;
	while((int) edges.size() < m) {
		int u = rnd.next(0, n - 1);
		int v = rnd.next(0, n - 1);
		if(u >= v) {
			continue;
		}
		edges.emplace(u, v);
	}
	for(auto [u, v] : edges) {
		add_edge(g, u, v);
	}
	return g;
}

Graph connected(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	if(n == 1) {
		return g;
	}
	std::set<std::pair<int, int>> s;
	auto perm = rnd.perm(n);
	for(int i = 1; i < n; i++) {
		int u = perm[rnd.next(i)];
		int v = perm[i];
		add_edge(g, u, v);
		s.emplace(std::min(u, v), std::max(u, v));
	}
	int extra = rnd.next(n, 10 * n);
	for(int i = 0; i < extra; i++) {
		int u = rnd.next(n - 1);
		int v = rnd.next(u + 1, n - 1);
		if(s.count({u, v})) {
			continue;
		}
		s.emplace(u, v);
		add_edge(g, u, v);
	}
	return g;
}

Graph bipartite(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	if(n == 1) {
		return g;
	}
	auto perm = rnd.perm(n);
	int l_cnt = rnd.next(1, n - 1);
	auto lv = std::vector<int>(perm.begin(), perm.begin() + l_cnt);
	auto rv = std::vector<int>(perm.begin() + l_cnt, perm.end());
	for(auto u : lv) {
		for(auto v : rv) {
			if(rnd.next(0, 1)) {
				add_edge(g, u, v);
			}
		}
	}
	return g;
}

Graph generate(int n, bool is_tree = false, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	using F = std::function<Graph(int, bool, long long, long long)>;
	std::vector<F> f{tree, path, star, perfect, simple, namori, sparse, bipartite};
	int mx = (is_tree ? 2 : (int) f.size());
	return f[rnd.next(0, mx)](n, weighted, w_min, w_max);
}

} // namespace GraphGenerator

} // namespace felix

#line 2 "library/random/graph-generator.hpp"
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <set>
#include <cassert>
#line 4 "library/random/random.hpp"
#include <cstring>
#include <array>
#line 7 "library/random/random.hpp"
#include <numeric>
#include <climits>
#include <string>
#line 2 "library/random/splitmix64.hpp"
#include <chrono>


namespace felix {

namespace internal {

// http://xoshiro.di.unimi.it/splitmix64.c

struct splitmix64_hash {
	static unsigned long long splitmix64(unsigned long long x) {
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
 
	unsigned long long operator()(unsigned long long x) const {
		static const unsigned long long FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

} // namespace internal


} // namespace felix

#line 11 "library/random/random.hpp"

namespace felix {

struct random_t {
public:
	explicit random_t(unsigned long long seed = 3905348978240129619LL) {
		set_seed(seed);
	}

	void set_seed(unsigned long long seed) {
		for(int i = 0; i < 4; i++) {
			s[i] = internal::splitmix64_hash::splitmix64(seed);
			seed += 0x9e3779b97f4a7c15;
		}
	}

	// [0, n)
	unsigned long long next(unsigned long long n) {
		const unsigned long long LIMIT = std::numeric_limits<unsigned long long>::max() / n * n;
		unsigned long long r;
		do {
			r = next();
		} while(r >= LIMIT);
		return r % n;
	}

	// [l, r]
	template<class T>
	T next(T l, T r) {
		assert(l <= r);
		return T(l + next(r - l + 1ULL));
	}

	template<class Iter>
	void shuffle(Iter l, Iter r) {
		if(l == r) {
			return;
		}
		int pos = 0;
		for(auto it = l + 1; it != r; it++) {
			pos += 1;
			int j = next(pos + 1);
			if(j != pos) {
				std::iter_swap(it, l + j);
			}
		}
	}

	// [0, n)
	std::vector<int> perm(int n) {
		std::vector<int> a(n);
		std::iota(a.begin(), a.end(), 0);
		shuffle(a.begin(), a.end());
		return a;
	}

	// [l, r]
	template<class T>
	std::vector<T> distinct(int size, T l, T r) {
		std::vector<T> result;
		if(size == 0) {
			return result;
		}
		assert(l <= r);
		assert(size > 0);
		unsigned long long n = r - l + 1;
		assert(size <= n);
		double expected = 0;
		for(int i = 1; i <= size; i++) {
			expected += double(n) / double(n - i + 1);
		}
		if(expected < (double) n) {
			std::set<T> s;
			while((int) s.size() < size) {
				T val = T(next(l, r));
				if(s.insert(val).second) {
					result.push_back(val);
				}
			}
		} else {
			std::vector<T> p(perm(n));
			for(auto& x : p) {
				x += l;
			}
			result.insert(result.end(), p.begin(), p.begin() + size);
		}
		return result;
	}

	std::string string(int n, char min_char = 'a', char max_char = 'z') {
		std::string s(n, '_');
		for(int i = 0; i < n; i++) {
			s[i] = next(min_char, max_char);
		}
		return s;
	}

private:
	std::array<unsigned long long, 4> s;

	static unsigned long long rotl(const unsigned long long x, int k) {
		return (x << k) | (x >> (64 - k));
	}

	unsigned long long next() {
		const unsigned long long result = rotl(s[1] * 5, 7) * 9;
		const unsigned long long t = s[1] << 17;
		s[2] ^= s[0];
		s[3] ^= s[1];
		s[1] ^= s[2];
		s[0] ^= s[3];
		s[2] ^= t;
		s[3] = rotl(s[3], 45);
		return result;
	}
} rnd;

} // namespace felix
#line 9 "library/random/graph-generator.hpp"

namespace felix {

namespace GraphGenerator {

struct Graph {
	struct Edge {
		int u, v;
		long long w;
		Edge(int x, int y, long long z = 1) : u(x), v(y), w(z) {}
	};

	int n, m = 0;
	bool weighted;
	std::vector<Edge> edges;
	std::vector<std::vector<int>> g;

	Graph(int _n = 0, bool _weighted = false) : n(_n), weighted(_weighted), g(_n) {}

	void add_edge(int u, int v, long long w = -1) {
		g[u].push_back(edges.size());
		edges.emplace_back(u, v, w);
		m += 1;
	}

	void add_undirected_edge(int u, int v, long long w = -1) {
		int x = std::min(u, v);
		int y = std::max(u, v);
		add_edge(x, y, w);
	}

	std::vector<std::vector<Edge>> adjacency_list(bool directed = false) {
		std::vector<std::vector<Edge>> h(n);
		for(auto& [u, v, w] : edges) {
			h[u].emplace_back(u, v, w);
			if(!directed) {
				h[v].emplace_back(v, u, w);
			}
		}
		return h;
	}

	std::vector<std::vector<long long>> adjacency_matrix(bool directed = false) {
		std::vector<std::vector<long long>> h(n, std::vector<long long>(n));
		for(auto& [u, v, w] : edges) {
			h[u][v] = w;
			if(!directed) {
				h[v][u] = w;
			}
		}
		return h;
	}

	void print_matrix(bool directed = false) {
		auto h = adjacency_matrix(directed);
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				std::cout << h[i][j] << " \n"[j == n - 1];
			}
		}
	}

	void print(int OFFSET = 0) {
		std::cout << n << " " << m << "\n";
		for(auto& [u, v, w] : edges) {
			std::cout << u + OFFSET << " " << v + OFFSET;
			if(weighted) {
				std::cout << " " << w;
			}
			std::cout << "\n";
		}
	}
};

long long w_low = 1, w_high = 1;

void set_weight(bool weighted, long long low, long long high) {
	if(!weighted) {
		low = high = 1;
	}
	w_low = low;
	w_high = high;
}

void add_edge(Graph& g, int u, int v) {
	long long w = rnd.next(w_low, w_high);
	g.add_undirected_edge(u, v, w);
}

Graph tree(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	auto order = rnd.perm(n);
	for(int i = 1; i < n; i++) {
		add_edge(g, order[rnd.next(0, i - 1)], order[i]);
	}
	assert(g.m == n - 1);
	return g;
}

Graph path(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	auto order = rnd.perm(n);
	for(int i = 0; i < n - 1; i++) {
		add_edge(g, order[i], order[i + 1]);
	}
	assert(g.m == n - 1);
	return g;
}

Graph star(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	auto order = rnd.perm(n);
	for(int i = 1; i < n; i++) {
		add_edge(g, order[0], order[i]);
	}
	assert(g.m == n - 1);
	return g;
}

Graph perfect(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			add_edge(g, i, j);
		}
	}
	return g;
}

Graph simple(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	auto order = rnd.perm(n);
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			if(rnd.next(0, 1)) {
				add_edge(g, i, j);
			}
		}
	}
	return g;
}

Graph namori(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	add_edge(g, 0, rnd.next(1, n - 1));
	for(int i = 1; i < n; i++) {
		add_edge(g, i, rnd.next(0, i - 1));
	}
	return g;
}

Graph sparse(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	if(n == 0) {
		return g;
	}
	int m = rnd.next(0, n - 1);
	std::set<std::pair<int, int>> edges;
	while((int) edges.size() < m) {
		int u = rnd.next(0, n - 1);
		int v = rnd.next(0, n - 1);
		if(u >= v) {
			continue;
		}
		edges.emplace(u, v);
	}
	for(auto [u, v] : edges) {
		add_edge(g, u, v);
	}
	return g;
}

Graph connected(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	if(n == 1) {
		return g;
	}
	std::set<std::pair<int, int>> s;
	auto perm = rnd.perm(n);
	for(int i = 1; i < n; i++) {
		int u = perm[rnd.next(i)];
		int v = perm[i];
		add_edge(g, u, v);
		s.emplace(std::min(u, v), std::max(u, v));
	}
	int extra = rnd.next(n, 10 * n);
	for(int i = 0; i < extra; i++) {
		int u = rnd.next(n - 1);
		int v = rnd.next(u + 1, n - 1);
		if(s.count({u, v})) {
			continue;
		}
		s.emplace(u, v);
		add_edge(g, u, v);
	}
	return g;
}

Graph bipartite(int n, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	set_weight(weighted, w_min, w_max);
	Graph g(n, weighted);
	if(n == 1) {
		return g;
	}
	auto perm = rnd.perm(n);
	int l_cnt = rnd.next(1, n - 1);
	auto lv = std::vector<int>(perm.begin(), perm.begin() + l_cnt);
	auto rv = std::vector<int>(perm.begin() + l_cnt, perm.end());
	for(auto u : lv) {
		for(auto v : rv) {
			if(rnd.next(0, 1)) {
				add_edge(g, u, v);
			}
		}
	}
	return g;
}

Graph generate(int n, bool is_tree = false, bool weighted = false, long long w_min = 1, long long w_max = 1) {
	using F = std::function<Graph(int, bool, long long, long long)>;
	std::vector<F> f{tree, path, star, perfect, simple, namori, sparse, bipartite};
	int mx = (is_tree ? 2 : (int) f.size());
	return f[rnd.next(0, mx)](n, weighted, w_min, w_max);
}

} // namespace GraphGenerator

} // namespace felix

Back to top page