圖論測資生成器

最近寫了一個 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> ,以節省重複打 firstsecond 的時間

程式碼

#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);
}

蘋果出品的程式設計教育推廣 App: Swift Playgrounds

iconSwiftPlaygrounds

說到程式設計教育推廣,網路上的資源很多,我猜,Code.org 或許是大家都知道的地方。

今天,分享一個蘋果出品,並且可能已經有不少人知道的 App:Swift Playgrounds – Apple (台灣)

swiftPlaygroundsoniPadandmacOS
本來只有 iPad 版本,後來也釋出能夠在 Catalina 以上的 macOS 運作的 Mac 版本,我在出掉手上的 iPad 之前,下載並且把玩過一段時間,同時,我也把它拿給沒有 iPad 的工程師玩過,我們對於這支 App 有相當一致的看法:非常適合程式設計的初學者。

在 Lubuntu 18.04 上安裝 CodeBlocks IDE 17.12

寫程式,弄個 IDE 真的會方便不少,如果您是要在 ubuntu 20.04 上面使用 Code::Blocks IDE 的話,直接下 sudo apt-get install codeblocks 這道指令,那麼,Code::Blocks IDE 20.03 就會安裝好,立馬可以進行 Coding。

由於我想用 Code::Blocks IDE 17.12 這個版本,而且是在 Lubuntu 上面安裝,就需要繞一點路,費一點小功夫。

先是安裝 gcc、gpp 與 g++。

再來是從官網下載 Code::Blocks IDE 17.12 的安裝檔。

最後,使用 dpkg 把程式裝起來,過程有點狀況,我試著用 sudo apt –fix-broken install 解決。