c++ - 动态添加 vertex_index 到 listS 图以实现中间中心性

Question

更新:问题可能出在中介代码中。如果我注释掉对 brandes_betweenness_centrality 的调用代码将编译。问题可能不是以前想象的那样设置的索引。如果你能想出一个对brandes_betweenness_centrality 的替代调用，我将奖励赏金，这将允许将索引保持在外部。

我正在尝试将我的一些旧 vecS 代码转换为与 listS 一起使用，特别是 brandes_betweenness_centrality算法。

我正在尝试保持 Vertex 和 Edge 属性的重量非常轻，并且主要使用外部属性。这样做的原因是，我不知道此时我想与他们关联什么。

我得到的错误来自内部 adjacency_list.hpp所以我认为问题出在我们的老 friend vertex_index_t与 listS。

以下代码显示了如何重现编译错误。在这个工作示例中，您可以更改定义以将 vertex_index 填充到图形定义中，并更改中介方法中的设置以获得完全工作的代码(正确运行中介)。

完整的例子:

#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);
}

错误:

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 输出:

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

这个 answer ，帮我加了boost::vertex_index_t图定义中允许代码运行的属性 boost::property<boost::vertex_index_t,size_t,VertexProperties> .

我想要一种方法来保留 vertex_index_t完全在图表之外，并在我运行算法之前添加它。

用于设置 edge_index 的几乎相同的代码允许这样做。我是否遗漏了什么或者这是一个 MSVS 的东西还是可能是一个错误？

我的具体问题是:我需要进行哪些更改才能将 vertex_index 排除在图形定义之外、即时添加它并仍然运行算法？

Answer 1

正如我在更新中所说，问题似乎在于中介中心性。挖掘 source 中的调度，并查看 docs 中的参数我发现如果 vertex_index_map未传递给默认为 get(vertex_index, g) 的算法据我们所知，该特定图表中不存在。

一段时间后，我把我命名为 bgl_named_params ，我发现我可以通过 v_index变量作为命名参数。

下面的代码成功了:

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

我认为错误出现在 brandes_betweenness_centrality试图调用get(vertex_index,g)并在 listS 上失败图表。