外平面的グラフの線形時間認識アルゴリズムの実装

外平面的グラフの線形時間認識アルゴリズムの実装

Implementation for Linear-Time Algorithms

of Recognizing Outerplanar Graphs

浮田 誉之

1∗

_{平田 耕一}

2

Yoshiyuki Ukita

1

Kouich Hirata

2

1

_{九州工業大学大学院 情報工学府 先端情報工学専攻}

1

_{Graduate School of Computer Science and Systems Engineering,}

Kyushu Institute of Technology

2

_{九州工業大学大学院 情報工学研究院 知能情報工学研究系}

2

_{Department of Artificial Intelligence, Kyushu Institute of Technology}

Abstract: It is known that the problem of recognizing outerplaner graphs is solvable in linear time. In this paper, we implement two linear-time recognition algorithms, one is designed by Mitchell and another is by Wiegers. Then, we compare the computation time of them, by applying them to NCI datasets consisting of graphs representing chemical compounds.

1

はじめに

外平面的グラフ (outerplanar graph) の認識問題 (recog-nition problem) は線形時間で解けることが知られてい る [5]. 実際, グラフクラスをまとめたページである IS-GCI [4] にも, Mitchell の論文 [5] を参照してそのこと が明記されている.

Mitchell のアルゴリズム [5] は, 辺の縮約に基づいて 極大外平面的グラフ (maximal outerplanar graph) の 線形時間認識アルゴリズムを設計した上で, それを外平 面的グラフの認識アルゴリズムに拡張している. その ため, 与えらえれたグラフを二重連結成分 (biconnected component) に分解し, それぞれの成分に対して認識ア ルゴリズムを適用する必要がある. Hopcroft と Tarjan のアルゴリズム [1,2] を用いることでグラフの二重連結 成分分解も線形時間で求まるため, 結果的に, 外平面的 グラフの認識問題は線形時間で解けることになる. 一方, Wiegers [7] は, Mitchell のアルゴリズムと同様 に辺を縮約しつつ辺のラベル付けを追加することで, 二 重連結成分分解を用いずに外平面的グラフの認識問題を 線形時間で解くアルゴリズムを設計した. この Wiegers のアルゴリズムは, Mitchell のアルゴリズムで用いてい たバケットソートも利用しない単純なアルゴリズムで あるため, 同じ線形時間アルゴリズムであっても, 実際 には非常に効率がよいと考えられる. そこで本論文では, Mitchell のアルゴリズム [5] と ∗_{連絡先： 九州工業大学}        820-8502 福岡県飯塚市川津 680-4        E-mail: y ukita(at)dumbo.ai.kyutech.ac.jp Wiegers のアルゴリズム [7] を実装し, その実計算時間 を比較する. 実計算時間の比較には, 外平面的グラフか らのパターンマイニング [3, 8] で利用されている, 化合 物データベースである NCI データセット [6] を対象と する. 文献 [3] では, その時点での NCI データセットの 94.3%が外平面的グラフであると指摘している. 本論文 では, 最新の NCI データセットにおける外平面的グラ フの割合も併せて報告する.

2

準備

頂点集合 V と, 頂点の組の集合 E ⊆ V × V の組 (V, E) をグラフという. グラフを G = (V, E) とする.E の要素を辺という. 頂点 u, v ∈ V を端点とする辺 e∈E を e = (u, v) とする. v に接している点の集合, すなわ ち_{{u ⊆ V |(u, v) ⊆ E} を v の近傍といい, N(v) で表} す. |N(v)| を v の次数という. 辺で結ばれた頂点の列を 道といい, グラフ G の任意の 2 点 v, u 間に道が存在す るとき, グラフ G は連結であるといい, そうでないとき 非連結であるという. また, グラフ G から頂点 v と v に 接続する辺をすべて取り除く操作を除去という. グラ フ G から次数が 2 以下の頂点 v を除去し, v の次数が 2 の場合は, 2 つの近傍 u, w ∈ V 間に辺がなければ辺 (u, w) を G に追加し, また v の次数が 1 の場合は, v と その近傍 u 間の辺を取り除くような操作を縮小という. 連結なグラフ G から任意の頂点 v を除去しても連結 であるとき, G は二重連結なグラフであるという. 二重 連結でない連結グラフ G から頂点 v を除去すると非連 人工知能学会研究会資料 SIG-FPAI-B801-04

