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;
}
------------------------------------------------------------
