Fruchterman Reingoldのレイアウトが収束しない

Question

RNA折りたたみのグラフをBGLでレイアウトしたいのですが、それは保証された平面構造を持ち、すべての辺が同じ長さでなければなりません（2種類の辺があります。このような赤で結合）、：

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）のために（私は非常にランダムなレイアウトを提供します。より長いコールドダウンは頂点をコーナーに押し込むだけです（イメージは完全なレイアウトを示します）。エッジは...一貫長すぎるように見える

私はエッジのターゲットの長さを指定し、それはいくつかのマージン内に達していますまで、シミュレーションの停止を持っていないしたいと思います。

私のコードは、ブーストサンプルから一緒に石畳されていますが、私はプロパティマップなどに固執する必要はありません、私はただGraphVizに頼ることなくレイアウトが欲しいです。

Answer 1

右手の画像でレイアウトが動作し始めているようですが、スペースが小さすぎて正しい形に展開できない場合があります。

また、より強力な魅力的な力が役立つかもしれません。 the documentationデフォルト吸引力関数によれば、square_distance_attractive_forceは、エッジ記述子による引力をで割るので、より小さいエッジ記述子はより近い頂点を意味することに注意してください。

---

あなたがうまくレイアウトされた平面グラフのために、各頂点は、それがエッジによってリンクされている頂点のみに近い、ということを考慮することにより、エッジのための「ターゲットの長さを」（一種の）ワークアウトすることができます。

• ：これは、我々は、単一エッジ（とあなたが頂点の規則的な格子を持っていたならば、それは4つ以上の要因によってではないでしょう）によって接合された2つの頂点を持つシンプルなケースにかなり似ています（デフォルト）反発力関数は、すべての頂点ペアに対して(vertex descriptor value, V)^2/distanceです。
• エッジでリンクされた頂点の（デフォルト）引力関数はdistance^2/(edge descriptor value, E)です。

これらは平衡状態にある。

V /距離=距離/E

そう：

距離= V ^{（2/3）E（1/3）}