図 1: 外平面的グラフ 図 2: 外平面的でないグラフ 結となるとき, v をカット点という. 同様に, 辺 e を取 り除くことで G が非連結となるとき, e をブリッジと いう. また, 頂点が 3 以上あり, 二重連結で極大な G の 部分グラフをブロックという. ブリッジとブロックを 合わせて二重連結成分という. グラフ G を平面上に辺を交差させることなく描ける とき, G は平面的グラフであるいう. 辺が交差しない ような埋め込みを平面埋め込みという. 平面埋め込み されたグラフを平面グラフといい, 平面グラフの辺で区 切られる領域をそれぞれ面という. グラフの外側にあ る非有界な面を外面といい, グラフ上に１つのみ存在す る. それ以外の面を内面という. 外平面的グラフとは, 全ての頂点が外面と接するよう に平面埋め込みが可能なグラフである. G を外平面的 グラフとする. G の頂点数が n のとき, G の辺数|E| は |E| ≦ 2n − 3 を満たす. G は少なくとも次数 2 以下の 点を２つもち, G から任意の頂点 v または辺 e を除去 して得られるグラフ G′もまた外平面的グラフである. 外平面的グラフを縮小することによって, より小さな外 平面的グラフを得ることができる. また, G の二重連結 成分がすべて外平面的グラフである場合のみ G は外平 面的グラフである.

3

外平面的グラフ認識アルゴリズム

本節では, 入力として頂点が数字でラベル付されたグ ラフ G = (V, E) を与えたとき, G が外平面的グラフで あるか否かを判定する 2 種類のアルゴリズムを紹介す る. どちらのアルゴリズムも頂点の数について線形時 間で動作する. 外平面的グラフの認識において, 次数が 3 以下のグラ フ (ブリッジ, 三角形など) は明らかに外平面的である. また, G の頂点数が|E| ≦ 2n − 3 を満たさない場合や 次数が 2 以下の点が 1 個以下の場合は, アルゴリズムを 動作させるまでもなく G は外平面的でないグラフだと 分かる. したがって, 入力グラフ G は頂点数が 4 以上か つ _{|E| ≦ 2n − 3 を満たすとする.}

3.1

Mitchell のアルゴリズム

Mitchell のアルゴリズム [5] は二重連結グラフのみに 適用可能であるため, Hopcroft, Tarjan の二重連結成分 分解アルゴリズム [2] によってグラフ G を二重連結成 分に分解し, G の各成分それぞれに Mitchell のアルゴ リズムを適用する必要がある. 二重連結成分分解は線 形時間で計算可能である [2]. G の二重連結成分がすべ て外平面的グラフであれば, G は外平面的グラフであ る. 二重連結なグラフは次数が 1 以下の頂点を持たな いため, 縮小の際には次数が 2 の頂点のみを除去する. アルゴリズム 1 は, 二重連結グラフ G = (V, E) と入 力として与えたとき, G が外平面的グラフであるかど うかを出力する. ここで, M は次数が 2 である頂点の リスト, edges, pairs は辺のリストであり, edges には G のすべての辺を格納しておき, pairs は始めは空にし ておく. 辺 e∈ E について, label(e) は e のラベルであ る. G の縮小を (G の頂点数−2) 回繰り返す. 縮小に よって追加した辺が縮小によって取り除かれる場合, そ の辺を edges に追加する. 縮小によって新たに次数が 2 の頂点が現れた場合, その頂点を M に追加する. また, 1 回の縮小を終えるごとにエラーチェックをする. ここ で (M の要素数− ループ回数) が 2 より小さければ, そ こでアルゴリズムは終了となる. G の縮小を終えると 最後に辺が 1 つ残るので, それを edges に加える. 次に, 比較時間を短縮するため, リスト edges と pairs の辺をバケットソートによって辞書順にソートする. バ ケットソートでは, データの取りうる値の分だけバケツ (配列) を用意しておき, データ 1 種類につき 1 つのバ ケツを対応付ける. データ n 個を線形に走査し, それ ぞれ対応するバケツに入れていく. バケツには, 対応す るデータの個数が記録される. データの走査後, バケツ を線形に走査し, 各要素の個数分だけデータを取り出 す. ここでは辞書順にソートするので, バケツは辞書順 に並んでいるものとする. データ数を n, データの取り うる値の最大値を k とすると, バケットソートの計算量 は O(n + k) となる. 頂点数を n とすると, 辺 (u1, u2) の値は (点 u1のラベル× n + 点 u2のラベル) で表せる (u1< u2). n× n 個目までバケツを走査する. アルゴリ ズム 2 はバケットソートのアルゴリズムである. ソー

