1

次のように、グラフにランダムなエッジを追加したいと思います。

#include <iostream>
#include <utility>                   // for std::pair
#include <algorithm> 
#include <boost/graph/adjacency_list.hpp>
#include "boost/graph/topological_sort.hpp"
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graphviz.hpp>

int main()
{
    using namespace std;
    using namespace boost;

    typedef adjacency_list< listS, vecS, undirectedS > undigraph;

    int const N = read_int_from_user("Number of vertices: ");   

    undigraph g(N);

    // add some edges,             // #1
    for (int i = 0; i != N; ++i)
    {
        for (int j = 0; j != N; ++j)
        {
            add_edge(i, j, g);
        }
    }
    write_graphviz(cout, g);
}

次の行#1はそれを行います。

しかし、ご覧のとおり、各頂点から 8 つのエッジが存在しますが、最大で 4 つだけにして、すべての頂点をランダムな方法で接続したいと考えています。どうすればそれを達成できますか？

4

1 に答える 1

1

編集：「順序付けられていないペア」を意味するときに「順序付けられたペア」と言いました！言い換えがより明確になることを願っています。

あなたがする必要があるのは、< N である非負の整数の順序付けられていないすべてのペアのセットから置換なしでサンプリングすることです。コンピューターにとって順序付けられていないペアよりも順序付けられたペアを表す方がはるかに簡単であるため、このセットを生成する通常の方法は次のとおりです。最初の要素が 2 番目の要素より小さいすべての順序付けられたペアを生成します。

vector<pair<int, int> > pairs;

for (int i = 0; i < N; ++i) {
    for (int j = i + 1; j < N; ++j) {
        pairs.push_back(make_pair(i, j));
    }
}

たとえば、N = 4 の場合、考慮すべきエッジのセットは次のようになります。

0, 1
0, 2
0, 3
1, 2
1, 3
2, 3

このセットを取得したら、このセットからサンプリングする良い方法は、リザーバー サンプリングを使用することです。

于 2012-09-18T14:47:03.183 に答える