Я сгенерировал случайный неориентированный граф, используя библиотеку графов 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++;
}
}
}
}
Как видно, я ограничиваю количество ребер до 4, используя while(k<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..
}
Как можно видеть, есть уже 4 исходящих ребра от 0, и есть входящее ребро из (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
, Это гарантирует, что вы не добавите слишком много ребер к одному из случайных узлов.
Других решений пока нет …