Boost graph: Apply algorithms considering a specific edge subset.

Question

Hi,

I've got a huge graph with typed edge (i.e. edge with a type property). Say

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

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

Best,
Ugo

Answer 1

I'm rather unfamiliar with boost::graph but I assume BFSVisitor is what you are looking for. It allows you to change the behaviour of the algorithm and your specific case would be to change the examination of outgoing edges after vertex discovery and to ignore the ones that are not of the required "type" (actually {A,B,C,D} are values as far as I understand and not types in the strict sense).

Answer 2

Finally I think the boost::graph way to do this is to use Filtered_graph
http://cs.swan.ac.uk/~csoliver/ok-sat-library/internet_html/doc/doc/Boost/1_34_1/libs/graph/doc/filtered_graph.html

"The filtered_graph class template is an adaptor that creates a filtered view of a graph. The predicate function objects determine which edges and vertices of the original graph will show up in the filtered graph."

Thus, you can provide a edge (or vertex) filtering functor base on a property_map. In my case I'm using internal bundled properties. See Properties maps from bundled properties in
http://www.boost.org/doc/libs/1_42_0/libs/graph/doc/bundles.html