Boost logo

Boost Users :

Subject: [Boost-users] Some questions about the time-costing of distributed adjacency list
From: Yan (yan_z_y_at_[hidden])
Date: 2011-09-26 22:57:34

Hi Nick,
I'm sorry for disturbing you again for some more help.
These days I have done some more test using the distributed adjacency list and distributed dijkstra SP-algorithm. The 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 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, WinXPsp3).
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 seconds.
Sequential bgl:
Creating of Graph g costs 4.563seconds; dijkstra computing costs 1.703 seconds.
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 "boost_1_46_1\libs\graph_parallel\doc\html\dijkstra_shortest_paths.html", which shows a good performance and speedup in the charts. Doesn't that mean less time costing than the sequential program?
By the way, when using distributed dijkstra, how to invoke the delta-stepping algorithm? Is it also through the dijkstra_shortest_paths(g, start, ...)?
Thank you very much for all your help.
Best regards!

发件人: Nick Edmonds [via Boost] <ml-node+s2283326n3837765h68_at_[hidden]>
收件人: Yan <yan_z_y_at_[hidden]>
发送日期: 2011年9月24日, 星期六, 上午 3:03
主题: Re: [BGL] Distributed adiacency_list memory allocation

> This is exactly what I was looking for, though I don't understand all of
> your words, but most. At least now I'm sure its not an error but normal. By
> the way, I'm new to PBGL, would you please tell me some forums or websites
> that good for beginers of PBGL.

I think this list is the best place I can suggest.  I'm not sure how many people are using the Boost release but most of the people actively using the development version are people I know personally or professionally and they tend to just contact me directly.  The folks on this list ought to be able to help with some of the basic parts though and I'll try to chime in when something about the internals comes up (i.e. your question about memory consumption).

Boost-users mailing list
[hidden email]


If you reply to this email, your message will be added to the discussion below:
To unsubscribe from [BGL] Distributed adiacency_list memory allocation, click here.

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