ト終了後, 2 つのリストを比較し, 同数の pairs の要素 が edges に含まれていれば G は外平面的グラフである. 1 times = 1; 2 while times≤頂点数− 2 do 3 u = M [times]; 4 if 辺(u1, u2)が存在しないthen 5 label((u1, u2)) = ”triangulation”;

6 if label((u, u1)) = ”triangulation” then

7 edgesに辺(u, u1)を追加;

8 if label((u, u2)) = ”triangulation” then

9 edgesに辺(u, u2)を追加; 10 M からuを取り除く; 11 pairsに辺(u1, u2)を追加; 12 if |N(u1)| = 2 then 13 M ⇐ M ∪ {u1}; 14 if |N(u2)| = 2 then 15 M ⇐ M ∪ {u2}; 16 if Mの要素数− times < 2 then 17 Gは外平面的でない; 18 times++; 19 辺が1本残るのでedgesに追加する; 20 pairsとedgesをバケットソートでソートする; 21 /* pairsとedgesを比較*/

22 if edgesにない要素がpairsに出現then 23 Gは外平面的でない; 24 else 25 Gは外平面的グラフである; アルゴリズム 1: Mitchell のアルゴリズム 例 1. 図 3 のようなグラフ G1 を入力とした場合の Mitchell のアルゴリズムの実行例を示す. G1 の頂点 数は 5 なので, 3 回縮小する. リスト M, edges, pairs の初期値は表 1 のようになる. ここで, 図 4, 図 5, 図 6 はそれぞれ縮小の手順を表す. 図 4 では頂点 1 を除去し, その近傍間の辺 (2,5) を pairs に追加する. また辺 (2,5) は G1中にないので新 しく追加する. 図 5 では頂点 2 を除去し, その近傍間の辺 (3,5) を pairs に追加する. 新しく追加した辺 (2,5) が取り除か れたので edges に追加する. また, 頂点 3, 5 の次数が 2 になったので M に追加する. 図 6 では頂点 4 を除去し, その近傍間の辺 (3,5) を pairs に追加する. 最後に残った 1 辺 (3,5) を edges に加える. 作り上げ た edges と pairs をバケットソートでソートする. 入 力 G1に対するリスト edges と pairs は表 2 のように なる. pairs の要素はすべて同じ数 edges に含まれてい るので, G1は外平面的グラフである. 1 n = Gの頂点数; 2 max = n× n; 3 foreach (u1, u2)∈ edges do 4 val = u1のラベル× n + u2のラベル; 5 bucket[val] + +; 6 while i≤ max do 7 while bucket[i] >0 do 8 bucket[i]- -; 9 iに対応する辺を リストEDGESに加える; 10 i++; 11 pairsについても同様の操作をして,リス トP AIRSをつく る; 12 EDGESとP AIRSはソート済み のedges, pairsである; アルゴリズム 2: バケットソート 表 1: G1の初期値 M {1, 2, 4} edges {(1,2), (1,5), (2,3), (3,5), (3,4), (4,5)} pairs ϕ 表 2: 縮小後のリスト edges, pairs edges {(1,2),(1,5),(2,3),(2,5),(3,4),(3,5),(3,5),(4,5)} pairs {(2,5),(3,5),(3,5)} 1 2 3 4 5 図 3: グラフ G1

