5

型付けされたエッジ (型プロパティを持つエッジ) を持つ巨大なグラフがあります。言う 

typedef adjacency_list<vecS, vecS, vertex_prop, edge_prop> Graph;

エッジの「タイプ」は edge_prop のメンバーであり、{A,B,C,D} の値を持ちます
。タイプ A または B のエッジのみを考慮して、幅優先探索アルゴリズムを実行したいと思い
ます。それを行う？

4

3 に答える 3

11

BGL のさまざまなトピックを組み合わせた単純な例を見つけるのは難しいため、filtered_graph とバンドルされたプロパティを使用した完全で実際の例を以下に投稿します。

#include <iostream>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>

using namespace boost;

enum edge_type_e {
  A, B, C, D
};

class edge_property_c {
public:
  edge_property_c(void) : type_m(A) {}
  edge_property_c(edge_type_e type) : type_m(type) {}
  edge_type_e type_m;
};

typedef adjacency_list<vecS, vecS, undirectedS, no_property, edge_property_c> graph_t;
typedef graph_t::edge_descriptor edge_id_t;

class edge_predicate_c {
public:
  edge_predicate_c() : graph_m(0) {}
  edge_predicate_c(graph_t& graph) : graph_m(&graph) {}
  bool operator()(const edge_id_t& edge_id) const {
    edge_type_e type = (*graph_m)[edge_id].type_m;
    return (type == A || type == B);
  }
private:
  graph_t* graph_m;
};

int main() {
  enum { a, b, c, d, e, n };
  const char* name = "abcde";
  graph_t g(n);
  add_edge(a, b, edge_property_c(A), g);
  add_edge(a, c, edge_property_c(C), g);
  add_edge(c, d, edge_property_c(A), g);
  add_edge(c, e, edge_property_c(B), g);
  add_edge(d, b, edge_property_c(D), g);
  add_edge(e, c, edge_property_c(B), g);

  filtered_graph<graph_t, edge_predicate_c> fg(g, edge_predicate_c(g));

  std::cout << "edge set: ";
  print_edges(g, name);
  std::cout << "filtered edge set: ";
  print_edges(fg, name);

  return 0;
}
于 2011-07-28T09:26:49.473 に答える
3

最後に、これを行うboost::graphの方法は、使用のためにboost:filtered_graphとdemoを使用することだと思います

「filtered_graph クラス テンプレートは、グラフのフィルター処理されたビューを作成するアダプターです。述語関数オブジェクトは、元のグラフのどのエッジと頂点がフィルター処理されたグラフに表示されるかを決定します。」

したがって、property_map に基づくエッジ (または頂点) フィルタリング ファンクターを提供できます。私の場合、内部にバンドルされたプロパティを使用しています。バンドルされたプロパティからのプロパティ マップを参照してください。

于 2010-04-23T11:56:45.107 に答える
0

私はboost::graphにはかなり慣れていませんが、 BFFSisitorがあなたが探しているものだと思います。これにより、アルゴリズムの動作を変更できます。特定のケースでは、頂点の検出後に出力エッジの検査を変更し、必要な「タイプ」(実際には {A,B,C,D } は私が理解している限りの値であり、厳密な意味での型ではありません)。

于 2010-04-22T19:47:51.227 に答える