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

From: Dima F. (quantera_at_[hidden])
Date: 2007-04-20 04:35:42

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 <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() {}
        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.