c++ - Fruchterman Reingold 布局不收敛

Question

我想用BGL布局一个RNA fold 的图，它有一个保证的平面结构，所有的边应该有相同的长度(有两种边:正常序列和红色的键)，像这样:

rna secondary structure http://www.ncrna.org/frnadb/sec_structure/png/FR096703.png

namespace boost {
    enum vertex_position_t { vertex_position };
    BOOST_INSTALL_PROPERTY(vertex, position);
};

template<class PairIterator>
void layout(std::string seq, PairIterator begin, PairIterator end) {
    using namespace boost; using namespace std;

    // backbone edges + bonding edges
    vector<pair<size_t,size_t>> edge_list(begin, end);
    for(size_t i = 0 ; i < seq.size() - 1 ; i++)
        edge_list.push_back(make_pair(i, i + 1));

    typedef rectangle_topology<> topology;
    typedef topology::point_type point;
    boost::minstd_rand random;
    topology space(random, -1000, -1000, 2000, 2000);

    adjacency_list<vecS, vecS, undirectedS,
        property<vertex_position_t, point>
    > g(edge_list.begin(), edge_list.end(), seq.size());

    random_graph_layout(g, get(vertex_position, g), space);
    fruchterman_reingold_force_directed_layout(g, get(vertex_position, g), space,
        cooling(linear_cooling<double>(100)));

    // draw
}

但是，这给了我一个非常随机的布局(冷却时间为 100、200、400)。更长的冷却时间只需将顶点压入角落(图像显示完整布局)。边缘似乎总是太长......

我想为边缘指定一个目标长度，并且在达到一定范围内之前不停止模拟。

我的代码是从 boost 示例中拼凑而成的，但我不需要坚持使用属性映射等，我只需要一个布局而不必求助于 GraphViz。

Answer 1

看起来布局开始在您最右侧的图像中起作用，但空间太小，无法展开成正确的形状:也许尝试使用更紧凑的随机布局开始？

或者更强的吸引力也可能有所帮助。注意根据the documentation默认的吸引力函数，square_distance_attractive_force 除以边缘描述符的吸引力 --- 因此较小的边缘描述符意味着更近的顶点。

---

考虑到对于布局良好的平面图，每个顶点仅靠近它通过边链接到的顶点，您可以计算出边的“目标长度”(某种程度上)。这与我们有两个顶点由一条边连接的简单情况非常相似(如果你有一个规则的顶点网格，它不会超过 4 倍):

• 所有顶点对的(默认)排斥力函数是(vertex descriptor value, V)^2/distance。
• 对于由边连接的顶点，(默认)吸引力函数是distance^2/(edge descriptor value, E)。

在以下情况下，它们处于平衡状态:

V²/距离 = 距离²/E

所以:

距离 = V^(2/3) E^(1/3)