Re: [Boost-users] [PBGL] Betweenness centrality and named vertexes

Subject: Re: [Boost-users] [PBGL] Betweenness centrality and named vertexes
From: Carmine Paolino (earcar_at_[hidden])
Date: 2010-11-27 11:45:05

On 27 Nov 2010, at 16:34, Cedric Laczny wrote:

> On Saturday, 27. November 2010 16:03:19 Carmine Paolino wrote:
> 
>>> When looking at the example adjacency_list<>-definition of the
>>> documentation on PBGL, I see they are using mpi::bsp_process_group
>>> whereas you are using mpi_process_group. I don't know if that makes a
>>> difference, but when I look at
>>> http://www.osl.iu.edu/research/pbgl/documentation/mpi_bsp_process_group.
>>> html, I can see no definition of local() there...
>> 
>> I don't know the origin of bsp_process_group, in fact I tried to compile
>> with this instead of mpi_process_group and it doesn't work… Probably it's
>> old: deprecated in the code, but left in the documentation…
>> 
> 
> This was just a guess and as we see it seems not to affect your problem.
> 

In boost/graph/parallel/process_group.hpp, comments suggest that `mpi_process_group` uses a BSP-type communication model, so I'm almost certain that that was an older name for the same function. I will also file a bug for this.

>> Yes, without this declaration it does compile:
>> 
>>        template<>
>>        struct internal_vertex_name<Vertex> {
>>            typedef multi_index::member<Vertex, std::string, &Vertex::name>
>> type; };
>> 
>> But the comfort of having boost manage adding and finding vertexes also
>> goes away, which means we have to use something like a map of all the
>> inserted names on a single process to know if a name should be added to
>> the graph or not. And that doesn't scale well. Anyway I'm open to
>> suggestion on this if the named graph way doesn't work…
> 
> I agree with you on this one. I experienced the boost library to be very 
> efficient in all cases where I used it and the authors probably have thought 
> about this in order to make it suitable (and fast) for distributed purposes.
> In fact, I find this feature very convenient and I think it may be also helpful 
> in non-distributed graphs. Using already existing features is IMHO definitively 
> nicer than putting all kinds of maps or such on top for lookup-purposes. It 
> will only bloat the code and make it harder to read and maintain and probably 
> will steal preformance.

Exactly.

> That's why it is important to check if this is actually a bug :)
> 

>>> Or you could test if your code compiles when using a different algorithm
>>> than brandes_betwenness_centrality, e.g. breadth_first_search() or such
>>> (if they have distributed specializations for them)
>> 
>> The code compiles and runs well with degree centrality, node strength (a
>> generalization of degree centrality to graphs with weighted edges), and
>> PageRank. You can see the working code here:
>> https://github.com/earcar/lana
> 
> Do you mean the code including the named vertices or the code without the 
> named vertices?
> 

It's the actual project (still in early stages!), which is implemented with named vertices.

>> 
>> 
>>> Maybe it was fixed in a recent version of the Boost library?
>> 
>> I have 1.45 on my computer, and have a FreeBSD build server with 1.43 but
>> it doesn't work in both cases.
> 
>>> While this might not resolve the issue with local(), it could actually
>>> track down one error and might reveal a bug.
>> 
>> Yes, I think you got it right. And thanks for the clear explanation. :)
>> 
>> I'm now exploring the possibilities I have: if I can implement the local()
>> function or if there's something else I can do.
>> 
> 
> Good to see that tracking down that error seems to have worked :)
> Thank you for testing the suggestions.
> 
> Because this might represent a bug (you seem to have the most recent version 
> of boost - maybe except for the svn-versions) and since you are actually 
> working on that problem, could you please file a bug report on this?

Here it is: https://svn.boost.org/trac/boost/ticket/4899

> Maybe it will even be fixed in the november bug sprint...
> 
> General information about the bug sprint is here:                       
> https://svn.boost.org/trac/boost/wiki/BugSprintNov2010

Great.

Carmine