0

我想从使用 Boost 图形库生成的图形中删除一些边。

我使用 Boostboost::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)是重复的。对于较大的图，有时例如：(1,3) and (3,1)exists 并且它们都与无向图相同。如何删除这些顶点。我知道 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++
}

如果您只想要一对节点之间的一条边而不管方向：

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连接到其他节点。但同时，您不会接受与已连接到当前节点的节点的连接。当您尝试为第二个节点生成边时，它无法连接到自身或第一个节点（已经连接到它），因此最多有 (N-2) 个连接。但是你一直等到它被发现N-1，这永远不会发生。

我尝试将其更改为while(k<(N/2))，这似乎对我有用。

于 2012-09-21T08:21:54.563 回答