编辑:正如@sehe所指出的,错误位于中间中心计算之前的某个地方。沿着走!
我用Python
和C++
实现了一个最小的程序来计算无向图的介数中心性。令人惊讶的是,networkx
(Python)版本 * 远 * 优于boost::graph
(C++)实现,即使考虑到加载开销等。我做的事情完全没有效率吗?
Python代码的要点很简单
# load graph and start chrono
clist = nx.betweenness_centrality(g)
# output
字符串
对于C++,
typedef boost::adjacency_list<boost::vecS,
boost::vecS,
boost::undirectedS> Graph;
typedef boost::property_map< Graph, boost::vertex_index_t>::type VertexIndexMap;
int main() {
Graph g;
// ...
// load graph
// ...
VertexIndexMap v_index = get(boost::vertex_index, g);
std::vector< double > vertex_property_vec(boost::num_vertices(g), 0.0);
boost::iterator_property_map< std::vector< double >::iterator, VertexIndexMap >
vertex_property_map(vertex_property_vec.begin(), v_index);
boost::brandes_betweenness_centrality(g, vertex_property_map);
// Output ...
return 0;
}
型
请注意,这两个库似乎实现了完全相同的算法(Brandes 2001)。
1条答案
按热度按时间z4bn682m1#
2023年编辑这里有一个类似的Python networkx与Boost Graph的比较:为什么Networkx的Dijkstra比Boost的更快?
我无法重现这个问题。代码中可能有你没有显示的内容?
希望我的基准测试能有所帮助,它在我的PC上运行了90个随机图,其中包括2000个节点和4000条边,总共20秒。
备注:
Live On Coliru
字符串
我的机器的输出(2000个节点/4000条边):
型