random_graph/gen.hpp

View this file on GitHub
Last update: 2026-06-19 18:03:18+09:00
Include: #include "random_graph/gen.hpp"

Depends on

Code

#pragma once

#include <array>
#include <cassert>
#include <chrono>
#include <numeric>
#include <set>
#include <vector>

#include "graph.hpp"
#include "random.hpp"

// ジェネレータ本体
struct UndirectedGraphGenerator {
 private:
  // 乱数生成器 (staticメンバ変数の代わり)
  Random& _gen() {
    static Random gen{};
    return gen;
  }
  // [l, r]上の一様乱数を生成
  long long random(long long l, long long r) {
    assert(l <= r && "UndirectedGraphGenerator::random(l, r)");
    return _gen().uniform(l, r);
  }
  // vをランダムにシャッフル
  template <typename U>
  void random_shuffle(vector<U>& v) {
    _gen().shuffle(begin(v), end(v));
  }

  W _w_min, _w_max;

  // 辺の重みを設定
  void set_weight(bool weighted, W w_min, W w_max) {
    _w_min = w_min, _w_max = w_max;
    if (!weighted) _w_min = _w_max = 1;
  }

  // 辺を追加
  void add_edge(Graph& g, int i, int j) {
    W w = _w_min == _w_max ? _w_min : random(_w_min, _w_max);
    g.add_undirected_edge(i, j, w);
  }

  // 乱数生成s
  unsigned long long random_seed() const {
    unsigned long long seed =
        chrono::duration_cast<chrono::nanoseconds>(
            chrono::high_resolution_clock::now().time_since_epoch())
            .count();
    return seed;
  }

 public:
  UndirectedGraphGenerator(unsigned long long seed = 0) : _w_min(1), _w_max(1) {
    if (seed == 0) seed = random_seed();
    set_seed(seed);
  }

  // シードを設定する
  void set_seed(unsigned long long seed) { _gen() = Random{seed ^ 1333uLL}; }

  /**
   * ランダムケース生成用。
   *  条件を満たす全ての関数の中からランダムに1つを選んでグラフを生成。
   */
  Graph test(int n, bool is_tree = true, bool weighted = false, W w_min = 1,
             W w_max = 1) {
    using F = Graph (UndirectedGraphGenerator::*)(int, bool, W, W);
    vector<F> f{tree, path, star, perfect, simple, namori, simple_sparse};
    int mx = is_tree ? 2 : 6;
    return (this->*f[random(0, mx)])(n, weighted, w_min, w_max);
  }

  // ランダムな無向の木を出力
  Graph tree(int n, bool weighted = false, W w_min = 1, W w_max = 1) {
    set_weight(weighted, w_min, w_max);
    Graph g(n, weighted);
    if (n == 2) add_edge(g, 0, 1);
    if (n <= 2) return g;
    vector<int> code(n - 2), deg(n, 1);
    for (auto& i : code) i = random(0, n - 1), deg[i]++;
    set<int> js;
    for (int j = 0; j < n; j++) {
      if (deg[j] == 1) js.insert(j);
    }
    for (auto& i : code) {
      int j = *js.begin();
      add_edge(g, i, j);
      js.erase(begin(js));
      if (--deg[i] == 1) js.insert(i);
      deg[j]--;
    }
    int u = *js.begin(), v = *next(js.begin());
    add_edge(g, u, v);
    assert(g.edges_size() == n - 1);
    return g;
  }

  // ランダムな無向のパスグラフを出力
  Graph path(int n, bool weighted = false, W w_min = 1, W w_max = 1) {
    set_weight(weighted, w_min, w_max);
    vector<int> ord(n);
    iota(begin(ord), end(ord), 0);
    random_shuffle(ord);
    Graph g(n, weighted);
    for (int i = 0; i < n - 1; i++) add_edge(g, ord[i], ord[i + 1]);
    return g;
  }

  // ランダムな無向のスターグラフを出力
  Graph star(int n, bool weighted = false, W w_min = 1, W w_max = 1) {
    set_weight(weighted, w_min, w_max);
    vector<int> ord(n);
    iota(begin(ord), end(ord), 0);
    random_shuffle(ord);
    Graph g(n, weighted);
    for (int i = 1; i < n; i++) add_edge(g, ord[0], ord[i]);
    return g;
  }

