matarillo.com

The best days are ahead of us.

グラフの自動レイアウトに挑戦

2022-08-12 13:37:22

追記 (2022/8)

もともとは、Windowsアプリケーション(.NET Windows Formsアプリケーション) として実装していましたが、再公開を機にJavaScriptに移行しました。

きっかけ

Nintendo DSのパズルゲーム「レイトン教授と最後の時間旅行」で出題された問題に、複雑に絡まったトンネルが出てくる。

複雑に絡まったトンネルの図

これを解くときに、道が絡まったままだと頭がこんがらがるので、交点に番号を振り、

交点に番号を振った図

位置を入れ替えて見やすくした。

道が交差しないように並び替えた図

これをコンピュータにやらせたら面白いのでは?というのがこの連載記事のきっかけだ。

目次

#1 グラフ構造をSVGで表示
ノード(節点)とエッジ(線)のデータをSVGで表示する。
#2 ばねモデル
Eadesのばねモデルをオイラー法を使って実装し、アニメーションさせる。
#3 ノードをドラッグできるようにする
ばねモデルではエッジの交差を無くせなかったので、ノードの位置を自由に変更できるようにする。