Adding a vertex_index to listS graph on the fly for betweenness centrality

Question

Update: The issue may be in the betweenness code. If I comment out the call to brandes_betweenness_centrality the code will compile. the problem may not be the index set up as previously thought. I'll award bounty if you can come up with an alternative call to brandes_betweenness_centrality that will allow keeping the index external.

I'm trying to convert some of my old vecS code to work with listS, specifically the brandes_betweenness_centrality algorithm.

I'm trying to keep the Vertex and Edge properties very light weight and work mainly with external properties. The reason for this is that I don't know what all I'll want to associate with them at this point.

The errors I'm getting are coming from inside adjacency_list.hpp so I figure the problem is with our old friend vertex_index_t with listS.

The following code shows how to reproduce the compile error. In this working example, you can change the definition to stuff a vertex_index into the graph definition and change the set up in the betweenness method for completely working code (which runs betweenness correctly).

The complete example:

#include <iostream>
#include <algorithm>
#include <vector>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/betweenness_centrality.hpp>

#include <boost/timer.hpp>

using namespace std;

enum edge_t {A,B};

struct VertexProperties{
    std::string id;
};

struct EdgeProperties{
    edge_t type;
};

//vertex_index in as internal property, switch to this graph and change below vertex map for working code
//typedef boost::adjacency_list < boost::listS, boost::listS, boost::undirectedS,
//      boost::property<boost::vertex_index_t,size_t,VertexProperties>, EdgeProperties > DynamicNet;

// No internal vertex_index
typedef boost::adjacency_list < boost::listS, boost::listS, boost::undirectedS,
        VertexProperties, EdgeProperties > DynamicNet;

typedef boost::graph_traits<DynamicNet>::vertex_descriptor DynamicNetVertex;
typedef boost::graph_traits<DynamicNet>::vertex_iterator   DynamicNetVI;

typedef boost::graph_traits<DynamicNet>::edge_descriptor   DynamicNetEdge;
typedef boost::graph_traits<DynamicNet>::edge_iterator     DynamicNetEI;


void calcBetweenness(DynamicNet &g,
                     std::vector<double> &v_centrality_vec,
                     std::vector<double> &e_centrality_vec);


int main(int argc, char* argv[]){
    cout <<  "betweenness" << endl;

    DynamicNet net;

    //Fig. 1, wheen graph (a - h), modified with added z added to a
    //http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/betweenness_centrality.html
    DynamicNetVertex a = boost::add_vertex(net); net[a].id = "a";
    DynamicNetVertex b = boost::add_vertex(net); net[b].id = "b";
    DynamicNetVertex c = boost::add_vertex(net); net[c].id = "c";
    DynamicNetVertex d = boost::add_vertex(net); net[d].id = "d";
    DynamicNetVertex e = boost::add_vertex(net); net[e].id = "e";
    DynamicNetVertex f = boost::add_vertex(net); net[f].id = "f";
    DynamicNetVertex g = boost::add_vertex(net); net[g].id = "g";

    //core
    DynamicNetVertex h = boost::add_vertex(net); net[h].id = "h";

    boost::add_edge(a,h,net); 
    boost::add_edge(b,h,net);
    boost::add_edge(c,h,net);
    boost::add_edge(d,h,net);
    boost::add_edge(e,h,net);
    boost::add_edge(f,h,net);
    boost::add_edge(g,h,net);

    //add an edge to make the calculation more interesting
    DynamicNetVertex z = boost::add_vertex(net); net[z].id = "z";
    boost::add_edge(a,z,net);



    vector<double> v_centrality_vec(boost::num_vertices(net),0.0);
    vector<double> e_centrality_vec(boost::num_edges(net),0.0);

    boost::timer t;
    t.restart();
    calcBetweenness(net,v_centrality_vec,e_centrality_vec);
    double s = t.elapsed();
    cout << s << " s" << endl;
    cout << endl;

    cout << "Vertex betweenness" << endl;
    DynamicNetVI vi,ve;     
    size_t i = 0;
    for(boost::tie(vi,ve) = boost::vertices(net); vi != ve; ++vi){
        cout << net[*vi].id << "\t" << v_centrality_vec.at(i) << endl;
        ++i;
    }

    cout << endl;

    cout << "Edge betweenness" << endl;
    DynamicNetEI ei,ee; 
    i = 0;
    for(boost::tie(ei,ee) = boost::edges(net); ei != ee; ++ei){
        DynamicNetEdge e = *ei;
        cout << net[boost::source(e,net)].id << "\t" 
             << net[boost::target(e,net)].id << "\t" << e_centrality_vec.at(i) << endl;
        ++i;
    }

    cin.get();
}

