我刚开始学习 boost 图形库,对使用 boost 图形库中的 remove_edge 函数有一个基本问题。
我想删除多重图中的一条边。对于有两条边连接顶点 0 和 1 的图,我想删除其中一条,但保留另一条。
根据用户指南,remove_edge(u ,v , g) 删除所有出现的 (u ,v)。所以我应该改用 remove_edge(e ,g) 。这里,e 是一个有效的边缘描述符。
对于单个图 g,我可以毫无问题地执行 remove_edge(u ,v , g) 和 remove_edge(e ,g) 操作。
但是,当我想通过将图形放入向量容器来概括实现以满足我的需要时,我遇到了 remove_edge(e ,graph_list[0]) 的段错误。 (编译器不显示任何警告消息。)另一方面,remove_edge(u,v,g) 工作得很好。我不确定这两种语法之间的区别是什么导致了我的问题。
我真的想让 remove_edge(e,g) 和向量容器同时工作。因此,任何可以帮助我绕过这个困难的建议都将受到赞赏。
非常感谢!!
以下是我的测试代码。
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include "boost/graph/graph_traits.hpp"
#include "boost/graph/adjacency_list.
hpp"
using namespace boost;
typedef adjacency_list<vecS, vecS, undirectedS> UndirectedGraph;
typedef boost::graph_traits<UndirectedGraph>::edge_iterator edge_iterator;
int graph_show(UndirectedGraph &g);
int main(int argc, char *argv[])
{
UndirectedGraph g;
typedef boost::graph_traits<UndirectedGraph>::edge_descriptor edge_descriptor;
edge_descriptor ed;
std::vector<edge_descriptor> edge_list;
std::vector<std::vector<edge_descriptor> > graph_edge_list;
std::vector<UndirectedGraph> graph_list;
int nb=0;
int Nl=4;
bool inserted;
while(nb<Nl)
{
tie(ed,inserted)=add_edge(nb,nb+1,g);
edge_list.push_back(ed);
tie(ed,inserted)=add_edge(nb,nb+1,g);
edge_list.push_back(ed);
graph_edge_list.push_back(edge_list);
nb=nb+1;
graph_list.push_back(g);
}
std::cout<<"size of the graph vector is: "<<graph_list.size()<<std::endl;
remove_edge(graph_edge_list[0][0],graph_list[0]);//This is where the problem shows.
//I got Segmentation fault (core dumped)
//remove_edge(0,1,graph_list[0]);
/*Remove edges by assigning vertices works fine, but that is not what I need.*/
for (int ig = 0; ig < Nl; ++ig) {
std::cout<<"graph#"<<ig<<std::endl;
std::cout<<"Size of edge_list is: "<<graph_edge_list[ig].size()<<std::endl;
graph_show(graph_list[ig]);
}
std::cout<<"Success"<<std::endl;
return 0;
}
int graph_show(UndirectedGraph &g)
{
std::cout<<"Number of edges is : "<<boost::num_edges(g)<<std::endl;
std::cout<<"Number of vertices is : "<<boost::num_vertices(g)<<std::endl;
std::pair<edge_iterator,edge_iterator> ei=edges(g);
for (edge_iterator edge_iter = ei.first; edge_iter!=ei.second; ++edge_iter) {
std::cout<<"("<< boost::source(*edge_iter,g)<<","<<boost::target(*edge_iter,g)<<")"<<std::endl;
}
typedef boost::graph_traits<UndirectedGraph>::vertex_iterator iter_v;
std::cout<<"vertices(g)={ ";
for (std::pair<iter_v,iter_v> p = vertices(g); p.first != p.second; ++p.first) {
std::cout<< *p.first;
std::cout<<" ";
}
std::cout<<"}"<<std::endl;
return 0;
}
最佳答案
这不是答案,但我尝试了代码,问题似乎出在:
g.m_edges.erase(edge_iter_to_erase);
在第 771 行的 adjacency_list.hpp 中。
这似乎是一个错误。您可能需要查看 boost 邮件列表。
上下文是:
template <>
struct remove_undirected_edge_dispatch<no_property> {
// O(E/V)
template <class edge_descriptor, class Config>
static void
apply(edge_descriptor e,
undirected_graph_helper<Config>& g_,
no_property&)
{
typedef typename Config::global_edgelist_selector EdgeListS;
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
typedef typename Config::graph_type graph_type;
graph_type& g = static_cast<graph_type&>(g_);
no_property* p = (no_property*)e.get_property();
typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
typename Config::OutEdgeList::iterator out_i = out_el.begin();
typename Config::EdgeIter edge_iter_to_erase;
for (; out_i != out_el.end(); ++out_i)
if (&(*out_i).get_property() == p) {
edge_iter_to_erase = (*out_i).get_iter();
out_el.erase(out_i);
break;
}
typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
typename Config::OutEdgeList::iterator in_i = in_el.begin();
for (; in_i != in_el.end(); ++in_i)
if (&(*in_i).get_property() == p) {
in_el.erase(in_i);
break;
}
g.m_edges.erase(edge_iter_to_erase);
}
};
当我单步执行调试器时,它显示 edge_iter_to_erase = (*out_i).get_iter();
从未执行过。这会在调用 vector 的 erase 时导致未定义的行为方法,因为位置无效(我猜)。
如果您只使用 g
而不是 graph_list[0]
它也能正常工作。
看看here对于邮件列表中的类似问题。他们使用不同的 adjacency_list。
如果我将图表更改为:
typedef adjacency_list<vecS, vecS, undirectedS,no_property,no_property,no_property,setS> UndirectedGraph;
就像那个帖子一样。我得到了访问读取冲突而不是段错误。
似乎是个错误,但我不知道为什么它对向量引用图而不是变量 g 这样做。
关于boost-graph - 在 boost 图形库中使用 remove_edge() 和 push_back 到向量容器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25279254/