Boost C++ Libraries: Ticket #4899: Parallel graphs don't work with named vertices

cpaolino@… — Sun, 28 Nov 2010 14:57:26 GMT

Another useful info might be, as Cedric Laczny pointed out on that mailing list thread:

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

owner changed

Jeremiah Willcock — Mon, 29 Nov 2010 14:33:07 GMT

owner changed from Andrew Sutton to ngedmond

owner, status changed

Jeremiah Willcock — Wed, 01 Dec 2010 20:32:24 GMT

owner changed from ngedmond to Jeremiah Willcock
status new → assigned

I agree with comment 1 -- it seems like you are trying to use a distribution that uses numbers to index vertex locations (it appears to use an std::vector), while something is trying to find vertex locations using their names. Do any PBGL algorithms work with your named vertex example? How important is it to you to use named vertices as opposed to just vertex numbers?

summary changed

Jeremiah Willcock — Wed, 01 Dec 2010 20:33:19 GMT

summary Parallel Brandes Betweenness Centrality doesn't work with named vertices (hashed_distribution doesn't have `local()`) → Parallel graphs don't work with named vertices

cpaolino@… — Thu, 02 Dec 2010 10:11:41 GMT

Replying to jewillco:

I agree with comment 1 -- it seems like you are trying to use a distribution that uses numbers to index vertex locations (it appears to use an std::vector), while something is trying to find vertex locations using their names.

I think it's the other way around: I'm trying to use named graphs with an algorithm that not expects them.

Do any PBGL algorithms work with your named vertex example?

Yes, PageRank and Degree centrality (the same from the non-parallel BGL, with two line changes to make it work with distributed graphs; will make another bug report for that).

How important is it to you to use named vertices as opposed to just vertex numbers?

I'll quote myself and Cedric Laczny on that mailing list thread:

Cedric Laczny wrote:

Carmine Paolino wrote:

Yes, without this declaration (editor's note: that makes it a named graph) 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 :)

owner, status changed

Jeremiah Willcock — Mon, 16 Apr 2012 17:56:49 GMT

owner changed from Jeremiah Willcock to ngedmond
status assigned → new