Boost logo

Boost :

Subject: Re: [boost] [BGL] Multithread problem inserting edges and exploring the same graph
From: Cosimo Calabrese (cosimo.calabrese_at_[hidden])
Date: 2009-09-23 14:32:36

> It looks like (from your description that I snipped out) that you are
> really creating a new graph for every thread that is a copy of the
> original graph plus some new, thread-specific edges. I would not
> recommend having a single graph for all of this because of the issues
> you are having. What about the following:

Well, I've really a single, unique, huge istance of an adjacency_list in
my application. I've called the initial form of that graph: 'original
graph'. There aren't other graphs in memory. Every thread creates a
filtered_graph object, that takes a reference of the original graph, but
it's not a memory copy of it, it's only an adaptor. The thread adds the
new edges and vertices using a reference of the original graph, and
explores the filtered graph. The original graph has about 5 million of
vertices and 10 million of edges. It takes about 1 Gb of RAM, I can't
replicate it.

> 1. Create a union_graph adapter that takes two graphs with the same
> number of vertices and merges their edge sets (concatenating the
> out_edges and in_edges for each vertex implicitly). Properties would
> also need to be handled (or indexes for external properties).
> 2. For every thread, create a new graph with just that thread's new
> edges and run Dijkstra's algorithm on the union_graph of that piece and
> the original graph.
> 3. Throw away the temporary, thread-specific graph when the thread is done.

It seems a very, very good idea. I like it very much. If it works, I
always access to the 'original' graph in read-only modality, that is the
only shared object; I don't need to add any vertex or edge to any
existing graph, but each thread only needs to create another, completly
new graph, which isn't shared with other threads. So the thread explore
the union adaptor in read-only modality. Exciting.

Now I must take a look on some 'graph arithmetic'... This adaptor needs
only to model the traversal graph concepts. The two graph type in input
to the union adaptor must be the same. So all the adaptor types required
by the concepts are the same of the input graphs. Now I need a moment to
think about the concept funcions (out_edges(), out_degree(), ... ). I'll
tell you about the state of the adaptor very soon.

> That should remove all of your locking (except in the memory allocator),


> and the filtered_graph,

Mmmmh, no, not yet. There is one thing of my project I've not mentioned,
it's difficult to explain all of it... The graph elements have many
properties. Each thread needs to explore not all the graph, but only a
particular view of it, that must change dependently by the specific
request. So, I need the filter_adaptor. But if you think that I haven't
understood something about this point, please... tell me.

> and greatly simplify (and probably speed up) the
> code. Do you think this will work?

Yes, I'm hopeful. I'll tell you soon. Thanks for the great idea.

But beyond the Jeremiah's idea, no one can explain what happens in my
application? I'm referring to the memory corruption. Surely it depends
on the contemporary reading and writing by different thread at the same
moment, but I would to know why it happens, even if I've locked all the

Thanks to all,
Cosimo Calabrese.

Boost list run by bdawes at, gregod at, cpdaniel at, john at