Re: [Boost-users] [BGL] changes in graph => changes in filtered_graph?

Subject: Re: [Boost-users] [BGL] changes in graph => changes in filtered_graph?
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2010-09-14 11:40:54

Hi,

On Tuesday, 14. September 2010 16:56:42 Adam Spargo wrote:
> Hi,
> Just a simple question - if I have a filtered_graph fg, based on
> adjacency_list g, do changes to g automagically turn up in fg? Or do I
> need to make a new fg, once I have finished changing g?
> 

AFAIK, a filtered graph is, broadly speaking, just some sort of "mask" that 
get's laid over the original graph. By "mask" I mean that if you want to 
access a vertex, it first checks if this vertex should be visible and if so, 
you can access that vertex in the filtered graph, otherwise not. In that sense, 
changes on the original graph will also be in the filtered graph.
However, you need to take care, that your filter is also valid for the changed 
original graph.
I ran into such a problem. The filter had an attribute that was used to check 
if a vertex should be visible, but that attribute was not updated properly on 
changing the original graph.That caused me quite some trouble in finding the 
issue because everything looked correct to me.
I have for example a program that is searching for all the triangles in a 
graph (Chiba&Nichizeki [1985]). During the execution of the algorithm, the  
nodes in the original graph get marked. The filtered graph then is used to 
display only the nodes that are _not_marked, or marked, I don't remember 
exactly ATM, sorry. In the first approach, the attribute of the filter was the 
original graph, more precisely, a copy of it. So the changes were not visible 
for the filter. I then had to recreate the filtered graph again after each 
change. But then I came along the idea to use a reference to the original 
graph and that eliminated the need to recreate the filtered graph each time.
This should just give you the general idea and is likely to be way off from 
being efficient or such.

> I know I could write a simple test to find out, which I am doing, but I'd
> be grateful if someone with more experience of BGL could let me know of
> any exceptions or potential pitfalls.

Unfortunately, I can't help you on this one and I am also interested in 
answers to this. I did not experience such things until now, except for what I 
wrote above.

> Thanks in advance,
> 
> Adam.
> 
> --
> Dr Adam Spargo
> High Performance Assembly Group   email: aws_at_[hidden]
> Wellcome Trust Sanger Institute   Tel: [phone] x7728
> Hinxton, Cambridge CB10 1SA       Fax: [phone]

Hope this helps.

Best,

Cedric