CODEWITHSUNDEEP
c++algorithmboostboost-graph
log0
log0

Reputation: 10917

Apply algorithms considering a specific edge subset

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?

Upvotes: 5

Views: 2069

Answers (3)

log0
log0

Reputation: 10917

Finally I think the boost::graph way to do this is to use boost:filtered_graph and demo for usage

"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.

Upvotes: 3

toch
toch

Reputation: 3945

Because it's hard to find simple example mixing different topics of the BGL, I post below a full and working example using filtered_graph and bundled 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;
}

Upvotes: 11

pmr
pmr

Reputation: 59811

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).

Upvotes: 0

Related Questions