Generating a Graph using Boost library by allowing user to select the number of vertex

Question

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

Answer 1

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