Re: [Boost-users] BGL: filtered_graph and breadth_first_search.

From: Dima F. (quantera_at_[hidden])
Date: 2007-04-20 07:58:19

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 <boost/tuple/tuple.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>

using namespace std;
using namespace boost;

template <typename DistanceMap, typename ParentMap>
class my_bfs_visitor : public default_bfs_visitor {

public:

        my_bfs_visitor(DistanceMap &dist, ParentMap &paren)
                : m_dist(dist), m_paren(paren) {}

        template <typename Edge, typename Graph>
        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 <typename Graph, typename VertexCont>
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 <listS, vecS, undirectedS> 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<graph_t>::edge_descriptor edge_t;
        typedef map<int, int> dist_t;
        typedef map<int, edge_t> paren_t;

        dist_t dist;
        paren_t paren;

        my_bfs_visitor<dist_t, paren_t> 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<graph_t, cont_t> filter_t;
        filter_t filter(&g, &cont);

        filtered_graph<graph_t, filter_t, filter_t> 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;

}
------------------------------------------------------------