Menu


グラフの自動レイアウトに挑戦 #1 ばねモデル

ソースコード

今回のソースコードのダウンロード (zip/tar, 10.2KB)

はじめに

連載記事のトップのところに書いた図はこのようなものだ。

グラフ構造

これをコンピュータに自動配置させたい。

Eadesのばねモデル

このような、つながった複数の物体をコンピュータに自動配置させるのは「グラフ描画」または「グラフレイアウト」と呼ばれる分野であり、さまざまなアルゴリズムが研究されている。この連載記事では比較的単純な「Eadesのばねモデル」というアルゴリズムを採用する。

Eadesのばねモデルとは、次のようなモデルをつくって物理シミュレーションすることで、物体を配置するアルゴリズムだ。

  • 各ノード(頂点)は、質点、つまり質量はあるけれども体積が0の理想物体と仮定する。
  • エッジ(頂点と頂点をつなぐ線)は、ある長さのばねでできていると仮定する。ばねは元の長さより長いと縮もうとするし、元の長さより短いと伸びようとする。
  • ノード同士には反発力が働く。反発力は磁石のN極とN極みたいに、遠ければ遠いほど力が弱まる。

……ここであらかじめネタばらししておくと、Eadesのばねモデルでは、上の図のような配置を得ることはできない。線が重ならないように配置させるにはもっと複雑なモデルを使わないといけない。ではどのようなモデルならいいのか?その答えはこの記事の範囲を超えるので、興味を持った人が各自で調べてほしい。ごめんなさい。

とりあえず、この連載記事のゴールは「Eadesのばねモデルを実装して動かしてみる」に設定する。では早速コードを書いていこう。

グラフ構造

まずは、ノードとエッジのデータ構造を考える。実現方法はいろいろあるが、今回は単純に、ノードを表現するクラスを作り、隣り合うノードへの参照も持たせることにしよう。

グラフ全体を表現するクラスには、初期化のためのメソッドを用意しておこう。

thisを返していたり、セパレータが','固定だったりと、強引なコードなので決してお勧めはできないが、面倒な初期化コードが短くなるので嬉しい。

物理シミュレーション: 運動方程式とオイラー法

グラフ構造の次は、物理シミュレーションの準備をしよう。シミュレーションでは、座標 (x, y)、速度 (vx, vy)、加速度 (ax, ay)、力 (fx, fy)という、2次元の値を使用する。よって専用の型を定義しておく。今回は構造体で定義したが、クラスでもかまわない。

この型を使って、ノードにプロパティを追加する。座標R と、速度Vだ。

ところで、このノードの動きをシミュレートするにはどうすればいいのだろうか。そう、物理(力学)の法則、ニュートンの運動方程式だ。中学の理科では「力=重さ×加速度」と習ったと思う。

ところで、加速度aというのは速度vの微分(≒時間変化量)だし、速度vというのは位置rの微分(≒時間変化量)なので、運動方程式を位置rを使って書き直すと、位置rを2回微分したものが式の中に出てくる。

物体の位置を正しく求めるためには、力Fを2回積分しないといけない。これは非常に面倒くさいので、積分をしないで近似値を求めることにする。近似値の求め方もいろいろあるのだが、今回はオイラー法と呼ばれる方法を使う。

オイラー法は、時間の流れを短い間隔Δtで区切ったときの、ある瞬間の値とその次の瞬間の値の差を単純な近似値で求める方法だ。速度の差分は加速度×Δt、位置の差分は速度×Δtで近似する。精度の高い近似とはいえないのだが、今回は精度の高いシミュレーションをする必要がないので、単純なオイラー法を選択した。

オイラー法をコードに落とすとこんなイメージになる。ちなみに、面倒なのでノードの質量を全部1だと決めた。欲しいのは厳密なシミュレーションではないので、縮尺とか比率に関係するところは適当に決めてしまってよい。

引数は2つある。最初の引数dtは定数だ。この値が小さいほど、オイラー法の誤差が小さくなる。今回はdt = 0.1dとする。

もうひとつの引数fが、このノードにかかる力だ。では、この力を計算しよう。

ノードにかかる力: ばねの弾性力

ノードとノードをつなぐエッジがばねでできているので、あるノードがばねから受ける力を考える。

こんな感じで、ノード間の距離をd、ばねの自然長をlとしたとき、右上のノードがばねから受ける力F

で表される。ちなみに、定数kはばねの強さを表す比例定数だ。

コードを書くときは、kやlの値は好きに決めていい。後から修正して変えてしまってもかまわない。

途中に不思議なコードが入っているのは、ノード間の距離が0のときの対策だ。現実世界の物体だとありえないが、このシミュレーションでは起こりえる。そうすると角度θが計算できなくなってしまう。なので、乱数を使ってランダムな方向に力を向けているのだ。ちょっと強引だが気にしない。

ノードにかかる力: ノードの反発力

ノード同士の反発力は、ばねでつながっているかどうかに関係なく、すべてのノード間で働く。

反発力は、電磁力や重力を参考に、逆2乗の法則に従うことにする。つまり、力Fの大きさが距離dの2乗に反比例するものとする。

ちなみに、定数gは反発力の強さを表す比例定数だが、ばねのときと同じように、好きな値に決めていい。

さっきと同じで、距離0のときはランダムに力を向けている。今回は、距離0のときに力の向きが決まらないだけでなく、力の大きさが無限大になってしまう。

ノードにかかる力: 摩擦力

さて、Eadesのばねモデルはこれで完璧のような気がするが、ここで終わりにすると想定外の結果になる。いつまでたってもノードが動き続けていて止まらないのだ。やりたかったことは自動レイアウトなのだから、いつまでも動き続けているのは具合が悪い。

ではどうすればいいかというと、摩擦力を加えるとよい。要するに、速度がだんだん小さくなっていくような仕掛けが必要なのだ。

今回のモデルでは空気抵抗を参考にしよう。力が速度と逆向きに加わることにする。

Fの大きさは速度vの大きさに比例する。

摩擦力でも、比例定数μは好きな値にしてよい。なお、ソースコード上はμという記号の変わりにアルファベットmを用いた。

第1回のまとめ

最後に、ここまでをまとめよう。すべてのノードについて、各ノードにかかる力を足し合わせてオイラー法を適用するのだ。そのようなメソッドはNodeCollectionに定義する。

さて、Eadesのばねモデルをオイラー法を使って実装するところまで説明した。かなり長くなってしまったので、今回はここまでとする。

今回のソースコードはGitHubに置いてある。まとめてダウンロードしたい人はここからダウンロードできる。

次回はWindows Formを使って今回のモデルをアニメーション表示してみたいと思う。


グラフの自動レイアウトに挑戦 インデックスへ戻る


Last Update: 2012-07-17 19:42:39