グラフ描画入門

グラフ理論の記号適切なグラフ描画関数の選択
入力書式参考文献
グラフ描画アルゴリズム
Wolfram言語は，グラフを美的に描画するための関数を提供している．実装されているアルゴリズムには，バネ埋込み法，バネ電気埋込み法，高次元埋込み法，放射状 描画法，ランダム埋込み法，円形埋込み法，らせん埋込み法等がある．これらに加え，有向グラフの階層描画法や木の描画も可能である ．これらのアルゴリズムはGraphPlot，GraphPlot3D，LayeredGraphPlot，TreePlotの4つの関数を通して実装されている．
GraphPlot
グラフのプロットを生成する
GraphPlot3D
グラフの3Dプロットを生成する
LayeredGraphPlot
グラフの階層的プロットを生成する
TreePlot
グラフの木を生成する
グラフ描画の関数
GraphPlotおよびGraphPlot3Dは，一般的なグラフの直線の描画に適している．LayeredGraphPlotはグラフの頂点を何層もの階層で描画しようとする．このため，フローチャートの描画のようなアプリケーションに適している．TreePlotは木構造のグラフの描画に特に有効である．これらの関数は，非常に大きいグラフに効率的に使えるよう設計されている．
次は，この4つの関数を使ったグラフ描画の例である：
このような関数では，グラフは{vi1->vj1,…}の形式の規則のリスト（ここで，vi1と vj1は頂点），あるいはグラフの隣接行列で表される． これらの関数は，非常に大きなグラフで効率的に動くようにデザインされている．
グラフ理論の記号
グラフ は一組の頂点 （ノードとも呼ばれる）と辺 からなっている． であれば，この2つの頂点 と で グラフの辺が形成される．
もし が を暗示するのであれば， は無向グラフである．さもなけれは有向グラフである． 前者は線分を用いて描くこと ができ，後者は矢印を用いて 描くことができる．無向グラフの場合は，辺が と の間に存在するということ を表すのに を使うと便利なことが多い ．
例えば，次は有向グラフの例である：
これは，無向グラフである：
入力書式
Wolfram言語では，グラフは次の3つのデータ構造のいずれかで表すことができる．グラフは規則のリストで表すことができる．
例えば，は次の有向グラフを表す：
グラフは隣接行列で表すこともできる．が有向グラフであるとしよう．頂点がから までの指標，すなわち であると仮定すると， の隣接行列は × 行列になる． のとき，項目 であり，その他の場合は である．
次の隣接行列は同じ有向グラフを表している：
無向グラフは対称隣接行列で表される． の場合は行列の項目 であり，その他の場合は である．例えば，次の隣接行列は，それに続く無向グラフを表す．
次の隣接行列は，それに続く無向グラフを表す：
隣接行列中に零の項目があるので，SparseArrayを使って表すのが便利なことが多い．
先の行列は次の疎行列として書くことができる：
グラフ描画アルゴリズム
グラフはしばしば，ものとものとの関係を囲い込むために用いられる．グラフを描画することでこの関係を可視化することができる．可視化したものの有用性は，描画が審美的かどうかによる．審美的描画に関する厳密な基準はないが，そのような描画は，例えば辺の交差が最小で，頂点が等間隔に描かれているものであるということで誰もが一致する．この問題は広範に研究されており[1]，多くのアプローチが提唱されている．一般的なストレートエッジ描画アルゴリズムであるバネ埋込み法とバネ電気埋込み法の2つは，グラフの物理モデルのエネルギーを最小にすることで働く． 一方，高次元埋込み法はグラフを高次元空間に埋め込んでから，2Dあるいは3D空間に投影し返す．加えて，有向グラフを階層的に描画するためのアルゴリズムや木の描画のためのアルゴリズムもある．ランダム埋込み法，円形埋込み法，らせん埋込み法は，グラフのレイアウトのための接続性情報を利用しないので，この後は言及しない．

バネ埋込み法

バネ埋込み法は，任意のノートペアの間に力を割り当てる．2つのノードが互いに近すぎる場合，反発しあう力が生じる．2つのノードが互いに遠すぎる場合には，引き合う力が生じる．この状況を図解する方法のひとつが，頂点間をバネでつなぐことであり，よってこれに「バネ埋込み法」の名前が与えられている．
バネモデルは，すべての辺にバネを加え，隣接していない全頂点ペアに弱めのバネを加えることで作用する．システム全体のエネルギーは2Dでは次のようになる．
ここで， と はノード とノード の座標ベクトル，は両者の間のユークリッド距離， は頂点 と の間のバネの自然長で， と の間のグラフ距離として選ぶこともできるものである．パラメータ はバネの強度である．ここで， はバネの強度を表すパラメータである．は頂点の数である．
グラフの頂点のレイアウトはこのエネルギー関数を最小にすることで計算される．エネルギー関数を最小にする方法のひとつは，バネの力の方向に沿っておおよその平衡が取れるまで各頂点を反復的に動かすことである．極小値の問題を解決するためにはマルチレベルの技法が使われる．
バネ埋込み法は，通常のグリッドグラフのような問題に特に効果がある．このような問題では頂点間のユークリッド距離とグラフ上の距離を比例させることが可能だからである．
バネ埋込み法を使って20×20の格子グラフを描画する：
しかし，このような方法にはより多くのメモリとCPU時間がかかる．の複雑さを軽減するために，力とエネルギーの計算の際，遠すぎる頂点は実際には無視する．詳細は，GraphPlotおよびGraphPlot3Dのメソッドオプション"InferentialDistance"を参照のこと．

