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 10:03:19

A response to all your emails follow:

On 27 Nov 2010, at 14:11, Cedric Laczny wrote:

> I read a little about PBGL and even though I still don't know any solution to you problem, it might help to bring in some ideas?
> If I understood the documentation correctly, the vertices are distributed over the available processes by some distribution.
> Except for using the named vertices solution, it is only possible to access the vertices local to the process (simply via indices). Digging a little into the headers, I found that the function local(), that the compiler is complaining about, must be implemented by the "templated" BaseDistribution (boost/graph/distributed/shuffled_distribution.hpp). So I could think of that the object of the class BaseDistribution does not implement this local()-function.

In fact it does not. BaseDistribution is a hashed_distribution when using a named graph, defined in boost/graph/distributed/named_graph.hpp

Great insight, I'm taking a closer look at this.

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

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

> 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

> Other possibilites might very well exist and might be more appropriate so I am looking forward to hear those. For the moment these were the ideas that came to my mind.

Thanks!

---
> I found out that you are not alone with that problem.
> Please see
> http://stackoverflow.com/q/4258136
Actually, he is working with me on this issue :)
> 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.
---
> Hi,
> 
> sorry, to split the whole communication into such "small" pieces. Your problem 
> really puzzles me and I can hardly quit trying to understand what is causing 
> it.
No problem, you're welcome!
> I would really be interested in the result when leaving the named vertices 
> aside.
See above.
> AFAIK this should not be necessary to see if your distributed code will 
> compile, even with brandes_betweenness_centrality().
> You might ask why this plays a role. Actually, when I look at your error logs, 
> I see "
> /usr/local/include/boost/graph/distributed/shuffled_distribution.hpp: In member 
> function ‘size_t 
> boost::graph::distributed::shuffled_distribution<BaseDistribution>::operator()
> (const T&) const [with T = size_t, BaseDistribution = 
> boost::graph::distributed::hashed_distribution<std::basic_string<char, 
> std::char_traits<char>, std::allocator<char> > >]’:
> The problem here is the collision between size_t and char* 
> (std::basic_string).
> The argument should be of type size_t (index of a vertex for the local 
> process) but the underlying distribution is based on std::basic_string, 
> probably due to the named vertices (specialization in named_graph.hpp). This 
> causes an error at line 40 of boost/graph/distributed/named_graph.hpp which is 
> called by line 68 in boost/graph/distributed/shuffled_distribution.hpp.
> So the specialization to named vertices could be the cause.
> 
> 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.
Thanks,
Carmine