  // 完全グラフ
  Graph perfect(int n, bool weighted = false, W w_min = 1, W 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, W w_min = 1, W 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++) {
        if (random(0, 1) == 1) add_edge(g, i, j);
      }
    }
    return g;
  }

  // なもりグラフ
  Graph namori(int n, bool weighted = false, W w_min = 1, W w_max = 1) {
    set_weight(weighted, w_min, w_max);
    Graph g(n, weighted);
    for (int i = 0; i < n; i++) {
      if (i == 0) {
        add_edge(g, i, random(1, n - 1));
      } else {
        add_edge(g, i, random(0, i - 1));
      }
    }
    return g;
  }

  // 疎な単純グラフ
  Graph simple_sparse(int n, bool weighted = false, W w_min = 1, W w_max = 1) {
    set_weight(weighted, w_min, w_max);
    if (n == 0) return Graph{};
    int m = random(0, n - 1);
    set<pair<int, int>> es;
    while ((int)es.size() < m) {
      int i = random(0, n - 1);
      int j = random(0, n - 1);
      if (i >= j) continue;
      es.emplace(i, j);
    }
    Graph g(n, weighted);
    for (auto& [i, j] : es) add_edge(g, i, j);
    return g;
  }
} undirected;

#line 2 "random_graph/gen.hpp"

#include <array>
#include <cassert>
#include <chrono>
#include <numeric>
#include <set>
#include <vector>

#line 2 "random_graph/graph.hpp"

#include <algorithm>
#line 5 "random_graph/graph.hpp"
#include <iostream>
#line 7 "random_graph/graph.hpp"

using namespace std;

// 辺の重みはlong long決め打ち
using W = long long;

// 辺の情報を格納する構造体
struct Edge {
  int u, v;
  W w;
  int idx;
  Edge(int _u, int _v, W _w = 1, int _idx = -1)
      : u(_u), v(_v), w(_w), idx(_idx) {}
};

// グラフの情報を格納する構造体
struct Graph {
 private:
  int n, m;
  vector<Edge> es;
  bool weighted;

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

  int edges_size() const { return m; }

  // u -> v, 重み w の辺を追加
  // 0-indexed で追加する必要あり
  void add_directed_edge(int u, int v, W w = 1, int idx = -1) {
    es.emplace_back(u, v, w, idx);
    m++;
  }

  // min(u,v) -> max(u,v), 重み w の辺を追加
  // 0-indexed で追加する必要あり
  void add_undirected_edge(int u, int v, W w = 1, int idx = -1) {
    int mn = min(u, v), mx = max(u, v);
    add_directed_edge(mn, mx, w, idx);
  }

  // 隣接リストを返す
  vector<vector<Edge>> adjacent_list(bool directed = false) const {
    vector<vector<Edge>> g(n);
    for (auto& [u, v, w, i] : es) {
      g[u].emplace_back(u, v, w, i);
      if (!directed) g[v].emplace_back(v, u, w, i);
    }
    return g;
  }

  // 隣接行列を返す
  vector<vector<W>> adjacent_matrix(bool directed = false) const {
    vector<vector<W>> g(n, vector<W>(n, 0));
    for (auto& [u, v, w, _] : es) {
      g[u][v] = w;
      if (!directed) g[v][u] = w;
    }
    return g;
  }

  // グラフを隣接行列の形式で出力
  void print_matrix(ostream& os, bool directed = false) const {
    auto g = adjacent_matrix(directed);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        os << g[i][j] << " \n"[j == n - 1];
      }
    }
  }

  // グラフの辺情報を一般的な形式で出力
  void print_edge(ostream& os, bool origin_0 = false) const {
    for (auto& e : es) {
      os << e.u + (origin_0 ? 0 : 1);
      os << " " << e.v + (origin_0 ? 0 : 1);
      if (weighted) os << " " << e.w;
      os << "\n";
    }
  }

  // グラフを一般的な形式で出力
  void print(ostream& os, bool origin_0 = false) const {
    os << n << " " << m << "\n";
    print_edge(os, origin_0);
  }

  friend ostream& operator<<(ostream& os, const Graph& g) {
    g.print(os);
    return os;
  }
};
#line 2 "random_graph/random.hpp"

// SPDX-License-Identifier: Apache-2.0
// This file includes code derived from Library Checker Problems:
//   https://github.com/yosupo06/library-checker-problems/blob/1e3da4fd4135f4f3cb3a6d76b51c827f7d987942/common/random.h
//
// The original work is licensed under the Apache License, Version 2.0.
//
// Local modifications in this repository:
// - Moved #pragma once to the first line for oj-bundle compatibility.
// - Made this header self-contained by adding missing standard library
//   includes and removing an unused include.

