力学モデル

力学モデルによるグラフ描画（力指向アルゴリズム）は、グラフ理論|グラフを美しく描画するためのアルゴリズムの一つである。 このアルゴリズムは、グラフのノードを2次元空間や3次元空間に配置して、辺の長さをほぼ等しい長さにし、グラフの辺ができるだけ交差しないようにすることを目的にしている。このアルゴリズムでは、グラフの頂点と辺に仮想的な力を割り当て、力学的エネルギーの低い安定状態を探すことで、この目的を達成している。もっとも直截的なモデルでは、それぞれの辺をフックの法則にしたがうばねとみなし、それぞれの頂点をクーロンの法則にしたがう電荷をもつ粒子とみなす。 そして、その力学系の挙動をシミュレートし、弾性力や静電気力が粒子を近づけたり遠ざけたりするようすを計算する。粒子が安定な配置になり、位置が変化しなくなるまで、力の計算と粒子の移動を繰り返す。その時点で、グラフのレイアウトが完了し、描画される。この平衡状態は、すべての力が釣り合った状態に相当する。