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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-04-21 08:14:53

On 4/20/07, Dima F. <quantera_at_[hidden]> wrote:
> 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"
>

<snip>

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

Hi Dima,

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).
But even though your filtered graph is declared as a

filtered_graph<graph_t, filter_t, filter_t>

You're only passing the constructor one filter (for the edges). So the
vertex filter is default constructed, then used, and you get a segmentation
fault. If you either (1) remove the extra filter_t template parameter or
(2) add an extra filter argument to the constructor, the segfault goes
away.

Regards,
Aaron