#line 17 "random_graph/random.hpp"
#include <cstddef>
#include <cstdint>
#line 21 "random_graph/random.hpp"
#include <string>
#include <utility>
#line 24 "random_graph/random.hpp"

struct Random {
  private:
    // Use xoshiro256**
    // References: http://xoshiro.di.unimi.it/xoshiro256starstar.c
    static uint64_t rotl(const uint64_t x, int k) {
        return (x << k) | (x >> (64 - k));
    }

    std::array<uint64_t, 4> s;

    uint64_t next() {
        const uint64_t result_starstar = rotl(s[1] * 5, 7) * 9;

        const uint64_t 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_starstar;
    }

    // random choice from [0, upper]
    uint64_t next(uint64_t upper) {
        if (!(upper & (upper + 1))) {
            // b = 00..0011..11
            return next() & upper;
        }
        int lg = 63 - __builtin_clzll(upper);
        uint64_t mask = (lg == 63) ? ~0ULL : (1ULL << (lg + 1)) - 1;
        while (true) {
            uint64_t r = next() & mask;
            if (r <= upper)
                return r;
        }
    }

  public:
    Random(uint64_t seed = 0) {
        // Use splitmix64
        // Reference: http://xoshiro.di.unimi.it/splitmix64.c
        for (int i = 0; i < 4; i++) {
            uint64_t z = (seed += 0x9e3779b97f4a7c15);
            z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
            z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
            s[i] = z ^ (z >> 31);
        }
    }

    // random choice from [lower, upper]
    template <class T>
    T uniform(T lower, T upper) {
        assert(lower <= upper);
        return T(lower + next(uint64_t(upper - lower)));
    }

    // random choice from false or true
    bool uniform_bool() { return uniform(0, 1) == 1; }

    // random choice from [0.0, 1.0]
    double uniform01() {
        uint64_t v = next(1ULL << 63);
        return double(v) / (1ULL << 63);
    }

    // random choice non-empty sub-interval from interval [lower, upper)
    // equal: random choice 2 disjoint elements from [lower, upper]
    template <class T>
    std::pair<T, T> uniform_pair(T lower, T upper) {
        assert(upper - lower >= 1);
        T a, b;
        do {
            a = uniform(lower, upper);
            b = uniform(lower, upper);
        } while (a == b);
        if (a > b) std::swap(a, b);
        return {a, b};
    }

    // generate random lower string that length = n
    std::string lower_string(std::size_t n) {
        std::string res = "";
        for (std::size_t i = 0; i < n; i++) {
            res += uniform('a', 'z');
        }
        return res;
    }

    // random shuffle
    template <class Iter>
    void shuffle(Iter first, Iter last) {
        if (first == last) return;
        // Reference and edit:
        // cpprefjp - C++日本語リファレンス
        // (https://cpprefjp.github.io/reference/algorithm/shuffle.html)
        int len = 1;
        for (auto it = first + 1; it != last; it++) {
            len++;
            int j = uniform(0, len - 1);
            if (j != len - 1)
                iter_swap(it, first + j);
        }
    }

    // generate random permutation that length = n
    template <class T>
    std::vector<T> perm(std::size_t n) {
        std::vector<T> idx(n);
        std::iota(idx.begin(), idx.end(), T(0));
        shuffle(idx.begin(), idx.end());
        return idx;
    }

    // random choice n elements from [lower, upper]
    template <class T>
    std::vector<T> choice(std::size_t n, T lower, T upper) {
        assert(T(n) <= upper - lower + 1);
        std::set<T> res;
        while (res.size() < n) res.insert(uniform(lower, upper));
        return {res.begin(), res.end()};
    }
} global_gen;
#line 12 "random_graph/gen.hpp"

// ジェネレータ本体
struct UndirectedGraphGenerator {
 private:
  // 乱数生成器 (staticメンバ変数の代わり)
  Random& _gen() {
    static Random gen{};
    return gen;
  }
  // [l, r]上の一様乱数を生成
  long long random(long long l, long long r) {
    assert(l <= r && "UndirectedGraphGenerator::random(l, r)");
    return _gen().uniform(l, r);
  }
  // vをランダムにシャッフル
  template <typename U>
  void random_shuffle(vector<U>& v) {
    _gen().shuffle(begin(v), end(v));
  }

  W _w_min, _w_max;

  // 辺の重みを設定
  void set_weight(bool weighted, W w_min, W w_max) {
    _w_min = w_min, _w_max = w_max;
    if (!weighted) _w_min = _w_max = 1;
  }