3.2

Wiegers のアルゴリズム

Wiegers [7] のアルゴリズムは, 辺のラベル付けと縮 小によって外平面的グラフの認識問題を解く. グラフ G = (V, E) を外平面的グラフとする. このとき, e∈ E について, e のラベル colG(e) は cross, out, bridge のい

ずれかとする.

アルゴリズム 3 は, グラフ G = (V, E) を入力として 与えたとき, G が外平面的グラフであるか否かを出力 する. ここで, M は次数が 2 以下である頂点リストで ある. outpla は bool 変数であり, 初期値を true とする.

2 3 5 4 図 4: G1の縮小 (1 回目) 3 4 5 図 5: G1の縮小 (2 回目) 3 5 図 6: G1の縮小 (3 回目) また, すべての辺のラベルを cross と初期化する. この とき, アルゴリズムでは M が空になるまで G を縮小し ていき, 除去する点の次数が 2 のとき, 以下の規則で辺 のラベルを決定する. 除去される頂点を u∈ M, その 近傍を u1, u2∈ V とする. 1. u1, u2間に辺が存在しない場合:

規則 1 : 辺 (u, u1), (u, u2) のラベルがそれぞれ bridge

でなければ, out でラベル付された辺 (u1, u2) を G に追加する. 規則 2 : 辺 (u, u1), (u, u2) のうち, 片方でもラベル が bridge であれば, bridge でラベル付され た辺 (u1, u2) を G に追加する. 2. u1, u2間に辺 (u1, u2) 存在し, 辺 (u, u1), (u, u2) のラベルがそれぞれ cross, out のいずれかであ る場合: 規則 3 : 辺 (u1, u2) のラベルが cross であれば, out に変更する. 規則 4 : 辺 (u1, u2) のラベルが out であれば, bridge に変更する. 3. 上記以外の場合, 縮小は終了する. u の次数が 0 または 1 のときは, ラベルを変更すること なく u を G から除去する. 縮小によって新たに次数が 2 以下の頂点が現れた場合, その頂点を M に追加する. 縮小終了後, G の辺がすべて取り除かれていれば G は 外平面的グラフである.   1 outpla⇐ true;

2 while u∈ M かつoutpla = true do

3 Mからuを取り除く; 4 switch|N(u)| do 5 case 0 do 6 case 1 do 7 辺(u, u1)を取り除く; 8 if |N(u1)| = 2 then 9 M⇐ M ∪ {u1}; 10 case 2 do

11 col1⇐ colG((u, u1)), col2⇐

colG((u, u2)); 12 辺(u, u1), (u, u2)を取り除く; 13 if 辺(u1, u2)が存在then 14 if |N(u1)| = 2 then 15 M⇐ M ∪ {u1}; 16 if |N(u2)| = 2 then 17 M⇐ M ∪ {u2};

18 if col1, col2∈ {cross, out} then

19 switch colG((u1, u2)) do

20 case cross do

21 colG((u1, u2))⇐ out;

22 case out do 23 colG((u1, u2))⇐ bridge; 24 case bridge do 25 outpla⇐ false; 26 else 27 outpla⇐ false; 28 else 29 辺(u1, u2)を追加;

30 if col1, col2∈ {cross, out} then

31 colG((u1, u2))⇐ out;

32 else

33 colG((u1, u2))⇐ bridge;

