Yet another BGL's Betweenness centrality issue

Question

Drawing on this reply, I've tried to implement the Betweenness centrality as follows:

typedef struct vpr_
{ 
    int id;         
} VProp;
typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, VProp, EProp> graph_t;
boost::shared_array_property_map<double, boost::property_map<graph_t, int>::const_type> centrality_map(num_vertices(g), get(VProp::id, g));

But the following error was returned.

In file included from /usr/local/include/boost/graph/adjacency_list.hpp:246:0,
             from /usr/local/include/boost/graph/random.hpp:23,
             from ../../src/graph/Graph.h:25,
             from Graph.cpp:23:
/usr/local/include/boost/graph/detail/adjacency_list.hpp: In instantiation of ‘struct boost::adj_list_any_vertex_pa::bind_<int, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, vpr_, epr_>, vpr_>’:
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2568:12:   required from ‘struct boost::detail::adj_list_choose_vertex_pa<int, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, vpr_, epr_>, vpr_>’
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2705:12:   required from ‘struct boost::adj_list_vertex_property_selector::bind_<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, vpr_, epr_>, vpr_, int>’
/usr/local/include/boost/graph/properties.hpp:217:12:   required from ‘struct boost::detail::vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, vpr_, epr_>, int>’
/usr/local/include/boost/graph/properties.hpp:228:10:   required from ‘struct boost::property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, vpr_, epr_>, int>’
Graph.cpp:374:76:   required from here
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2498:29: error: forming reference to void
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2499:35: error: forming reference to void
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2502:47: error: forming reference to void
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2504:53: error: forming reference to void
Graph.cpp: In member function ‘void Graph::getBetweennes()’:
Graph.cpp:374:88: error: template argument 2 is invalid
Graph.cpp:375:17: error: invalid type in declaration before ‘(’ token
In file included from ../../src/graph/graph_t.h:33:0,
             from ../../src/graph/Graph.h:26,
             from Graph.cpp:23:
../../src/graph/VProp.h:38:6: error: invalid use of non-static data member ‘vpr_::id’
Graph.cpp:375:46: error: from this location
Graph.cpp:375:52: error: expression list treated as compound expression in initializer [-fpermissive]

EDIT

#include <boost/graph/iteration_macros.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/graph/random.hpp> 

typedef struct vpr_
{ 
    int id;         
} VProp;
typedef struct epr_
{ 
    int id;         
} EProp;
typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, VProp, EProp> graph_t;


int main(void) {
    graph_t g;
    boost::shared_array_property_map<double, boost::property_map<graph_t,  VProp::*>::const_type> centrality_map(num_vertices(g), get(&VProp::id, g));
}

The code has been compiled with g++ -L/usr/local/lib -lboost_graph gtest.cpp, and the returned error is:

 gtest.cpp: In function ‘int main()’:
 gtest.cpp:18:81: error: template argument 2 is invalid
 gtest.cpp:18:94: error: template argument 2 is invalid
 gtest.cpp:18:110: error: invalid type in declaration before ‘(’ token
 gtest.cpp:18:146: error: expression list treated as compound expression in initializer [-fpermissive]
 gtest.cpp:18:146: error: cannot convert ‘boost::adj_list_any_vertex_pa::bind_<int vpr_::*, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, vpr_, epr_>, vpr_>::type {aka boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, vpr_, epr_>, int, int&, int vpr_::*>}’ to ‘int’ in initialization

How could I fix this? Thanks in advance

I think, following [this](http://www.boost.org/libs/graph/doc/bundles.html)(in section "Properties maps from bundled properties"), that it should be `boost::shared_array_property_map::const_type> centrality_map(num_vertices(g), get(&VProp::id, g));`. But since you don't provide a compilable example I can't be sure. — llonesmiz, Apr 18 '14 at 14:20
@sehe, yes, but some people downgrade your posts only because It already existed... I wanted to make sure that I know that somebody had already posted something about this. @cv_and_he, why do you use `int VProp::*` as a type parameter? — jackb, Apr 18 '14 at 18:15
@cv_and_he, I've added some compiled code above here as requested. — jackb, Apr 18 '14 at 18:23
@jackb I haven't used the Boost.Graph library in anything serious, and I know very little about graph theory so my answer is only a guess. The only reason I use `int VProp::*` as a type parameter is because the documentation I linked in my previous comment says that that's the way to get a property map from a bundled property. Specifically it says that you should use `boost::property_map::const_type` or `boost::property_map::type` depending on whether your graph is const or not. The code you added fails with `const_type` but compiles with `type`. — llonesmiz, Apr 18 '14 at 19:13

score 2 · Answer 1 · edited May 23 '17 at 11:55

2

Jackb, this BGL algorithm like many others in BGL requires a "vertex index property map" -- a one-to-one mapping between set of graph vertices and integer numbers within interval [0,num_vertices(g)).

Now, your structures EProp and VProp cannot be used as substitutes for vertex_index property maps, and it is what causes the compilation errors.

If you can use boost::adjacency_list<boost::vecS, ...> as your graph type, then vertex_index mapping will come for free (as internal property of the graph). Then you will be able to call centrality algorithms the way it is called in your referenced thread: centrality_map(num_vertices(g), get(boost::vertex_index, g));.

If for some reasons you cannot use boost::vecS, you have to organize the mapping yourself. For setS and listS it is discussed here How to use boost::graph algorithms with listS, setS as vertex/edge containers? and references thereof.

See related discussions on Property Map here What is a property map in BOOST? and specifically on vertex_index map here: Dijkstra Shortest Path with VertexList = ListS in boost graph

edited May 23 '17 at 11:55

Community

1
1

answered Apr 19 '14 at 01:30

Michael Simbirsky

3,045
1
12
24

I have to associate to each vertex and edge some properties that are needed to associate to each node and hyperedge some C++ classes (not showed in my example in order to make the code compilable). I have to use listS because I want to make my graph editable at runtime, that is remove or add edges. My aim is similar as the one showed above, that is I would like to call afterwards `boost::brandes_betweenness_centrality(g,centrality_map);`. You mean that I have to map all the `VProp`s and `EProp`s into a `std::map`? I wanted to avoid that soultion if possible... – jackb Apr 19 '14 at 11:36
You can use vecS even when you plan to remove the vertices or edges. – Michael Simbirsky Apr 20 '14 at 07:03
If you use listS for vertices, you _have_ to populate some_map (some_map can be std::map, boost::unordered_map or even boost::bimap). You then have to populate them map and later pass it to the algorithm instead of vertex_index map. See the code doing exactly this here http://stackoverflow.com/a/7257966/2876861 – Michael Simbirsky Apr 20 '14 at 07:13

Yet another BGL's Betweenness centrality issue

1 Answers1

Linked