c++ - 限制随机生成图中顶点的边数

Question

我使用 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++;
                }
                }
        }
    }    

正如所见，我使用 while(k<4) 将边数限制为 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 个。

非常感谢任何帮助。

非常感谢。

干杯!

Answer 1

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

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

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