1

我有一段代码，它生成一个随机图，每个顶点最多有 4 条边。代码如下：

int const N = read_int("Number of vertices: ",
        "I did not understand, try again. Number of vertices: ");   

    // Creating a instance g of unigraph undirected graph
    undigraph g;

    //Assigining property(name) to graph vertex
    property_map<undigraph, vertex_name_t>::type
        name = get(vertex_name, g);
    typedef graph_traits<undigraph>::vertex_descriptor Vertex;
    Vertex u1;
    u1=add_vertex(g);
    name[u1] = "Controller";

    //Creatng other vertices in the graph by iterating
    for(Vertex p = 1; p <= N-1; ++p)
    {
        p=add_vertex(g);
    }

    // Priting out the controller
    vp = vertices(g);
    std::cout << "The name of the first vertex is " << name[*vp.first]<<" and the output graph is:" <<std::endl;

    // --------------------------------------------------------------
    // Generating a random edges from a vertex, maximum edges are four
    //    Using Mersenne twister- A Pseudo random generator algorithm
    //     Mersenne twister gives un-distributed random numbers
    //----------------------------------------------------------------

    RNGType rng( time(0) );
    boost::uniform_int<> one_to_four( 0, (N-1) );
    boost::variate_generator< RNGType, boost::uniform_int<> >gen(rng, one_to_four);
    for(int i =0; i<N; i++)
    {
        // Intialising the number of inedges and outedges to a vetrex
        // to k, so that number of edges from a vertex are less than 4.
        int k = (in_degree(i, g) + out_degree(i, g)); 
        while(k<4)
            //while(k<(N/2 -1))
        {  
            //Getting a random number from Mersenne twister
            int n  = gen();

            // The coming block adds edges onto the graph "g" and outputs it in grpahviz format

            // Checking if there are edges such as (3,2) and (2,3), if any one of them exist, then the edges are not added.
            if(!boost::edge(i, n, g).second && !boost::edge(n, i, g).second)    
            {
                //if(i !=n )
                // Checking if no of incoming edges and outgoing edges from a vertex is 4 or less than it
                if ((in_degree(n,g) + out_degree(n,g) + 1) <= 4)
                {
                    // Adding edges after performing all the checks.
                    add_edge(i, n, g);
                }        
            }k++;
        }
        // Removing edges that directs on the same vertex where they are originated.
        if(i == i)
        {
            remove_edge(i,i,g);
        }
    }   
    //output the graph in graph viz format in the console.
    write_graphviz(cout, g);
    return 0;
}

但是当我输入顶点数时，比如说 20，我得到如下输出：

vertices=20 的 graphviz 输出

可以看出，顶点 10 和 13 是分开的，并且没有连接到任何其他顶点。有没有办法将此顶点连接到某个随机顶点？

任何帮助将非常感激。

4

0 回答 0