3

BGLを使用してRNAフォールディングのグラフをレイアウトしたいのですが、平面構造が保証されており、すべてのエッジが同じ長さである必要があります（通常のシーケンスと赤の結合の2種類のエッジがあります）。

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の場合）。より長いクールダウンは、頂点をコーナーに押し込むだけです（画像は完全なレイアウトを示しています）。エッジが一貫して長すぎるようです...

出力

エッジのターゲットの長さを指定し、ある程度のマージン内に到達するまでシミュレーションを停止させたくありません。

私のコードはブーストサンプルからまとめられていますが、プロパティマップなどに固執する必要はなく、GraphVizに頼らずにレイアウトが必要です。

4

1 に答える 1

3

一番右の画像でレイアウトが機能し始めているように見えますが、スペースが小さすぎて適切な形状に展開できません。最初は、よりコンパクトなランダム レイアウトを使用してみてください。

または、より強い引力も役立つかもしれません。ドキュメントによると、デフォルトの引力関数は、引力をエッジ記述子でsquare_distance_attractive_force 除算することに注意してください。つまり、エッジ記述子が小さいほど、頂点が近くなります。

適切にレイアウトされた平面グラフの場合、各頂点はエッジによってリンクされている頂点にのみ近いことを考慮することにより、エッジの「ターゲット長」(一種) を計算できます。これは、1 つのエッジで結合された 2 つの頂点がある単純なケースと非常によく似ています (また、頂点の規則的なグリッドがある場合、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 に答える