我想对boost :: graph的边缘列表进行排序,如下所示:
struct Vertex{
int index;
};
struct Edge{
double weight;
};
boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, Vertex, Edge> Graph;
添加顶点和边后,如何对边列表进行排序 . 首先获得最高重量的边缘?
我知道可以使用
std::sort(edgeIt_begin,edgeIt_end,compare);
对于向量,但它不适用于std :: list .
4 回答
对边缘进行排序不是惯用的boost :: graph . 查看生成树的Kruskal's algorithm的BGL implementation . 该算法需要以递增的重量顺序查看每个边缘 .
它使用单独的数据结构对边进行排序,然后按顺序迭代边 . 在您的情况下,您首先需要最高加权边,因此您将看起来更改比较器运算符 .
您可以编写自己的EdgeList或OutEdgeList类,自动对Elements进行排序 . 我举一个例子,因为它不是那么明显如何做到这一点 .
输出:
我不知道与Boost Graph表示的任何交互,但是IIRC你可以使用
std::list::sort(Cmp)
以前的答案虽然非常有用,但是以一种不正确的方式管理bgl标签,导致冗余的push_dispatch定义,并且如果调用其他* _dispatch函数(例如,在擦除操作的情况下)可能导致构建问题 .
第二个令人困惑的情况是每个节点边缘列表在adj_list模板中被替换,但是打印了未受影响的全边缘列表 .
有些代码可能会纠正这些缺陷: