グラフレイアウト

数多くの要素について、要素をノードで、要素間の関係をエッジで表したものをグラフという。
グラフはこの定義からもわかるように、図示することが本質ではない。
本質ではないけれども、図示することで、「全体が持つ情報を的確に捕らえる」ことの手助けができることがある。
その「図示」は、『グラフレイアウト』と呼ばれる。
こちらのPDFによくまとまっている。ちなみに、このPDFシリーズの前後の章は"http://cgi.members.interq.or.jp/pacific/moto/shuron/Master_Thesis_k.pdf" のkに1,2,3,...を入れれば表示される。
先日も紹介した、VGJでは、Springという図示方法が選べるようになっているが、それは、Kamada and Kawai's spring algorithmと呼ばれるもので、すべてのノード間に、グラフ上の最短パスによって決まるようなバネが存在して、引き合っているような状態を想定し、ノード全体が持つエネルギーが最小になるようにしたもの。