0

Boostグラフライブラリを使用して生成されたグラフからいくつかのエッジを削除したいと思います。

以下に示すように、 Boostを使用boost::mt19937して1からN（頂点の数）までの乱数を生成し、ランダムなエッジを追加します。

#include "stdafx.h"
#include <ctime>
#include <iostream>
#include <utility>                   // for std::pair
#include <algorithm> 
#include <time.h>
#include <boost/graph/adjacency_list.hpp>
#include "boost/graph/topological_sort.hpp"
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graphviz.hpp>
#include "boost/generator_iterator.hpp"
#include "boost/random.hpp"

// ----------------------------------------------
// Reading the number of vertices from the user.
//-----------------------------------------------

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);
}

int main()
{
    using namespace std;
    using namespace boost;
    typedef boost::mt19937 RNGType;


    //Assignign a property value to first vertex, (i.e) the name
    typedef property<vertex_name_t, std::string> VertexNameProperty;

    // Defifning the type of gprah(undirected)
    typedef adjacency_list< listS, vecS, undirectedS, VertexNameProperty > undigraph;

    // a vertex iterator to iterate through the vertex to get the property vale
    typedef graph_traits<undigraph>::vertex_iterator vertex_iter;
    std::pair<vertex_iter, vertex_iter> vp;

    int const N = read_int("Number of vertices: ",
        "I did not understand, try again. Number of vertices: ");   

    // Creating a instance g of unigraph undirected graph
    undigraph g;

    //Assigining property(name) to graph vertex
    property_map<undigraph, vertex_name_t>::type
        name = get(vertex_name, g);
    typedef graph_traits<undigraph>::vertex_descriptor Vertex;
    Vertex u1;
    u1=add_vertex(g);
    name[u1] = "Controller";

    // Creatng other vertices in the graph by iterating
    for(Vertex p = 1; p <= N-1; ++p)
    {
        p=add_vertex(g);
    }

    // Priting out the controller
    vp = vertices(g);
    std::cout << "The name of the first vertex is " << name[*vp.first]<<" and the output graph is:" <<std::endl;

    // --------------------------------------------------------------
    // Generating a random edges from a vertex, maximum edges are four
    //    Using Mersenne twister- A Pseudo random generator algorithm
    //     Mersenne twister gives un-distributed random numbers
    //----------------------------------------------------------------

    RNGType rng( time(0) );
    boost::uniform_int<> one_to_four( 1, (N-1) );
    boost::variate_generator< RNGType, boost::uniform_int<> >gen(rng, one_to_four);
    for(int i =0; i<(N-1); i++)
    {
        int k = 0;
        while(k<(N-1))
        {  
            int n  = gen();
            // Adding edges onto graph

            if(!boost::edge(i, n, g).second && !boost::edge(n, i, g).second)
                {
                add_edge(i, n, g);
                k++;
                }

        }
        // removing edges that direct to same vertex graph
    }   

    write_graphviz(cout, g);
    return 0;
}

しかし、次のように4つの頂点がある場合、上記の出力が得られます。

graph G
0;
1;
2;
3;
4;
0--1 ;
0--2 ;
0--2 ;
0--2 ;
1--3 ;
2--1 ;
2--4 ;
3--2 ;
3--2 ;
3--4 ;
}

しかし、ご覧のとおり、エッジ(0,2) and (3,2)が繰り返されています。そして、より大きなグラフの場合、時にはex：(1,3) and (3,1)が存在し、それらは両方とも無向グラフと同じです。これらの頂点を削除するにはどうすればよいですか。Boostにはと呼ばれるものがあることは知ってremove_edge_if()いますが、私のケースをサポートする正確な例は見つかりませんでした。

4

1 に答える 1

3

必要に応じて。ソースノードとエンドノードをチェックせずに、大量の乱数を取得してエッジを追加しているので、繰り返しと循環パスがいくつかあるのは当然です。

変更することをお勧めします

add_edge(i, n, g)
k++

に

if(!has_edge(i,n,g))
{
    add_edge(i, n, g)
    k++
}

また、方向に関係なく、ノードのペア間に1つのエッジのみが必要な場合：

if(!has_edge(i,n,g) && !has_edge(n,i,g))
{
    add_edge(i, n, g)
    k++
}

また、エッジを追加して後で削除することはお勧めしません。だから私はあなたのチェックを削除し(i == i)（とにかく、これは決して偽になることはありません）、を(i != n)呼び出す前に条件に追加しadd_edgeます。

編集後

これ：

for(Vertex p = 1; p <= N-1; ++p)
{
    p=add_vertex(g);
}

うまくいかない可能性があります。繰り返しますpが、編集しながら編集pします。しかし、そうではないかもしれません。また、Nその値を確認するために、どの段階でも出力していますか？

それを実行しようとした後

要素がなく、グラフの生成中にぶら下がっています。それはあなたのせいだと思いますwhile(k<(N-1))。N-1各ノードに他のノードへの接続を持たせようとしています。ただし、同時に、現在のノードにすでに接続しているノードへの接続は受け入れられません。2番目のノードのエッジを生成しようとすると、それ自体または最初のノード（すでに接続されている）に接続できないため、最大（N-2）の接続があります。しかし、あなたはそれが見つかるまで待っていますN-1、それは決して起こりません。

私はそれをに変えてwhile(k<(N/2))みました、そしてそれは私にとってうまくいったようでした。

于 2012-09-21T08:21:54.563 に答える