バネ電気埋込み法

バネ埋込み法の欠点は，任意の2つの頂点間のグラフ距離を知る必要がある点である．バネ電気埋込み法は2つの力を使う．引力の は隣接する頂点に限られ，頂点間のユークリッド距離に比例する．ここで はバネの自然長である．電気の力の は大域的力で， と の間のユークリッド距離に反比例する．全体として，最小化されるべきエネルギーはである．ここでは以下が成り立つ．
ここで， は引力と反発力の相対的な強さを規制する定数である．はノード とノード の間のユークリッド距離である．頂点が2つのグラフでは，ゼロエネルギーを与える両者の理想的なユークリッド距離は である．
グラフの頂点のレイアウトはエネルギー関数を最小にすることで計算できる．ひとつの方法として，各頂点をバネの力の方向に沿ってほぼ均衡に達するまで繰返し移動することが考えられる．極小値の問題を解決するためにはマルチレベルの技法[7]が使われ，時として計算の複雑性を軽減するために8進木データ構造[16]が使われる．
バネ電気埋込み法は一般にほとんどの問題に使える．マルチレベルのテクニックおよびOCTREEテクニックを使えば程度の複雑なものに対しても非常に効果的に実装することができる．
"SpringElectricalEmbedding"を使って20×20の格子グラフを描画する：
このアルゴリズムの副作用は，周辺上の頂点の方が中心の頂点よりも互いに近づく傾向があるという点である．この傾向は，「一般的なグラフの描画」で説明されているメソッドオプション"RepulsiveForcePower"で軽減することができる．

高次元埋込み法

高次元埋込み法では，グラフが高次元空間に埋め込まれ，そこから2Dないし3D空間に投影し直される．まず 個の「中心」から 次元の「座標系」が作られる． 中心は，互いに可能な限り離れている 個の頂点の頂点集合である．最初の頂点がランダムに選ばれる．続いて残っている各中心が，直前に選ばれた中心から最も遠い頂点として選ばれる．つまり， 個の中心が選ばれたなら， 個の中心への最短グラフ距離が他のすべての頂点から 個の中心までの距離よりも長いかあるいは等しい頂点は 個になる．
これらの 個の中心で， 次元座標系が構築できる．各頂点 は座標 を持つ．ここで， は頂点 と中心 のグラフ距離である． 次元の座標ベクトルは × 行列 を形成する．ここで， は の 番目の行である．
二次元ないし三次元でしか描けないので，また，座標が相関しているので， 次元座標は適切な一時結合によって二次元または三次元に投影し直される．ここで 個の座標と 個の中心を持つグラフが再び二次元で投影されるとすると，この投影をシフト不変にするために， はまず に正規化される．
と がそのような 次元ベクトルであるとする．この2つのベクトルは無相関であり，互いに直交でなければならない．
また，それぞれが0から可能な限り離れていなければならない．
このために， と を × の対称行列 の2つの最大固有値に対応する固有ベクトルとする．このようにほとんど相関関係のない2つのベクトルを選ぶプロセスは，主成分分析としても知られるものである．
グラフを二次元で描画するために，高次元埋込み法では と で与える頂点座標が使われる．
"HighDimensionalEmbedding"を使った20×20格子グラフの描画である：
高次元埋込み法は非常に速い傾向があるが，力指向アルゴリズムよりも質が劣ることがよくある．このメソッドはGraphPlotおよびGraphPlot3DのMethod->"HighDimensionalEmbedding"で指定することができる．

有向グラフを描くための階層的描画アルゴリズム

DAG（有向非巡回グラフ）を描画するためのアルゴリズムは，杉山等によるアルゴリズム[14]とそれを発展したもの[15]に従っている．これは，下記のような段階からなっている．

1.  DAGの頂点は， から への辺がある場合は となるように，まず予備的に ランクが与えられる．これは，最終的な画像における有向の辺のほとんどが下を向くようにするためである．

2.   座標は，から への辺があり，である場合， 座標がなるべく近くなるようにするが，最小値のセットによって分離されるように生成される．これは，最終結果の描画に多くの長い辺が含まれないようにするためである．このプロセスにより，頂点が有限個の層に振り分けられる．辺が数層に渡る場合，仮想頂点が加えられる．

3.  辺の交差を最小にするために，予備的な ランクが各頂点に割り当てられる．

