[BGL] Serializing a filtered_graph
Hi, I was wondering if there is a way to serialize filtered_graphs? My first attempts fail because keep_all seems not to be serializable: /usr/include/boost/serialization/access.hpp:109: error: ‘struct boost::keep_all’ has no member named ‘serialize’ I have no problems serializing even custom adjacency_lists using the same approach. Besides discussing if it actually makes sense to serialize a filtered_graph, I am interested in suggestions on how to achieve it (if it is indeed possible). Thank you. Best regards, Cedric
On Tue, 16 Nov 2010, Cedric Laczny wrote:
Hi,
I was wondering if there is a way to serialize filtered_graphs?
My first attempts fail because keep_all seems not to be serializable: /usr/include/boost/serialization/access.hpp:109: error: ‘struct boost::keep_all’ has no member named ‘serialize’
I have no problems serializing even custom adjacency_lists using the same approach.
Could you please try adding serialization code to the keep_all structure? It should be easy since IIRC it does not have any members.
Besides discussing if it actually makes sense to serialize a filtered_graph, I am interested in suggestions on how to achieve it (if it is indeed possible).
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. -- Jeremiah Willcock
On Tuesday, 16. November 2010 17:50:12 Jeremiah Willcock wrote:
On Tue, 16 Nov 2010, Cedric Laczny wrote:
Hi,
I was wondering if there is a way to serialize filtered_graphs?
My first attempts fail because keep_all seems not to be serializable: /usr/include/boost/serialization/access.hpp:109: error: ‘struct boost::keep_all’ has no member named ‘serialize’
I have no problems serializing even custom adjacency_lists using the same approach.
Could you please try adding serialization code to the keep_all structure? It should be easy since IIRC it does not have any members.
I'm sorry, but I do not know how to do that actually. I mean, I do not know how to add some functionality without changing the original code. Is this actually possible?
Besides discussing if it actually makes sense to serialize a filtered_graph, I am interested in suggestions on how to achieve it (if it is indeed possible).
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 would be my view too.
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.
That second option sounds nice but it would mean to loose a lot of information, as you probably know. Therefore, serializing the original, input graph completely and serializing the filter function would be more like the solution I need.
-- Jeremiah Willcock
Thank you. Best, Cedric
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
Hi,
Could you please specify how to avoid the copy and get the original graph- type?
Yes, that would be useful :o) I'm currently using filtered graphs, but I can imagine situations where the memory overhead of storing a new graph would be preferable to the CPU overhead of using the filtered graph. -- The Wellcome Trust Sanger Institute is operated by Genome Research Limited, a charity registered in England with number 1021457 and a company registered in England with number 2742969, whose registered office is 215 Euston Road, London, NW1 2BE.
On Thursday, 18. November 2010 14:23:35 Adam Spargo wrote:
Hi,
Could you please specify how to avoid the copy and get the original graph- type?
Yes, that would be useful :o) I'm currently using filtered graphs, but I can imagine situations where the memory overhead of storing a new graph would be preferable to the CPU overhead of using the filtered graph.
Hi Adam, I don't know if you are actually particulary interested into the steps that will _not_ involve copying, or if you are simply interested into getting the graph resulting from the filtering into the original graph-type. In case you don't care about the copying, you can simply use copy_graph() (defined in boost/graph/copy.hpp). Although I could imagine that avoiding copying might be quite crucial for your applications. Best, Cedric
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
participants (3)
-
Adam Spargo -
Cedric Laczny -
Jeremiah Willcock