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..
}

可以看出，已经有 4 个来自 0 的出边，并且有一个来自 (3,0) 的入边，因此离开和进入顶点 0 的边数变为 5，我想将其限制为 4 或者可能少于但不超过 4 个。

任何帮助将非常感激。

提前非常感谢。

干杯！！

4

1 回答 1

2

您可以使用 和 请求节点的传入和传出边in_degree数out_degree。

如果您初始化k为in_degree(i, g) + out_degree(i, g)0 而不是 0，您将确保您将考虑已为节点 i 添加的边。

在添加 i 和 n 之间的边之前，您还需要检查(in_degree(n) + out_degree(n) + 1) <= 4。这将确保您不会向其中一个随机节点添加太多边。

于 2012-09-22T13:07:25.147 回答