4.   座標は，同じ層の頂点はステップ3で生成された ランクに従い，最小値のセットで分離されるという制約条件に従って，を最小化することで生成される．

結果の描画は階層的な構造でグラフをレイアウトする．このグラフではほとんどの辺が下を向いている． LayeredGraphPlot関数がこのアルゴリズムを実装している．

木描画のアルゴリズム

木を描画するための2つのアルゴリズムは，放射状描画法と階層描画法[1]である．放射状描画法では，まず適当な木の根が選ばれる．続いて，木の根から始めて各楔形の内側に部分木が描画される．楔形の角度は部分木の葉の数に比例する．階層描画法でも，まず適当な木の根が選ばれる．次に，その根から始めて，同レベルの頂点が同じ 座標を持ち，各部分木が等間隔になるようにして，1つの根から出る部分木が再帰的に描画される．根は部分木の 座標の中心で 座標は1単位上に置かれる．TreePlot関数はその第2引数により，これらの2つのアルゴリズムのいずれかを選ぶ．
適切なグラフ描画関数の選択
一般的なグラフの描画では，GraphPlotかGraphPlot3Dを使うとよい．GraphPlotおよびGraphPlot3Dは視覚的に好ましい2D/3Dのレイアウトとこのレイアウトのグラフのプロットを計算する．これらの関数については「一般的なグラフの描画」を，アルゴリズムの詳細については[17]を参照されたい．
有向グラフの層／階層の描画にはLayeredGraphPlotを使う．LayeredGraphPlotはグラフの頂点を，主頂点を最上層とする階層的な一連の層で描画しようとする．この関数はフローチャートの描画等に最適である．この関数の詳細は「有向グラフの階層的な描画」を参照されたい．
TreePlotは，木および木状のグラフの描画のために特に設計されたものである．この関数の詳細は「木の描画」を参照されたい．
参考文献

[1] Di Battista, G., P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.

[2] Fruchterman, T. M. J. and E. M. Reingold. "Graph Drawing by Force-Directed Placement." Software—Practice and Experience 21, no. 11 (1991): 1129–1164.

[3] Eades, P. "A Heuristic for Graph Drawing." Congressus Numerantium 42 (1984): 149–160.

[4] Quinn, N. and M. Breuer. "A Force Directed Component Placement Procedure for Printed Circuit Boards." IEEE Trans. on Circuits and Systems 26, no. 6 (1979): 377–388.

[5] Kamada, T. and S. Kawai. "An Algorithm for Drawing General Undirected Graphs." Information Processing Letters 31 (1989): 7–15.

[6] Harel, D. and Y. Koren. "Graph Drawing by High-Dimensional Embedding." In Proceedings of 10th Int. Symp. Graph Drawing (GD'02), 207–219, 2002.

[7] Walshaw, C. "A Multilevel Algorithm for Force-Directed Graph-Drawing." J. Graph Algorithms Appl. 7, no. 3 (2003): 253–285.

[8] Cuthill, E. and J. McKee. "Reducing the Bandwidth of Sparse Symmetric Matrices." In Proceedings, 24th National Conference of ACM, 157–172, 1969.

[9] Lim, A., B. Rodrigues, and F. Xiao. "A Centroid-Based Approach to Solve the Bandwidth Minimization Problem." In Proceedings of the 37th Annual Hawaii International Conference on System Sciences (HICSS'04), 30075.1, 2004.

[10] Barnard, S. T., A. Pothen, and H. D. Simon. "A Spectral Algorithm for Envelope Reduction of Sparse Matrices." Journal of Numerical Linear Algebra with Applications 2, no. 4 (1995): 317–334.

[11] Sloan, S. "A Fortran Program for Profile and Wavefront Reduction." International Journal for Numerical Methods in Engineering 28, no. 11 (1989): 2651–2679.

[12] Reid, J. K. and J. A. Scott. "Ordering Symmetric Sparse Matrices for Small Profile and Wavefront." International Journal for Numerical Methods in Engineering 45, no. 12 (1999): 1737–1755.

[13] George, J. A. "Computer Implementation of the Finite-Element Method." Report STAN CS-71-208, PhD Thesis, Department of Computer Science, Stanford University, Stanford, California, 1971.

[14] Sugiyama, K., S. Tagawa, and M. Toda. "Methods for Visual Understanding of Hierarchical Systems." IEEE Trans. Syst. Man, Cybern. 11, no. 2 (1981): 109–125.

[15] Gansner, E. R., E. Koutsofios, S. C. North, and K. P. Vo. "A Technique for Drawing Directed Graphs." IEEE Trans. Software Engineering 19, no. 3 (1993): 214–230.

[16] Quigley, A. "Large Scale Relational Information Visualization, Clustering, and Abstraction." PhD Thesis, Department of Computer Science and Software Engineering, University of Newcastle, Australia, 2001.

[17] Hu, Y. F. "Efficient, High-Quality Force-Directed Graph Drawing." The Mathematica Journal 10, no. 1 (2006): 37–71.