Processing math: 100%
My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Random Graph Generator

コードについての説明(個人的メモ)

ランダムグラフを生成するアルゴリズム. 1 つ目は簡単なものの寄せ集め(Erdős–Rényi (ER)モデルとか) で 2 つ目は次数列が与えられたときにそれを満たすような(連結な)グラフを一様ランダムで生成するアルゴリズムになっている. 元論文は "Efficient Generation of Large Random Networks" [Batagelj Brandes 2005] および "Efficient and simple generation of random simple connected graphswith prescribed degree sequence" [Viger, Latapy 2011]
(注) verify してないのでちゃんとやらないと...

Random Graph Generator

  1. struct pair_hash {
  2.     template <class T1, class T2>
  3.     size_t operator() (const pair<T1, T2>& p) const {
  4.         size_t lhs = hash<T1>()(p.first), rhs = hash<T2>()(p.second);
  5.         return lhs^(rhs+0x9e3779b9+(lhs<<6)+(lhs>>2));
  6.     }
  7. };
  8.  
  9. // (多重辺、自己ループも許した)ランダムグラフ (計算量 O(m))
  10. void random_graph(const int node_size, const int edge_size, vector<vector<int> >& graph){
  11.     random_device rnd;
  12.     mt19937 mt(rnd());
  13.     uniform_int_distribution<> _rand(0, node_size-1);
  14.     for(int i = 0; i < edge_size; i++){
  15.         int from = _rand(mt), to = _rand(mt);
  16.         graph[from].push_back(to), graph[to].push_back(from);
  17.     }
  18. }
  19.  
  20. // G(n, p) (各辺が確率 p で存在) (平均計算量 O(np))
  21. void given_probability_random_simple_graph(const int node_size, const double prob, vector<vector<int> >& graph){
  22.     random_device rnd;
  23.     mt19937 mt(rnd());
  24.     uniform_real_distribution<double> _rand(0.0, 1.0);
  25.     int v = 1, w = -1;
  26.     while(v < node_size){
  27.         w += 1 + floor(log(1.0 -_rand(mt))/log(1.0 - prob));
  28.         while(w >= v && v < node_size) w -= v, v++;
  29.         if(v < node_size) graph[v].push_back(w), graph[w].push_back(v);
  30.     }
  31. }
  32.  
  33. // G(n, m) ランダムな単純グラフ (平均計算量 O(m))
  34. void random_simple_graph(const int node_size, int edge_size, vector<vector<int> >& graph){
  35.     assert(edge_size <= (long long)(node_size)*(node_size-1)/2);
  36.     bool complement = false;
  37.     if((edge_size > (long long)(node_size)*(node_size-1)/4)){
  38.         complement = true;
  39.         edge_size = (long long)(node_size)*(node_size-1)/2 - edge_size;
  40.     }
  41.     unordered_set<pair<int, int>, pair_hash> edge_set;
  42.     random_device rnd;
  43.     mt19937 mt(rnd());
  44.     uniform_int_distribution<> rand1(0, node_size-1), rand2(0, node_size-2);
  45.     for(int i = 0; i < edge_size; i++){
  46.         while(true){
  47.             int from = rand1(mt), to = rand2(mt);
  48.             if(to < from) swap(from, to); else to++;
  49.             if(edge_set.find({from, to}) != edge_set.end()) continue;
  50.             if(!complement){
  51.                 graph[from].push_back(to), graph[to].push_back(from);
  52.             }
  53.             edge_set.insert({from, to});
  54.             break;
  55.         }
  56.     }
  57.     if(complement){
  58.         for(int i = 0; i < node_size-1; i++){
  59.             for(int j = i+1; j < node_size; j++){
  60.                 if(edge_set.find({i, j}) == edge_set.end()){
  61.                     graph[i].push_back(j), graph[j].push_back(i);
  62.                 }
  63.             }
  64.         }
  65.     }
  66. }
  67.  
  68. // ランダムな単純連結グラフ (平均計算量 O(m))
  69. void random_simple_connected_graph(const int node_size, int edge_size, vector<vector<int> >& graph){
  70.     assert(edge_size >= node_size - 1);
  71.     assert(edge_size <= (long long)(node_size)*(node_size-1)/2);
  72.     unordered_set<pair<int, int>, pair_hash> edge_set;
  73.     random_device rnd;
  74.     mt19937 mt(rnd());
  75.     vector<int> ver(node_size);
  76.     iota(ver.begin(), ver.end(), 0);
  77.     shuffle(ver.begin(), ver.end(), mt);
  78.     for(int i = 1; i < node_size; i++){
  79.         int u = mt() % i;
  80.         graph[ver[u]].push_back(ver[i]), graph[ver[i]].push_back(ver[u]);
  81.         edge_set.insert({min(ver[i], ver[u]), max(ver[i], ver[u])});
  82.     }
  83.     edge_size -= node_size - 1;
  84.     bool complement = false;
  85.     if((edge_size > (long long)(node_size)*(node_size-1)/4)){
  86.         complement = true;
  87.         edge_size = (long long)(node_size)*(node_size-1)/2 - edge_size;
  88.     }
  89.     uniform_int_distribution<> rand1(0, node_size-1), rand2(0, node_size-2);
  90.     for(int i = 0; i < edge_size; i++){
  91.         while(true){
  92.             int from = rand1(mt), to = rand2(mt);
  93.             if(to < from) swap(from, to); else to++;
  94.             if(edge_set.find({from, to}) != edge_set.end()) continue;
  95.             if(!complement){
  96.                 graph[from].push_back(to), graph[to].push_back(from);
  97.             }
  98.             edge_set.insert({from, to});
  99.             break;
  100.         }
  101.     }
  102.     if(complement){
  103.         for(int i = 0; i < node_size-1; i++){
  104.             for(int j = i+1; j < node_size; j++){
  105.                 if(edge_set.find({i, j}) == edge_set.end()){
  106.                     graph[i].push_back(j), graph[j].push_back(i);
  107.                 }
  108.             }
  109.         }
  110.     }
  111. }
  112.  
  113. // ランダムな木 (計算量 O(n))
  114. void random_tree(const int node_size, vector<vector<int> >& graph){
  115.     random_device rnd;
  116.     mt19937 mt(rnd());
  117.     vector<int> ver(node_size);
  118.     iota(ver.begin(), ver.end(), 0);
  119.     shuffle(ver.begin(), ver.end(), mt);
  120.     for(int i = 1; i < node_size; i++){
  121.         int u = mt() % i;
  122.         graph[ver[u]].push_back(ver[i]), graph[ver[i]].push_back(ver[u]);
  123.     }
  124. }
  125.  
  126. // 一様ランダムな木 (計算量 O(n log n))
  127. void uniformly_random_tree(const int node_size, vector<vector<int> >& graph){
  128.     random_device rnd;
  129.     mt19937 mt(rnd());
  130.     uniform_int_distribution<> _rand(0, node_size - 1);
  131.     vector<int> prufer_code(node_size - 2);
  132.     vector<int> used(node_size, 0);
  133.     set<int> unused;
  134.     for(int i = 0; i < node_size - 2; ++i){
  135.         prufer_code[i] = _rand(mt);
  136.         ++used[prufer_code[i]];
  137.     }
  138.     for(int i = 0; i < node_size; ++i){
  139.         if(!used[i]) unused.insert(i);
  140.     }
  141.     for(int i = 0; i < node_size - 2; ++i){
  142.         const int ver = *unused.begin();
  143.         graph[prufer_code[i]].push_back(ver);
  144.         graph[ver].push_back(prufer_code[i]);
  145.         unused.erase(unused.begin());
  146.         if(--used[prufer_code[i]] == 0){
  147.             unused.insert(prufer_code[i]);
  148.         }
  149.     }
  150.     const int ver1 = *unused.begin(), ver2 = *next(unused.begin(), 1);
  151.     graph[ver1].push_back(ver2);
  152.     graph[ver2].push_back(ver1);
  153. }

