圖論測資生成器

最近寫了一個 GRAPH_GEN.h 檔，想說可以方便生成測資。

簡介

• 4~5 行是防禦性程式設計，避免多次引用標頭檔時發生編譯錯誤
• 7~19 行用來生成隨機數
• 21~32 行是帶有建構式的 edge 物件
• 底下就是生成測資的物件

具體使用

• GenTree(n) -> 生成一個有 n 個點，且無邊權的無根樹
• GenConnectedGraph(n,m) -> 生成一個有 n 個點， m 條邊，且無邊權的連通圖
• GenGraph(n,m) -> 生成一個有 n 個點， m 條邊，且無邊權的不保證連通圖
• GenTree(n,k) -> 生成一個有 n 個點，且邊權介於 1~k 的無根樹
• GenConnectedGraph(n,m,k) -> 生成一個有 n 個點， m 條邊，且邊權介於 1~k 的連通圖
• GenGraph(n,m,k) -> 生成一個有 n 個點， m 條邊，且邊權介於 1~k 的不保證連通圖

前三個會回傳 vector<pair<int,int>> 每個皆有保證沒有自環，後三個則會回傳 vector<edge> ，以節省重複打 first 與 second 的時間

程式碼

#include<bits/stdc++.h>
using namespace std;

#ifndef GRAPH_GEN
#define GRAPH_GEN

unsigned seed=chrono::steady_clock().now().time_since_epoch().count();
mt19937_64 rng(seed);

using ll=long long;

ll Rand(ll a,ll b){
    uniform_int_distribution<ll> dis(a,b);
    return dis(rng);
}

ll Rand(ll a){
    return Rand(1,a);
}

struct edge{
    int from,to;
    long long dis;

    edge(){}

    edge(int f,int t,long long d){
        from=f;
        to=t;
        dis=d;
    }
};

class GraphGen{
    private :
        struct DSU{
            vector<int> dsu,rk;

            DSU(int n){
                dsu.resize(n+10);
                rk.resize(n+10);
                init();
            }

            void init(){
                for(int i=0;i<dsu.size();++i){
                    dsu[i]=i;
                }
            }

            int find(int a){
                if(dsu[a]==a){
                    return a;
                }else{
                    return dsu[a]=find(dsu[a]);
                }
            }

            bool same(int a,int b){
                return find(a)==find(b);
            }

            void uni(int a,int b){
                if(same(a,b)){
                    return;
                }

                if(rk[find(a)]==rk[find(b)]){
                    dsu[find(b)]=find(a);
                    rk[a]++;
                }else if(rk[find(a)]>rk[find(b)]){
                    dsu[find(b)]=find(a);
                }else{
                    dsu[find(a)]=find(b);
                }
            }
        };
    public :
//      nodes 1~n
        static vector<pair<int,int>> GenTree(int n){
            DSU dsu(n);
            vector<pair<int,int>> result;

            while(result.size()<n-1){
                int a=Rand(n),b=Rand(n);
                if(!dsu.same(a,b)){
                    result.emplace_back(a,b);
                    dsu.uni(a,b);
                }
            }

            return result;
        }
//      n nodes m edges, m need to bigger than n-1
        static vector<pair<int,int>> GenConnectedGraph(int n,int m){
            vector<pair<int,int>> result=GenTree(n);

            for(int i=0;i<m-n+1;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                result.emplace_back(a,b);
            }

            return result;
        }
//      n nodes m edges, m need to bigger than n-1
        static vector<pair<int,int>> GenGraph(int n,int m){
            vector<pair<int,int>> result;

            for(int i=0;i<m;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                result.emplace_back(a,b);
            }

            return result;
        }
//      nodes 1~n, and weight in 1~k
        static vector<edge> GenTree(int n,int k){
            DSU dsu(n);
            vector<edge> result;

            while(result.size()<n-1){
                int a=Rand(n),b=Rand(n),c=Rand(k);
                if(!dsu.same(a,b)){
                    result.emplace_back(a,b,c);
                    dsu.uni(a,b);
                }
            }

            return result;
        }

        static vector<edge> GenConnectedGraph(int n,int m,int k){
            vector<edge> result=GenTree(n,k);

            for(int i=0;i<m-n+1;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                int c=Rand(k);

                result.emplace_back(a,b,c);
            }

            return result;
        }

        static vector<edge> GenGraph(int n,int m,int k){
            vector<edge> result;

            for(int i=0;i<m;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                int c=Rand(k);

                result.emplace_back(a,b,c);
            }

            return result;
        }
};

#endif

使用範例

#include<bits/stdc++.h>
#include "GRAPH_GEN.h"
using namespace std;

int main(){
    vector<pair<int,int>> edges=GraphGen::GenTree(100000);
}