void calcBetweenness(DynamicNet &g,
                     std::vector<double> &v_centrality_vec,
                     std::vector<double> &e_centrality_vec)
{
    std::cout << "betweenness called" << std::endl;

    //vertex
    //Uncomment and change to internal vertex graph above for working code.

/*
    typedef std::map<DynamicNetVertex,size_t> StdVertexIndexMap;
    StdVertexIndexMap viMap;
    typedef boost::property_map<DynamicNet, boost::vertex_index_t>::type VertexIndexMap;
    VertexIndexMap v_index = boost::get(boost::vertex_index,g);
    DynamicNetVI vi,ve;
    size_t i = 0;
    for(boost::tie(vi,ve) = boost::vertices(g); vi != ve; ++vi){
        boost::put(v_index,*vi,i);
        ++i;
    }
    boost::iterator_property_map< std::vector< double >::iterator, VertexIndexMap >
        v_centrality_map(v_centrality_vec.begin(), v_index);
*/  

    //this code which exactly mimics the working approached used by edge results in an error
    typedef std::map<DynamicNetVertex,size_t> StdVertexIndexMap;
    StdVertexIndexMap viMap;
    typedef boost::associative_property_map<StdVertexIndexMap> VertexIndexMap;
    VertexIndexMap v_index(viMap);
    DynamicNetVI vi,ve;
    size_t i = 0;
    for(boost::tie(vi,ve) = boost::vertices(g); vi != ve; ++vi){
        boost::put(v_index,*vi,i);
        ++i;
    }
    boost::iterator_property_map< std::vector< double >::iterator, VertexIndexMap >
        v_centrality_map(v_centrality_vec.begin(), v_index);



    //edge, this appraoch works fine for edge
    typedef std::map<DynamicNetEdge,size_t> StdEdgeIndexMap;
    StdEdgeIndexMap eiMap;
    typedef boost::associative_property_map<StdEdgeIndexMap> EdgeIndexMap;
    EdgeIndexMap e_index(eiMap);
    DynamicNetEI ei,ee; 
    i = 0;
    for(boost::tie(ei,ee) = boost::edges(g); ei != ee; ++ei){
        boost::put(e_index,*ei,i);
        ++i;
    }
    boost::iterator_property_map< std::vector< double >::iterator, EdgeIndexMap >
        e_centrality_map(e_centrality_vec.begin(), e_index);

    brandes_betweenness_centrality(g,v_centrality_map, e_centrality_map);
}

The error:

Error   1   error C2182: 'reference' : illegal use of type 'void'   ... \boost_1_58_0\boost\graph\detail\adjacency_list.hpp 2543
Error   2   error C2182: 'const_reference' : illegal use of type 'void' ... \boost_1_58_0\boost\graph\detail\adjacency_list.hpp 2544

MSVS output:

1>------ Build started: Project: testBetweenness, Configuration: Release 

