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

Subject: Re: [Boost-users] [BGL] Serializing a filtered_graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-11-30 13:03:17

On Thu, 18 Nov 2010, Cedric Laczny wrote:

> 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?

There isn't one AFAIK.  I think what you really want is to pick a graph 
type to use as the materialized graph (for example, some simple 
adjacency_list type).  You actually do want to copy the filtered_graph 
into another graph, then serialize that, and read back into the 
non-filtered graph type.  If copy_graph is too slow, you might want to 
write your own version that applies the filter function directly; the 
infrastructure needed to make filtered_graph look like a normal graph type 
slows down iteration of vertices and edges compared to a straightforward 
for loop with an if statement inside.

> 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.

Yes, I agree with how you're proposing to do this.  See above for what to 
do.

-- Jeremiah Willcock