グラフ同型性判定装置、グラフ同型性判定方法、プログラム及び評価システム
【課題】２つのグラフの同型性を確実かつ短時間に判定する。
【解決手段】グラフ同型性判定装置１００は、複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフの同型性を判定する。ツリー変換部１０は、リンクで接続された他のノードとの接続関係に基づいて、複数のノード各々の階層及び階級をノード間で重複しないように与えることにより、各グラフの構造を、各ノードの階層及び階級に基づくツリー構造に変換する。比較判定部１１は、ツリー変換部１０によりツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する。
【解決手段】グラフ同型性判定装置１００は、複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフの同型性を判定する。ツリー変換部１０は、リンクで接続された他のノードとの接続関係に基づいて、複数のノード各々の階層及び階級をノード間で重複しないように与えることにより、各グラフの構造を、各ノードの階層及び階級に基づくツリー構造に変換する。比較判定部１１は、ツリー変換部１０によりツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフが同一であるか否かを判定するグラフ同型性判定装置、グラフ同型性判定方法、プログラム及び評価システムに関する。
【背景技術】
【０００２】
有向グラフ、無向グラフ等のグラフ同型性問題は、２つのグラフが与えられたときに、それらが同型であるか否かを判定する問題である（例えば、非特許文献１、２参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】戸田誠之助、”グラフ同型性判定問題の計算量”、信学技法、COMP2001-95、March 2002
【非特許文献２】福田和真、中森眞理雄、”グラフ同型性問題の解放における完全マッチング問題の利用の効果”、電子情報通信学会論文誌、D-I Vol．J85-D-I、No．10、pp．994-999 October 2002
【発明の概要】
【発明が解決しようとする課題】
【０００４】
同型性判定問題を、多項式時間（計算理論において多項式で表される計算時間）で解けるアルゴリズムは未だに存在していない。それどころか、同型性判定問題では、計算複雑性理論において、どの程度の計算量が必要であるかも未知となっている。
【０００５】
本発明は、上記実情に鑑みてなされたものであり、２つのグラフの同型性を確実かつ短時間で判定することができるグラフ同型性判定装置、グラフ同型性判定方法、プログラム及び評価システムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、本発明の第１の観点に係るグラフ同型性判定装置は、
複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフの同型性を判定するグラフ同型性判定装置であって、
前記リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて、前記複数のノード各々の階層及び階級をノード間で重複しないように与えることにより、前記各グラフの構造を、前記各ノードの階層及び階級に基づくツリー構造に変換するツリー変換部と、
前記ツリー変換部によりツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する比較判定部と、
を備える。
【０００７】
この場合、前記ツリー変換部は、
前記他のノードとの接続関係に基づいて、前記各ノードの階層を設定するノード階層化部と、
前記他のノードとの接続関係を含む各ノードの状態に基づいて、前記各ノードの階級を仮に算出する処理を、前記階層の昇順及び降順に繰り返す階級算出部と、
前記各ノードの階級の変動が収束したか否かを、前記階級算出部による階級算出の終了条件として判定する収束判定部と、
同一の階層の前記ノードの階級が互いに異なるように、前記各ノードの階級を調整する階級調整部と、
を備え、
前記階級算出部による階級算出と、前記収束判定部による判定と、前記階級調整部による調整と、を同一の階層において階級が重複する前記ノードがなくなるまで繰り返す、
こととしてもよい。
【０００８】
この場合、前記階級算出部は、
前記各ノードの階級を仮に算出する処理を、前記各階層で行う際に、
同一の階層における前記各ノードの階級の変動が収束するまで、その階層における前記各ノードの階級の算出を繰り返す、
こととしてもよい。
【０００９】
また、前記階級算出部は、
前記他のノードとの接続関係を含む各ノードの状態を、所定の規則に従って数値化し、
数値化された前記各ノードの状態の大小関係に応じて、同一の階層におけるすべてのノードの階級を算出する、
こととしてもよい。
【００１０】
この場合、前記階級算出部は、
前記ツリー構造における前記他のノードとの相対位置関係、前記リンクの向き、前記他のノードの階級を各要素とするベクトルを、前記リンクごとに生成し、
前記リンクごとに生成されたベクトルの要素を、各桁の数値として昇順に並べることにより生成される前記リンクごとのスカラー量を求め、
前記リンクごとのスカラー量を、その大きさに従ってソートして、各桁の数値として昇順に並べることにより生成されるスカラー量を前記各ノードの最終的なスコアとして求め、
前記スコアに基づいて、同一の階層のすべてのノードの階級を算出する、
ようにしてもよい。
【００１１】
また、前記階級調整部は、
同一の階層における前記各ノードの階級が逆転することのないように、前記各ノードの階級を調整する、
こととしてもよい。
【００１２】
また、前記ツリー変換部は、
前記各グラフのツリー構造への変換を、ルートノードを変更しながら前記各グラフのすべてのノードについて繰り返し行い、
変換された複数のツリー構造各々について、前記各ノードのレベル及びランクに基づく評価値をそれぞれ算出し、
前記評価値が最大となるツリー構造を、前記複数のツリー構造の中から選択し、
前記比較判定部は、
前記選択されたツリー構造を用いて、２つのグラフを比較する、
こととしてもよい。
【００１３】
本発明の第２の観点に係るグラフ同型性判定方法は、
複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフの同型性を判定するグラフ同型性判定方法であって、
前記リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて、前記複数のノード各々の階層及び階級をノード間で重複しないように与えることにより、前記各グラフの構造を、前記各ノードの階層及び階級に基づくツリー構造に変換するツリー変換工程と、
前記ツリー変換工程においてツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する比較判定工程と、
を含む。
【００１４】
本発明の第３の観点に係るプログラムは、
複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフの同型性を判定するコンピュータに実行させるプログラムであって、
前記リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて、前記複数のノード各々の階層及び階級をノード間で重複しないように与えることにより、前記各グラフの構造を、前記各ノードの階層及び階級に基づくツリー構造に変換するツリー変換手順と、
前記ツリー変換手順においてツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する比較判定手順と、
を実行させる。
【００１５】
本発明の第４の観点に係る評価システムは、
グラフ化された物質の結合構造を記憶する記憶装置と、
前記記憶装置に記憶された物質の結合構造を示す２つのグラフの同型性を判定する本発明のグラフ同型性判定装置と、
前記グラフ同型性判定装置における判定結果に基づいて、前記記憶装置に記憶されたグラフを評価する評価装置と、
を備える。
【発明の効果】
【００１６】
本発明によれば、他のノードとの接続関係を含む各ノードの状態に基づいて各ノードに階層及び階級を与えることにより、各グラフの構造がツリー構造に変換される。ツリー構造は、一定の秩序に従って階層化されたものであるため、ツリー構造に変換されたグラフを比較すれば、両者が同一であるか否かを確実かつ短時間に判定することができる。
【００１７】
また、各グラフは、各ノードの階層及び階級がノード間で重複しないようにツリー構造に変換される。このようにすれば、ノードを１対１で比較する際のノードの組み合わせの数を最小限に留めることができる。この結果、グラフの比較判定に要する時間をさらに短縮することができる。
【００１８】
以上のように、本発明によれば、２つのグラフの同型性を確実かつ短時間に判定することができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施形態に係るグラフ同型性判定装置の構成を示すブロック図である。
【図２】図２（Ａ）及び図２（Ｂ）は、比較対象となるグラフの一例を示す図である。
【図３】ツリー構造の一例を示す図である。
【図４】図４（Ａ）は、隣接ノードとのリンク毎のスコアのフォーマットを示す図である。図４（Ｂ）は、隣接ノードの相対位置関係に基づくスコアの要素の値を説明するための図である。図４（Ｃ）は、リンクの向きに基づくスコアの要素の値を説明するための図（その１）である。図４（Ｄ）は、リンクの向きに基づくスコアの要素の値を説明するための図（その２）である。
【図５】図５（Ａ）は、あるノードについて求められるスコアの一例を示す図である。図５（Ｂ）は、図５（Ａ）のノードのスコアの一例を示す図である。図５（Ｃ）は、トータルスコアの算出方法を説明するための図である。
【図６】図６（Ａ）は、同じレベルにおける各ノードの仮ランクの設定例を示す図である。図６（Ｂ）は、図６（Ａ）のスコアが重複するノードがある場合の各ノードの仮ランクの設定例を示す図である。
【図７】図１のグラフ同型性判定装置の動作のフローチャートである。
【図８】図７のレベルスイープ処理の詳細を示すフローチャートである。
【図９】ランクの算出過程を示す図（その１）である。
【図１０】ランクの算出過程を示す図（その２）である。
【図１１】ランクの算出過程を示す図（その３）である。
【図１２】ランクが重複した場合の処理の一例を示す図（その１）である。
【図１３】ランクが重複した場合の処理の一例を示す図（その２）である。
【図１４】図１のグラフ同型性判定装置の適用例を示すブロック図である。
【図１５】図１５（Ａ）は、水分子の模式図である。図１５（Ｂ）は、水分子の水素結合を模したノードとリンクを示す図である。図１５（Ｃ）、図１５（Ｄ）は、水クラスタを模したグラフを示す図である。
【発明を実施するための形態】
【００２０】
この発明の実施の形態について、図面を参照して詳細に説明する。
【００２１】
図１には、本実施形態に係るグラフ同型性判定装置１００の構成が示されている。このグラフ同型性判定装置１００は、２つのグラフの同型性を判定する装置、すなわち、２つのグラフが同一であるか否かを判定する装置である。
【００２２】
図２（Ａ）、図２（Ｂ）には、比較されるグラフの一例として、それぞれグラフＧ１、Ｇ２が示されている。図２（Ａ）及び図２（Ｂ）に示すように、グラフＧ１、Ｇ２は、複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される。
【００２３】
グラフ同型性判定装置１００は、ＣＰＵ及びメモリ（いずれも不図示）を備えるコンピュータである。ＣＰＵがメモリに記憶されたプログラムを実行することにより、グラフ同型性判定装置１００の各種構成要素の機能が実現される。
【００２４】
図１に示すように、グラフ同型性判定装置１００は、ツリー変換部１０と、比較判定部１１と、を備える。
【００２５】
ツリー変換部１０は、２つのグラフを入力する。ツリー変換部１０は、グラフの各ノードに対して階層（レベル）及び階級（ランク）を付与することにより、図３に示すように、２つのグラフの構造を各ノードの階層及び階級に基づくツリー構造に変換する。本実施形態では、階層化されたツリー構造の階層をレベルと呼び、同一のレベルにおけるノードの階級をランクと呼ぶ。
【００２６】
この際、ツリー変換部１０は、リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて、複数のノード各々のレベル及びランクをノード間で重複しないように与える。
【００２７】
比較判定部１１は、ツリー変換部１０によりツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する。比較判定部１１は、その判定結果を出力する。この判定結果を参照すれば、入力された２つのグラフが同一であるか否かを確認することができる。
【００２８】
ツリー変換部１０のさらなる詳細な構成について説明する。
【００２９】
図１に示すように、ツリー変換部１０は、ノード階層化部２０と、ランク算出部２１と、収束判定部２２と、ランク調整部２３と、ツリー評価部２４と、記憶部３０と、を備える。
【００３０】
ノード階層化部２０は、グラフに含まれる複数のノードの中からルートノードを選択する。例えば、図３では、ノードＡが、ルートノードとして選択されている。選択されるノードは任意でよい。
【００３１】
ノード階層化部２０は、リンクで接続された他のノードとの接続関係に基づいて、各ノードのレベルを設定する。ルートノードはレベル１となる。続いて、ノード階層化部２０は、ルートノードとして選択されたノードに直接リンクされたノードをレベル２のノードとして選択する。さらに、レベル２のノードとして選択されたノードに直接リンクされたノードをレベル３のノードとして選択する。このようにして、各レベルのノードが選択される。
【００３２】
例えば、図３に示す例であれば、ルートノードであるノードＡとリンクを介して接続しているノードＢ、Ｃ、Ｄ、Ｅがレベル２のノードとなる。さらに、ノードＢ、Ｃ、Ｄ、Ｅにリンクを介して接続しているノードＦ、Ｇ、Ｈ、Ｉがレベル３のノードとなる。このようにして、各ノードのレベルが設定され、基本的な木構造が設定される。
【００３３】
ランク算出部２１は、各ノードのランク（仮ランク）を仮に算出する処理を、ツリー構造のレベルの昇順及び降順に繰り返す。
【００３４】
ランク算出部２１における各ノードの仮ランクは、リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて算出される。各ノードの状態は、所定の規則に従って数値化される。ランク算出部２１は、数値化された各ノードの状態の大小関係に応じて、同一の階層におけるすべてのノードの階級を算出する。
【００３５】
より具体的には、この各ノードの状態は、まず、スコアと呼ばれる１次元のベクトルに変換される。図４（Ａ）に示すように、スコアの要素の数は、３又は４つである。
【００３６】
要素の数が３つであるスコアは、上下のレベルに跨ったリンクにおける各ノードの状態の数値化に用いられる。
【００３７】
このスコアの１番目の要素の値は、ツリー構造において隣接する他のノードの相対位置関係を示している。例えば、図４（Ｂ）に示すように、この要素の値は、ランクの算出対象となるノード（黒丸）に対して隣接するノード（白丸）が上のレベルである場合には３となり、同じレベルである場合には２となり、下のレベルである場合には１となる。また、そのノード自身のスコアでは、１番目の要素の値は０となる。
【００３８】
続いて、このスコアの２番目の要素は、リンクの向きを表している。図４（Ｃ）に示すように、この要素の値は、リンクが上のレベルから下のレベルに向いている場合には１となり、リンクが下のレベルから上のレベルに向いている場合には０となる。また、そのノード自身のスコアでは、２番目の要素の値は０となる。
【００３９】
続いて、このスコアの３番目の要素は、隣接するノードのランクを示している。ここで、この要素の値は、ランクが小さければ小さいほど大きくなっている。また、各ノード自身のスコアでは、３番目の要素の値は、そのノード自身のランクに基づく値となる。
【００４０】
続いて、要素の数が４つであるスコアは、同一のレベルのノード同士のリンクを対象として用いられる。
【００４１】
このスコアの１番目の要素の値は、隣接するノードの相対位置関係を表し、２番目の要素がリンクの向きを表しているのは、上述のスコアと同じである。ただし、図４（Ｄ）に示すように、２番目の要素の値は、リンクがランクの算出対象に向いているときには１となり、反対を向いているときには０となる。
【００４２】
さらに、このスコアの３番目の要素の値はリンクの始点のランクであり、このスコアの４番目の要素の値はリンクの終点のランクである。
【００４３】
ランク算出部２１は、ランクの算出対象である各ノードについて、リンク毎に、上記スコアを求める。
【００４４】
例えば、図５（Ａ）に示すように、あるノード（仮ランクｍ）について、３つの隣接ノード（それぞれの仮ランクｎ１、ｎ２、ｎ３）がそれぞれ接続しているものとする。この場合、図５（Ｂ）に示すように、各リンクについて、（３、１、ｎ１）、（２、１、ｎ２、ｍ）、（１、１、ｎ３）という３つのスコアが求められ、そのノード自身のスコアとして、（０、０、ｍ）が求められる。なお、（２、１、ｎ２、ｍ）は、（２、０、ｍ、ｎ２）であってもよい。
【００４５】
ランク算出部２１は、各ノードについて求められたスコアを、スカラー量に変換する。スカラー量は、例えば、各要素の値を各桁の値として昇順に並べることにより生成される。例えば、最上位の数桁の値を１番目の要素の値とし、続く数桁の値を２番目の要素の値とし、続く数桁の値を３番目の要素の値とし、最下位の数桁の値を４番目の要素の値とすることにより、１つのスカラー量が生成される。
【００４６】
例えば、図５（Ｂ）に示すように、（３、１、ｎ１）は、３００１０００００００００００００（ｎ１）という数値に変換される。また、（２、１、ｎ２、ｍ）は、２００１０００００（ｎ２）０００００００（ｍ）という数値に変換される。さらに、（１、１、ｎ３）は、１００１０００００００００００００（ｎ３）という数値に変換される。さらに、（０、０、ｍ）は、０００００００００００００００００（ｍ）という数値に変換される。ｎ１、ｎ２、ｎ３、ｍには、その数値に対応する値が挿入される。
【００４７】
続いて、ランク算出部２１は、スカラー量に変換されたスコアを大きさに従ってソートして、各桁の数値として昇順に並べることにより生成されるスカラー量を、トータルスコアとして求める。例えば、図５（Ｃ）に示すように、スコア１＞スコア２＞スコア３＞スコア４である場合には、ランク算出部２１は、大きい桁の方からスコア１→スコア２→スコア３→スコア４の順に並べ、それらを合成することにより形成される数値をトータルスコアとして算出する。
【００４８】
ランク算出部２１は、同一レベルの全てのルートについてこのトータルスコアを求め、同じレベルにある全てのノードのトータルスコアを比較することにより、そのレベルにおける各ノードの仮ランクを算出する。
【００４９】
このとき、ランク算出部２１は、各ノードのランクを仮に算出する処理を、各レベルで行う際に、同一のレベルにおける各ノードの仮ランクの変動が収束するまで、そのレベルにおける各ノードのランクの算出を繰り返す。
【００５０】
例えば、図６（Ａ）に示すように、同じレベルにノードＡ乃至Ｄがあり、それぞれのトータルスコアＳＡ乃至ＳＤが算出され、それぞれのトータルスコアにＳＡ＞ＳＢ＞ＳＣ＞ＳＤの関係があったとする。この場合、ランク算出部２１は、ノードＡの仮ランクをランク１とし、ノードＢの仮ランクをランク２とし、ノードＣの仮ランクをランク３とし、ノードＤの仮ランクをランク４とする。
【００５１】
なお、場合によっては、同一のレベルにスコアが重複するノードが存在することがある。例えば、図６（Ｂ）に示すように、それぞれのスコアの関係がＳＡ＞ＳＢ＝ＳＣ＞ＳＤとなっている場合、ランク算出部２１は、ノードＡの仮ランクをランク１とし、ノードＢの仮ランクをランク２とし、ノードＣの仮ランクをランク２とし、ノードＤの仮ランクをランク４とする。ノードＢ、Ｃの仮ランクは、後述するように、調整される可能性があるため、ノードＤの仮ランクは、その調整の余裕を確保すべく、３ではなく４に設定される。
【００５２】
ランク算出部２１は、このようなノードの仮ランクの算出を、最上位レベルから降順に最下位のレベルまで行った後、今度は、最下位のレベルから昇順に最上位のレベルまで行い、各レベルの各ノードの仮ランクの算出を繰り返す。
【００５３】
収束判定部２２は、ランク算出部２１によって算出された各ノードの仮ランクの変動が収束したか否かを、ランク算出部２１による階級算出の終了条件として判定する。収束判定部２２で各ノードの仮ランクが収束したと判定されたときの各ノードの仮ランクが最終的なそのノードのランクとなる。
【００５４】
ランク調整部２３は、同一の階層の各ノードの仮ランクが互いに異なるように、各ノードの仮ランクを調整する。ランク調整部２３は、同一のレベルにおける各ノードの仮ランクが逆転することのないように、各ノードの仮ランクを調整する。例えば、図６（Ｂ）に示すように、ノードＣ、Ｄの仮ランクが重複している場合には、一方のノードＣの仮ランクが２から３に変更される。なお、この場合、ノードＢの仮ランクを２から３に変更するようにしてもよい。
【００５５】
ルート変換部１０は、ランク算出部２１による仮ランクの算出と、収束判定部２２による判定と、ランク調整部２３による調整と、を同一のレベルにおいてランクが重複するノードがなくなるまで繰り返す。これにより、各グラフを、あるノードをルートノードとして設定したときのツリー構造に変換することができる。ルート変換部１０は、上述のようなツリー構造への変換を、ルートノードを変更しながら繰り返し行う。このようにして、ルート変換部１０は、各グラフを、Ｍ（ノードの数）通りのツリー構造に変換する。
【００５６】
ツリー評価部２４は、Ｍ通りのツリー構造各々について、レベル及び仮ランクに基づく評価値を算出し、その評価値が最大となるツリー構造を、Ｍ通りのツリー構造の中から選択する。より具体的には、ツリー評価部２４は、各ツリー構造について、各ノードのレベルとランクとを一列に並べることにより生成される数値を算出し、例えば、その数値が一番大きいツリー構造をそのグラフのツリー構造、すなわちグラフ間の比較に用いられるツリー構造として選択する。比較判定部１１には、この選択されたツリー構造が出力され、２つのグラフの比較に用いられる。
【００５７】
記憶部３０は、入力された２つのグラフのデータや、ノード階層化部２０、ランク算出部２１、ランク調整部２３で生成されるデータを必要に応じて記憶する。
【００５８】
次に、本実施形態に係るグラフ同型性判定装置１００の動作について説明する。
【００５９】
図７、図８には、グラフ同型性判定装置１００の動作のフローチャートが示されている。グラフ同型性判定装置１００では、２つのグラフが入力され、その情報が記憶部３０に記憶される。続いて、グラフ同型性判定装置１００は、まず一方のグラフについて、図７、図８に示す処理を開始する。
【００６０】
図７に示すように、まず、ノード階層化部２０は、ルートノードを決定する（ステップＳ１）。
【００６１】
この場合、ルートノードとして選択されるノードは、まだ選択されていないもののうち、任意のものでよい。ここでは、すでに選択されたノードはないので、すべてのノードの中から任意のノードが選択される。
【００６２】
続いて、ノード階層化部２０は、他のノードとの接続関係に基づいて、各ノードのレベルを設定する（ステップＳ２）。これにより、このグラフのツリー構造の全体のレベル数（階層数）Ｎmaxが明らかになる。各ノードのレベル及びレベル数Ｎmaxは、記憶部３０に記憶される。
【００６３】
続いて、ランク算出部２１は、各ノードに仮ランクを付与し、付与した仮ランクの値を記憶部３０に記憶する（ステップＳ３）。付与される仮ランクは、任意の数値でよいが、本実施形態では、全てのノードに仮ランクとして０を付与するものとする。
【００６４】
続いて、ランク算出部２１は、レベルカウンタＮを１に初期化し、極変数ｐを１に初期化する（ステップＳ４）。この極変数ｐは、＋１か−１かのいずれかの値をとる。
【００６５】
続いて、ランク算出部２１は、レベルカウンタＮにｐを加算する（ステップＳ５）。ここで、ｐ＝＋１なので、レベルカウンタＮは１インクリメントされる。
【００６６】
続いて、ランク算出部２１は、レベルＮのレベルスイープ処理のサブルーチンを実行する（ステップＳ６）。
【００６７】
図８には、このレベルスイープ処理の詳細が示されている。図８に示すように、ランク算出部２１は、記憶部３０から、レベルＮの各ノードの情報を読み出す（ステップＳ２１）。
【００６８】
続いて、ランク算出部２１は、読み出した各ノードの情報から、各ノードの仮ランクを抽出して、記憶部３０の別の領域に記憶する（ステップＳ２２）。
【００６９】
続いて、ランク算出部２１は、各ノードのリンクごとのスコアを算出する（ステップＳ２３）。例えば、ここで、図５（Ｂ）に示すように、スコア１乃至３（ベクトル）が算出される。
【００７０】
続いて、ランク算出部２１は、各ノードのスコアをスカラー変換する（ステップＳ２４）。例えば、ここで、図５（Ｂ）に示すように、スコア１乃至３がスカラー量に変換される。
【００７１】
続いて、ランク算出部２１は、スカラー変換された各スコアを、その大きさに従ってソートして、その順番にスコアを合成することにより、トータルスコアを算出する（ステップＳ２５）。例えば、ここで、図５（Ｃ）に示すように、スコア１、２、３が昇順にソートされ、その順番に合成されてトータルスコアが算出される。
【００７２】
続いて、ランク算出部２１は、レベルＮの各ノードのトータルスコアの大小関係に基づいて、レベルＮの各ノードの仮ランクを設定する（ステップＳ２６）。例えば、ここで、図６（Ａ）に示すように、トータルスコアＳＡ、ＳＢ、ＳＣ、ＳＤの大小関係に基づいて、ノードＡ、Ｂ、Ｃ、Ｄの仮ランク１、２、３、４が設定される。
【００７３】
続いて、ランク算出部２１は、上記ステップＳ２２で記憶部３０に記憶された仮ランクと、上記ステップＳ２６で算出された仮ランクとを比較して、それらに変化が無いか否かを判定する（ステップＳ２７）。
【００７４】
この判定が否定されると（ステップＳ２７；Ｎｏ）、ランク算出部２１は、ステップＳ２２に戻る。ランク算出部２１は、記憶部３０に記憶された各ノードの仮ランクを、ステップＳ２６で算出された仮ランクに更新する（ステップＳ２２）。以降、ステップＳ２７における判定が肯定されるまで（ステップＳ２７；Ｙｅｓ）、ステップＳ２２→Ｓ２３→Ｓ２４→Ｓ２５→Ｓ２６→Ｓ２７が繰り返される。
【００７５】
ステップＳ２２で記憶部３０に記憶され更新された仮ランクと、上記ステップＳ２６で算出された仮ランクとを比較して、それらに変化がないと判定されると（ステップＳ２７；Ｙｅｓ）、ランク算出部２１は、レベルスイープ処理を終了する。
【００７６】
続いて、ランク算出部２１は、ランクを算出するレベルが最下層まで到達し、レベルカウンタＮがＮmax又は１であるか否かを判定する（ステップＳ７）。この判定が否定されると（ステップＳ７；Ｎｏ）、ランク算出部２１は、ステップＳ５に戻る。
【００７７】
以降、ランクの算出対象となるレベルが最下層まで到達しない限り（ステップＳ７；Ｎｏ）、ランク算出部２１は、ステップＳ５→Ｓ６→Ｓ７を繰り返し、各レベルでのレベルスイープ処理を行う。
【００７８】
ランクの算出対象となるレベルが最下層になり、レベルカウンタＮがＮmaxになると（ステップＳ７；Ｙｅｓ）、ランク算出部２１は、各ノードの仮ランクを記憶部３０に記憶する（ステップＳ８）。ここで、ランク算出部２１は、上記ステップＳ３で記憶された仮ランクが記憶された領域とは、別の領域に仮ランクを記憶する。
【００７９】
続いて、ランク算出部２１は、極変数ｐに−１を乗算する（ステップＳ９）。ここで、ｐ＝１であったので、乗算の結果、極変数ｐは−１となる。
【００８０】
続いて、収束判定部２２は、前回記憶した仮ランク（ステップＳ３で記憶した仮ランク）と、今回記憶した仮ランク（ステップＳ８で記憶した仮ランク）とに差異がなく、各ノードの仮ランクの変動が収束しているか否かを判定する（ステップＳ１０）。この判定が否定されると（ステップＳ１０；Ｎｏ）、ツリー変換部１０は、ステップＳ５に戻る。ここでは、ステップＳ３で記憶された仮ランクはすべて０であり、両者が一致することはないので、判定は否定され（ステップＳ１０；Ｎｏ）、ツリー変換部１０は、ステップＳ５に戻る。
【００８１】
続いて、ランク算出部２１は、レベルカウンタＮにｐを加算する（ステップＳ５）。ここで、ｐ＝−１となっているので、実際には、レベルカウンタＮは１デクリメントされる。
【００８２】
続いて、ランク算出部２１は、レベルＮのレベルスイープ処理のサブルーチンを実行する（ステップＳ６）。なお、このレベルスイープ処理については、すでに説明したので、詳細な説明を省略する（図８参照）。
【００８３】
続いて、ランク算出部２１は、レベルカウンタＮがＮmax又は１であるか否かを判定する（ステップＳ７）。この判定が否定されれば（ステップＳ７；Ｎｏ）、ランク算出部２１は、ステップＳ５に戻る。
【００８４】
ランクの算出対象となるレベルが最上位レベルまで到達しない限り、すなわちレベルカウンタＮが１とならない限り（ステップＳ７；Ｎｏ）、ランク算出部２０は、ステップＳ５→Ｓ６→Ｓ７を繰り返し、各レベルでのレベルスイープ処理を行う。
【００８５】
ランクの算出対象となる階層が最上位レベルになると（ステップＳ７；Ｙｅｓ）、ランク算出部２１は、各ノードの仮ランクを記憶部３０に記憶する（ステップＳ８）。この際に、上記ステップＳ８で記憶された仮ランクとは、別の領域に仮ランクが記憶される。
【００８６】
続いて、ランク算出部２１は、極変数ｐに−１を乗算する（ステップＳ９）。ここで、ｐ＝−１であったので、乗算の結果、極変数ｐは１となる。
【００８７】
続いて、収束判定部２２は、前回のステップＳ８で記憶された仮ランクと、今回のステップＳ８で記憶された仮ランクとに差異がないか、すなわち、各ノードの仮ランクの変動が収束しているか否かを判定する（ステップＳ１０）。この判定が否定されれば（ステップＳ１０；Ｎｏ）、ツリー変換部１０は、ステップＳ５に戻る。
【００８８】
以降、各ノードの仮ランクの変動が収束していると判定されるまで（ステップＳ１０；Ｙｅｓ）、ステップＳ５からステップＳ１０の処理が繰り返される。
【００８９】
本実施形態では、このようにして、ランク算出部２１が、レベルの降順及び昇順に、各レベルのノードのランク算出を繰り返すことにより、各ノードの仮ランクを収束させる。
【００９０】
仮ランクの変動が収束すると（ステップＳ１０；Ｙｅｓ）、ランク調整部２３は、同じレベルに仮ランクが重複するノードが無いか否かを判定する（ステップＳ１１）。ランクが重複するノードが有る場合（ステップＳ１１；Ｎｏ）、ランク調整部２３は、そのレベルのノードの仮ランクを再調整する（ステップＳ１２）。具体的には、ランク調整部２３は、同一のレベルのノードの仮ランクが互いに異なるように、各ノードの仮ランクを調整する。
【００９１】
例えば、図６（Ｂ）に示す例では、同じレベルに仮ランクが重複するノードＢ、Ｃが存在する。この場合には、ランク調整部２３は、例えば、ノードＣをランク３に変更すれば、同一の階層のノードの仮ランクが互いに異なるように、各ノードの仮ランクを調整することができる。
【００９２】
なお、ＳＢ＝ＳＣであるため、ノードＢをランク３とし、ノードＣをランク２としてもよい。すなわち、いずれのノードの仮ランクを変更してもよい。
【００９３】
ただし、ノードＢ、Ｃの仮ランクは、ノードＢ、Ｃよりもトータルスコアの高いノードＡのランク１と、ノードＢ、Ｃよりもトータルスコアの低いノードＤのランク４との間とする必要がある。すなわち、本実施形態では、ランク調整部２３は、同一のレベルにおける各ノードの仮ランクが逆転することのないように、各ノードの仮ランクを調整する。
【００９４】
ステップＳ１２実行後、ツリー変換部１０は、ステップＳ５に戻る。以降ステップＳ４〜ステップＳ１１が繰り返される。そして、再び、収束判定部２２が、記憶した仮ランクの変化が無いと判定されると（ステップＳ１０；Ｙｅｓ）、ランク調整部２３は、同じレベルに仮ランクが重複するノードが無いか否かを判定する（ステップＳ１１）。仮ランクが重複するノードが有る場合（ステップＳ１１；Ｎｏ）、前述のように、仮ランクの再調整が行われ（ステップＳ１２）、仮ランク算出及び収束判定（ステップＳ５〜Ｓ１１）が繰り返される。
【００９５】
同じレベルにランクが重複するノードが無くなると（ステップＳ１１；Ｙｅｓ）、収束判定部２２は、各ノードの仮ランクを最終的なランクとして記憶部３０に記憶する（ステップＳ１３）。
【００９６】
続いて、ツリー変換部１０は、グラフを、Ｍ通りのツリー構造に変換したか否かを判定する（ステップＳ１４）。ここでは、まだ１通りのツリー構造にしか変換されていないので判定は否定され（ステップＳ１４；Ｎｏ）、ツリー変換部１０は、ステップＳ１に戻る。
【００９７】
以降、ステップＳ１からステップＳ１４までの処理が繰り返され、各グラフが、各ノードをそれぞれルートノードとするＭ通りのツリー構造に変換される。Ｍ通りのツリー構造に変換されたと判定されると（ステップＳ１４；Ｙｅｓ）、ツリー評価部２４は、Ｍ通りのツリー構造の中から、最適な１つのツリー構造を選択する（ステップＳ１５）。
【００９８】
より具体的には、ツリー評価部２４は、各ツリー構造について、例えば、次のような、レベルとランクの組み合わせから成るベクトルを各ノードについて生成する。
（レベル１、ランク＊）、（レベル２、ランク＊）、（レベル３、ランク＊）、・・・
【００９９】
続いて、ツリー評価部２４は、各ノードについて生成されたベクトルを、例えばレベル順、ランク順に１列に並べた結合行列を生成し、その結合行列を、上述と同様にして、スカラー量に変換する。さらに、ツリー評価部２４は、そのスカラー量が最大となるツリー構造を、最終的なツリー構造として選択する（ステップＳ１６）。
【０１００】
続いて、ツリー変換部１０は、各ノードのレベル及びランクを含むツリー構造情報を出力する（ステップＳ１６）。ステップＳ１６終了後、ツリー変換部１０は、処理を終了する。
【０１０１】
上述のように、ステップＳ５〜Ｓ１０の繰り返しにおいて、例えば、図９に示すように、まず、レベル２のノードの仮ランクが設定される。この場合、レベル２の２つのノードは、互いに他のノードの接続形態が同一であるため、仮ランクは同じ１となる。そして、続いて、図１０に示すように、レベル３のノードの仮ランク（１と２）が設定され、レベル４のノードの仮ランク１が設定される。
【０１０２】
さらに、ステップＳ５〜Ｓ１０の繰り返しにおいて、レベル３のノードの仮ランク（１と２）が設定され、続いてレベル２のノードの仮ランクが設定される。ここで、図１１に示すように、レベル２の右側のノードの仮ランクは、１から２に変更される。このように、仮ランクの算出を、レベルの昇順及び降順に繰り返すことにより、各ノードの仮ランクが収束していく。この処理は、ツリースイープ処理ともいうべきものである。
【０１０３】
また、図１２に示すように、例えばレベル２のノードの中に、仮ランク１で重複しているノードがある場合、ランク調整部２３は、図１３に示すように、一方のノードの仮ランクを、２に変更することにより仮ランクを調整する。この後、再び、仮ランクの算出が、レベルの昇順及び降順に繰り返される。
【０１０４】
ツリー変換部１０は、入力した２つのグラフ各々について、ステップＳ１乃至Ｓ１６の処理を実行する。これにより、ツリー変換部１０から２つのグラフ各々に対応するツリー構造情報が出力される。各グラフについて出力されるツリー構造情報は１つだけである。
【０１０５】
比較判定部１１は、入力した２つのツリー構造情報に基づいて、２つのグラフが一致するか否かを判定する。個々のツリー構造は、レベルやランクの重複するノードが存在しないので、比較するノードの組み合わせの数を少なくすることができる。
【０１０６】
以上詳細に説明したように、本実施形態によれば、他のノードとの接続関係に基づいて各ノードにレベル及びランクを与えることにより、各グラフがツリー構造に変換される。各グラフのツリー構造は、一定の秩序に従って階層化されているため、両者が同一であるか否かを確実かつ短時間に判定することができる。
【０１０７】
また、このツリー構造は、各ノードのレベル及びランクがノード間で重複しないように生成される。このようにすれば、ノードを１対１で比較する際のノードの組み合わせの数を最小限に留めることができる。この結果、ツリー構造の比較判定に要する時間を短縮することができる。
【０１０８】
以上のように、本実施形態によれば、２つのグラフの同型性を確実かつ短時間に判定することができる。
【０１０９】
また、本実施形態によれば、比較対象となるツリー構造を各グラフにつき１つずつとすることができるので、同型性の判定に要する時間を短縮することができる。
【０１１０】
なお、これまで、グラフ理論における同型性判定問題の最悪計算量Ｏ（ｎ）は、Ｂａｂａｉらによると、次式のようになる。
【０１１１】
【数１】
【０１１２】
しかしながら、本実施形態に係るグラフ同型性判定装置１００を用いれば、最悪計算量Ｏ（ｎ）は、次式のようになる。
【０１１３】
【数２】
【０１１４】
この最悪計算量Ｏ（ｎ）は、ツリースイープの計算量ｎ・ｌｏｇ（ｎ）に、すべてのノードのランクが重複しなくなるまでの回数と、最悪の場合に生成されなければならないツリーの数を考慮して求められたものである。
【０１１５】
上記式（２）の最悪計算量Ｏ（ｎ）は、上記式（１）の最悪時間量Ｏ（ｎ）よりも少ない。したがって、本実施形態に係るグラフ同型性判定装置１００によれば、より短時間に、グラフの同型性を判定することができる。
【０１１６】
ところで、ノード数が１４であるグラフの一致不一致をコンピュータに判定させた場合、グラフをそのまま比較した場合には１８０分を要したのに対し、本実施形態に係るグラフ同型性判定装置１００にてツリー構造に変換されたグラフを比較したときに要した時間は、３秒であった。
【０１１７】
なお、本実施形態に係るグラフ同型性判定装置１００は、閉路を有するグラフであってもよい。また、このグラフ同型性判定装置１００は、有向グラフであっても、無向グラフであっても、適用が可能である。無向グラフの場合には、ノード間に、逆向きの２つのリンクが接続されているものとみなして、スコアを求めるようにすればよい。
【０１１８】
本実施形態に係るグラフ同型性判定装置１００は、様々な用途に適用可能である。
【０１１９】
例えば、グラフ同型性判定装置１００を、図１４に示すような、データベースシステム２００に適用可能である。図１４に示すように、データベースシステム２００は、化合物データベース４０と、管理部４１と、を備える。データベース４０には、化学構造式をグラフ化した多数の化合物データが登録されている。管理部４１は、データベース４０に登録された化合物の化学構造式のグラフを評価し、必要であればデータの追加登録や削除を行う。
【０１２０】
グラフ同型性判定装置１００は、化合物データベース４０に登録された化合物の２つのグラフを入力し、２つのグラフが同一であるか否かを判定し、その判定結果を、管理部４１に出力する。管理部４１は、２つのグラフが一致する場合に、例えば、一方のグラフを削除するか、２つのグラフを１つのグラフに統合する。このようにすれば、化合物データベース４０に登録されたデータを整理することができる。
【０１２１】
また、グラフ同型性判定装置１００を水クラスタの解析に適用することも可能である。水クラスタは、例えば図１５（Ａ）に示すように、水分子５０が水素結合で結合されることにより形成される。この水クラスタは、図１５（Ｂ）に示すように、水分子５０と水素結合のリンク５１として表現することができる。
【０１２２】
この水クラスタは、様々な形態をとる。例えば、水クラスタは、図１５（Ｃ）に示すような構造もとり得るし、図１５（Ｄ）に示すように状態も取り得る。
【０１２３】
本実施形態に係るグラフ同型性判定装置１００は、モンテカルロシミュレーションにより発生する数億個の水クラスタの１つ１つが、同一の構造を有するものであるか否かを判定し、同じ構造を有する水クラスタの分布数を求めるのに用いることができる。これにより、ある特定の条件における、図１５（Ｃ）の構造を有する水クラスタの分布数や、図１５（Ｄ）の構造を有する水クラスタの分布数などを調べることができる。
【０１２４】
このように、本実施形態に係るグラフ同型性判定装置１００は、物質の結合構造の解析評価に好適である。このグラフ同型性判定装置１００は、記憶装置に記憶された２つのグラフを比較する。管理部４１は、グラフ同型性判定装置における判定結果に基づいて、記憶装置に記憶されたグラフを評価する。
【０１２５】
また、本実施形態に係るグラフ同型性判定装置は、グラフとして表現されるものであれば、同型性の判定が可能である。例えば、人と人との間に形成される人的ネットワークの解析にも適用することが可能である。
【０１２６】
なお、上記実施形態において、実行されるプログラムは、フレキシブルディスク、ＣＤ−ＲＯＭ（Compact Disk Read-Only Memory）、ＤＶＤ（Digital Versatile Disk）、ＭＯ（Magneto-Optical Disk）等のコンピュータ読み取り可能な記録媒体に格納して配布し、そのプログラムをインストールすることにより、上述の処理を実行するシステムを構成することとしてもよい。
【０１２７】
また、プログラムをインターネット等の通信ネットワーク上の所定のサーバ装置が有するディスク装置等に格納しておき、例えば、搬送波に重畳させて、ダウンロード等するようにしてもよい。
【０１２８】
また、上述の機能を、ＯＳ（Operating System）が分担して実現する場合又はＯＳとアプリケーションとの協働により実現する場合等には、ＯＳ以外の部分のみを媒体に格納して配布してもよく、また、ダウンロード等してもよい。
【０１２９】
なお、本発明は、上記実施の形態及び図面によって限定されるものではない。本発明の要旨を変更しない範囲で実施の形態及び図面に変更を加えることができるのはもちろんである。
【産業上の利用可能性】
【０１３０】
本発明は、例えば、ＣＡＳレジストリシステム等の化学データベースに多数登録された化学物質や、水クラスタ等の物質の結合構造を示す２つのグラフの同定に有用である。この他、本発明は、人的ネットワークなど、グラフとして表現可能なあらゆるものの同定に有用である。
【符号の説明】
【０１３１】
１０ ツリー変換部
１１ 比較判定部
２０ ノード階層化部
２１ ランク算出部
２２ 収束判定部
２４ ツリー評価部
２３ ランク調整部
３０ 記憶部
４０ データベース
４１ 管理部
５０ 水分子
５１ リンク
１００ グラフ同型性判定装置
２００ データベースシステム
【技術分野】
【０００１】
本発明は、複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフが同一であるか否かを判定するグラフ同型性判定装置、グラフ同型性判定方法、プログラム及び評価システムに関する。
【背景技術】
【０００２】
有向グラフ、無向グラフ等のグラフ同型性問題は、２つのグラフが与えられたときに、それらが同型であるか否かを判定する問題である（例えば、非特許文献１、２参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】戸田誠之助、”グラフ同型性判定問題の計算量”、信学技法、COMP2001-95、March 2002
【非特許文献２】福田和真、中森眞理雄、”グラフ同型性問題の解放における完全マッチング問題の利用の効果”、電子情報通信学会論文誌、D-I Vol．J85-D-I、No．10、pp．994-999 October 2002
【発明の概要】
【発明が解決しようとする課題】
【０００４】
同型性判定問題を、多項式時間（計算理論において多項式で表される計算時間）で解けるアルゴリズムは未だに存在していない。それどころか、同型性判定問題では、計算複雑性理論において、どの程度の計算量が必要であるかも未知となっている。
【０００５】
本発明は、上記実情に鑑みてなされたものであり、２つのグラフの同型性を確実かつ短時間で判定することができるグラフ同型性判定装置、グラフ同型性判定方法、プログラム及び評価システムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、本発明の第１の観点に係るグラフ同型性判定装置は、
複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフの同型性を判定するグラフ同型性判定装置であって、
前記リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて、前記複数のノード各々の階層及び階級をノード間で重複しないように与えることにより、前記各グラフの構造を、前記各ノードの階層及び階級に基づくツリー構造に変換するツリー変換部と、
前記ツリー変換部によりツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する比較判定部と、
を備える。
【０００７】
この場合、前記ツリー変換部は、
前記他のノードとの接続関係に基づいて、前記各ノードの階層を設定するノード階層化部と、
前記他のノードとの接続関係を含む各ノードの状態に基づいて、前記各ノードの階級を仮に算出する処理を、前記階層の昇順及び降順に繰り返す階級算出部と、
前記各ノードの階級の変動が収束したか否かを、前記階級算出部による階級算出の終了条件として判定する収束判定部と、
同一の階層の前記ノードの階級が互いに異なるように、前記各ノードの階級を調整する階級調整部と、
を備え、
前記階級算出部による階級算出と、前記収束判定部による判定と、前記階級調整部による調整と、を同一の階層において階級が重複する前記ノードがなくなるまで繰り返す、
こととしてもよい。
【０００８】
この場合、前記階級算出部は、
前記各ノードの階級を仮に算出する処理を、前記各階層で行う際に、
同一の階層における前記各ノードの階級の変動が収束するまで、その階層における前記各ノードの階級の算出を繰り返す、
こととしてもよい。
【０００９】
また、前記階級算出部は、
前記他のノードとの接続関係を含む各ノードの状態を、所定の規則に従って数値化し、
数値化された前記各ノードの状態の大小関係に応じて、同一の階層におけるすべてのノードの階級を算出する、
こととしてもよい。
【００１０】
この場合、前記階級算出部は、
前記ツリー構造における前記他のノードとの相対位置関係、前記リンクの向き、前記他のノードの階級を各要素とするベクトルを、前記リンクごとに生成し、
前記リンクごとに生成されたベクトルの要素を、各桁の数値として昇順に並べることにより生成される前記リンクごとのスカラー量を求め、
前記リンクごとのスカラー量を、その大きさに従ってソートして、各桁の数値として昇順に並べることにより生成されるスカラー量を前記各ノードの最終的なスコアとして求め、
前記スコアに基づいて、同一の階層のすべてのノードの階級を算出する、
ようにしてもよい。
【００１１】
また、前記階級調整部は、
同一の階層における前記各ノードの階級が逆転することのないように、前記各ノードの階級を調整する、
こととしてもよい。
【００１２】
また、前記ツリー変換部は、
前記各グラフのツリー構造への変換を、ルートノードを変更しながら前記各グラフのすべてのノードについて繰り返し行い、
変換された複数のツリー構造各々について、前記各ノードのレベル及びランクに基づく評価値をそれぞれ算出し、
前記評価値が最大となるツリー構造を、前記複数のツリー構造の中から選択し、
前記比較判定部は、
前記選択されたツリー構造を用いて、２つのグラフを比較する、
こととしてもよい。
【００１３】
本発明の第２の観点に係るグラフ同型性判定方法は、
複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフの同型性を判定するグラフ同型性判定方法であって、
前記リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて、前記複数のノード各々の階層及び階級をノード間で重複しないように与えることにより、前記各グラフの構造を、前記各ノードの階層及び階級に基づくツリー構造に変換するツリー変換工程と、
前記ツリー変換工程においてツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する比較判定工程と、
を含む。
【００１４】
本発明の第３の観点に係るプログラムは、
複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフの同型性を判定するコンピュータに実行させるプログラムであって、
前記リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて、前記複数のノード各々の階層及び階級をノード間で重複しないように与えることにより、前記各グラフの構造を、前記各ノードの階層及び階級に基づくツリー構造に変換するツリー変換手順と、
前記ツリー変換手順においてツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する比較判定手順と、
を実行させる。
【００１５】
本発明の第４の観点に係る評価システムは、
グラフ化された物質の結合構造を記憶する記憶装置と、
前記記憶装置に記憶された物質の結合構造を示す２つのグラフの同型性を判定する本発明のグラフ同型性判定装置と、
前記グラフ同型性判定装置における判定結果に基づいて、前記記憶装置に記憶されたグラフを評価する評価装置と、
を備える。
【発明の効果】
【００１６】
本発明によれば、他のノードとの接続関係を含む各ノードの状態に基づいて各ノードに階層及び階級を与えることにより、各グラフの構造がツリー構造に変換される。ツリー構造は、一定の秩序に従って階層化されたものであるため、ツリー構造に変換されたグラフを比較すれば、両者が同一であるか否かを確実かつ短時間に判定することができる。
【００１７】
また、各グラフは、各ノードの階層及び階級がノード間で重複しないようにツリー構造に変換される。このようにすれば、ノードを１対１で比較する際のノードの組み合わせの数を最小限に留めることができる。この結果、グラフの比較判定に要する時間をさらに短縮することができる。
【００１８】
以上のように、本発明によれば、２つのグラフの同型性を確実かつ短時間に判定することができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施形態に係るグラフ同型性判定装置の構成を示すブロック図である。
【図２】図２（Ａ）及び図２（Ｂ）は、比較対象となるグラフの一例を示す図である。
【図３】ツリー構造の一例を示す図である。
【図４】図４（Ａ）は、隣接ノードとのリンク毎のスコアのフォーマットを示す図である。図４（Ｂ）は、隣接ノードの相対位置関係に基づくスコアの要素の値を説明するための図である。図４（Ｃ）は、リンクの向きに基づくスコアの要素の値を説明するための図（その１）である。図４（Ｄ）は、リンクの向きに基づくスコアの要素の値を説明するための図（その２）である。
【図５】図５（Ａ）は、あるノードについて求められるスコアの一例を示す図である。図５（Ｂ）は、図５（Ａ）のノードのスコアの一例を示す図である。図５（Ｃ）は、トータルスコアの算出方法を説明するための図である。
【図６】図６（Ａ）は、同じレベルにおける各ノードの仮ランクの設定例を示す図である。図６（Ｂ）は、図６（Ａ）のスコアが重複するノードがある場合の各ノードの仮ランクの設定例を示す図である。
【図７】図１のグラフ同型性判定装置の動作のフローチャートである。
【図８】図７のレベルスイープ処理の詳細を示すフローチャートである。
【図９】ランクの算出過程を示す図（その１）である。
【図１０】ランクの算出過程を示す図（その２）である。
【図１１】ランクの算出過程を示す図（その３）である。
【図１２】ランクが重複した場合の処理の一例を示す図（その１）である。
【図１３】ランクが重複した場合の処理の一例を示す図（その２）である。
【図１４】図１のグラフ同型性判定装置の適用例を示すブロック図である。
【図１５】図１５（Ａ）は、水分子の模式図である。図１５（Ｂ）は、水分子の水素結合を模したノードとリンクを示す図である。図１５（Ｃ）、図１５（Ｄ）は、水クラスタを模したグラフを示す図である。
【発明を実施するための形態】
【００２０】
この発明の実施の形態について、図面を参照して詳細に説明する。
【００２１】
図１には、本実施形態に係るグラフ同型性判定装置１００の構成が示されている。このグラフ同型性判定装置１００は、２つのグラフの同型性を判定する装置、すなわち、２つのグラフが同一であるか否かを判定する装置である。
【００２２】
図２（Ａ）、図２（Ｂ）には、比較されるグラフの一例として、それぞれグラフＧ１、Ｇ２が示されている。図２（Ａ）及び図２（Ｂ）に示すように、グラフＧ１、Ｇ２は、複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される。
【００２３】
グラフ同型性判定装置１００は、ＣＰＵ及びメモリ（いずれも不図示）を備えるコンピュータである。ＣＰＵがメモリに記憶されたプログラムを実行することにより、グラフ同型性判定装置１００の各種構成要素の機能が実現される。
【００２４】
図１に示すように、グラフ同型性判定装置１００は、ツリー変換部１０と、比較判定部１１と、を備える。
【００２５】
ツリー変換部１０は、２つのグラフを入力する。ツリー変換部１０は、グラフの各ノードに対して階層（レベル）及び階級（ランク）を付与することにより、図３に示すように、２つのグラフの構造を各ノードの階層及び階級に基づくツリー構造に変換する。本実施形態では、階層化されたツリー構造の階層をレベルと呼び、同一のレベルにおけるノードの階級をランクと呼ぶ。
【００２６】
この際、ツリー変換部１０は、リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて、複数のノード各々のレベル及びランクをノード間で重複しないように与える。
【００２７】
比較判定部１１は、ツリー変換部１０によりツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する。比較判定部１１は、その判定結果を出力する。この判定結果を参照すれば、入力された２つのグラフが同一であるか否かを確認することができる。
【００２８】
ツリー変換部１０のさらなる詳細な構成について説明する。
【００２９】
図１に示すように、ツリー変換部１０は、ノード階層化部２０と、ランク算出部２１と、収束判定部２２と、ランク調整部２３と、ツリー評価部２４と、記憶部３０と、を備える。
【００３０】
ノード階層化部２０は、グラフに含まれる複数のノードの中からルートノードを選択する。例えば、図３では、ノードＡが、ルートノードとして選択されている。選択されるノードは任意でよい。
【００３１】
ノード階層化部２０は、リンクで接続された他のノードとの接続関係に基づいて、各ノードのレベルを設定する。ルートノードはレベル１となる。続いて、ノード階層化部２０は、ルートノードとして選択されたノードに直接リンクされたノードをレベル２のノードとして選択する。さらに、レベル２のノードとして選択されたノードに直接リンクされたノードをレベル３のノードとして選択する。このようにして、各レベルのノードが選択される。
【００３２】
例えば、図３に示す例であれば、ルートノードであるノードＡとリンクを介して接続しているノードＢ、Ｃ、Ｄ、Ｅがレベル２のノードとなる。さらに、ノードＢ、Ｃ、Ｄ、Ｅにリンクを介して接続しているノードＦ、Ｇ、Ｈ、Ｉがレベル３のノードとなる。このようにして、各ノードのレベルが設定され、基本的な木構造が設定される。
【００３３】
ランク算出部２１は、各ノードのランク（仮ランク）を仮に算出する処理を、ツリー構造のレベルの昇順及び降順に繰り返す。
【００３４】
ランク算出部２１における各ノードの仮ランクは、リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて算出される。各ノードの状態は、所定の規則に従って数値化される。ランク算出部２１は、数値化された各ノードの状態の大小関係に応じて、同一の階層におけるすべてのノードの階級を算出する。
【００３５】
より具体的には、この各ノードの状態は、まず、スコアと呼ばれる１次元のベクトルに変換される。図４（Ａ）に示すように、スコアの要素の数は、３又は４つである。
【００３６】
要素の数が３つであるスコアは、上下のレベルに跨ったリンクにおける各ノードの状態の数値化に用いられる。
【００３７】
このスコアの１番目の要素の値は、ツリー構造において隣接する他のノードの相対位置関係を示している。例えば、図４（Ｂ）に示すように、この要素の値は、ランクの算出対象となるノード（黒丸）に対して隣接するノード（白丸）が上のレベルである場合には３となり、同じレベルである場合には２となり、下のレベルである場合には１となる。また、そのノード自身のスコアでは、１番目の要素の値は０となる。
【００３８】
続いて、このスコアの２番目の要素は、リンクの向きを表している。図４（Ｃ）に示すように、この要素の値は、リンクが上のレベルから下のレベルに向いている場合には１となり、リンクが下のレベルから上のレベルに向いている場合には０となる。また、そのノード自身のスコアでは、２番目の要素の値は０となる。
【００３９】
続いて、このスコアの３番目の要素は、隣接するノードのランクを示している。ここで、この要素の値は、ランクが小さければ小さいほど大きくなっている。また、各ノード自身のスコアでは、３番目の要素の値は、そのノード自身のランクに基づく値となる。
【００４０】
続いて、要素の数が４つであるスコアは、同一のレベルのノード同士のリンクを対象として用いられる。
【００４１】
このスコアの１番目の要素の値は、隣接するノードの相対位置関係を表し、２番目の要素がリンクの向きを表しているのは、上述のスコアと同じである。ただし、図４（Ｄ）に示すように、２番目の要素の値は、リンクがランクの算出対象に向いているときには１となり、反対を向いているときには０となる。
【００４２】
さらに、このスコアの３番目の要素の値はリンクの始点のランクであり、このスコアの４番目の要素の値はリンクの終点のランクである。
【００４３】
ランク算出部２１は、ランクの算出対象である各ノードについて、リンク毎に、上記スコアを求める。
【００４４】
例えば、図５（Ａ）に示すように、あるノード（仮ランクｍ）について、３つの隣接ノード（それぞれの仮ランクｎ１、ｎ２、ｎ３）がそれぞれ接続しているものとする。この場合、図５（Ｂ）に示すように、各リンクについて、（３、１、ｎ１）、（２、１、ｎ２、ｍ）、（１、１、ｎ３）という３つのスコアが求められ、そのノード自身のスコアとして、（０、０、ｍ）が求められる。なお、（２、１、ｎ２、ｍ）は、（２、０、ｍ、ｎ２）であってもよい。
【００４５】
ランク算出部２１は、各ノードについて求められたスコアを、スカラー量に変換する。スカラー量は、例えば、各要素の値を各桁の値として昇順に並べることにより生成される。例えば、最上位の数桁の値を１番目の要素の値とし、続く数桁の値を２番目の要素の値とし、続く数桁の値を３番目の要素の値とし、最下位の数桁の値を４番目の要素の値とすることにより、１つのスカラー量が生成される。
【００４６】
例えば、図５（Ｂ）に示すように、（３、１、ｎ１）は、３００１０００００００００００００（ｎ１）という数値に変換される。また、（２、１、ｎ２、ｍ）は、２００１０００００（ｎ２）０００００００（ｍ）という数値に変換される。さらに、（１、１、ｎ３）は、１００１０００００００００００００（ｎ３）という数値に変換される。さらに、（０、０、ｍ）は、０００００００００００００００００（ｍ）という数値に変換される。ｎ１、ｎ２、ｎ３、ｍには、その数値に対応する値が挿入される。
【００４７】
続いて、ランク算出部２１は、スカラー量に変換されたスコアを大きさに従ってソートして、各桁の数値として昇順に並べることにより生成されるスカラー量を、トータルスコアとして求める。例えば、図５（Ｃ）に示すように、スコア１＞スコア２＞スコア３＞スコア４である場合には、ランク算出部２１は、大きい桁の方からスコア１→スコア２→スコア３→スコア４の順に並べ、それらを合成することにより形成される数値をトータルスコアとして算出する。
【００４８】
ランク算出部２１は、同一レベルの全てのルートについてこのトータルスコアを求め、同じレベルにある全てのノードのトータルスコアを比較することにより、そのレベルにおける各ノードの仮ランクを算出する。
【００４９】
このとき、ランク算出部２１は、各ノードのランクを仮に算出する処理を、各レベルで行う際に、同一のレベルにおける各ノードの仮ランクの変動が収束するまで、そのレベルにおける各ノードのランクの算出を繰り返す。
【００５０】
例えば、図６（Ａ）に示すように、同じレベルにノードＡ乃至Ｄがあり、それぞれのトータルスコアＳＡ乃至ＳＤが算出され、それぞれのトータルスコアにＳＡ＞ＳＢ＞ＳＣ＞ＳＤの関係があったとする。この場合、ランク算出部２１は、ノードＡの仮ランクをランク１とし、ノードＢの仮ランクをランク２とし、ノードＣの仮ランクをランク３とし、ノードＤの仮ランクをランク４とする。
【００５１】
なお、場合によっては、同一のレベルにスコアが重複するノードが存在することがある。例えば、図６（Ｂ）に示すように、それぞれのスコアの関係がＳＡ＞ＳＢ＝ＳＣ＞ＳＤとなっている場合、ランク算出部２１は、ノードＡの仮ランクをランク１とし、ノードＢの仮ランクをランク２とし、ノードＣの仮ランクをランク２とし、ノードＤの仮ランクをランク４とする。ノードＢ、Ｃの仮ランクは、後述するように、調整される可能性があるため、ノードＤの仮ランクは、その調整の余裕を確保すべく、３ではなく４に設定される。
【００５２】
ランク算出部２１は、このようなノードの仮ランクの算出を、最上位レベルから降順に最下位のレベルまで行った後、今度は、最下位のレベルから昇順に最上位のレベルまで行い、各レベルの各ノードの仮ランクの算出を繰り返す。
【００５３】
収束判定部２２は、ランク算出部２１によって算出された各ノードの仮ランクの変動が収束したか否かを、ランク算出部２１による階級算出の終了条件として判定する。収束判定部２２で各ノードの仮ランクが収束したと判定されたときの各ノードの仮ランクが最終的なそのノードのランクとなる。
【００５４】
ランク調整部２３は、同一の階層の各ノードの仮ランクが互いに異なるように、各ノードの仮ランクを調整する。ランク調整部２３は、同一のレベルにおける各ノードの仮ランクが逆転することのないように、各ノードの仮ランクを調整する。例えば、図６（Ｂ）に示すように、ノードＣ、Ｄの仮ランクが重複している場合には、一方のノードＣの仮ランクが２から３に変更される。なお、この場合、ノードＢの仮ランクを２から３に変更するようにしてもよい。
【００５５】
ルート変換部１０は、ランク算出部２１による仮ランクの算出と、収束判定部２２による判定と、ランク調整部２３による調整と、を同一のレベルにおいてランクが重複するノードがなくなるまで繰り返す。これにより、各グラフを、あるノードをルートノードとして設定したときのツリー構造に変換することができる。ルート変換部１０は、上述のようなツリー構造への変換を、ルートノードを変更しながら繰り返し行う。このようにして、ルート変換部１０は、各グラフを、Ｍ（ノードの数）通りのツリー構造に変換する。
【００５６】
ツリー評価部２４は、Ｍ通りのツリー構造各々について、レベル及び仮ランクに基づく評価値を算出し、その評価値が最大となるツリー構造を、Ｍ通りのツリー構造の中から選択する。より具体的には、ツリー評価部２４は、各ツリー構造について、各ノードのレベルとランクとを一列に並べることにより生成される数値を算出し、例えば、その数値が一番大きいツリー構造をそのグラフのツリー構造、すなわちグラフ間の比較に用いられるツリー構造として選択する。比較判定部１１には、この選択されたツリー構造が出力され、２つのグラフの比較に用いられる。
【００５７】
記憶部３０は、入力された２つのグラフのデータや、ノード階層化部２０、ランク算出部２１、ランク調整部２３で生成されるデータを必要に応じて記憶する。
【００５８】
次に、本実施形態に係るグラフ同型性判定装置１００の動作について説明する。
【００５９】
図７、図８には、グラフ同型性判定装置１００の動作のフローチャートが示されている。グラフ同型性判定装置１００では、２つのグラフが入力され、その情報が記憶部３０に記憶される。続いて、グラフ同型性判定装置１００は、まず一方のグラフについて、図７、図８に示す処理を開始する。
【００６０】
図７に示すように、まず、ノード階層化部２０は、ルートノードを決定する（ステップＳ１）。
【００６１】
この場合、ルートノードとして選択されるノードは、まだ選択されていないもののうち、任意のものでよい。ここでは、すでに選択されたノードはないので、すべてのノードの中から任意のノードが選択される。
【００６２】
続いて、ノード階層化部２０は、他のノードとの接続関係に基づいて、各ノードのレベルを設定する（ステップＳ２）。これにより、このグラフのツリー構造の全体のレベル数（階層数）Ｎmaxが明らかになる。各ノードのレベル及びレベル数Ｎmaxは、記憶部３０に記憶される。
【００６３】
続いて、ランク算出部２１は、各ノードに仮ランクを付与し、付与した仮ランクの値を記憶部３０に記憶する（ステップＳ３）。付与される仮ランクは、任意の数値でよいが、本実施形態では、全てのノードに仮ランクとして０を付与するものとする。
【００６４】
続いて、ランク算出部２１は、レベルカウンタＮを１に初期化し、極変数ｐを１に初期化する（ステップＳ４）。この極変数ｐは、＋１か−１かのいずれかの値をとる。
【００６５】
続いて、ランク算出部２１は、レベルカウンタＮにｐを加算する（ステップＳ５）。ここで、ｐ＝＋１なので、レベルカウンタＮは１インクリメントされる。
【００６６】
続いて、ランク算出部２１は、レベルＮのレベルスイープ処理のサブルーチンを実行する（ステップＳ６）。
【００６７】
図８には、このレベルスイープ処理の詳細が示されている。図８に示すように、ランク算出部２１は、記憶部３０から、レベルＮの各ノードの情報を読み出す（ステップＳ２１）。
【００６８】
続いて、ランク算出部２１は、読み出した各ノードの情報から、各ノードの仮ランクを抽出して、記憶部３０の別の領域に記憶する（ステップＳ２２）。
【００６９】
続いて、ランク算出部２１は、各ノードのリンクごとのスコアを算出する（ステップＳ２３）。例えば、ここで、図５（Ｂ）に示すように、スコア１乃至３（ベクトル）が算出される。
【００７０】
続いて、ランク算出部２１は、各ノードのスコアをスカラー変換する（ステップＳ２４）。例えば、ここで、図５（Ｂ）に示すように、スコア１乃至３がスカラー量に変換される。
【００７１】
続いて、ランク算出部２１は、スカラー変換された各スコアを、その大きさに従ってソートして、その順番にスコアを合成することにより、トータルスコアを算出する（ステップＳ２５）。例えば、ここで、図５（Ｃ）に示すように、スコア１、２、３が昇順にソートされ、その順番に合成されてトータルスコアが算出される。
【００７２】
続いて、ランク算出部２１は、レベルＮの各ノードのトータルスコアの大小関係に基づいて、レベルＮの各ノードの仮ランクを設定する（ステップＳ２６）。例えば、ここで、図６（Ａ）に示すように、トータルスコアＳＡ、ＳＢ、ＳＣ、ＳＤの大小関係に基づいて、ノードＡ、Ｂ、Ｃ、Ｄの仮ランク１、２、３、４が設定される。
【００７３】
続いて、ランク算出部２１は、上記ステップＳ２２で記憶部３０に記憶された仮ランクと、上記ステップＳ２６で算出された仮ランクとを比較して、それらに変化が無いか否かを判定する（ステップＳ２７）。
【００７４】
この判定が否定されると（ステップＳ２７；Ｎｏ）、ランク算出部２１は、ステップＳ２２に戻る。ランク算出部２１は、記憶部３０に記憶された各ノードの仮ランクを、ステップＳ２６で算出された仮ランクに更新する（ステップＳ２２）。以降、ステップＳ２７における判定が肯定されるまで（ステップＳ２７；Ｙｅｓ）、ステップＳ２２→Ｓ２３→Ｓ２４→Ｓ２５→Ｓ２６→Ｓ２７が繰り返される。
【００７５】
ステップＳ２２で記憶部３０に記憶され更新された仮ランクと、上記ステップＳ２６で算出された仮ランクとを比較して、それらに変化がないと判定されると（ステップＳ２７；Ｙｅｓ）、ランク算出部２１は、レベルスイープ処理を終了する。
【００７６】
続いて、ランク算出部２１は、ランクを算出するレベルが最下層まで到達し、レベルカウンタＮがＮmax又は１であるか否かを判定する（ステップＳ７）。この判定が否定されると（ステップＳ７；Ｎｏ）、ランク算出部２１は、ステップＳ５に戻る。
【００７７】
以降、ランクの算出対象となるレベルが最下層まで到達しない限り（ステップＳ７；Ｎｏ）、ランク算出部２１は、ステップＳ５→Ｓ６→Ｓ７を繰り返し、各レベルでのレベルスイープ処理を行う。
【００７８】
ランクの算出対象となるレベルが最下層になり、レベルカウンタＮがＮmaxになると（ステップＳ７；Ｙｅｓ）、ランク算出部２１は、各ノードの仮ランクを記憶部３０に記憶する（ステップＳ８）。ここで、ランク算出部２１は、上記ステップＳ３で記憶された仮ランクが記憶された領域とは、別の領域に仮ランクを記憶する。
【００７９】
続いて、ランク算出部２１は、極変数ｐに−１を乗算する（ステップＳ９）。ここで、ｐ＝１であったので、乗算の結果、極変数ｐは−１となる。
【００８０】
続いて、収束判定部２２は、前回記憶した仮ランク（ステップＳ３で記憶した仮ランク）と、今回記憶した仮ランク（ステップＳ８で記憶した仮ランク）とに差異がなく、各ノードの仮ランクの変動が収束しているか否かを判定する（ステップＳ１０）。この判定が否定されると（ステップＳ１０；Ｎｏ）、ツリー変換部１０は、ステップＳ５に戻る。ここでは、ステップＳ３で記憶された仮ランクはすべて０であり、両者が一致することはないので、判定は否定され（ステップＳ１０；Ｎｏ）、ツリー変換部１０は、ステップＳ５に戻る。
【００８１】
続いて、ランク算出部２１は、レベルカウンタＮにｐを加算する（ステップＳ５）。ここで、ｐ＝−１となっているので、実際には、レベルカウンタＮは１デクリメントされる。
【００８２】
続いて、ランク算出部２１は、レベルＮのレベルスイープ処理のサブルーチンを実行する（ステップＳ６）。なお、このレベルスイープ処理については、すでに説明したので、詳細な説明を省略する（図８参照）。
【００８３】
続いて、ランク算出部２１は、レベルカウンタＮがＮmax又は１であるか否かを判定する（ステップＳ７）。この判定が否定されれば（ステップＳ７；Ｎｏ）、ランク算出部２１は、ステップＳ５に戻る。
【００８４】
ランクの算出対象となるレベルが最上位レベルまで到達しない限り、すなわちレベルカウンタＮが１とならない限り（ステップＳ７；Ｎｏ）、ランク算出部２０は、ステップＳ５→Ｓ６→Ｓ７を繰り返し、各レベルでのレベルスイープ処理を行う。
【００８５】
ランクの算出対象となる階層が最上位レベルになると（ステップＳ７；Ｙｅｓ）、ランク算出部２１は、各ノードの仮ランクを記憶部３０に記憶する（ステップＳ８）。この際に、上記ステップＳ８で記憶された仮ランクとは、別の領域に仮ランクが記憶される。
【００８６】
続いて、ランク算出部２１は、極変数ｐに−１を乗算する（ステップＳ９）。ここで、ｐ＝−１であったので、乗算の結果、極変数ｐは１となる。
【００８７】
続いて、収束判定部２２は、前回のステップＳ８で記憶された仮ランクと、今回のステップＳ８で記憶された仮ランクとに差異がないか、すなわち、各ノードの仮ランクの変動が収束しているか否かを判定する（ステップＳ１０）。この判定が否定されれば（ステップＳ１０；Ｎｏ）、ツリー変換部１０は、ステップＳ５に戻る。
【００８８】
以降、各ノードの仮ランクの変動が収束していると判定されるまで（ステップＳ１０；Ｙｅｓ）、ステップＳ５からステップＳ１０の処理が繰り返される。
【００８９】
本実施形態では、このようにして、ランク算出部２１が、レベルの降順及び昇順に、各レベルのノードのランク算出を繰り返すことにより、各ノードの仮ランクを収束させる。
【００９０】
仮ランクの変動が収束すると（ステップＳ１０；Ｙｅｓ）、ランク調整部２３は、同じレベルに仮ランクが重複するノードが無いか否かを判定する（ステップＳ１１）。ランクが重複するノードが有る場合（ステップＳ１１；Ｎｏ）、ランク調整部２３は、そのレベルのノードの仮ランクを再調整する（ステップＳ１２）。具体的には、ランク調整部２３は、同一のレベルのノードの仮ランクが互いに異なるように、各ノードの仮ランクを調整する。
【００９１】
例えば、図６（Ｂ）に示す例では、同じレベルに仮ランクが重複するノードＢ、Ｃが存在する。この場合には、ランク調整部２３は、例えば、ノードＣをランク３に変更すれば、同一の階層のノードの仮ランクが互いに異なるように、各ノードの仮ランクを調整することができる。
【００９２】
なお、ＳＢ＝ＳＣであるため、ノードＢをランク３とし、ノードＣをランク２としてもよい。すなわち、いずれのノードの仮ランクを変更してもよい。
【００９３】
ただし、ノードＢ、Ｃの仮ランクは、ノードＢ、Ｃよりもトータルスコアの高いノードＡのランク１と、ノードＢ、Ｃよりもトータルスコアの低いノードＤのランク４との間とする必要がある。すなわち、本実施形態では、ランク調整部２３は、同一のレベルにおける各ノードの仮ランクが逆転することのないように、各ノードの仮ランクを調整する。
【００９４】
ステップＳ１２実行後、ツリー変換部１０は、ステップＳ５に戻る。以降ステップＳ４〜ステップＳ１１が繰り返される。そして、再び、収束判定部２２が、記憶した仮ランクの変化が無いと判定されると（ステップＳ１０；Ｙｅｓ）、ランク調整部２３は、同じレベルに仮ランクが重複するノードが無いか否かを判定する（ステップＳ１１）。仮ランクが重複するノードが有る場合（ステップＳ１１；Ｎｏ）、前述のように、仮ランクの再調整が行われ（ステップＳ１２）、仮ランク算出及び収束判定（ステップＳ５〜Ｓ１１）が繰り返される。
【００９５】
同じレベルにランクが重複するノードが無くなると（ステップＳ１１；Ｙｅｓ）、収束判定部２２は、各ノードの仮ランクを最終的なランクとして記憶部３０に記憶する（ステップＳ１３）。
【００９６】
続いて、ツリー変換部１０は、グラフを、Ｍ通りのツリー構造に変換したか否かを判定する（ステップＳ１４）。ここでは、まだ１通りのツリー構造にしか変換されていないので判定は否定され（ステップＳ１４；Ｎｏ）、ツリー変換部１０は、ステップＳ１に戻る。
【００９７】
以降、ステップＳ１からステップＳ１４までの処理が繰り返され、各グラフが、各ノードをそれぞれルートノードとするＭ通りのツリー構造に変換される。Ｍ通りのツリー構造に変換されたと判定されると（ステップＳ１４；Ｙｅｓ）、ツリー評価部２４は、Ｍ通りのツリー構造の中から、最適な１つのツリー構造を選択する（ステップＳ１５）。
【００９８】
より具体的には、ツリー評価部２４は、各ツリー構造について、例えば、次のような、レベルとランクの組み合わせから成るベクトルを各ノードについて生成する。
（レベル１、ランク＊）、（レベル２、ランク＊）、（レベル３、ランク＊）、・・・
【００９９】
続いて、ツリー評価部２４は、各ノードについて生成されたベクトルを、例えばレベル順、ランク順に１列に並べた結合行列を生成し、その結合行列を、上述と同様にして、スカラー量に変換する。さらに、ツリー評価部２４は、そのスカラー量が最大となるツリー構造を、最終的なツリー構造として選択する（ステップＳ１６）。
【０１００】
続いて、ツリー変換部１０は、各ノードのレベル及びランクを含むツリー構造情報を出力する（ステップＳ１６）。ステップＳ１６終了後、ツリー変換部１０は、処理を終了する。
【０１０１】
上述のように、ステップＳ５〜Ｓ１０の繰り返しにおいて、例えば、図９に示すように、まず、レベル２のノードの仮ランクが設定される。この場合、レベル２の２つのノードは、互いに他のノードの接続形態が同一であるため、仮ランクは同じ１となる。そして、続いて、図１０に示すように、レベル３のノードの仮ランク（１と２）が設定され、レベル４のノードの仮ランク１が設定される。
【０１０２】
さらに、ステップＳ５〜Ｓ１０の繰り返しにおいて、レベル３のノードの仮ランク（１と２）が設定され、続いてレベル２のノードの仮ランクが設定される。ここで、図１１に示すように、レベル２の右側のノードの仮ランクは、１から２に変更される。このように、仮ランクの算出を、レベルの昇順及び降順に繰り返すことにより、各ノードの仮ランクが収束していく。この処理は、ツリースイープ処理ともいうべきものである。
【０１０３】
また、図１２に示すように、例えばレベル２のノードの中に、仮ランク１で重複しているノードがある場合、ランク調整部２３は、図１３に示すように、一方のノードの仮ランクを、２に変更することにより仮ランクを調整する。この後、再び、仮ランクの算出が、レベルの昇順及び降順に繰り返される。
【０１０４】
ツリー変換部１０は、入力した２つのグラフ各々について、ステップＳ１乃至Ｓ１６の処理を実行する。これにより、ツリー変換部１０から２つのグラフ各々に対応するツリー構造情報が出力される。各グラフについて出力されるツリー構造情報は１つだけである。
【０１０５】
比較判定部１１は、入力した２つのツリー構造情報に基づいて、２つのグラフが一致するか否かを判定する。個々のツリー構造は、レベルやランクの重複するノードが存在しないので、比較するノードの組み合わせの数を少なくすることができる。
【０１０６】
以上詳細に説明したように、本実施形態によれば、他のノードとの接続関係に基づいて各ノードにレベル及びランクを与えることにより、各グラフがツリー構造に変換される。各グラフのツリー構造は、一定の秩序に従って階層化されているため、両者が同一であるか否かを確実かつ短時間に判定することができる。
【０１０７】
また、このツリー構造は、各ノードのレベル及びランクがノード間で重複しないように生成される。このようにすれば、ノードを１対１で比較する際のノードの組み合わせの数を最小限に留めることができる。この結果、ツリー構造の比較判定に要する時間を短縮することができる。
【０１０８】
以上のように、本実施形態によれば、２つのグラフの同型性を確実かつ短時間に判定することができる。
【０１０９】
また、本実施形態によれば、比較対象となるツリー構造を各グラフにつき１つずつとすることができるので、同型性の判定に要する時間を短縮することができる。
【０１１０】
なお、これまで、グラフ理論における同型性判定問題の最悪計算量Ｏ（ｎ）は、Ｂａｂａｉらによると、次式のようになる。
【０１１１】
【数１】
【０１１２】
しかしながら、本実施形態に係るグラフ同型性判定装置１００を用いれば、最悪計算量Ｏ（ｎ）は、次式のようになる。
【０１１３】
【数２】
【０１１４】
この最悪計算量Ｏ（ｎ）は、ツリースイープの計算量ｎ・ｌｏｇ（ｎ）に、すべてのノードのランクが重複しなくなるまでの回数と、最悪の場合に生成されなければならないツリーの数を考慮して求められたものである。
【０１１５】
上記式（２）の最悪計算量Ｏ（ｎ）は、上記式（１）の最悪時間量Ｏ（ｎ）よりも少ない。したがって、本実施形態に係るグラフ同型性判定装置１００によれば、より短時間に、グラフの同型性を判定することができる。
【０１１６】
ところで、ノード数が１４であるグラフの一致不一致をコンピュータに判定させた場合、グラフをそのまま比較した場合には１８０分を要したのに対し、本実施形態に係るグラフ同型性判定装置１００にてツリー構造に変換されたグラフを比較したときに要した時間は、３秒であった。
【０１１７】
なお、本実施形態に係るグラフ同型性判定装置１００は、閉路を有するグラフであってもよい。また、このグラフ同型性判定装置１００は、有向グラフであっても、無向グラフであっても、適用が可能である。無向グラフの場合には、ノード間に、逆向きの２つのリンクが接続されているものとみなして、スコアを求めるようにすればよい。
【０１１８】
本実施形態に係るグラフ同型性判定装置１００は、様々な用途に適用可能である。
【０１１９】
例えば、グラフ同型性判定装置１００を、図１４に示すような、データベースシステム２００に適用可能である。図１４に示すように、データベースシステム２００は、化合物データベース４０と、管理部４１と、を備える。データベース４０には、化学構造式をグラフ化した多数の化合物データが登録されている。管理部４１は、データベース４０に登録された化合物の化学構造式のグラフを評価し、必要であればデータの追加登録や削除を行う。
【０１２０】
グラフ同型性判定装置１００は、化合物データベース４０に登録された化合物の２つのグラフを入力し、２つのグラフが同一であるか否かを判定し、その判定結果を、管理部４１に出力する。管理部４１は、２つのグラフが一致する場合に、例えば、一方のグラフを削除するか、２つのグラフを１つのグラフに統合する。このようにすれば、化合物データベース４０に登録されたデータを整理することができる。
【０１２１】
また、グラフ同型性判定装置１００を水クラスタの解析に適用することも可能である。水クラスタは、例えば図１５（Ａ）に示すように、水分子５０が水素結合で結合されることにより形成される。この水クラスタは、図１５（Ｂ）に示すように、水分子５０と水素結合のリンク５１として表現することができる。
【０１２２】
この水クラスタは、様々な形態をとる。例えば、水クラスタは、図１５（Ｃ）に示すような構造もとり得るし、図１５（Ｄ）に示すように状態も取り得る。
【０１２３】
本実施形態に係るグラフ同型性判定装置１００は、モンテカルロシミュレーションにより発生する数億個の水クラスタの１つ１つが、同一の構造を有するものであるか否かを判定し、同じ構造を有する水クラスタの分布数を求めるのに用いることができる。これにより、ある特定の条件における、図１５（Ｃ）の構造を有する水クラスタの分布数や、図１５（Ｄ）の構造を有する水クラスタの分布数などを調べることができる。
【０１２４】
このように、本実施形態に係るグラフ同型性判定装置１００は、物質の結合構造の解析評価に好適である。このグラフ同型性判定装置１００は、記憶装置に記憶された２つのグラフを比較する。管理部４１は、グラフ同型性判定装置における判定結果に基づいて、記憶装置に記憶されたグラフを評価する。
【０１２５】
また、本実施形態に係るグラフ同型性判定装置は、グラフとして表現されるものであれば、同型性の判定が可能である。例えば、人と人との間に形成される人的ネットワークの解析にも適用することが可能である。
【０１２６】
なお、上記実施形態において、実行されるプログラムは、フレキシブルディスク、ＣＤ−ＲＯＭ（Compact Disk Read-Only Memory）、ＤＶＤ（Digital Versatile Disk）、ＭＯ（Magneto-Optical Disk）等のコンピュータ読み取り可能な記録媒体に格納して配布し、そのプログラムをインストールすることにより、上述の処理を実行するシステムを構成することとしてもよい。
【０１２７】
また、プログラムをインターネット等の通信ネットワーク上の所定のサーバ装置が有するディスク装置等に格納しておき、例えば、搬送波に重畳させて、ダウンロード等するようにしてもよい。
【０１２８】
また、上述の機能を、ＯＳ（Operating System）が分担して実現する場合又はＯＳとアプリケーションとの協働により実現する場合等には、ＯＳ以外の部分のみを媒体に格納して配布してもよく、また、ダウンロード等してもよい。
【０１２９】
なお、本発明は、上記実施の形態及び図面によって限定されるものではない。本発明の要旨を変更しない範囲で実施の形態及び図面に変更を加えることができるのはもちろんである。
【産業上の利用可能性】
【０１３０】
本発明は、例えば、ＣＡＳレジストリシステム等の化学データベースに多数登録された化学物質や、水クラスタ等の物質の結合構造を示す２つのグラフの同定に有用である。この他、本発明は、人的ネットワークなど、グラフとして表現可能なあらゆるものの同定に有用である。
【符号の説明】
【０１３１】
１０ ツリー変換部
１１ 比較判定部
２０ ノード階層化部
２１ ランク算出部
２２ 収束判定部
２４ ツリー評価部
２３ ランク調整部
３０ 記憶部
４０ データベース
４１ 管理部
５０ 水分子
５１ リンク
１００ グラフ同型性判定装置
２００ データベースシステム
【特許請求の範囲】
【請求項１】
複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフの同型性を判定するグラフ同型性判定装置であって、
前記リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて、前記複数のノード各々の階層及び階級をノード間で重複しないように与えることにより、前記各グラフの構造を、前記各ノードの階層及び階級に基づくツリー構造に変換するツリー変換部と、
前記ツリー変換部によりツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する比較判定部と、
を備えるグラフ同型性判定装置。
【請求項２】
前記ツリー変換部は、
前記他のノードとの接続関係に基づいて、前記各ノードの階層を設定するノード階層化部と、
前記他のノードとの接続関係を含む各ノードの状態に基づいて、前記各ノードの階級を仮に算出する処理を、前記階層の昇順及び降順に繰り返す階級算出部と、
前記各ノードの階級の変動が収束したか否かを、前記階級算出部による階級算出の終了条件として判定する収束判定部と、
同一の階層の前記ノードの階級が互いに異なるように、前記各ノードの階級を調整する階級調整部と、
を備え、
前記階級算出部による階級算出と、前記収束判定部による判定と、前記階級調整部による調整と、を同一の階層において階級が重複する前記ノードがなくなるまで繰り返す、
ことを特徴とする請求項１に記載のグラフ同型性判定装置。
【請求項３】
前記階級算出部は、
前記各ノードの階級を仮に算出する処理を、前記各階層で行う際に、
同一の階層における前記各ノードの階級の変動が収束するまで、その階層における前記各ノードの階級の算出を繰り返す、
ことを特徴とする請求項２に記載のグラフ同型性判定装置。
【請求項４】
前記階級算出部は、
前記他のノードとの接続関係を含む各ノードの状態を、所定の規則に従って数値化し、
数値化された前記各ノードの状態の大小関係に応じて、同一の階層におけるすべてのノードの階級を算出する、
ことを特徴とする請求項２又は３に記載のグラフ同型性判定装置。
【請求項５】
前記階級算出部は、
前記ツリー構造における前記他のノードとの相対位置関係、前記リンクの向き、前記他のノードの階級を各要素とするベクトルを、前記リンクごとに生成し、
前記リンクごとに生成されたベクトルの要素を、各桁の数値として昇順に並べることにより生成される前記リンクごとのスカラー量を求め、
前記リンクごとのスカラー量を、その大きさに従ってソートして、各桁の数値として昇順に並べることにより生成されるスカラー量を前記各ノードの最終的なスコアとして求め、
前記スコアに基づいて、同一の階層のすべてのノードの階級を算出する、
ことを特徴とする請求項４に記載のグラフ同型性判定装置。
【請求項６】
前記階級調整部は、
同一の階層における前記各ノードの階級が逆転することのないように、前記各ノードの階級を調整する、
ことを特徴とする請求項２乃至４のいずれか一項に記載のグラフ同型性判定装置。
【請求項７】
前記ツリー変換部は、
前記各グラフのツリー構造への変換を、ルートノードを変更しながら前記各グラフのすべてのノードについて繰り返し行い、
変換された複数のツリー構造各々について、前記各ノードのレベル及びランクに基づく評価値をそれぞれ算出し、
前記評価値が最大となるツリー構造を、前記複数のツリー構造の中から選択し、
前記比較判定部は、
前記選択されたツリー構造を用いて、２つのグラフを比較する、
ことを特徴とする請求項１乃至６のいずれか一項に記載のグラフ同型性判定装置。
【請求項８】
複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフの同型性を判定するグラフ同型性判定方法であって、
前記リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて、前記複数のノード各々の階層及び階級をノード間で重複しないように与えることにより、前記各グラフの構造を、前記各ノードの階層及び階級に基づくツリー構造に変換するツリー変換工程と、
前記ツリー変換工程においてツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する比較判定工程と、
を含むグラフ同型性判定方法。
【請求項９】
複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフの同型性を判定するコンピュータに実行させるプログラムであって、
前記リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて、前記複数のノード各々の階層及び階級をノード間で重複しないように与えることにより、前記各グラフの構造を、前記各ノードの階層及び階級に基づくツリー構造に変換するツリー変換手順と、
前記ツリー変換手順においてツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する比較判定手順と、
を実行させるプログラム。
【請求項１０】
グラフ化された物質の結合構造を記憶する記憶装置と、
前記記憶装置に記憶された物質の結合構造を示す２つのグラフの同型性を判定する請求項１乃至７のいずれか一項に記載のグラフ同型性判定装置と、
前記グラフ同型性判定装置における判定結果に基づいて、前記記憶装置に記憶されたグラフを評価する評価装置と、
を備える評価システム。
【請求項１】
複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフの同型性を判定するグラフ同型性判定装置であって、
前記リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて、前記複数のノード各々の階層及び階級をノード間で重複しないように与えることにより、前記各グラフの構造を、前記各ノードの階層及び階級に基づくツリー構造に変換するツリー変換部と、
前記ツリー変換部によりツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する比較判定部と、
を備えるグラフ同型性判定装置。
【請求項２】
前記ツリー変換部は、
前記他のノードとの接続関係に基づいて、前記各ノードの階層を設定するノード階層化部と、
前記他のノードとの接続関係を含む各ノードの状態に基づいて、前記各ノードの階級を仮に算出する処理を、前記階層の昇順及び降順に繰り返す階級算出部と、
前記各ノードの階級の変動が収束したか否かを、前記階級算出部による階級算出の終了条件として判定する収束判定部と、
同一の階層の前記ノードの階級が互いに異なるように、前記各ノードの階級を調整する階級調整部と、
を備え、
前記階級算出部による階級算出と、前記収束判定部による判定と、前記階級調整部による調整と、を同一の階層において階級が重複する前記ノードがなくなるまで繰り返す、
ことを特徴とする請求項１に記載のグラフ同型性判定装置。
【請求項３】
前記階級算出部は、
前記各ノードの階級を仮に算出する処理を、前記各階層で行う際に、
同一の階層における前記各ノードの階級の変動が収束するまで、その階層における前記各ノードの階級の算出を繰り返す、
ことを特徴とする請求項２に記載のグラフ同型性判定装置。
【請求項４】
前記階級算出部は、
前記他のノードとの接続関係を含む各ノードの状態を、所定の規則に従って数値化し、
数値化された前記各ノードの状態の大小関係に応じて、同一の階層におけるすべてのノードの階級を算出する、
ことを特徴とする請求項２又は３に記載のグラフ同型性判定装置。
【請求項５】
前記階級算出部は、
前記ツリー構造における前記他のノードとの相対位置関係、前記リンクの向き、前記他のノードの階級を各要素とするベクトルを、前記リンクごとに生成し、
前記リンクごとに生成されたベクトルの要素を、各桁の数値として昇順に並べることにより生成される前記リンクごとのスカラー量を求め、
前記リンクごとのスカラー量を、その大きさに従ってソートして、各桁の数値として昇順に並べることにより生成されるスカラー量を前記各ノードの最終的なスコアとして求め、
前記スコアに基づいて、同一の階層のすべてのノードの階級を算出する、
ことを特徴とする請求項４に記載のグラフ同型性判定装置。
【請求項６】
前記階級調整部は、
同一の階層における前記各ノードの階級が逆転することのないように、前記各ノードの階級を調整する、
ことを特徴とする請求項２乃至４のいずれか一項に記載のグラフ同型性判定装置。
【請求項７】
前記ツリー変換部は、
前記各グラフのツリー構造への変換を、ルートノードを変更しながら前記各グラフのすべてのノードについて繰り返し行い、
変換された複数のツリー構造各々について、前記各ノードのレベル及びランクに基づく評価値をそれぞれ算出し、
前記評価値が最大となるツリー構造を、前記複数のツリー構造の中から選択し、
前記比較判定部は、
前記選択されたツリー構造を用いて、２つのグラフを比較する、
ことを特徴とする請求項１乃至６のいずれか一項に記載のグラフ同型性判定装置。
【請求項８】
複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフの同型性を判定するグラフ同型性判定方法であって、
前記リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて、前記複数のノード各々の階層及び階級をノード間で重複しないように与えることにより、前記各グラフの構造を、前記各ノードの階層及び階級に基づくツリー構造に変換するツリー変換工程と、
前記ツリー変換工程においてツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する比較判定工程と、
を含むグラフ同型性判定方法。
【請求項９】
複数のノードと、ノード間を結ぶリンクとの集合でそれぞれ構成される２つのグラフの同型性を判定するコンピュータに実行させるプログラムであって、
前記リンクで接続された他のノードとの接続関係を含む各ノードの状態に基づいて、前記複数のノード各々の階層及び階級をノード間で重複しないように与えることにより、前記各グラフの構造を、前記各ノードの階層及び階級に基づくツリー構造に変換するツリー変換手順と、
前記ツリー変換手順においてツリー構造に変換された２つのグラフを比較することにより、両者が一致するか否かを判定する比較判定手順と、
を実行させるプログラム。
【請求項１０】
グラフ化された物質の結合構造を記憶する記憶装置と、
前記記憶装置に記憶された物質の結合構造を示す２つのグラフの同型性を判定する請求項１乃至７のいずれか一項に記載のグラフ同型性判定装置と、
前記グラフ同型性判定装置における判定結果に基づいて、前記記憶装置に記憶されたグラフを評価する評価装置と、
を備える評価システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２０１２−８９８３（Ｐ２０１２−８９８３Ａ）
【公開日】平成２４年１月１２日（２０１２．１．１２）
【国際特許分類】
【出願番号】特願２０１０−１４６９１９（Ｐ２０１０−１４６９１９）
【出願日】平成２２年６月２８日（２０１０．６．２８）
【出願人】（５０４１３６５６８）国立大学法人広島大学 (924)
【Ｆターム（参考）】
【公開日】平成２４年１月１２日（２０１２．１．１２）
【国際特許分類】
【出願日】平成２２年６月２８日（２０１０．６．２８）
【出願人】（５０４１３６５６８）国立大学法人広島大学 (924)
【Ｆターム（参考）】
[ Back to top ]