Win32 ------
1>Compiling...
1>testBetweenness.cpp
1>...\boost_1_58_0\boost/graph/detail/adjacency_list.hpp(2543) : error C2182: 'reference' : illegal use of type 'void'
1>        ...\boost_1_58_0\boost/graph/detail/adjacency_list.hpp(2619) : see reference to class template instantiation 'boost::adj_list_any_vertex_pa::bind_<Tag,Graph,Property>' being compiled
1>        with
1>        [
1>            Tag=boost::vertex_index_t,
1>            Graph=boost::adjacency_list<boost::listS,boost::listS,boost::undirectedS,pintk::VertexProperties,pintk::EdgeProperties>,
1>            Property=pintk::VertexProperties
1>        ]
1>        ...\boost_1_58_0\boost/graph/detail/adjacency_list.hpp(2752) : see reference to class template instantiation 'boost::detail::adj_list_choose_vertex_pa<Tag,Graph,Property>' being compiled
1>        with
1>        [
1>            Tag=boost::vertex_index_t,
1>            Graph=boost::adjacency_list<boost::listS,boost::listS,boost::undirectedS,pintk::VertexProperties,pintk::EdgeProperties>,
1>            Property=pintk::VertexProperties
1>        ]
1>        ...\boost_1_58_0\boost/graph/properties.hpp(208) : see reference to class template instantiation 'boost::adj_list_vertex_property_selector::bind_<Graph,Property,Tag>' being compiled
1>        with
1>        [
1>            Graph=boost::adjacency_list<boost::listS,boost::listS,boost::undirectedS,pintk::VertexProperties,pintk::EdgeProperties>,
1>            Property=pintk::VertexProperties,
1>            Tag=boost::vertex_index_t
1>        ]
1>        ...\boost_1_58_0\boost/graph/properties.hpp(217) : see reference to class template instantiation 'boost::detail::vertex_property_map<Graph,PropertyTag>' being compiled
1>        with
1>        [
1>            Graph=boost::adjacency_list<boost::listS,boost::listS,boost::undirectedS,pintk::VertexProperties,pintk::EdgeProperties>,
1>            PropertyTag=boost::vertex_index_t
1>        ]
1>        ...\boost_1_58_0\boost/graph/betweenness_centrality.hpp(562) : see reference to class template instantiation 'boost::property_map<Graph,Property,Enable>' being compiled
1>        with
1>        [
1>            Graph=boost::adjacency_list<boost::listS,boost::listS,boost::undirectedS,pintk::VertexProperties,pintk::EdgeProperties>,
1>            Property=boost::vertex_index_t,
1>            Enable=void
1>        ]
1>        ...\Visual Studio 2008\Projects\yapnl\yapnl\ProteinNetworks.h(82) : see reference to function template instantiation 'void boost::brandes_betweenness_centrality<pintk::DynamicNet,boost::iterator_property_map<RandomAccessIterator,IndexMap>,boost::iterator_property_map<RandomAccessIterator,EdgeIndexMap>>(const Graph &,CentralityMap,EdgeCentralityMap,boost::graph::detail::no_parameter)' being compiled
1>        with
1>        [
1>            RandomAccessIterator=std::_Vector_iterator<double,std::allocator<double>>,
1>            IndexMap=VertexIndexMap,
1>            Graph=pintk::DynamicNet,
1>            CentralityMap=boost::iterator_property_map<std::_Vector_iterator<double,std::allocator<double>>,VertexIndexMap>,
1>            EdgeCentralityMap=boost::iterator_property_map<std::_Vector_iterator<double,std::allocator<double>>,EdgeIndexMap>
1>        ]
1>...\boost_1_58_0\boost/graph/detail/adjacency_list.hpp(2544) : error C2182: 'const_reference' : illegal use of type 'void'
1>Build log was saved at "file://...\Visual Studio 2008\Projects\yapnl\testBetweenness\Release\BuildLog.htm"
1>testBetweenness - 2 error(s), 0 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

This answer, helped me add boost::vertex_index_t property in the graph definition which allowed the code to run by using boost::property<boost::vertex_index_t,size_t,VertexProperties>.

I would like a way to keep vertex_index_t completely external from the graph and add it just before I run the algorithm.

The virtually identical code for setting up edge_index allows this. Am I missing something or is this an MSVS thing or could it be a bug?

My specific question is: What do I need to change to keep vertex_index out of the graph definition, add it on the fly, and still run the algorithm?

Answer 1

As I stated in the update, it looks like the problem was in betweenness centrality. Digging through the dispatches in the source, and looking at the parameters in the docs I found that if vertex_index_map is not passed to the algorithm it defaults to get(vertex_index, g) which as we know does not exist in this particular graph.

After some time wrapping my head around named bgl_named_params, I figured out I could pass the v_index variable as a named parameter.

The following code did the trick:

brandes_betweenness_centrality(g,
            boost::centrality_map(v_centrality_map).edge_centrality_map(e_centrality_map).vertex_index_map(v_index));

I think the error was in the brandes_betweenness_centrality trying to call get(vertex_index,g)and failing on the listS graph.