今回は、グラフのレイアウトを自動化するためのアルゴリズムを紹介する。
ここでいうグラフはExcelのグラフ機能のことではなく、数学のグラフ理論の方のグラフ。
知らない方は、以下のような作業工程図をイメージしてもらえば良いかと思う。
マインドマップ等も一種のグラフと見做すことができ、私がグラフの自動レイアウトを知ったのはFrieve Editorというツールがきっかけだ。
www.frieve.com
このグラフ自動レイアウトは5年以上前からずっと気になっていたのだが、当時の私はどうやっても調べることができず断念していた。
ところが先日たまたま気になって検索しなおすと、Wikipediaのページに疑似コードが掲載されていることに気づいた。
ja.wikipedia.org
これだ！と思ったけど私の技術力ではこれをVBAコードに置き換えることはできなかった。
そこでまずは英語版Wikipediaからタイトルの「Force-directed graph drawing」を拾い上げて+言語名でGoogle検索したところ、Python2で書かれたコードを見つけることができた。
Simple force directed graph drawing algorithm · GitHub
実行すると、次のようにランダム配置されたノードが接続関係を保ったまま綺麗にほどかれていく様がアニメーションになっている。
(アルゴリズムの仕様上、初期配置が悪いとたまに絡まったまま完了してしまうことがある。)
そこで、このコードを穴が開くほど読み込んで、なんとかVBAに移植することができた。
実コードは以下のGitHubページのbinフォルダーからxlsmファイルをダウンロードするか、src/Spring.xlsmフォルダーの各ファイルから直接閲覧できる。
github.com
移植したといっても挙動はPython版と異なり、アニメーションはせずに直接格子型のレイアウトがパッと現れておしまい。
これはパフォーマンスを心配してあえてアニメーションさせなかったんだけど、内部の管理座標はランダムで開始されて徐々に本来の座標に移動し、レイアウトが完成したところで描画している。
こればかりはソースコードを読まないと分からず、最初から定義された座標に配置してるんじゃないかと疑われるかもしれないが。
このアルゴリズムの考え方は、ざっくり言えば接続されたノード同士は引き合い接続されていないノード同士は反発しあうというもの。
この法則でノードにかかる力を計算しながら移動していき、全体のつり合いがとれたところで終了すると綺麗に展開されるという手法である。
私が自分で考えを巡らせていた頃は、線の重なりを解析してそれを避ける配置を探すというアルゴリズムなのかなと思っていたので、こういう力学的な解き方があるというのは目から鱗だった。
この反発力は電磁気学からクーロンの法則が用いられ、引張力は力学からフックの法則が用いられる。
電磁気学も力学も、それ自体を目的としてコンピューターシミュレーションが行われるのは普通のことだが、コンピューター上で図形のレイアウトを行う目的で全然違う分野をまぜこぜに使っているのが逆輸入みたいでとても面白いと思う。
ちなみに力学を用いている関係で、初期配置によっては絡まったままつり合いが取れてしまうこともあって、現状100%うまくいくわけではない。まぁそうなってもボタンを押しなおすだけなので人が配置するよりもはるかに楽ではあるが、ユーザー目線だと微妙な印象は与えてしまうかなと思う。
多分これより優れたやり方はあるんだろうけど、自分が使う分には十分に満足できそうなので、今後、先日作成したネットワークダイアグラムの作成ツールに組み込めないか思案中である。
以上
