通过允许用户选择顶点数量，使用Boost库生成图形

Question

我想使用boost库生成一个图，该库允许用户输入边和顶点的数量。我基本上想做的是，

1. 我希望用户输入顶点的数量和每个顶点的数量
2. 我会给用户一个特权，使用数字作为参考，选择一个顶点作为主顶点
3. 我希望用户在控制台中指定每个顶点的边数，并且这些边可以是随机的

是否可以使用BGL以某种方式实现这一点？如果是这样的话，一个例子将是一个很好的开始。

提前感谢

干杯！！

Answer 1

假设你知道a）基本C++和b）基本BGL，这里有一个简单的算法来构建一个具有给定顶点价的随机无向图：

1. 读取所需顶点的数量；称之为CCD_ 1。我们得到了顶点集CCD_ 2。

2. 对于[0, N)中的每个i，读取所需的价态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!
}