8

非常に単純なグラフの BFS をコンパイルするのに問題があります。私が何をしても、一致しないメソッド呼び出しに関するさまざまなコンパイラ メッセージが表示されます (私は試しboost::visitorて拡張boost::default_bfs_visitorなどを行いました)。

#include <stdint.h>
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>

int main() {
  typedef boost::adjacency_list<boost::vecS, boost::hash_setS, boost::undirectedS, uint32_t, uint32_t, boost::no_property> graph_t;
  graph_t graph(4);
  graph_t::vertex_descriptor a = boost::vertex(0, graph);
  graph_t::vertex_descriptor b = boost::vertex(1, graph);
  graph_t::vertex_descriptor c = boost::vertex(2, graph);
  graph_t::vertex_descriptor d = boost::vertex(3, graph);
  graph[a] = 0;
  graph[b] = 1;
  graph[c] = 2;
  graph[d] = 3;
  std::pair<graph_t::edge_descriptor, bool> result = boost::add_edge(a, b, 0, graph);
  result = boost::add_edge(a, c, 1, graph);
  result = boost::add_edge(c, b, 2, graph);
  class {
  public:
    void initialize_vertex(const graph_t::vertex_descriptor &s, graph_t &g) {
      std::cout << "Initialize: " << g[s] << std::endl;
    }
    void discover_vertex(const graph_t::vertex_descriptor &s, graph_t &g) {
      std::cout << "Discover: " << g[s] << std::endl;
    }
    void examine_vertex(const graph_t::vertex_descriptor &s, graph_t &g) {
      std::cout << "Examine vertex: " << g[s] << std::endl;
    }
    void examine_edge(const graph_t::edge_descriptor &e, graph_t &g) {
      std::cout << "Examine edge: " << g[e] << std::endl;
    }
    void tree_edge(const graph_t::edge_descriptor &e, graph_t &g) {
      std::cout << "Tree edge: " << g[e] << std::endl;
    }
    void non_tree_edge(const graph_t::edge_descriptor &e, graph_t &g) {
      std::cout << "Non-Tree edge: " << g[e] << std::endl;
    }
    void gray_target(const graph_t::edge_descriptor &e, graph_t &g) {
      std::cout << "Gray target: " << g[e] << std::endl;
    }
    void black_target(const graph_t::edge_descriptor &e, graph_t &g) {
      std::cout << "Black target: " << g[e] << std::endl;
    }
    void finish_vertex(const graph_t::vertex_descriptor &s, graph_t &g) {
      std::cout << "Finish vertex: " << g[s] << std::endl;
    }
  } bfs_visitor;
  boost::breadth_first_search(graph, a, bfs_visitor);
  return 0;
}

を使用してグラフにアクセスするにはbfs_visitor?

PS。「C++ Boost 無向グラフを作成し、それを深さ優先検索 (DFS) 順序でトラバースする方法」を見てコンパイルしました。しかし、それは役に立ちませんでした。

4

2 に答える 2

7

のオーバーロードのリストをここで見ることができますbreadth_first_search。すべてのパラメーターを指定したくない場合は、名前付きパラメーター バージョンを使用する必要があります。次のようになります。

breadth_first_search(graph, a, boost::visitor(bfs_visitor));

vecSグラフ定義で VertexList ストレージとして使用した場合、または内部の vertex_index プロパティ マップを構築して初期化した場合、これはそのまま機能します。を使用しhash_setSているため、呼び出しを次のように変更する必要があります。

breath_first_search(graph, a, boost::visitor(bfs_visitor).vertex_index_map(my_index_map));

uint32_t バンドル プロパティで既にインデックス マップを使用しています。を使用get(boost::vertex_bundle, graph)してアクセスできます。

訪問者にも問題がありました。から派生させる必要があり、メンバー関数boost::default_bfs_visitorのパラメーターは const で修飾する必要があります。graph_t

完全なコード:

#include <stdint.h>
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>

typedef boost::adjacency_list<boost::vecS, boost::hash_setS, boost::undirectedS, uint32_t, uint32_t, boost::no_property> graph_t;


struct my_visitor : boost::default_bfs_visitor{

    void initialize_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const {
      std::cout << "Initialize: " << g[s] << std::endl;
    }
    void discover_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const {
      std::cout << "Discover: " << g[s] << std::endl;
    }
    void examine_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const {
      std::cout << "Examine vertex: " << g[s] << std::endl;
    }
    void examine_edge(const graph_t::edge_descriptor &e, const graph_t &g) const {
      std::cout << "Examine edge: " << g[e] << std::endl;
    }
    void tree_edge(const graph_t::edge_descriptor &e, const graph_t &g) const {
      std::cout << "Tree edge: " << g[e] << std::endl;
    }
    void non_tree_edge(const graph_t::edge_descriptor &e, const graph_t &g) const {
      std::cout << "Non-Tree edge: " << g[e] << std::endl;
    }
    void gray_target(const graph_t::edge_descriptor &e, const graph_t &g) const {
      std::cout << "Gray target: " << g[e] << std::endl;
    }
    void black_target(const graph_t::edge_descriptor &e, const graph_t &g) const {
      std::cout << "Black target: " << g[e] << std::endl;
    }
    void finish_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const {
      std::cout << "Finish vertex: " << g[s] << std::endl;
    }
  };

int main() {
  graph_t graph(4);
  graph_t::vertex_descriptor a = boost::vertex(0, graph);
  graph_t::vertex_descriptor b = boost::vertex(1, graph);
  graph_t::vertex_descriptor c = boost::vertex(2, graph);
  graph_t::vertex_descriptor d = boost::vertex(3, graph);
  graph[a] = 0;
  graph[b] = 1;
  graph[c] = 2;
  graph[d] = 3;
  std::pair<graph_t::edge_descriptor, bool> result = boost::add_edge(a, b, 0, graph);
  result = boost::add_edge(a, c, 1, graph);
  result = boost::add_edge(c, b, 2, graph);

  my_visitor vis;

  breadth_first_search(graph, a, boost::visitor(vis).vertex_index_map(get(boost::vertex_bundle,graph)));
  return 0;
}
于 2013-01-23T07:30:33.607 に答える