c++ - 提高图形连通性计算的性能

Question

我正在编写一个程序来生成图形并检查它是否已连接。下面是代码。这里有一些解释:我在平面上的随机位置生成了一些点。然后我连接节点，而不是仅基于接近度。我的意思是说一个节点更有可能连接到更近的节点，这是由我在代码中使用的随机变量 (h_sq) 和距离决定的。因此，我生成所有链接(对称的，即，如果我可以与 j 对话，反之亦然)，然后使用 BFS 检查图形是否已连接。
我的问题是代码似乎工作正常。但是，当节点数大于 ~2000 时，速度非常慢，我需要多次运行此函数以进行模拟。我什至尝试将其他库用于图表，但性能是一样的。有谁知道我怎么可能加快一切？

谢谢，

int Graph::gen_links() {
    if( save == true ) { // in case I want to store the structure of the graph
        links.clear();
        links.resize(xy.size());
    }

    double h_sq, d;
    vector< vector<luint> > neighbors(xy.size());

    // generate links
    double tmp = snr_lin / gamma_0_lin;
    // xy is a std vector of pairs containing the nodes' locations
    for(luint i = 0; i < xy.size(); i++) {
        for(luint j = i+1; j < xy.size(); j++) {
            // generate |h|^2
            d = distance(i, j);
            if( d < d_crit ) // for sim purposes
                d = 1.0;
            h_sq = pow(mrand.randNorm(0, 1), 2.0) + pow(mrand.randNorm(0, 1), 2.0);
            if( h_sq * tmp  >= pow(d, alpha) ) {
                // there exists a link between i and j
                neighbors[i].push_back(j);
                neighbors[j].push_back(i);
                // options
                if( save == true )
                    links.push_back( make_pair(i, j) );
            }
        }
        if( neighbors[i].empty() && save == false  ) {
        // graph not connected. since save=false i dont need to store the structure, 
        // hence I exit
            connected = 0; 
            return 1;  
        }
    }

    // here I do BFS to check whether the graph is connected or not, using neighbors
    // BFS code...
    return 1;
}

更新:主要问题似乎是内部 for 循环中的 push_back 调用。在这种情况下，这是花费大部分时间的部分。我应该使用 reserve() 来提高效率吗？

Answer 1

您确定速度慢是由生成引起的而不是由您的搜索算法引起的吗？

图的生成是 O(n^2) 的，你不能对它做太多。但是，如果至少某些实验的点位置是固定的，您显然可以使用内存来换取一些时间。

首先，所有节点对的距离和 pow(d, alpha) 可以预先计算并保存到内存中，这样您就不需要一次又一次地计算它们。 10000 个节点的额外内存成本对于 double 大约为 800mb，对于 float 大约为 400mb..

另外，如果我没记错的话，正态变量的平方和是卡方分布..如果精度允许，你可能可以进行一些预先计算的表查找？

最后，如果距离超过某个值，两个节点连接的概率很小，那么你就不需要O(n^2)，可能你只能计算那些距离更小的节点对超过一些限制？