Re: [Boost-bugs] [Boost C++ Libraries] #4899: Parallel graphs don't work with named vertices

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #4899: Parallel graphs don't work with named vertices
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2010-12-02 10:11:43

#4899: Parallel graphs don't work with named vertices
-----------------------------------+----------------------------------------
  Reporter:  cpaolino@…            |       Owner:  jewillco                                          
      Type:  Bugs                  |      Status:  assigned                                          
 Milestone:  To Be Determined      |   Component:  graph                                             
   Version:  Boost 1.45.0          |    Severity:  Problem                                           
Resolution:                        |    Keywords:  parallel, distributed, betweenness, named vertices
-----------------------------------+----------------------------------------

Comment (by cpaolino@…):

 Replying to [comment:3 jewillco]:
 > I agree with [#comment:1 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
 [http://www.boost.org/doc/libs/1_45_0/libs/graph_parallel/doc/html/distributed_adjacency_list.html

 #named-vertices named graphs] with an algorithm that not expects them.

 > Do any PBGL algorithms work with your named vertex example?

 Yes, !PageRank and Degree centrality
 ([https://github.com/earcar/lana/blob/develop/src/degree_centrality.hpp

 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 :)

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/4899#comment:5>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.