1

Boost グラフ ライブラリを使用してランダムな無向グラフを生成しました。

次のように、頂点とエッジの数をランダムに追加します。

RNGType rng( time(0) );
    boost::uniform_int<> one_to_four( 1, (N-1) );
    boost::variate_generator< RNGType, boost::uniform_int<> >gen(rng, one_to_four);
    for(int i =0; i<(N-1); i++)
    {
        int k = 0;
        while(k<4)
        //while(k<(N/2))
        {  
            int n  = gen();
            // Adding edges onto graph

            if(!boost::edge(i, n, g).second && !boost::edge(n, i, g).second)    
                {
                if(i !=n )
                {       
                add_edge(i, n, g);
                k++;
                }
                }
        }
    }

ご覧のとおり、使用するエッジの数を 4 に制限してwhile(k<4)いますが、着信エッジに対してのみ機能します。着信エッジと発信エッジの両方を 4 に制限したい。たとえば、頂点の数を 10 に入力すると、次のようになります。

graph G{
0;
1;
2;
3;
4;
5;
6;
7;
8;
9;
0--1 ;
0--2 ;
0--2 ;
0--2 ;
1--3 ;
2--1 ;
2--4 ;
3--2 ;
3--2 ;
3--4 ;
3--0 ;
4--1 ;
4--9 ;
4--8 ;
5--
and so on..
}

0 から 4 つの発信エッジが既にあり、(3,0) からの着信エッジがあることがわかるように、頂点 0 を出入りするエッジの数は 5 になります。 4 以下。

どんな助けでも本当に感謝しています。

よろしくお願いします。

乾杯！！

4

1 に答える 1

2

in_degreeおよびを使用して、ノードの着信エッジと発信エッジの数を要求できますout_degree。

0 の代わりに初期化kするとin_degree(i, g) + out_degree(i, g)、ノード i に既に追加されているエッジが考慮されるようになります。

また、 i と n の間にエッジを追加する前に確認する必要があります(in_degree(n) + out_degree(n) + 1) <= 4。これにより、ランダム ノードの 1 つにエッジを追加しすぎないようにすることができます。

于 2012-09-22T13:07:25.147 に答える