c++ - 从图中删除边

Question

我想从使用 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) 和 (3,2) 是重复的。对于更大的图，有时例如:(1,3) 和 (3,1) 存在并且它们都相同，因为它是无向图。 我怎样才能删除这些顶点。我知道 Boost 有一个叫做 remove_edge_if() 的东西，但是我没有找到任何精确的例子来支持我的情况。

Answer 1

应该的。您正在获取一堆随机数并为它们添加边而不检查源节点和结束节点，因此存在一些重复和一些循环路径也就不足为奇了。

我建议改变

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吗？在任何阶段，检查它的值(value)？

尝试运行之后

它没有没有元素，它在生成图形时挂起。我想那是因为你的 while(k<(N-1)) .你试图让每个节点都有 N-1与其他节点的连接。但与此同时，您不会接受与已经连接到当前节点的节点的连接。当您尝试为第二个节点生成边时，它无法连接到自身或第一个节点(已经连接到它)，因此最多有 (N-2) 个连接。但是你要等到它被发现N-1 ，这永远不会发生。

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