Добавление случайных ребер в граф, созданный с использованием графической библиотеки BOOST

Я хотел бы добавить случайные ребра в мой график, который выглядит следующим образом:

#include <iostream>
#include <utility>                   // for std::pair
#include <algorithm>
#include <boost/graph/adjacency_list.hpp>
#include "boost/graph/topological_sort.hpp"#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graphviz.hpp>

int main()
{
using namespace std;
using namespace boost;

typedef adjacency_list< listS, vecS, undirectedS > undigraph;

int const N = read_int_from_user("Number of vertices: ");

undigraph g(N);

// add some edges,             // #1
for (int i = 0; i != N; ++i)
{
for (int j = 0; j != N; ++j)
{
add_edge(i, j, g);
}
}
write_graphviz(cout, g);
}

Следующие строки #1 сделай это.

Но, как вы можете видеть, существует 8 ребер из каждой вершины, но я бы хотел, чтобы их было максимум 4, и я хотел бы соединить все вершины случайным образом, и что наиболее важно, может быть только 4 валентности из каждой вершины. Как я могу этого достичь?

1

Решение

РЕДАКТИРОВАТЬ: Я сказал «заказанная пара», когда имел в виду «неупорядоченная пара»! Надеюсь, что перефразирование стало понятнее.

Что вам нужно сделать, это образец без замены из набора всех неупорядоченный пары неотрицательных целых чисел, которые < N. Поскольку компьютеру гораздо проще представить упорядоченную пару, чем неупорядоченную пару, обычным способом создания этого набора является создание всех упорядоченных пар, в которых первый элемент меньше второго:

vector<pair<int, int> > pairs;

for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
pairs.push_back(make_pair(i, j));
}
}

Так, например если N = 4, множество возможных ребер для рассмотрения:

0, 1
0, 2
0, 3
1, 2
1, 3
2, 3

Хороший способ попробовать этот набор, как только он у вас есть, это использовать отбор проб из пласта.

1

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

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

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