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

Subject: Re: [Boost-users] [PBGL] Betweenness centrality and named vertexes
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2010-11-27 10:34:20

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.

> > And it seems that this local() function performs the access of the vertex
> > local to the process via indices. My thoughts on this are that either
> > there is a bug and that the local() function needs to be implemented
> > accordingly or that there is something going wrong with using
> > named-vertices here. It might be worth a try to leave that aside and
> > compile your example without that code.
> 
> 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.

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?

> 
> 
> > 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?
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

> Thanks,

Your are welcome

> Carmine

Best,

Cedric

> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users