将 vertex_index 动态添加到 listS 图以获得中间中心性
Adding a vertex_index to listS graph on the fly for betweenness centrality
更新：问题可能出在介数代码上。如果我注释掉对 brandes_betweenness_centrality 的调用，代码将编译。问题可能不是像以前认为的那样设置索引。如果您能提出对 brandes_betweenness_centrality 的替代调用，允许将索引保持在外部，我将悬赏。
我正在尝试将我的一些旧 vecS 代码转换为与 listS 一起使用，特别是 brandes_betweenness_centrality 算法。
我试图让 Vertex 和 Edge 属性保持非常轻量，并且主要使用外部属性。这样做的原因是我不知道此时我想与他们联系的是什么。
我得到的错误来自 adjacency_list.hpp 内部，所以我认为问题出在我们的老朋友 vertex_index_t 和 listS 上。
以下代码显示了如何重现编译错误。在这个工作示例中，您可以更改定义以将 vertex_index 填充到图形定义中，并更改中间方法中的设置以获得完整的工作代码（正确 运行s 中间）。
完整示例：
#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 ==========
这个 ，帮助我在图表定义中添加 boost::vertex_index_t 属性，这允许代码通过使用 boost::property<boost::vertex_index_t,size_t,VertexProperties>.[=22 运行 =]
我想要一种方法，使 vertex_index_t 完全远离图表，并在我 运行 算法之前添加它。
用于设置 edge_index 的几乎相同的代码允许这样做。我是不是遗漏了什么，或者这是一个 MSVS 问题，还是一个错误？
我的具体问题是：我需要更改什么才能将 vertex_index 保留在图形定义之外，即时添加它，并且仍然 运行算法？
正如我在更新中所说，问题似乎出在中间中心性上。通过 source, and looking at the parameters in the 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 图表上失败。
更新：问题可能出在介数代码上。如果我注释掉对 brandes_betweenness_centrality 的调用，代码将编译。问题可能不是像以前认为的那样设置索引。如果您能提出对 brandes_betweenness_centrality 的替代调用，允许将索引保持在外部，我将悬赏。
我正在尝试将我的一些旧 vecS 代码转换为与 listS 一起使用，特别是 brandes_betweenness_centrality 算法。
我试图让 Vertex 和 Edge 属性保持非常轻量，并且主要使用外部属性。这样做的原因是我不知道此时我想与他们联系的是什么。
我得到的错误来自 adjacency_list.hpp 内部，所以我认为问题出在我们的老朋友 vertex_index_t 和 listS 上。
以下代码显示了如何重现编译错误。在这个工作示例中，您可以更改定义以将 vertex_index 填充到图形定义中，并更改中间方法中的设置以获得完整的工作代码（正确 运行s 中间）。
完整示例：
#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 ==========
这个 我想要一种方法，使 用于设置 edge_index 的几乎相同的代码允许这样做。我是不是遗漏了什么，或者这是一个 MSVS 问题，还是一个错误？ 我的具体问题是：我需要更改什么才能将 vertex_index 保留在图形定义之外，即时添加它，并且仍然 运行算法？boost::vertex_index_t 属性，这允许代码通过使用 boost::property<boost::vertex_index_t,size_t,VertexProperties>.[=22 运行 =]
vertex_index_t 完全远离图表，并在我 运行 算法之前添加它。
正如我在更新中所说，问题似乎出在中间中心性上。通过 source, and looking at the parameters in the 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 图表上失败。