3

我想使用 BGL 布局 RNA 折叠图，它具有保证的平面结构，并且所有边都应该具有相同的长度（有两种边：正常序列和红色键），如下所示：

rna 二级结构 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。

4

1 回答 1

3

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

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

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

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

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

V 2 / 距离 = 距离2 / E

所以：

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

于 2012-05-08T19:54:55.987 回答