Boost logo

Boost Users :

Subject: [Boost-users] Why does the creating of distributed adjacency list cost so much time?
From: Yan (yan_z_y_at_[hidden])
Date: 2011-10-13 09:53:12

Hi all,
I'm learning to use the distributed adjacency list and distributed dijkstra
SP-algorithm. I use some test data contains about 3,800,000 edges and
2,800,000 vertices. I use a pair of iterators to pass the data to the
distributed adjacency list, like that:
Graph g(reader.begin(), reader.end(), reader.weight_begin(),
reader.num_vertices(), pg, dist);
    "reader" is an user-defined class which supplys required data (edges,
vertices, weights).
    "pg" is defined like that "mpi_process_group pg;"
    "dist" is supplied by the reader like that "graph::metis_distribution
dist = reader.distribution();". It is based on a metis partition file
coordinating the test data.
I run 2 processes on my notebook computer(Intel core2 2.0G, Ram 2G,
I also test the same data using a sequential bgl dijkstra SP-algorithm on
this computer.
The result is that:
Parallel bgl:
Creating of Graph g costs *10080 seconds*; dijkstra computing costs 28.281
Sequential bgl:
Creating of Graph g costs *4.563 seconds*; dijkstra computing costs 1.703
As you see, when using distributed adjacency list, it costs so much time to
create the graph. Is it nomal?
I have done some more comparison between 2-processes parallel dijkstra on
one core2 computer and sequential dijkstra on the same computer, using
different scale data set. Always, the sequential bgl dijkstra costs less
time than the 2-processes parallel dijkstra. What's the problem? I have read
the boost document on
which shows a good performance and speedup in the charts. Doesn't that mean
less time costing than the sequential program?

Any advice would be appreciated.


View this message in context:
Sent from the Boost - Users mailing list archive at

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at