Re: [Boost-users] [BGL] Serializing a filtered_graph

Subject: Re: [Boost-users] [BGL] Serializing a filtered_graph
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2010-11-18 07:26:41

Hi,

On Tuesday, 16. November 2010 17:50:12 Jeremiah Willcock wrote:

> What about the graph do you want to keep?  In my view (and probably what
> actually happens), serializing a filtered_graph means serializing all of
> the input graph (even with vertices and edges that are hidden by the
> filter) and then serializing the filter function.  That may not be what
> you want, though: you might actually want to serialize the graph after
> filtering, and thus read the data back into a normal, non-filtered graph.
> Right now, that second option would require copying the filtered_graph
> into a normal graph type then serializing that; deserialization would be
> directly into the normal graph type.  It would be possible to avoid the
> copy, though, if that was important.

Could you please specify how to avoid the copy and get the original graph-
type?

This interests me, besides for the serialization, also for another scenario.
I have a certain amount of information that I want to put into a graph. 
Depending on the actual requirements, some vertices/edges need to be filtered 
out.
This filtering does not necessarily need to be reversable, so I would like to 
take the graph, apply the filter to it and get the resulting graph again into 
an original graph-type.
While this may sound awkward, I expect it to have dramatic performance 
improvements because applying some of my algorithms to the filtered_graph 
directly is very expensive. They tend to have rather bad asymptotic running 
times, because vertices/edges will be visited multiple times. Each time an 
edge/vertex is accessed the filtered_graph must retrieve the properties of this 
vertex (involves retrieving a property_map and the mandatory logarithmic 
lookup of the corresponding value/property).
If it would only do this step once, copy the resulting graph into the original 
graph type again, the algorithms would not "need" all these lookups.

Thank you

Best,

Cedric

> -- Jeremiah Willcock