通过允许用户选择顶点数量，使用Boost库生成图形 [英] Generating a Graph using Boost library by allowing user to select the number of vertex

问题描述

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

1. 我想让用户输入顶点的数量和每个顶点数。


2. 我会给用户一个权限，使用数字作为参考来选择一个顶点作为主顶点。


3. 我希望用户在控制台中指定，每个顶点和边缘的边数可以是随机的。

是否可以使用BGL以某种方式实现？

提前一吨感谢，

干杯！！

解决方案

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

1. 读取所需顶点的数量;调用 N 。我们有顶点集 [0，N）。




2. 在 [0，N）中读取所需价格 v [i] 例如存储在诸如 std :: vector< int> 的容器中。




3. 现在有趣的部分：迭代每个顶点，并添加一个随机边缘，只要你可以。这里有一些类似于C ++的伪代码，有空格供您填写。

     for（i = 0; i！= N ; ++ i）
    {
    if（i + 1 == N& v [i]> 0）
    {
   错误：用户输入不可能满足
   中止程序
   } 
    
    while（v [i]> 0）
    {
   在[i + N）
    
    if（v [j]> 0）
    {
   添加边i j 
    --v [i]; 
    --v [j]; 
   } 
   } 
   } 
    
   如果我们没有中止，我们现在有一个随机图。 
     

这是一个示例实现。会有差距;它只是一个大纲。

  #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<< 意外结束输入！Aborting.\\\
; 
 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<< 意外结束输入！Aborting.\\\
; 
 std :: exit（1）; 
} 
 
 int main（）
 {
 int const N = read_int（Number of vertices：，
I did not understand，try再次。顶点数：）; 
 
 std :: vector< unsigned int>价态; 
 std :: vector< std :: string> vertex_names; 
 
 valencies.reserve（N）; 
 vertex_names.reserve（N）; 
 
 for（int i = 0; i！= N; ++ i）
 {
 std :: string const msg1 =输入顶点的效价+ std :: to_string（i）+：; 
 std :: string const msg2 =输入描述顶点+ std :: to_string（i）+：; 
 std :: string const rep =对不起，再说一遍 
 
 valencies.push_back（read_int（msg1，rep））; 
 vertex_names.push_back（read_string（msg2））; 
} 
 
 for（int i = 0; i！= N; ++ i）
 {
 std :: cout< 顶点<< i<< （\<< vertex_names [i] 
<<\）具有价态<价态[i] std :: endl; 
} 
 
 //现在运行上面的算法！ 
} 
  

I would like to generate a graph using boost library which would allow user to input the number of edges and vertex. What I basically want to do is,

1. I would want the user to input the number of vertices and number each vertex.
2. I would give the user a privilege to select a vertex as a master vertex using the numeral as a reference.
3. I would like the user to specify in the console, number of edges from each vertex and the edges can be random.

Is it possible to somehow implement this using BGL? If so, an example would be a great thing to start with.

Thanks a ton in advance,

Cheers!!

解决方案

Assuming you know a) basic C++, and b) basic BGL, here's a simple algorithm to build a random undirected graph with given vertex valencies:

1. Read the number of desired vertices; call it N. We have the vertex set [0, N).

2. For each i in[0, N), read the desired valency v[i] (to be stored for example in a container such as a std::vector<int>).

3. Now the fun part: Iterate over each vertex and add a random edge as long as you can. Here's some C++-like pseudo code, with gaps for you to fill in.

   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.
   

Leave a comment if you want any part of this expanded.

---

Update: Here's an example implementation. There will be gaps; it's just an outline.

#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!
}

这篇关于通过允许用户选择顶点数量，使用Boost库生成图形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！