  // 辺を追加
  void add_edge(Graph& g, int i, int j) {
    W w = _w_min == _w_max ? _w_min : random(_w_min, _w_max);
    g.add_undirected_edge(i, j, w);
  }

  // 乱数生成s
  unsigned long long random_seed() const {
    unsigned long long seed =
        chrono::duration_cast<chrono::nanoseconds>(
            chrono::high_resolution_clock::now().time_since_epoch())
            .count();
    return seed;
  }

 public:
  UndirectedGraphGenerator(unsigned long long seed = 0) : _w_min(1), _w_max(1) {
    if (seed == 0) seed = random_seed();
    set_seed(seed);
  }

  // シードを設定する
  void set_seed(unsigned long long seed) { _gen() = Random{seed ^ 1333uLL}; }

  /**
   * ランダムケース生成用。
   *  条件を満たす全ての関数の中からランダムに1つを選んでグラフを生成。
   */
  Graph test(int n, bool is_tree = true, bool weighted = false, W w_min = 1,
             W w_max = 1) {
    using F = Graph (UndirectedGraphGenerator::*)(int, bool, W, W);
    vector<F> f{tree, path, star, perfect, simple, namori, simple_sparse};
    int mx = is_tree ? 2 : 6;
    return (this->*f[random(0, mx)])(n, weighted, w_min, w_max);
  }

  // ランダムな無向の木を出力
  Graph tree(int n, bool weighted = false, W w_min = 1, W w_max = 1) {
    set_weight(weighted, w_min, w_max);
    Graph g(n, weighted);
    if (n == 2) add_edge(g, 0, 1);
    if (n <= 2) return g;
    vector<int> code(n - 2), deg(n, 1);
    for (auto& i : code) i = random(0, n - 1), deg[i]++;
    set<int> js;
    for (int j = 0; j < n; j++) {
      if (deg[j] == 1) js.insert(j);
    }
    for (auto& i : code) {
      int j = *js.begin();
      add_edge(g, i, j);
      js.erase(begin(js));
      if (--deg[i] == 1) js.insert(i);
      deg[j]--;
    }
    int u = *js.begin(), v = *next(js.begin());
    add_edge(g, u, v);
    assert(g.edges_size() == n - 1);
    return g;
  }

  // ランダムな無向のパスグラフを出力
  Graph path(int n, bool weighted = false, W w_min = 1, W w_max = 1) {
    set_weight(weighted, w_min, w_max);
    vector<int> ord(n);
    iota(begin(ord), end(ord), 0);
    random_shuffle(ord);
    Graph g(n, weighted);
    for (int i = 0; i < n - 1; i++) add_edge(g, ord[i], ord[i + 1]);
    return g;
  }

  // ランダムな無向のスターグラフを出力
  Graph star(int n, bool weighted = false, W w_min = 1, W w_max = 1) {
    set_weight(weighted, w_min, w_max);
    vector<int> ord(n);
    iota(begin(ord), end(ord), 0);
    random_shuffle(ord);
    Graph g(n, weighted);
    for (int i = 1; i < n; i++) add_edge(g, ord[0], ord[i]);
    return g;
  }

  // 完全グラフ
  Graph perfect(int n, bool weighted = false, W w_min = 1, W 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, W w_min = 1, W 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++) {
        if (random(0, 1) == 1) add_edge(g, i, j);
      }
    }
    return g;
  }

  // なもりグラフ
  Graph namori(int n, bool weighted = false, W w_min = 1, W w_max = 1) {
    set_weight(weighted, w_min, w_max);
    Graph g(n, weighted);
    for (int i = 0; i < n; i++) {
      if (i == 0) {
        add_edge(g, i, random(1, n - 1));
      } else {
        add_edge(g, i, random(0, i - 1));
      }
    }
    return g;
  }

  // 疎な単純グラフ
  Graph simple_sparse(int n, bool weighted = false, W w_min = 1, W w_max = 1) {
    set_weight(weighted, w_min, w_max);
    if (n == 0) return Graph{};
    int m = random(0, n - 1);
    set<pair<int, int>> es;
    while ((int)es.size() < m) {
      int i = random(0, n - 1);
      int j = random(0, n - 1);
      if (i >= j) continue;
      es.emplace(i, j);
    }
    Graph g(n, weighted);
    for (auto& [i, j] : es) add_edge(g, i, j);
    return g;
  }
} undirected;

Nyaan's Library

This documentation is automatically generated by online-judge-tools/verification-helper

random_graph/gen.hpp

Depends on

Code