Ограничение числа ребер вершиной в случайно сгенерированном графе

Я сгенерировал случайный неориентированный граф, используя библиотеку графов 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.

Любая помощь могла бы быть полезна.

Заранее большое спасибо.

Ура !!

1

Решение

Вы можете запросить количество входящих и исходящих ребер для узла с 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, Это гарантирует, что вы не добавите слишком много ребер к одному из случайных узлов.

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]