アルゴリズム 3: Wiegers のアルゴリズム 例 2. 図 7 のようなグラフ G2 を入力とした場合の Wiegers のアルゴリズムの実行例を示す. すべての辺 のラベルを cross で初期化する. また, M ={1, 2, 4} と なる. 図 8, 図 9, 図 10 はそれぞれ縮小の手順を表す. 図 8 では頂点 1 を除去し, その近傍間の辺 (2,5) が G2 中に存在しないので新たに追加する. 辺 (1,2), (1,5) の ラベルが cross なので規則 1 より, 辺 (2,5) のラベルは out となる. 図 9 では頂点 2 を除去し, その近傍間の辺 (3,5) のラ ベルが corss, 辺 (2,3) のラベルが cross, 辺 (2,5) のラ

ベルが out なので規則 3 より, 辺 (3,5) のラベルは out となる. ここで, 頂点 3, 5 の次数が 2 になったので M に追加する. 図 10 では頂点 4 を除去し, その近傍間の辺 (3,5) のラ ベルが out, 辺 (3,4) のラベルが cross, 辺 (4,5) のラベル が cross なので規則 4 より, 辺 (3,5) のラベルは bridge となる. 次数が 1 以下の頂点はそのまま除去できるので, 頂点 3, 頂点 5 を除去し, 縮小は終了する. このとき, G2から 辺がなくなっているので, G2は外平面的グラフである.

4

実験

ここでは, 3 節で紹介した二種類の外平面的グラフ認 識アルゴリズムを実装し, 実データに適用する. 実験用 のデータとして用いる NCI データセット [6] には様々 な化合物のデータがテキスト形式で記載されている. 表 3 は, NCI データから生成されたグラフデータご との全グラフ数, グラフの平均頂点数 (nave), 外平面的 グラフの割合である. 表 3 より, 最新の NCI データに ついても 90%以上が外平面的であることが確認できる. 表 4 は, 表 3 のデータに Mitchell のアルゴリズムと Wiegers のアルゴリズムを適用した場合の計算時間で ある. 表 4 より, データセット全体について, Mitchell のアルゴリズムは Wiegers のおよそ 2 倍の計算時間を 要していることが分かる. この理由として, Mitchell の アルゴリズムで用いているバケットソートによる比較 に時間がかかっていることが考えられる. 次に, グラフ数が与える影響を取り除くため, 各デー タセットの中で頂点数が大きいグラフを順に 20000 個 抽出し, それらに対してアルゴリズムを適用する. 表 5 は平均頂点数 (nave), 平均辺数 (eave), 平均二重連結成 分数 (bave) であり, 表 6 はアルゴリズムを適用した場 合の計算時間である. 表 5 と表 6 より, Mitchell のアルゴリズムは Wiegers のアルゴリズムに比べて平均頂点数の増加に対する計 算時間の増加の割合が小さいことが分かる. この理由 として 頂点数が少ない場合でもバケットソートで使用 する配列をある程度用意する必要があり, 平均頂点数が 少ないデータであるほど実行時間の比 (W/M) が大き くなるためである. 平均辺数, 平均二重連結成分数につ いても同様である. また, 平均頂点数におよそ 2 倍の差があるデータ NCI 0DA99 と NCI Open 0903 について, Mitchell のアル ゴリズムの計算時間が 2 倍以内に収まっていることが 分かる. 他のデータについても同様なので, 線形時間で 計算可能であるといえる.

一方, Wiegers のアルゴリズムについても計算時間が 線形時間の関係となっているが, NCI0DA99 と NCI Ope

1 2 cross 3 cross 4 cross 5 cross cross cross 図 7: 入力グラフ G2 2 3 cross 5 out 4 cross cross cross 図 8: G2の縮小 (1 回目) 3 4 cross 5 out cross 図 9: G2の縮小 (2 回目) 3 5 bridge 図 10: G2の縮小 (3 回目)

