c++ - 将边缘的数量限制为随机生成的图形中的顶点

我使用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。

任何帮助将非常感激。

非常感谢。

干杯!!

最佳答案

您可以使用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之前进行检查。这样可以确保您不会在随机节点之一上添加过多的边。