I am experiencing a problem with multithreading using the boost graph library on a dual core Pentium D platform. If I attempt to calculate average path length of a graph, I get at least a 2x slowdown using multiple threads when using johnson_all_pairs_shortest_path. Calculating betweenness is even worse (~7x) when I use  brandes_betweenness_centrality and relative_betweenness_centrality.
<br><br>In my test setup, I have no locks anywhere and no shared memory (the graphs are loaded from a file for each iteration in the test). The graph has been defined similar to the following (I can&#39;t get actual code on the list due to restrictions from employer): 
<br><br>struct VertexProperties<br>{<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; string name;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; string group;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; vector&lt;string&gt; properties;<br>};<br><br>struct EdgeProperties<br>{<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; string name;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; double weight;<br>};<br>
<br>typedef boost::property&lt;...&gt; GraphProperty //a group of enums mapped to doubles and ints<br><br>typedef boost::adjacency_list&lt;listS, vecS, undirectedS, VertexProperties, EdgeProperties, GraphProperty&gt; BoostGraph;
<br><br>All I have to do in my code to see the slowdown is to use a populated graph with johnson_all_pairs_shortest_path in some iterative loop in both one and multiple threads. A real kicker is that currently I can get around this problem by spawning multiple processes to deal with the data load (so I have an interim solution at least) and that gives me a performance improvement by 2x which I expect with dual core... However, I really want to know why this isn&#39;t working in a multi-threaded environment.
<br><br>&nbsp;What could I be doing wrong? Is there some proprocessor #define that makes the boost graph library more thread independent? Is there something wrong with the way that I am declaring the graph? Any help is appreciated!
<br><br>Thanks,<br>Thranil<br>