Aaron Windsor wrote:

Your predicate should have const member functions - replace

bool operator()(const vertex_t &v) {}

bool operator()(const edge_t &e) {}

with bool operator()(const vertex_t &v) const {}

bool operator()(const edge_t &e) const {}

and it should compile.

Thanks, it indeed compiles fine. Is there are other restrictions on using filtered_graph with breadth_first_search? The problem is that predicates of a filtered_graph should be Default Constructable, and it seems that even though in an example in a documentation of filtered_graph predicate has instance members, predicates of filtered_graphs which are used in breadth_first_search couldn't have any non-static members, because at some stage during the search predicates are default-constructed, and values of it's members are lost - for example, in order to be able to implement my idea of an induced subgraph, I would like each predicate instance to have a pointer to a graph to which filtering is going to be applied (see an example below). Is it somehow possible to let predicates to a filtered_graph have instance variables? Of course it is possible to use globals or static members, but this is a bad solution. P.S.: it seems that an idea of an induced graph can be realized by using 'subgraph' adaptor, but in a general case having predicates with instance members or some equivalent of instance members looks like a good thing - if at least it have been possible to get a reference to a graph given it's edge or vertex the problem would have been much easier to solve, but unfortunately it seems that graph's edge/vertex doesn't know anything about a graph it belongs to. Predicate example: ---------------------------------------------------------------- template class induced_graph_filter { public: typedef typename graph_traits<Graph>::edge_descriptor edge_t; typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; induced_graph_filter() {} induced_graph_filter(Graph *g, VertexCont *vert) : m_g(g), m_vert(vert) {} bool operator()(const vertex_t &v) const { if (this::m_vert->find(v) != this::m_vert->end()) return true; return false; } bool operator()(const edge_t &e) const { if (m_vert->find(source(e, *m_g)) != m_vert->end() && m_vert->find(target(e, *m_g)) != m_vert->end()) { return true; } return false; } Graph *m_g; VertexCont *m_vert; }; ---------------------------------------------------------------- VertexCont can be, for example, a set or list of vertices of an induced subgraph.

Aaron Windsor wrote:

The predicates used in a filtered_graph can have non-static members. In particular, I don't see anything wrong with the example you included in your previous email. The predicate needs to be default constructable because in the implementation of filtered_graph, it's stored by value in an iterator and the iterator must be default constructable. But you can still create a non-default instance of your predicate and pass it in to filtered_graph and you should get the results you expect - just make sure it has the correct semantics when default constructed.

Here is an example which (it seems to me) shows that non-static members in predicate can cause a problem (see code below). The program causes segmentation fault, and it happens when pointer to one of non-static members is dereferenced. When I tried to find the reason, it seems that a pointer, when used in operator() during an execution of BFS, contains garbage, that is - it doesn't point to an object it was pointing to after a predicate object was constructed. When you run the program, it is possible to see according to a log messages that sometimes predicate is constructed using a default constructor, which means that it's members are not copied to a new object. P.S.: Also, I see that copy-constructor is used, which is somewhat strange - it is written (http://www.sgi.com/tech/stl/DefaultConstructible.html): "[1] The form X x = X() is not guaranteed to be a valid expression, because it uses a copy constructor. A type that is DefaultConstructible is not necessarily Assignable" and predicate is only supposed to be Default Constructible, not Assignable... Test program: ------------------------------------------------------------ #include <set> #include <iostream> #include #include #include #include using namespace std; using namespace boost; template class my_bfs_visitor : public default_bfs_visitor { public: my_bfs_visitor(DistanceMap &dist, ParentMap &paren) : m_dist(dist), m_paren(paren) {} template void tree_edge(Edge e, Graph& g) { m_dist[target(e, g)] = m_dist[source(e, g)] + 1; m_paren[target(e, g)] = e; } private: DistanceMap &m_dist; ParentMap &m_paren; }; template class induced_graph_filter { public: typedef typename graph_traits<Graph>::edge_descriptor edge_t; typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; induced_graph_filter() { cout << "constructed\n";} induced_graph_filter(const induced_graph_filter& g) { cout << "copy-constructed\n"; m_g = g.m_g; m_vert = g.m_vert; } induced_graph_filter(Graph *g, VertexCont *vert) : m_g(g), m_vert(vert) {} induced_graph_filter& operator=(const induced_graph_filter &g) { cout << "assigned\n"; m_g = g.m_g; m_vert = g.m_vert; } bool operator()(const vertex_t &v) const { if (m_vert->find(v) != m_vert->end()) return true; return false; } bool operator()(const edge_t &e) const { if (m_vert->find(source(e, *m_g)) != m_vert->end() && m_vert->find(target(e, *m_g)) != m_vert->end()) { return true; } return false; } private: Graph *m_g; VertexCont *m_vert; }; int main() { typedef adjacency_list graph_t; graph_t g(7); add_edge(0, 1, g); add_edge(0, 2, g); add_edge(1, 2, g); add_edge(2, 3, g); add_edge(3, 4, g); add_edge(3, 5, g); add_edge(4, 6, g); add_edge(5, 6, g); typedef graph_traits::edge_descriptor edge_t; typedef map dist_t; typedef map paren_t; dist_t dist; paren_t paren; my_bfs_visitor vis(dist, paren); cout << "Distances in original graph:\n\n"; breadth_first_search(g, 0, visitor(vis)); for (dist_t::iterator it = dist.begin(); it != dist.end(); it++) cout << "Distance of " << it->first << " is: " << it->second << endl; typedef set<int> cont_t; cont_t cont; cont.insert(0); cont.insert(1); cont.insert(2); cout << "\nAnd in filtered graph:\n\n"; typedef induced_graph_filter filter_t; filter_t filter(&g, &cont); filtered_graph g2(g, filter); dist.clear(); paren.clear(); breadth_first_search(g2, 0, visitor(vis)); for (dist_t::iterator it = dist.begin(); it != dist.end(); it++) cout << "Distance of " << it->first << " is: " << it->second << endl; } ------------------------------------------------------------

Aaron Windsor wrote:

Well, you do need a copy constructor - look a the line above, where you pass filter by value in the filtered_graph constructor. The copy constructor is called there (and anywhere else filter is passed by value).

Thanks a lot for all your explanations!