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

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 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users