2

次のように定義された boost::graph のエッジ リストを並べ替えたいと思います。

struct Vertex{
int index;
};

struct Edge{
double weight;
};

boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, Vertex, Edge> Graph;

頂点とエッジを追加した後、エッジ リストを並べ替える方法。最初に最大の重みで優位に立ちますか?

私は1つが使用できることを知っています

std::sort(edgeIt_begin,edgeIt_end,compare);

ベクトルの場合、std::list では機能しません。

4

4 に答える 4

8

要素を自動的にソートする独自の 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
于 2011-09-28T19:14:02.320 に答える
2

エッジの並べ替えは、慣用的なboost::graphではありません。スパニングツリーのためのクラスカルのアルゴリズムのBGL実装を見てください。アルゴリズムは、重みの昇順で各エッジを調べる必要があります。

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

別のデータ構造を使用してエッジを並べ替え、後でエッジをこの順序で繰り返します。あなたの場合、最初に最も高い重みのエッジが必要なので、コンパレータ演算子を変更するように見えます。

于 2011-09-28T15:24:52.203 に答える
0

Boost Graph表現との相互作用についてはわかりませんが、IIRCを使用できますstd::list::sort(Cmp)

std::list<int> l = { 1, 3, -1, 9, 2 };
l.sort();
于 2011-09-28T19:31:21.010 に答える
0

前の回答は非常に便利ですが、bgl タグを少し間違った方法で管理しているため、push_dispatch 定義が冗長になり、他の *_dispatch 関数が呼び出された場合 (消去操作の場合など) にビルドの問題が発生する可能性があります。

2 つ目の紛らわしい状況は、ノードごとのエッジ リストが 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;
       }
  }
于 2016-06-06T11:42:01.750 に答える