排序在提振EdgeList都::图

Question

我想给升压的边缘列表排序::图定义如下：

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

为载体，但它并不适用于标准::名单的工作。

Answer 1

排序的边缘不是惯用的boost :: graph。查看生成树的Kruskal's algorithm的BGL implementation。该算法需要以增加的权重顺序查看每个边缘。

std::priority_queue<Edge, std::vector<Edge>, weight_greater> Q(wl); 
    /*push all edge into Q*/ 
    typename graph_traits<Graph>::edge_iterator ei, eiend; 
    for (boost::tie(ei, eiend) = edges(G); ei != eiend; ++ei) 
    Q.push(*ei); 

它使用单独的数据结构对边进行排序，然后按照该顺序遍历边。在你的情况下，你首先需要最高加权的边缘，所以你会改变比较运算符。

Answer 2

你可以写你自己的EdgeList都或OutEdgeList类自动排序元素。 我举一个例子，因为它不是那么明显，如何做到这一点。

#include <iostream> 
#include <boost/graph/graph_traits.hpp> 
#include <boost/graph/adjacency_list.hpp> 

using namespace boost; 

template<class T> struct Sorted_list 
{ 
    std::list<T> v; 

public: 
    typedef T value_type; 
    typedef typename std::list<T>::size_type size_type; 
    typedef typename std::list<T>::iterator iterator; 

    iterator insert(const T& x) 
    { 
    Sorted_list<T>::iterator i = v.begin(); 

    while(i != v.end() && x > *i) 
    { 
     i++; 
    } 

    return v.insert(i, x); 
    } 

    iterator begin() { return v.begin(); } 
    iterator end() { return v.end(); } 

    size_type size() const { return v.size(); } 
}; 

struct SlistS {}; 

namespace boost { 
    template <class ValueType> struct container_gen<SlistS, ValueType> 
    { 
    typedef Sorted_list<ValueType> type; 
    }; 

    struct sorted_list_tag {}; 

    template<class T> sorted_list_tag container_category(Sorted_list<T>&) 
    { 
    return sorted_list_tag(); 
    } 

    template<class T> std::pair<typename Sorted_list<T>::iterator, bool> 
    push_dispatch(Sorted_list<T>& v, const T& x, sorted_list_tag) 
    { 
    return std::make_pair(v.insert(x), true); 
    } 

    template <> struct parallel_edge_traits<SlistS> { 
    typedef allow_parallel_edge_tag type; 
    }; 
} 

int main() 
{ 
    typedef adjacency_list<SlistS> Graph; 
    Graph g(10); 
    add_edge(1, 2, g); 
    add_edge(1, 5, g); 
    add_edge(1, 3, g); 
    add_edge(1, 7, g); 
    add_edge(1, 1, g); 

    graph_traits<Graph>::edge_iterator i, end; 

    for (tie(i, end) = edges(g); i != end; ++i) { 
    std::cout << source(*i, g) << " -> " << target(*i, g) << std::endl; 
    } 

    return 0; 
} 

输出：

1 -> 1 
1 -> 2 
1 -> 3 
1 -> 5 
1 -> 7 

Answer 3

我不知道用加速图形表示的任何互动，但IIRC你可以使用std::list::sort(Cmp)

std::list<int> l = { 1, 3, -1, 9, 2 }; 
l.sort(); 

Answer 4

以前的答案，虽然很有用，以不正确的方式管理bgl标签，导致冗余的push_dispatch定义，并可能导致构建问题，如果调用其他* _dispatch函数（例如在擦除操作的情况下）。

二混乱的情况是，每个节点的边缘列表在adj_list模板取代的，但打印不受影响整个边缘列表。

有一些代码，大概是纠正这些缺陷：

// ... 

template<class T> struct Sorted_vector : public std::vector<T> 
{ 
public: 

    iterator insert(const T& x) 
    { 
    iterator where = std::upper_bound(begin(), end(), x, std::less<T>()); 
    return std::vector<T>::insert(where, x); 
    } 

}; 

struct vecSS{}; 

namespace boost{ 

    template <class ValueType> struct container_gen<vecSS, ValueType> 
    { 
     typedef Sorted_vector<ValueType> type; 
    }; 

    template <> struct parallel_edge_traits<vecSS> { 
     typedef allow_parallel_edge_tag type; 
    }; 

    template<class T> graph_detail::vector_tag container_category(const Sorted_vector<T>&) 
    { 
     return graph_detail::vector_tag(); 
    } 

    template <class T> graph_detail::unstable_tag iterator_stability(const Sorted_vector<T>&) 
    { 
     return graph_detail::unstable_tag(); 
    } 
} 

typedef adjacency_list<vecSS, ...> Graph; 

// .... 

    graph_traits<Graph>::vertex_iterator ii, ee; 
    for(boost::tie(ii,ee) = vertices(g);ii!=ee;++ii){ 
     std::cout << *ii << std::endl; 
     graph_traits<Graph>::adjacency_iterator jj, ff; 
     for(boost::tie(jj,ff)=adjacent_vertices(*ii, g);jj != ff; ++jj){ 
      std::cout << "\t -> " << *jj<<std::endl; 
     } 
    }