0

ユーザーがエッジと頂点の数を入力できるブーストライブラリを使用してグラフを生成したいと思います。私が基本的にやりたいのは、

  1. ユーザーに頂点の数を入力して、各頂点に番号を付けてもらいたいと思います。
  2. 数字を参照として使用して、マスター頂点として頂点を選択する特権をユーザーに与えます。
  3. コンソールでユーザーに指定してもらいたいのですが、各頂点からのエッジの数とエッジはランダムにすることができます。

BGLを使用してこれを何らかの方法で実装することは可能ですか？もしそうなら、例は最初に素晴らしいことでしょう。

よろしくお願いします。

乾杯！！

4

1 に答える 1

2

a）基本的なC ++、およびb）基本的な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!
}
于 2012-09-16T19:23:56.583 に答える