1

グラフをレンダリングできるgraphvizに似たツールを探していますが、これにより、各ノードのx座標のみを制限できます。次に、ツールが自動的に y 座標を選択して、グラフがきれいに見えるようにします。

基本的に、タイムラインを作りたいと思っています。

言語/プラットフォーム/レンダリング メディアはあまり重要ではありません。

4

1 に答える 1

0

見栄えの良いグラフが必要な場合は、力指向のアルゴリズムが最適です。最高のものの 1 つは SFDP (AT&T によって開発され、graphviz に含まれています) ですが、疑似コードや簡単な実装が見つからないようです。これほど特化したアルゴリズムはないと思います。ありがたいことに、独自のコードを作成するのは簡単です。主にウィキペディアから引用した疑似コードをいくつか紹介しますが、適切に 1 次元の変更を加えています。n頂点があり、x 位置のベクトルが でx、添え字が であると仮定しますx.i。

set all vertex velocities to (0,0)
set all vertex positions to (x.i, random)
while (KE > epsilon)
    KE = 0
    for each vertex v
        force = (0,0)
        for each vertex u != v
            force = force + (0, coulomb(u, v).y)
            if u is incident to v
                force = force + (0, hooke(u, v).y)
        v.velocity = (v.velocity + timestep * force) * damping
        v.position = v.position + timestep * v.velocity
        KE = KE + |v.velocity| ^ 2

ここで、.yは力の y 成分を取得することを示します。これにより、頂点の位置の x コンポーネントが、設定した値から決して変化しないことが保証されます。このepsilonパラメーターはユーザーが設定するものであり、ユーザーが期待するもの KE(運動エネルギー) に比べて小さい値にする必要があります。また、|v|はベクトルの大きさを示しますv(上記では、KE を除いて、すべての計算は 2-ベクトルです)。すべてのノードの質量を 1 に設定しましたが、必要に応じて変更できます。

HookeおよびCoulomb関数は、節点間のそれぞれの力を計算します。1 つ目は頂点間の距離が線形で、2 つ目は 2 次であるため、平衡が保証されます。これらの関数は次のようになります

def hooke(u, v)
    return -k * |u.position - v.position|

def coulomb(u, v)
    return C * |u.position - v.position|

ここでも、ほとんどの計算はベクトル形式です。C と k には実際の値がありますが、実験して目的のグラフを取得してください。これは通常は必要ありません。これは、スケーリング係数が 2 次元でグラフ全体をかなり拡大または縮小するためです。 .

于 2012-12-31T06:51:59.390 に答える