Promotion graph: apply algorithms based on a specific subset of edges

Question

I have a huge graph with a typed edge (i.e. an edge with the type property). Tell me

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

The "type" of the rib is a member of edge_prop and has a value in {A, B, C, D},
I would like to run a width-width search algorithm, considering only edges of type A or B.
How would you do that?

Answer 1

Finally, I think the boost :: graph way to do this is to use boost: filter_graph and a demo to use

"The filter_graph class template is an adapter that creates a filtered representation of the graph. The predicate function objects determine which edges and vertices of the original graph will be displayed in the filtered graph."

Thus, you can provide a basic filter base (or vertices) for filtering in property_map. In my case, I use internal related properties. See Map Properties from Nested Properties .

Answer 2

Since it is difficult to find a simple example mixing different BGL themes, I will post below a complete and working example using filter_graph and related properties:

 #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 3

I'm pretty new to boost :: graph, but I assume BFSVisitor is what you are looking for. This allows you to change the behavior of the algorithm, and your specific case would be to change the consideration of outgoing edges after detecting the vertex and ignore those that are not of the required "type" (in fact, {A, B, C, D} are values, as far as I understand, not types in the strict sense of the word.)