読者です 読者をやめる 読者になる 読者になる

有向グラフの簡潔表現GLOUDS

ネタ元

Johannes Fischer, Daniel Peters: GLOUDS: Representing tree-like graphs. J. Discrete Algorithms 36: 39-49 (2016)

概要

  • 木の簡潔データ構造LOUDSを拡張した有向グラフの簡潔データ構造GLOUDSを提案する
  • in-edgeが2以上のノードをコピーして、グラフを木に変換しLOUDSに似たデータ構造で表現する
  • in-edgeの数が少ない、つまり木に近い有向グラフの場合効果を発揮する

LOUDS

木のビット表現。LOUDSの話は今までにも聞いたことがあるが、この論文の説明が一番わかり易い。

  • 各ノードを1*子の数+0で表現する(0が親、1が子ノードを表すと考えると分かりやすい)
  • level-order(深さ毎)にノードの01表現を連結する
  • level iでk番目に出現する1で表された子ノードは、level i+1でk番目に出現する0で表された親ノードに対応する
  • この性質から、親から子、子から親へ01表現のrank, selectで辿ることが出来る

GLOUDS

次のような方法で有向グラフから木を作る。

  • あるノードから有向辺で全てのノードに辿れるようなノードをrootと呼ぶ
  • 複数あり得るが、簡単のためrootが一つだけあると仮定する
  • rootノードからlevel orderで各ノードuを辿る
  • uの各子供vについて、vがまだ辿られていないノードだったら枝を貼る
  • vが既に辿られているノードだったらvをコピーしたshadowノードを作り、そのノードに枝を貼る

次にこの木を簡潔データ構造で表すにはどうすればよいかを考える。

  • vがまだ辿られていないノードであればvを1で表す
  • vがすでに辿られているノードであればvを2で表す
  • 親ノードuを0で表す

これで木を表すことが出来たが、これだけでは元の有向グラフで出来た操作が行えない。 以下の情報を付け加え、操作可能にする。

  • 有向グラフ上のノードは、変換した木上でshadowノードとそうでないノード(1ノードと呼ぶことにする)で表される
  • 1ノードは有向グラフ上のノードが表す子の情報全てと親の情報を1つ持っている。
  • shadowノードは親の情報を1つ持っている。
  • つまり、子を辿るためには、全てのshadowノードから対応する1ノードに、
  • 親をたどるためには全てのノードからそれ以外のノードへと遷移することが出来ればよい
  • 対応関係を整数文字列で表し、整数文字列上のrank, selectで実現する
  • level-orderで木を辿りshadowノードを、対応する1ノードのrank(何番目に出現したか)で表すことで木のshadowノードの出現を整数文字列Hとして持つ
  • H[i]=xはlevel-orderでi番目のshadowノードに対応する1ノードがlevel-orderでx番目に出現することを表す
  • 対応するノード間はこの文字列Hを経由し、木のrank, select、Hのrank, selectで対応するノード間を辿ることが出来る

その他

以下は今後覚えておくと良さそうなのでメモ

  • ビット配列上のrank, selectはn+o(1)bitsでO(1)時間で実行可能
  • rank, selectは文字列上にも拡張できる。
  • よく知られている方法だとn log σ(1 + o(1)) bitsでrankがO(log log σ)時間、selectがO(1)時間で実行可能、ここでσは文字種類数
  • 当たり前だが文字列を陽に持っていればn log σ bitsで各位置の文字にO(1)時間でアクセスできる
  • σ=wO(1)の時上記の3つの操作はより高速に実行可能、ここでwはワード長
  • この場合O(n log σ) bitsで上記3つの処理がO(1)時間で実行可能