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

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

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

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

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

Ура !!

0

Решение

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

  1. Прочитайте количество желаемых вершин; назови это N, У нас есть набор вершин [0, N),

  2. Для каждого i в[0, N)прочитайте желаемую валентность v[i] (храниться, например, в контейнере, таком как std::vector<int>).

  3. Теперь самое интересное: перебирайте каждую вершину и добавляйте случайное ребро как можно дольше. Вот немного 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

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

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