我有一个带有类型边的巨大图形(即具有类型属性的边)。说
typedef adjacency_list<vecS, vecS, vertex_prop, edge_prop> Graph;
边的“类型”是edge_prop的成员,值在{A,B,C,D}中,
我想运行广度优先搜索算法,只考虑类型 A 或 B 的边。
你会怎么做?
最佳答案
因为很难找到混合 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;
}
关于c++ - 应用考虑特定边缘子集的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2693374/