Re: [boost] [BGL] Multithread problem inserting edges and exploring the same graph

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

> Here are some ideas:
> Do you need all of the properties in the explorer threads? maybe you
> can construct a somewhat cheap copy of the graph of just vertices,
> edges and weights?

Unfortunately no, my graph has 5 million of vertices and 10 million of 
edges, and the properties RAM cost is very lower confronted to the graph 
structure. The graph structure takes approximately the same RAM quantity 
of the graph + properties.
Moreover I've tried to make a graph copy, but it takes about 30 seconds 
on my machine (Pentium D 2.8GHz, 3Gb RAM, WinXP); it's too much 
confronted to the Dijkstra's time (about 6-7 seconds).

> 
> When each explorer thread runs an instance of Dijkstra you might
> consider a parallel version of Dijkstra [1,2] working on disjoint
> graph regions? That might allow you to cut the graph into pieces and
> assigning a 'local' version of the graph to each explorer thread and
> joining them later on?
> 

These arguments are relatively new to me... do you think that's the way?

I've take a look to PBGL and MTGL:

https://software.sandia.gov/trac/mtgl/
http://www.osl.iu.edu/research/pbgl/

Maybe I can use them to resolve my problem?

Thanks,
Cosimo Calabrese.