contentグラフ描画アルゴリズムとNetworkxの裏側Pythonアルゴリズムnetworkx0.グラフの描画ってどうやるの?二次元に描画するためには各頂点に適切に座標を与える必要がありますが、グラフは頂点と辺の情報しか持っていません。networkxというライブラリで簡単に使用できます。実装を追いながら仕組みを確認していきます。この記事の流れはこうです。実装を追う1.動かしてみる動けば満足な方のために先に実装例を示しときます。networkxがインストールされてるので、コピペですぐ試せます。node_shape='.')plt.axis("off")plt.show()うわぁ...。ランダムな配置では見るに堪えませんね。node_shape='.')plt.axis("off")plt.show()いい感じに配置されてますね。「いい感じの配置」ってなに?もう少し厳密に「よい配置」を考えます。今、グラフ$G$の情報を以下のように持っているとします。E)$$V$:頂点集合$E$:辺集合このグラフを二次元に配置する方法は無数にあります。(先ほどのようにランダムに配置してもいいわけです。)しかしできることなら見やすく配置したいです。以下の条件を満たす配置を「よい配置」としましょう。1辺の接続関係が距離に反映されているつまり辺で接続された点どうしは近くに配置して、辺で接続されていない点どうしは遠くに配置するようにします。隣接行列だと、接続されていない部分はinfにしたりするので、辺の有無に関係なくすべての点を同様に扱えそうです。➁頂点が重ならない頂点どうしが重なっていては、辺も見れないので困りますね。以上二つの条件を満たすようなグラフ配置を求めたいです。それを実現するのが、力学モデル(力指向グラフ)です。今回はこれを紹介します。この手法のイメージをつかむために以下のgifを見てください。ランダムな初期配置から、だんだんきれいになっていく!!(こちらから借りました)アルゴリズムを知りたくなってきましたか?(y/n)y知りましょう。力学モデルでは、頂点に力を加えて移動させていきます。Force)が出てきます。引力は辺で接続されている頂点どうしに働きます。斥力は辺で接続されていない頂点どうしに働きます。これは先ほどの条件1「辺の接続関係が距離に反映されている」に対応しています。力はどのように定義してもいいのですが、とりあえず論文で提案されている定義を使ってみましょう。\text{area}$は描画する画面の面積ばねの式みたいで直観的ですね。力と距離の関係のグラフは以下です。グラフと式から以下のことがわかります。適切な大きさにすれば、先ほどの条件➁「頂点が重ならない」を満たすことができます。アルゴリズムさてアルゴリズムを見てみましょう。力に従って頂点を移動。枠の外に出ないようにする。頂点の移動量を制限するパラメータです。以下になるようにします。t)$この温度$t$を適切に小さくしていきます。するとはじめは移動量が大きいものの、終盤はあまり移動しないようになります。(収束性を保証)あと論文ではステップ3では画面内に配置するために壁との衝突を弾性反射として扱ったりしています。placement"を読んでください。(networkxの実装では考慮していません...)ここまででアルゴリズムがわかったので、実装してみます。めんどくさくなったので実装は読者に委ねます。実装方法を見ていきます。実装を見てみる人の実装を見て学ぼう。当時のもので、例外処理など説明しない部分は省略しました。networkx.spring_layout()を使用して「いい感じ」にグラフを描画しました。今度は参照先であるfruchterman_reingold_layoutを見てみます。postry-except部分では、グラフの大きさによって呼び出す関数を分けています。(if文じゃダメなんですかね...?教えてください。solverを使っているみたいです。ここまで見てもアルゴリズムの部分にたどり着けてないので、_fruchterman_reingold()を見てみましょう。posここがアルゴリズムの実装部分ですね。引力や斥力をどう扱っているのかまとめてみます。最初は大きく下げるように、iterationが進むにつれて少しづつ下げるようになってます。厳密には方向ベクトルではないですが、最終的にはノルムを調整してるのでそう書きました。気になるのは力の定義です。引力も斥力も論文のものとは違います。論文が1991年のものなので、その後改良版が出たりしてるんですかね。他の知見として重み付きのグラフの場合、斥力に隣接行列の値をかければ良いことも分かりました。自分で実装してみる際は、同様の設定で実装すると良いと思います。おまけソースコードを少しいじって、アルゴリズムの動きを可視化してみました。(パラメータをいじって200回のイテレーションにしました。)バラバラの点のかたまりが徐々にヒモのようになっていくのが興味深いですね。自分でほとんど実装せずに、参考にしたサイト「グラフ(ネットワーク)を奇麗に描画するアルゴリズム」と近いものが得られました。