c++ - 应用考虑特定边缘子集的算法

Question

我有一个带有类型边缘的巨大图（即带有类型属性的边缘）。说

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

边的“类型”是 edge_prop 的成员，并且在 {A,B,C,D} 中有一个值，
我想运行广度优先搜索算法，只考虑 A 或 B 类型的边。
你会怎么做去做？

Answer 1

因为很难找到混合 BGL 不同主题的简单示例，所以我在下面发布了一个使用 filters_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;
}

Answer 2

最后我认为 boost::graph 的方法是使用boost:filtered_graph和demo 来使用

“filtered_graph 类模板是一个适配器，用于创建图形的过滤视图。谓词函数对象确定原始图形的哪些边和顶点将显示在过滤图形中。”

因此，您可以提供基于 property_map 的边（或顶点）过滤函子。就我而言，我使用的是内部捆绑属性。请参阅捆绑属性中的属性映射。

Answer 3

我对 boost::graph 相当不熟悉，但我认为BFSVisitor是您正在寻找的。它允许您更改算法的行为，您的具体情况是在顶点发现后更改对传出边的检查并忽略不属于所需“类型”的那些（实际上是 {A,B,C,D } 是据我了解的值，而不是严格意义上的类型）。