随机图

id: random_graph

随机图生成代码

随机无向图

点击 
//这里我封装了一个类，可以用来生成随机无向图
// 同时它也可以生用生成随机的dag
#include <bits/stdc++.h>

//随机double
class random_double {

public:
    random_double(double l=0,double r=1)
    :   rnd( std::random_device{}()),
        dis(l,r)
    {} 

    double operator()() {
        return dis(rnd);
    }
private:
    std::mt19937 rnd;
    std::uniform_real_distribution<> dis;

};


class random_graph {

public:
    using edge  = std::pair<int,int>;

    //是不是无向图
    random_graph(int n,double p)
    : rnd(0,p),_p(p),_n(n),_m(0)
     {}

    //生成图
    void generator(){
        //任意两者点间的关系
        for(int i =1;i<=_n;i++) {
            for(int j = i+1;j<=_n;j++)
            {
                if( rnd() <= _p) 
                {
                    ++_m;
                    _edges.emplace_back(i,j);
                }
            }
        }
    }
    
    int n() const { return _n;}    
    int m() const { return _m;}    

    void print_nodes() {
        //TODO
    }

    //输出所有的边
    void print_edges() {
        // for( auto  &e : _set) {

        // }
        // for( auto it = _set.begin() ; it != _set.end();++it)
        // {
        //     std::cout << it->first << " " << it->second << '\n';
        // }
        std::for_each(_edges.begin(),_edges.end(),[](auto &e){
            std::cout << e.first << " " << e.second << '\n';
        });
    }


private:

    double _p; //存在边的概率
    int _n;//点的数量 
    int _m; 
    // std::set<std::pair<int,int>> _set;// 用来判断边<u,v>是否存
    std::vector<edge> _edges;
    random_double rnd;
};

int main(){
    random_graph rg(3,0.5);
    rg.generator();
    std::cout  << rg.n() << " ";
    std::cout  << rg.m() << "\n";
    rg.print_edges();
    return 0;
}
点击 
//这里我封装了一个类，可以用来生成随机无向图
// 同时它也可以生用生成随机的dag
// 这个算法是 n^2 不能用来生成大的图
#include <bits/stdc++.h>

//随机double
class random_double {

public:
    random_double(double l=0,double r=1)
    :   rnd( std::random_device{}()),
        dis(l,r)
    {} 

    double operator()() {
        return dis(rnd);
    }
private:
    std::mt19937 rnd;
    std::uniform_real_distribution<> dis;

};


class random_digraph {

public:
    using edge  = std::pair<int,int>;

    //是不是无向图
    random_digraph(int n,double p)
    : rnd(0,p),_p(p),_n(n),_m(0)
     {}

    //生成图
    void generator(){
        //任意两者点间的关系
        for(int i =1;i<=_n;i++) {
            for(int j = 1;j<=_n;j++)//只改这里
            {
                if( rnd() <= _p) 
                {
                    ++_m;
                    _edges.emplace_back(i,j);
                }
            }
        }
    }
    
    int n() const { return _n;}    
    int m() const { return _m;}    

    void print_nodes() {
        //TODO
    }

    //输出所有的边
    void print_edges() {
        // for( auto  &e : _set) {

        // }
        // for( auto it = _set.begin() ; it != _set.end();++it)
        // {
        //     std::cout << it->first << " " << it->second << '\n';
        // }
        std::for_each(_edges.begin(),_edges.end(),[](auto &e){
            std::cout << e.first << " " << e.second << '\n';
        });
    }


private:

    double _p; //存在边的概率
    int _n;//点的数量 
    int _m; 
    // std::set<std::pair<int,int>> _set;// 用来判断边<u,v>是否存
    std::vector<edge> _edges;
    random_double rnd;
};

int main(){
    random_digraph rg(3,0.5);
    rg.generator();
    std::cout  << rg.n() << " ";
    std::cout  << rg.m() << "\n";
    rg.print_edges();
    return 0;
}

random dag

点击 
//这里我封装了一个类，可以用来生成随机DAG
#include <bits/stdc++.h>

//随机double
class random_double {

public:
    random_double(double l=0,double r=1)
    :   rnd( std::random_device{}()),
        dis(l,r)
    {} 

    double operator()() {
        return dis(rnd);
    }
private:
    std::mt19937 rnd;
    std::uniform_real_distribution<> dis;

};


class random_dag {

public:
    using edge  = std::pair<int,int>;

    //是不是无向图
    random_dag(int n,double p)
    : rnd(0,p),_p(p),_n(n),_m(0)
     {}

    //生成图
    void generator(){
        //任意两者点间的关系
        for(int i =1;i<=_n;i++) {
            for(int j = i+1;j<=_n;j++)
            {
                if( rnd() <= _p) 
                {
                    ++_m;
                    _edges.emplace_back(i,j);
                }
            }
        }
    }
    
    int n() const { return _n;}    
    int m() const { return _m;}    

    void print_nodes() {
        //TODO
    }

    //输出所有的边
    void print_edges() {
        // for( auto  &e : _set) {

        // }
        // for( auto it = _set.begin() ; it != _set.end();++it)
        // {
        //     std::cout << it->first << " " << it->second << '\n';
        // }
        std::for_each(_edges.begin(),_edges.end(),[](auto &e){
            std::cout << e.first << " " << e.second << '\n';
        });
    }


private:

    double _p; //存在边的概率
    int _n;//点的数量 
    int _m; 
    // std::set<std::pair<int,int>> _set;// 用来判断边<u,v>是否存
    std::vector<edge> _edges;
    random_double rnd;
};

int main(){
    random_dag rg(5,0.4);
    rg.generator();
    std::cout << rg.n() <<" ";
    std::cout << rg.m() <<"\n";
    rg.print_edges();
    return 0;
}
点击 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6+5;
const int maxe = 1e6+5;

std::random_device rd;
std::default_random_engine __rnd(rd());
std::mt19937 mtrnd(rd());
int rnd(int l,int r) {
    return __rnd() % (r-l+1) + l;
}


struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    //遍历点u 周围点
    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w); //u v w
    }

    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    void add2(int u,int v,int w=0){
        add(u,v,w);
        add(v,u,w);
    }
    //下标访问
    edge& operator[](int i){ return e[i]; }
    //返回head[u]
    int operator()(int u){ return h[u]; }
} e;


//maxEdges=0 表示不设置最大的边的数量
void generateRandomDAG(int numberNodes,int maxEdges=0)
{
    int e_cnt = 0;
    for(int i =1;i<=numberNodes;i++) {
        for(int j = i+1; j<=numberNodes;j++)
        {
            if( rnd(0,1) ) {
                e.add(i,j);
                if( maxEdges && ++e_cnt == maxEdges)
                    return;
            }
        }
    }
}

int main () {
    int nodes = 6;
    generateRandomDAG(nodes);
    return 0;
}