n 0903 では計算時間に 2 倍以上の差がある. この要因 として, 辺ラベルの初期化などに要する時間が挙げら れる. また,AID2DA99 に対する両アルゴリズムの計算時間 は, 平均頂点数, 平均辺数ともに大きいデータ CAD2DA99 と CAN2DA99 に対する計算時間より小さいが, これは グラフデータの記述量の差によるものである.

5

まとめと今後の課題

外平面的グラフの認識アルゴリズムを二つ実装し, 計 算時間を比較した. ラベル付けを行うためソートを行 わなくてよい Wiegers のアルゴリズムは, Mitchell の アルゴリズムに比べて高速に動作した. 今後の課題と しては, バケットソートの改良による Mitchell のアル ゴリズムの高速化や, 今回実装したアルゴリズムを利用 したグラフマイニングの研究が挙げられる.

参考文献

[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to algorithms (3rd Edi-tion), MIT Press, 2010.

[2] J. Hopcroft, R. Tarjan: Efficient algorithms for graph manipulation, Comm. ACM 16, 327–378, 1973.

[3] T. Horv´ath, J. Ramon, S. Wrobel: Frequent sub-graph mining in outerplanar sub-graphs, Data Min. Knowl. Disc. 21, 472–508, 2010.

[4] Information System on Graph

Classes and their Inclusion (ISGCI), http://www.graphclasses.org/classes. [5] S. L. Mitchell: Linear algorithms to recognize

outerplanar and maximal outerplanar graphs, In-form. Process. Let. 9, 229–232, 1979.

[6] NCI dataset , http://cactus.nci.nih.gov/. [7] M. Wiegers: Recognizing outerplanar graphs in

linear time, Proc. WG’86, LNCS 246, 165–176, 1987.

[8] H. Yamasaki, Y. Sasaki, T. Shoudai, T. Uchida, Y. Suzuki: Learning block-preserving graph pat-terns and its application to data mining, Mach. Learn. 76, 137–173, 2009. 表 3: NCI グラフデータ 入力データ グラフ数 nave 割合 [%] CAD2DA99 23031 25.927 92.554 AID2DA99 42689 25.603 91.609 CAN2DA99 32557 26.326 91.881 NCA2DA99 249081 21.450 94.483 NCI0DA99 249081 21.451 94.395 NCI aug00 2D 250251 39.805 94.377 NCI Open 0501 265242 41.763 94.612 NCI Open 0903 260071 40.291 94.288 ncidb 250250 39.805 94.377 表 4: 表 3 のデータに対する計算時間 入力データ Mitchell[秒] Wiegers[秒] CAD2DA99 9.355 5.898 AID2DA99 13.198 6.634 CAN2DA99 13.240 8.196 NCA2DA99 68.351 34.708 NCI0DA99 61.855 28.101 NCI aug00 2D 103.723 62.001 NCI Open0501 121.993 71.986 NCI Open 0903 116.650 67.978 ncidb 106.243 63.911 表 5: グラフ数を揃えたデータセット

入力データ nave eave bave

CAD2DA99 27.760 29.97 14.065 AID2DA99 34.053 36.823 17.876 CAN2DA99 31.968 34.582 16.276 NCA2DA99 45.816 49.483 25.308 NCI0DA99 45.817 49.643 25.288 NCI aug00 2D 88.615 91.913 69.974 NCI Open0501 90.357 93.547 71.148 NCI Open 0903 90.703 94.016 71.494 ncidb 88.615 91.913 69.974 表 6: 表 5 のデータに対する計算時間 入力データ Mitchell[秒] Wiegers[秒] CAD2DA99 8.230 4.926 AID2DA99 7.663 4.156 CAN2DA99 8.939 5.534 NCA2DA99 10.165 6.129 NCI0DA99 9.208 5.140 NCI aug00 2D 16.954 12.764 NCI Open0501 17.658 13.202 NCI Open 0903 18.245 14.001 ncidb 17.013 12.822