Добавление случайных ребер в граф, созданный с использованием графической библиотеки 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 валентности из каждой вершины. Как я могу этого достичь?
Решение
РЕДАКТИРОВАТЬ: Я сказал «заказанная пара», когда имел в виду «неупорядоченная пара»! Надеюсь, что перефразирование стало понятнее.
Что вам нужно сделать, это образец без замены из набора всех неупорядоченный пары неотрицательных целых чисел, которые < 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
Хороший способ попробовать этот набор, как только он у вас есть, это использовать отбор проб из пласта.
Другие решения
Других решений пока нет …