Random Simple Connected Graphs with Prescribed Degree Sequence

  1. // 次数列 d とグラフ G(vector<vecotr<int> >型で予め頂点数分の配列を確保する), 連結であるべきかを与える.
  2. // TIME は適宜設定する.
  3. class GraphGenerator {
  4. private:
  5.     int V;
  6.     bool connected;
  7.     vector<unordered_set<int> > G;
  8.     vector<vector<pair<int, int> > > off_tree;
  9.     vector<pair<int, int> > population;
  10.     vector<int> visit, non_tree, tree;
  11.     chrono::high_resolution_clock::time_point start;
  12.     random_device rnd;
  13.     mt19937 mt;
  14.     const int TIME = 1000; // (ms)
  15.     static constexpr double UP = 1.13108324944;
  16.     static constexpr double DOWN = 0.92371260217;
  17.     int _time() const noexcept {
  18.         chrono::high_resolution_clock::time_point end = chrono::high_resolution_clock::now();
  19.         return (int)chrono::duration_cast<chrono::milliseconds>(end - start).count();
  20.     }
  21.     bool check() const noexcept {
  22.         if(*max_element(degree.begin(), degree.end()) >= V) return false;
  23.         if(*min_element(degree.begin(), degree.end()) <= -(!connected)) return false;
  24.         long long edge_size = accumulate(degree.begin(), degree.end(), 0LL);
  25.         if(edge_size % 2 || (connected && edge_size < 2 * (V - 1))) return false;
  26.         return true;
  27.     }
  28.     void add_edge(const int u, const int v) noexcept { G[u].insert(v), G[v].insert(u); }
  29.     void erase_edge(const int u, const int v) noexcept { G[u].erase(v), G[v].erase(u); }
  30.     void swap_edge(const pair<int, int>& p, const pair<int, int>& q) noexcept {
  31.         erase_edge(p.first, p.second), erase_edge(q.first, q.second);
  32.         add_edge(p.first, q.first), add_edge(p.second, q.second);
  33.     }
  34.     bool construct_init_graph() noexcept {
  35.         const int node_size = (int)degree.size();
  36.         const int max_degree = *max_element(degree.begin(), degree.end());
  37.         if(max_degree > node_size - 1) return false;
  38.         if(accumulate(degree.begin(), degree.end(), 0LL) % 2 == 1) return false;
  39.         vector<stack<int> > bucket(max_degree + 1);
  40.         vector<int> deg_cnt(max_degree + 1, 0);
  41.         for(int i = 0; i < node_size; ++i) bucket[degree[i]].push(i);
  42.         vector<pair<int, int> > deg_seq;
  43.         for(int i = max_degree; i >= 1; --i){
  44.             deg_cnt[i] = (int)bucket[i].size();
  45.             while(!bucket[i].empty()){
  46.                 deg_seq.emplace_back(i, bucket[i].top()), bucket[i].pop();
  47.             }
  48.         }
  49.         while(!deg_seq.empty()){
  50.             int pos = 0, rem = deg_seq.back().first, cur_degree;
  51.             const int ver = deg_seq.back().second;
  52.             --deg_cnt[rem], deg_seq.pop_back();
  53.             stack<int> update;
  54.             while(rem > 0){
  55.                 if(pos >= (int)deg_seq.size()) return false;
  56.                 cur_degree = deg_seq[pos].first;
  57.                 const int start = max(pos, pos + deg_cnt[cur_degree] - rem);
  58.                 for(int i = start; i < pos + deg_cnt[cur_degree]; ++i){
  59.                     add_edge(ver, deg_seq[i].second);
  60.                     --deg_seq[i].first, update.push(cur_degree);
  61.                 }
  62.                 pos += deg_cnt[cur_degree], rem -= deg_cnt[cur_degree];
  63.             }
  64.             while(!update.empty()){
  65.                 --deg_cnt[update.top()], ++deg_cnt[update.top() - 1], update.pop();
  66.             }
  67.             while(!deg_seq.empty() && deg_seq.back().first == 0) deg_seq.pop_back();
  68.         }
  69.         return true;
  70.     }
  71.     void dfs(const int u, const int p, const int c) noexcept {
  72.         visit[u] = 1;
  73.         for(int v : G[u]){
  74.             if(!visit[v]) dfs(v, u, c);
  75.             else if(v != p && visit[v] == 1) off_tree[c].emplace_back(u, v);
  76.         }
  77.         visit[u] = 2;
  78.     }
  79.     void detect_component() noexcept {
  80.         int comp_size = 0;
  81.         for(int i = 0; i < V; i++){
  82.             if(!visit[i]){
  83.                 off_tree.push_back(vector<pair<int, int> >());
  84.                 dfs(i, -1, comp_size++);
  85.                 if(off_tree.back().empty()){
  86.                     off_tree.back().emplace_back(min(i, *G[i].begin()), -max(i, *G[i].begin()));
  87.                 }
  88.             }
  89.         }
  90.         for(int i = 0; i < comp_size; i++){
  91.             if(off_tree[i][0].second < 0) tree.push_back(i);
  92.             else non_tree.push_back(i);
  93.         }
  94.     }
  95.     void transform_to_connected_graph() noexcept {
  96.         detect_component();
  97.         while(!tree.empty()){
  98.             int id = non_tree.back();
  99.             while(!off_tree[id].empty() && !tree.empty()){
  100.                 pair<int, int> p = off_tree[id].back(), q = off_tree[tree.back()][0];
  101.                 q.second = -q.second;
  102.                 swap_edge(p, q);
  103.                 off_tree[id].pop_back(), tree.pop_back();
  104.             }
  105.             if(off_tree[id].empty()) non_tree.pop_back();
  106.         }
  107.         while((int)non_tree.size() >= 2){
  108.             int q = non_tree.back(); non_tree.pop_back();
  109.             int p = non_tree.back(); non_tree.pop_back();
  110.             pair<int, int> e1 = off_tree[p].back(), e2 = off_tree[q].back();
  111.             off_tree[p].pop_back(), off_tree[q].pop_back();
  112.             swap_edge(e1, e2);
  113.             off_tree[q].emplace_back(e1.first, e2.first);
  114.             for(auto& e : off_tree[p]) off_tree[q].push_back(e);
  115.             non_tree.push_back(q);
  116.         }
  117.     }
  118.     void dfs(const int u, const int p, int& ver_sm, vector<bool>& _visit) const noexcept {
  119.         _visit[u] = true, ver_sm++;
  120.         for(int v : G[u]) if(!_visit[v]) dfs(v, u, ver_sm, _visit);
  121.     }
  122.     bool IsConnected() const noexcept {
  123.         int ver_sm = 0;
  124.         vector<bool> _visit(V, false);
  125.         dfs(0, -1, ver_sm, _visit);
  126.         return (ver_sm == V);
  127.     }
  128.     bool check_swap_edge(const pair<int, int>& p, const pair<int, int>& q) noexcept {
  129.         if(G[p.first].find(q.first) != G[p.first].end()) return false;
  130.         if(G[p.second].find(q.second) != G[p.second].end()) return false;
  131.         erase_edge(p.first, p.second), erase_edge(q.first, q.second);
  132.         add_edge(p.first, q.first), add_edge(p.second, q.second);
  133.         return true;
  134.     }
  135.     bool transition(pair<int, int> p, pair<int, int> q, bool flag) noexcept {
  136.         if(p.first == q.second || p.second == q.first || p.second == q.second) return false;
  137.         if(flag) swap(q.first, q.second);
  138.         return check_swap_edge(p, q);
  139.     }
  140.     void shuffle_graph() noexcept {
  141.         for(int i = 0; i < V; i++) for(int j = 0; j < degree[i]; j++) population.emplace_back(i, j);
  142.         uniform_int_distribution<> _rand(0, (int)population.size()-1);
  143.         int window = 1;
  144.         double ex_window = 1.0;
  145.         while(true){
  146.             vector<unordered_set<int> > tmpG;
  147.             if(connected) tmpG = G;
  148.             bool finish = false, done = false;
  149.             for(int i = 0; i < window; i++){
  150.                 pair<int, int> id1 = {0, 0}, id2 = {0, 0};
  151.                 while(id1.first == id2.first) id1 = population[_rand(mt)], id2 = population[_rand(mt)];
  152.                 unordered_set<int>::iterator it1 = G[id1.first].begin(), it2 = G[id2.first].begin();
  153.                 advance(it1, id1.second), advance(it2, id2.second);
  154.                 done |= transition({id1.first, *it1}, {id2.first, *it2}, mt() % 2);
  155.                 if(_time() > TIME){ finish = true; break; }
  156.             }
  157.             if(!connected || !done || IsConnected()){
  158.                 loop_count += window, ex_window *= UP, window = round(ex_window);
  159.             }
  160.             else G = tmpG, ex_window *= DOWN, window = max((int)round(ex_window), 1);
  161.             if(finish) break;
  162.         }
  163.     }
  164.     void construct_graph() noexcept {
  165.         vector<int> index(V);
  166.         iota(index.begin(), index.end(), 0);
  167.         shuffle(index.begin(), index.end(), mt);
  168.         for(int i : index) for(int to : G[i]) graph[i].push_back(index[to]);
  169.         for(int i = 0; i < V; i++) for(int to : G[i]) graph[i].push_back(to);
  170.     }
  171.  
  172. public:
  173.     int loop_count;
  174.     vector<vector<int> >& graph;
  175.     const vector<int>& degree;
  176.     GraphGenerator(const vector<int>& d, vector<vector<int> >& g, bool _connected=false) noexcept
  177.         : V((int)d.size()), connected(_connected), G(V), visit(V, 0),
  178.             start(chrono::high_resolution_clock::now()), mt(rnd()), loop_count(0), graph{g}, degree{d}{
  179.         assert(check());
  180.         assert(construct_init_graph());
  181.         if(connected) assert(IsConnected());
  182.         shuffle_graph();
  183.         construct_graph();
  184.     }
  185. };

verify 用の問題

verify していません(verify 問題を知らない) verify をちゃんとやらないとなぁという気はしている