Генерация графика с использованием библиотеки Boost, позволяя пользователю выбирать количество вершин

Question

Генерация графика с использованием библиотеки Boost, позволяя пользователю выбирать количество вершин

Я хотел бы сгенерировать график, используя библиотеку наддува, которая позволила бы пользователю вводить число ребер и вершину. Что я в основном хочу сделать, это

Я бы хотел, чтобы пользователь вводил количество вершин и нумерацию каждой вершины.
Я бы дал пользователю право выбирать вершину в качестве главной вершины, используя цифру в качестве ссылки.
Я хотел бы, чтобы пользователь указал в консоли, количество ребер из каждой вершины и ребра могут быть случайными.

Можно ли как-то реализовать это с помощью BGL? Если так, то пример был бы отличным для начала.

Большое спасибо заранее,

Ура !!

0

boost boost-graph c++graph

Решение

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

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

Источник

Accepted Answer

Предполагая, что вы знаете а) базовый C ++ и б) базовый BGL, вот простой алгоритм построения случайного неориентированного графа с заданными валентными вершинами:

Прочитайте количество желаемых вершин; назови это N, У нас есть набор вершин [0, N),
Для каждого i в[0, N)прочитайте желаемую валентность v[i] (храниться, например, в контейнере, таком как std::vector<int>).
Теперь самое интересное: перебирайте каждую вершину и добавляйте случайное ребро как можно дольше. Вот немного C ++ — например, псевдокода, с пробелами для заполнения.
```
for (i = 0; i != N; ++i)
{
if (i + 1 == N && v[i] > 0)
{
Error: The user input was impossible to satisfy
Abort program
}

while (v[i] > 0)
{
pick a random j in [i + 1, N)

if (v[j] > 0)
{
Add edge i <-> j
--v[i];
--v[j];
}
}
}

If we haven't aborted, we now have a random graph.
```

Оставьте комментарий, если вы хотите, чтобы какая-либо часть была расширена.

Обновить: Вот пример реализации. Там будут пробелы; это просто набросок.

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>

int read_int(std::string const & initmsg, std::string const & repeatmsg)
{
std::cout << initmsg;

for (std::string line; std::getline(std::cin, line); )
{
std::istringstream iss(line);
int res;

if (iss >> res >> std::ws && iss.get() == EOF) { return res; }

std::cout << repeatmsg;
}

std::cerr << "Unexpected end of input! Aborting.\n";
std::exit(1);
}

std::string read_string(std::string const & msg)
{
std::string res;
std::cout << msg;

if (std::getline(std::cin, res)) { return res; }

std::cerr << "Unexpected end of input! Aborting.\n";
std::exit(1);
}

int main()
{
int const N = read_int("Number of vertices: ",
"I did not understand, try again. Number of vertices: ");

std::vector<unsigned int> valencies;
std::vector<std::string> vertex_names;

valencies.reserve(N);
vertex_names.reserve(N);

for (int i = 0; i != N; ++i)
{
std::string const msg1 = "Enter valency for vertex " + std::to_string(i) + ": ";
std::string const msg2 = "Enter description for vertex " + std::to_string(i) + ": ";
std::string const rep = "Sorry, say again: ";

valencies.push_back(read_int(msg1, rep));
vertex_names.push_back(read_string(msg2));
}

for (int i = 0; i != N; ++i)
{
std::cout << "Vertex " << i << " (\"" << vertex_names[i]
<< "\") has valency " << valencies[i] << std::endl;
}

// Now run the above algorithm!
}

2