CODEWITHSUNDEEP
c++boostgraphboost-graph
Spaniard89
Spaniard89

Reputation: 2419

Limiting the number of edges to a vertex in a randomly generated graph

I have a generated a random un-directed graph using Boost graph library.

I add the number of vertices and edges randomly as follow:

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++;
                }
                }
        }
    }

As it can seen, i limit the number of edges to 4 using while(k<4) but it works only for incoming edges. I want to limit both incoming and outgoing edges to 4. For example if I enter the number of vertex to be 10 i get:

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

As it can be seen there are already 4 outgoing edges from 0 and there is an incoming edge from (3,0), hence the number of edged leaving and entering the vertex 0 becomes 5, I want to restrict it to just 4 or maybe less but not more than 4.

Any help would be really appreciated.

Thanks a lot in advance.

Cheers!!

Upvotes: 1

Views: 276

Answers (1)

Martin
Martin

Reputation: 3753

You can request the number of incoming and outgoing edges for a node with in_degree and out_degree.

If you initialise k to be in_degree(i, g) + out_degree(i, g) instead of 0, you'll ensure you'll take into account edges already added for node i.

You'll also want to check before adding the edge between i and n that (in_degree(n) + out_degree(n) + 1) <= 4. That will make sure you don't add too many edges to one of the random nodes.

Upvotes: 2

Related Questions