首页 文章

限制随机生成的图形中的顶点边数

提问于
浏览 次
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++;
                }
                }
        }
    }

可以看出，我使用 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 .

任何帮助将非常感激 .

非常感谢提前 .

干杯！！

c++ boost graph boost-graph

1 回答

  • 2

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

    如果将 k 初始化为 in_degree(i, g) + out_degree(i, g) 而不是0，则'll ensure you'll将考虑已为节点i添加的边 .

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

    回复于

相关问题