修行の場

知人が言っていました。これは修行だと。

グラフの基本的なアルゴリズム

## 背景 グラフを扱う場面は多いです。 例えば、道路のネットワークはグラフであるともいえますし、 Webのネットワークは巨大なグラフと言えますし、人と人のつながりもグラフです。 マス目の上でキャラを動かすゲームもグラフ用のアルゴリズムを使ってAIを作ったりできます。 ツリーなどと比べるとMLエンジニアでも直接扱う機会が多いでしょう。

Pythonでグラフを扱えるライブラリ

  • networkx
    • バージョンアップもされている(去年が最新)
    • pure pythonのようです。
  • igraph
    • C言語で書かれたライブラリのpythonラッパーっぽい
  • graph-tool
    • 大半はC++で書かれていて速いとのことです。Boost Graph Libraryを活用しているとのこと。
    • condaパッケージもある。

とりあえず、pure pythonのnetworkxから使ってみることにします。

グラフの表現方法

グラフをメモリ上で表現する方法にはadjacency matrixとadjacency listがあります。 $G=(V, E)$のグラフを表現する場合、adjacency listはO(V+E)個のメモリ領域を占有します。adjacency matrixは$O(V2)$のメモリ領域を占有します。

どちらを選択すべきかは自分が実装したいアルゴリズムとパフォーマンス要件次第のようです。 例えば、2つの頂点が与えられたときに、これら頂点の接続関係を調べたければ、adjacency matrixなら、O(1)です。adjacency listはリストを辿らないと行けないのでその分時間がかかります。(実行時間は不明ですが、頂点数は超えないので最悪でもO(V)なはずです)

satellite dataの格納方法も方法がいくつかありますが、 これはアルゴリズムプログラミング言語に大きく依存することになります。 クラスがサポートされていれば、例えば、ノードクラスにsatellite dataを入れておき、 IDやポインタで位置をadjacency matrix|listのいちを示せば良いです。

頂点やエッジを削除した場合 adjacency listの場合は、すべてをメモリ上から削除するとなると、ポインタ管理している配列の変更と各リスト上の要素削除が必要になります。なので、O(E), O(V)の計算量になりそうです。削除せずに空き状況を管理すると、たどるたびに削除されているされていないの判断が必要になり、ある頂点から接続されている頂点をたどるたびにO(V)程度の計算量になりそうです。 adjacency matrixの場合は、メモリ上から削除は$O(V2)$かかりそうですが、削除フラグだけ立てて空き状況を管理しておけばいいので、O(V)で削除フラグを立てられて、O(V)のメモリ容量になりそうです。 なので、削除はadjancy matrixのほうが楽そうです。

グラフの探索アルゴリズム

breadth first search(BFS)

BFSはbreadth first treeを作れます。 BFTは、rootから任意の頂点までの単純パスが最短距離のパスになっています。

BFSは次に訪れる頂点をFIFOなキューで管理していて、 発見したノードをキューに追加していきます。 頂点sから同じ距離の頂点間の順序は、隣接リストの実装・グラフの構築アルゴリズムの実装などに依存しますが、必ず頂点sから近い頂点の処理が先に終わるという性質は変わりません。

すべての頂点を探索するならば、すべての頂点は一回ずつenqueueとdequeueされます。 また、隣接した頂点を調べるためにすべてのエッジを一回調べるので、adjacency listのリストはすべて一回ずつアクセスされます。なので、計算量はadjacency listの読み込みとキューの読み書きになるので、$(T{qw} + T{qr})V + T_{lr}E = O(V + E)$となります。

depth first search(DFS)

DFSは深さ優先探索で、

  • ソース頂点の隣接頂点のうち、先に探索すると決めた頂点の周囲の頂点がすべて探索済みになったら、他の隣接頂点を探索する。
  • 探索済みとは、隣接した頂点が全て探索中から探索済みであること
  • 探索中とは周囲の隣接頂点を探索している途中の状態

のようなアルゴリズムです。

計算量は$\Theta(V+E)$です。すべての頂点は必ず一回ずつ辿られること、すべてのエッジは必ず一回ずつ検査されるからです。BFSの計算量が$O(V+E)$であるのは、BFSではグラフが分断されていたり、有向グラフでs頂点から辿れない場合は、全ノード、全エッジが辿られないからです。DFSでは全頂点を探索するため表記が$\Theta$となっています。(多分)

DFSの性質は

  • predecessor subgraphがforestであること。ある頂点から辿れる頂点がなくなったとき、グラフ中の他の頂点から次の探索頂点を選ぶ。(=ツリーが複数できる)
  • discovery=(, finish=,)としたときカッコの対応付けがちゃんとなる。ツリーのin-order traverseの性質に近い?

BFSとDFSを隣接行列で実装した場合

BFSはすべてのエッジを最大一回ずつ、DFSはすべてのエッジを一回ずつたどる必要があるため、 BFSは$O(V2)$, DFSは$\Theta(V2)$の計算量になります。

BFSとDFSのユースケース

  • BFS: ある頂点の付近の頂点を探索したい場合
  • DFS: すべての頂点を探索したい場合、何か要素を一つ発見したい場合

from Cracking Coding Interview

要素発見はもっといい方法がありそうですが、汎用的ならDFSでしょう。

例:周囲の頂点探索の実現

BFSベースなら、ある一定の距離以上なら、Enqueueしないようにすれば実装できます。 DFSベースなら、スタート地点をソース頂点のみにし、ある一定以上の距離ならVisitしない。という方法があります。(距離を別途保存する必要あり) BFSベースのほうが楽。ということでしょう。