(57)【要約】  推移閉包情報生成装置が、有向ハイパーグラフを取得するグラフ取得部と、前記有向ハイパーグラフのノードのうち少なくとも１つのノードについて、そのノードへ到達可能なノード集合を示す推移閉包情報を、そのノードの親ノードの推移閉包情報を用いて生成する推移閉包情報生成部と、を備える。
2019176108.tif 000002
【特許請求の範囲】
【請求項１】
有向ハイパーグラフを取得するグラフ取得部と、
前記有向ハイパーグラフのノードのうち少なくとも１つのノードについて、そのノードへ到達可能なノード集合を示す推移閉包情報を、そのノードの親ノードの推移閉包情報を用いて生成する推移閉包情報生成部と、
を備える推移閉包情報生成装置。
【請求項２】
前記有向ハイパーグラフのハイパーエッジを単エッジに置き換えた有向グラフに対するトポロジカルソートにより、前記有向ハイパーグラフのノードの順番を決定する順番決定部をさらに備え、
前記推移閉包情報生成部は、前記順番で各ノードの前記推移閉包情報を生成する、
請求項１に記載の推移閉包情報生成装置。
【請求項３】
前記推移閉包情報生成部は、前記ノード集合の要素が前記推移閉包情報における到達先のノードの祖先ノードに限定された前記推移閉包情報を生成する、
請求項１または請求項２に記載の推移閉包情報生成装置。
【請求項４】
前記推移閉包情報生成部は、前記有向ハイパーグラフの全てのノードのうち１つ以上のノードの任意の組み合わせについて、その組み合わせによる前記ノード集合から前記推移閉包情報における到達先のノードへの到達可能性を示す前記推移閉包情報を生成する、
請求項１または請求項２に記載の推移閉包情報生成装置。
【請求項５】
有向ハイパーグラフを取得する工程と、
前記有向ハイパーグラフのノードのうち少なくとも１つのノードについて、そのノードへ到達可能なノード集合を示す推移閉包情報を、そのノードの親ノードの推移閉包情報を用いて生成する工程と、
を含む推移閉包情報生成方法。
【請求項６】
コンピュータに、
有向ハイパーグラフを取得する工程と、
前記有向ハイパーグラフのノードのうち少なくとも１つのノードについて、そのノードへ到達可能なノード集合を示す推移閉包情報を、そのノードの親ノードの推移閉包情報を用いて生成する工程と、  を実行させるためのプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、推移閉包情報生成装置、推移閉包情報生成方法および記録媒体に関する。
【背景技術】
【０００２】
有向ハイパーグラフにおける到達可能性判定問題に関して、非特許文献１に記載の方法では、有向ハイパーグラフの全ノード集合に含まれている任意の部分集合を作成する。この部分集合は、到達可能性問題における始点ノード集合の候補に該当する。そして、この方法では、有向ハイパーグラフの全ノード集合に属している各ノードに関して、この部分集合（始点ノード集合の候補）に含まれている何れのノードからも到達可能であるか否かを表す情報を保持しておく。ここでは、この到達先のノードは、到達可能性問題における終点ノードの候補に該当する。また、始点ノード集合に属している何れのノードからも終点ノードに到達可能であるか否かを、単に、始点ノード集合から終点ノードへの到達可否と表記する。【０００３】
この方法では、具体的には、始点ノード集合の候補と終点ノードの候補との全ての組み合わせについて、始点ノード集合の候補から終点ノードの候補への到達可否を表形式で記憶しておく。そして、この方法では、始点ノード集合および終点ノードが与えられると、表の該当箇所を参照することで、始点ノード集合から終点ノードへの到達可否を判定する。
有向ハイパーグラフにおいては、たとえば、複数のノードに対応する事象が生じた場合（すなわち、複数の事象が共起した場合）に異なる事象が生じるという情報を、ハイパーエッジを用いて表すことができる。一方、有向グラフにおいては、複数の事象が共起するという情報を表すことはできない。従って、有向ハイパーグラフと、有向グラフとは、例えば、共起を表すことができるか否かという点に関して異なっている。尚、有向ハイパーグラフに関しては、図２から図４まで等を参照しながら後述する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Giorgio Ausiello、外１名、「Directed hypergraphs: Introduction and fundamental algorithms-A survey」、Theoretical Computer Science、２０１７年１月、Volume 658、Part B、p.293-306
【発明の概要】
【発明が解決しようとする課題】
【０００５】
有向ハイパーグラフにおける到達可能性の判定に用いるための情報を予め生成しておく場合、情報を効率よく生成できることが好ましい。
例えば、特許文献１に記載の方法では、到達可能性の判定に用いるための情報として、始点ノードの集合の候補の各々と各ノードとの全ての組み合わせについて到達可否を示す表を用意する。始点ノード集合の候補の数は、およそ２のノード数乗であり、始点ノードの集合の候補の各々と各ノードとの組み合わせの数は、およそ２のノード数乗×ノード数である。ノード数が増えると組み合わせの数が大幅に増加し、表の生成に膨大な時間を要することが考えられる。
ノード数が比較的多い場合でも、到達可能性の判定に用いるための情報を現実的な時間で得られるよう、かかる情報を効率よく生成できることが好ましい。【０００６】
本発明の目的の一例は、上述の課題を解決することのできる、推移閉包情報生成装置、推移閉包情報生成方法および記録媒体を提供することである。
【課題を解決するための手段】
【０００７】
本発明の第１の態様によれば、推移閉包情報生成装置は、有向ハイパーグラフを取得するグラフ取得部と、前記有向ハイパーグラフのノードのうち少なくとも１つのノードについて、そのノードへ到達可能なノード集合を示す推移閉包情報を、そのノードの親ノードの推移閉包情報を用いて生成する推移閉包情報生成部と、を備える。【０００８】
本発明の第２の態様によれば、推移閉包情報生成方法は、有向ハイパーグラフを取得する工程と、前記有向ハイパーグラフのノードのうち少なくとも１つのノードについて、そのノードへ到達可能なノード集合を示す推移閉包情報を、そのノードの親ノードの推移閉包情報を用いて生成する工程と、を含む。【０００９】
本発明の第３の態様によれば、記録媒体は、コンピュータに、有向ハイパーグラフを取得する工程と、前記有向ハイパーグラフのノードのうち少なくとも１つのノードについて、そのノードへ到達可能なノード集合を示す推移閉包情報を、そのノードの親ノードの推移閉包情報を用いて生成する工程と、を実行させるためのプログラムを記録した記録媒体である。
【発明の効果】
【００１０】
上記した推移閉包情報生成装置、推移閉包情報生成方法および記録媒体によれば、到達可能性の判定に用いるための情報を比較的効率よく生成できる。
【図面の簡単な説明】
【００１１】
【図１】実施形態に係る推移閉包情報生成装置の機能構成を示す概略ブロック図である。
【図２】複数のノードから１つのノードへのハイパーエッジと、１つのノードから複数のノードへのハイパーエッジとを含む有向ハイパーグラフの例を示す図である。
【図３】１つの上流側接続ノードおよび複数の下流側接続ノードに接続するハイパーエッジが置き換えられた単エッジの例を示す図である。
【図４】１つの上流側接続ノードおよび複数の下流側接続ノードに接続するハイパーエッジから、下流側接続ノードそれぞれへの単エッジへの置き換え後の有向ハイパーグラフの例を示す図である。
【図５】推移閉包行列のデータ構造の例を示す図である。
【図６】論理関数の木構造表現による推移閉包情報のデータ構造の例を示す図である。
【図７】親ノードの例を示す図である。
【図８】祖先推移閉包情報の例を示す図である。
【図９】到達先ノードに対する親ノードの構成の第１例を示す図である。
【図１０】到達先ノードに対する親ノードの構成の第２例を示す図である。
【図１１】ハイパーエッジから単エッジへの置き換え前のグラフの例を示す図である。
【図１２】ハイパーエッジから単エッジへの置き換え後のグラフの例を示す図である。
【図１３】実施形態に係る推移閉包情報生成装置が有向ハイパーグラフの各ノードについて推移閉包情報を生成する処理手順の例を示すフローチャートである。
【図１４】実施形態に係る推移閉包情報生成部が１つのノードの祖先推移閉包情報を生成する処理手順の例を示すフローチャートである。
【図１５】実施形態に係る推移閉包情報生成部が１つのノードの全推移閉包情報を生成する処理手順の例を示すフローチャートである。
【図１６】実施形態に係る推移閉包情報生成装置の構成の例を示す図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施形態を説明するが、以下の実施形態は請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
図１は、実施形態に係る推移閉包情報生成装置の機能構成を示す概略ブロック図である。図１に示すように、推移閉包情報生成装置１００は、入出力部１１０と、記憶部１８０と、制御部１９０とを備える。制御部１９０は、順番決定部１９１と、推移閉包情報生成部１９２とを備える。
【００１３】
推移閉包情報生成装置１００は、有向ハイパーグラフ（Directed Hypergraph）における推移閉包情報（Transitive Closure Information）を生成する。推移閉包情報生成装置１００は、例えばワークステーション（Workstation）またはパソコン（Personal Computer；ＰＣ）等のコンピュータを用いて構成される。
ここでいう推移閉包情報は、有向ハイパーグラフ上のノード集合（ノード（Node）の集合）から有向ハイパーグラフ上のノードへの到達可否を示す情報である。また、あるノードに対する推移閉包情報は、そのノードに到達可能なノード集合を示す情報である。
有向ハイパーグラフにおける到達可能性判定問題を解くために、推移閉包情報生成装置１００が生成する推移閉包情報を用いることができる。
推移閉包情報生成装置１００が対象とする有向ハイパーグラフおよび到達可能性問題について、図２から図４までを参照して説明する。
【００１４】
図２は、複数のノードから１つのノードへのハイパーエッジと、１つのノードから複数のノードへのハイパーエッジとを含む有向ハイパーグラフの例を示す図である。
有向ハイパーグラフでは、複数のノード間の関係をハイパーエッジ（Hyperedge）により示すことができ、さらにそれらの関係の向きを有向エッジ（Directed Edge）により示すことができる。
【００１５】
有向ハイパーグラフは、ＤＨ（Ｖ，Ｅ）の形で定義される。Ｖはノード集合を示し、Ｅはエッジの集合を示す。
Ｓ、Ｔをそれぞれノード集合として、エッジｅ∈Ｅは、ｅ＝｛Ｓ，Ｔ｝のように示される。このように、有向ハイパーグラフのエッジはノード集合とノード集合の関係で示され、ノード集合Ｓからノード集合Ｔへの方向を有している。
【００１６】
ノードｓ∈Ｓは、エッジの上流側に接続されるノードである。ノードｓ∈Ｓを上流側接続ノードと称する。ノードｔ∈Ｔは、エッジの下流側に接続されるノードである。ノードｔ∈Ｔを下流側接続ノードと称する。
図２に示される有向ハイパーグラフは、ノードＶ１からＶ１１までと、ノードをつなぐ有向のエッジとで構成されている。
【００１７】
有向ハイパーグラフのエッジは、単エッジ（Single Edge）と、ハイパーエッジ（Hyperedge）とに分類される。
単エッジは、１つのノードと１つのノードとの間の関係を示す。単エッジの場合、ｅ＝｛Ｓ，Ｔ｝の表記で、Ｓ、Ｔ共に１つのノードを要素とするノード集合である。
図２では、エッジＥ１１が単エッジの例に該当する。
【００１８】
ハイパーエッジは、１つのノードと複数ノードとの間の関係、または、複数ノードと複数ノードとの間の関係を示す。１つのノードと複数ノードとの間の関係を示すハイパーエッジは、さらに、１つの上流側接続ノードおよび複数の下流側接続ノードに接続するハイパーエッジと、複数の上流側接続ノードおよび１つの下流側接続ノードに接続するハイパーエッジとに分類される。図２では、エッジＥ１２が、複数の上流側接続ノードおよび１つの下流側接続ノードに接続するハイパーエッジの例に該当する。エッジＥ１３が、１つの上流側接続ノードおよび複数の下流側接続ノードに接続するハイパーエッジの例に該当する。
【００１９】
推移閉包情報生成装置１００が対象とする到達可能性判定問題では、始点ノード集合と終点ノードとを与えられ、始点ノード集合から終点ノードへ到達可能か否かを判定する。ここでいう始点ノード集合から終点ノードへ到達可能とは、始点ノード集合の少なくとも１つの部分集合から終点ノードへ到達可能であることである。
１つまたは複数の始点ノードが始点ノード集合として与えられるのに対し、与えられる終点ノードの数は１つである。
【００２０】
推移閉包情報生成装置１００が対象とする到達可能性判定問題では、複数の上流側接続ノードおよび１つの下流側接続ノードに接続するハイパーエッジは、「and」条件（共起）を示す。具体的には、全ての上流側接続ノードに到達可能な場合、かつ、この場合に限り、このハイパーエッジを通って下流側接続ノードに到達可能である。
一方、１つの上流側接続ノードおよび複数の下流側接続ノードに接続するハイパーエッジは、このハイパーエッジを通って上流側接続ノードからいずれの下流側接続ノードへも到達可能であることを示す。
また、推移閉包情報生成装置１００は、非巡回（Acyclic）有向ハイパーグラフを対象とする。すなわち、推移閉包情報生成装置１００は、グラフ理論における閉路（Cycle）のない有向ハイパーグラフにおける推移閉包情報を生成する。以下では、非巡回有向ハイパーグラフを単に有向ハイパーグラフと称する。
【００２１】
推移閉包情報生成装置１００が対象とする到達可能性判定問題は、グラフ理論における基本的かつ重要な問題の一つであり、幅広い応用が可能である。一つの例として、与えられた１つ以上の化合物を化学反応させて、１つの目的の化合物を生成可能か否かを判定すること問題が挙げられる。例えば、化学反応のデータベースを有向ハイパーグラフの形式で用意しておき、与えられた１つ以上の化合物を始点ノード集合とし、目的の化合物を終点ノードとする。これにより、目的の化合物を生成可能か否かの問題を到達可能性判定問題として解くことができる。
【００２２】
推移閉包情報生成装置１００が対象とする有向ハイパーグラフで、１つの上流側接続ノードおよび複数の下流側接続ノードに接続するハイパーエッジは、下流側接続ノードそれぞれへの単エッジに置き換えることができる。
図３は、１つの上流側接続ノードおよび複数の下流側接続ノードに接続するハイパーエッジが置き換えられた単エッジの例を示す図である。図３は、図２のエッジＥ１３が単エッジに置き換えられた例を示している。図２のエッジＥ１３が、ノードＶ７からノードＶ９およびＶ１０へのハイパーエッジであるのに対し、図３では、ノードＶ７からノードＶ９への単エッジと、ノードＶ７からノードＶ１０への単エッジとが設けられている。これらの単エッジにて、エッジＥ１３の場合と同様、ノードＶ７からノードＶ９およびＶ１０のいずれへも到達可能であることが示されている。
【００２３】
このように、１つの上流側接続ノードおよび複数の下流側接続ノードに接続するハイパーエッジから、下流側接続ノードそれぞれへの単エッジへ、等価な置き換えを行うことができる。複数の上流側接続ノードおよび複数の下流側接続ノードに接続するハイパーエッジの場合は、下流側接続ノード毎に、複数の上流側接続ノードおよびその下流側接続ノードに接続するハイパーエッジに置き換えることができる。
【００２４】
図４は、１つの上流側接続ノードおよび複数の下流側接続ノードに接続するハイパーエッジから、下流側接続ノードそれぞれへの単エッジへの置き換え後の有向ハイパーグラフの例を示す図である。図４は、図２の有向ハイパーグラフにて、エッジＥ１３を、図３のように単エッジに置き換えた例を示している。
置き換え後の有向ハイパーグラフでは、いずれのハイパーエッジも複数の上流側接続ノードおよび１つの下流側接続ノードに接続している。すなわち、置き換え後の有向ハイパーグラフは、複数の下流側接続ノードに接続しているハイパーエッジを含まない。
【００２５】
推移閉包情報生成装置１００は、このように、いずれのハイパーエッジも複数の上流側接続ノードおよび１つの下流側接続ノードに接続している有向ハイパーグラフにおける推移閉包情報を生成する。すなわち、推移閉包情報生成装置１００は、ノードと１つ以上のノードから１つのノードへのエッジとで構成される有向ハイパーグラフでの推移閉包情報を生成する。
【００２６】
一般的な有向ハイパーグラフは、その有向ハイパーグラフと等価な有向ハイパーグラフ、かつ、ハイパーエッジが、複数の上流側接続ノードおよび１つの下流側接続ノードに接続しているハイパーエッジに限定された有向ハイパーグラフに変換可能である。従って、推移閉包情報生成装置１００は、一般的な有向ハイパーグラフにおける到達可能性問題を解くための推移閉包情報を生成することができる。ここでいう一般的な有向ハイパーグラフは、ハイパーエッジが必ずしも複数の上流側接続ノードおよび１つの下流側接続ノードに接続しているハイパーエッジに限定されない有向ハイパーグラフである。
【００２７】
推移閉包情報生成装置１００が、上記のエッジの置き換えを行うようにしてもよい。あるいは、推移閉包情報生成装置１００が、いずれのハイパーエッジも複数の上流側接続ノードおよび１つの下流側接続ノードに接続している有向ハイパーグラフを、他の装置等から取得するようにしてもよい。
以下では、複数の上流側接続ノードおよび１つの下流側接続ノードに接続しているハイパーエッジを、単にハイパーエッジと称する。
【００２８】
次に、図５および図６を参照して、推移閉包情報について説明する。
以下では、推移閉包情報における到達先のノードを到達先ノードと称する。到達先ノードは、推移閉包情報にて、ノード集合からそのノードへの到達可否を示されるノードである。また、推移閉包情報が示す到達の可否にて出発地点となっているノード集合を出発元ノード集合と称する。
推移閉包情報は、出発元ノード集合から到達先ノードへの到達可否を示す情報である。また、あるノードに対する推移閉包情報は、そのノードを到達先ノードとして、到達先ノードに到達可能な出発元ノード集合を示す情報である。
【００２９】
推移閉包情報の表現方法の１つとして、推移閉包情報を行列の形式で示すことができる。行列の形式で示される推移閉包情報を推移閉包行列と称する。
図５は、推移閉包行列のデータ構造の例を示す図である。図５の例で、｜ｖ｜（｜ｖ｜は正整数）は、有向ハイパーグラフにおけるノードの数を示す。ｖ１からｖ｜ｖ｜までは、それぞれノードを示す。
図５に示す推移閉包行列は、ノードｖ１からｖ｜ｖ｜までと一対一に対応付けられる｜ｖ｜個の列を有する。また、図５に示す推移閉包行列は、とり得る全てのノード集合から空集合φを除いたノード集合（ｖ１）から（ｖ１，ｖ２，ｖ３，・・・，ｖ｜ｖ｜）までと一対一に対応付けられる２｜ｖ｜−１個の行を有する。
【００３０】
図５に示す推移閉包行列の各要素には、行に対応付けられたノード集合から、列に対応付けられたノードへの到達可能性を示す情報が格納される。行に対応付けられたノード集合から、列に対応付けられたノードへ到達可能であることを要素の値「１」で示し、到達不可能であることを要素の値「０」で示すようにしてもよい。
【００３１】
推移閉包情報のもう１つの表現方法として、到達ノード毎の推移閉包情報を論理関数の形式で示すことができる。また、この論理関数を木構造の形式で示すことができる。さらには、この論理関数の木構造表現をグラフ的に縮約（Reduce）した形式にて示すことができる。推移閉包情報生成装置１００が、これらの形式のいずれかの推移閉包情報を生成するようにしてもよい。
図６は、論理関数の木構造表現による推移閉包情報のデータ構造の例を示す図である。図６では、推移閉包情報を二分決定木（Binary Decision Tree）の形式で表現した例が示されている。
【００３２】
図６の二分決定木の中間ノードに示される「ｖｉ」（ｉは、１≦ｉ≦｜ｖ｜の正整数）は、有向ハイパーグラフのノードｖｉが出発元ノード集合に含まれていることを示す。「¬ｖｉ」は、有向ハイパーグラフのノードｖｉが出発元ノード集合に含まれていないことを示す。
葉（Leaf）の値「１」は、出発元ノード集合から到達先ノードへ到達可能であることを示す。葉の値「０」は、出発元ノード集合から到達先ノードへ到達不可であることを示す。
【００３３】
推移閉包情報の二分決定木表現を、出発元ノード集合に従って根（Root）から葉へ辿ることで、出発元ノード集合から到達先ノードへの到達可否を「１」または「０」で示す情報を得られる。この二分決定木表現を辿る具体的方法は、以下のようになる。
根から出発して、有向ハイパーグラフのノードｖ１が出発元ノード集合に含まれていれば、二分決定木の「ｖ１」のノードへ進む。有向ハイパーグラフのノードｖ１が出発元ノード集合に含まれていなければ、二分決定木の「¬ｖ１」のノードへ進む。
【００３４】
さらに、有向ハイパーグラフのノードｖ２が出発元ノード集合に含まれていれば、二分決定木の「ｖ２」のノードへ進む。有向ハイパーグラフのノードｖ２が出発元ノード集合に含まれていなければ、二分決定木の「¬ｖ２」のノードへ進む。
このように、有向ハイパーグラフのノードｖｉ（ｉは、１≦ｉ≦｜ｖ｜の正整数）が出発元ノード集合に含まれていれば、二分決定木の「ｖｉ」のノードへ進む。有向ハイパーグラフのノードｖｉが出発元ノード集合に含まれていなければ、二分決定木の「¬ｖｉ」のノードへ進む。この処理を有向ハイパーグラフのノードｖ｜ｖ｜まで順に繰り返し、二分決定木の「ｖ｜ｖ｜」のノードまたは「¬ｖ｜ｖ｜」のノードに到達する。
【００３５】
到達したノードとエッジで対応付けられている葉から、到達可否の情報を読み出す。
この場合、有向ハイパーグラフのノードが出発元ノードに含まれているか否かの判定を｜ｖ｜回行うことになり、｜ｖ｜のオーダーの処理（Ｏ（｜ｖ｜））で、到達可否の情報を得られる。
【００３６】
また、ＢＤＤ（Binary Decision Diagram）およびＺＤＤ（Zero-suppressed Binary Decision Diagram）など、二分決定木をグラフ的に縮約して効率的に表記する既存技術がある。例えば、ＢＤＤでは、二分決定木における冗長なノードを削除し、等価なノードを共有とすることで、二分決定木をグラフ的に縮退する。
これらの既存技術を用いることで、推移閉包情報記憶部２８１が推移閉包情報を記憶するために必要な記憶容量が比較的少なくて済むことが期待される。
【００３７】
また、連長圧縮法（Run Length Encoding）等の圧縮技術では、データを読み出すためにデータを解凍する必要がある。これに対し、ＢＤＤおよびＺＤＤでは、二分決定木を縮退して得られたグラフを辿る際、データを解凍する必要はない。このように、到達可能性判定装置２００では、論理関数の木構造表現をグラフ的に縮退した推移閉包情報を用いることで、処理の効率化と、記憶容量の低減との両立を図ることができる。
【００３８】
推移閉包情報の二分決定木表現は、１つの到達先ノードに対する推移閉包情報を論理関数の形式で表現し、その論理関数を二分決定木の形式で表現することで得られる。
式（１）は、１つの到達先ノードに対する推移閉包情報の論理関数表現の例を示す。
【００３９】
【数１】
2019176108.tif 000003
【００４０】
式（１）では、１つの到達先ノードに対する推移閉包情報が積和標準形で示されている。１つの出発元ノード集合に含まれる全てのノードの論理積をとり、出発元ノード集合毎に得られた論理積の論理和をとることで、１つの到達先ノードに対する推移閉包情報の積和標準形による表現を得られる。ここで得られる積和標準形の論理関数には、否定リテラルは含まれない。
【００４１】
式（１）の左辺の「ａ」、「ｃ」、「ａｂ」、「ａｂｃ」は、それぞれノード集合｛ａ｝、｛ｃ｝、｛ａ，ｂ｝、｛ａ，ｂ，ｃ｝を示している。これらのノード集合の各々は、到達先ノードへ到達可能な出発元ノード集合を示している。
式（１）の右辺では、「ａ」、「ｃ」、「ａ∧ｂ」、「ａ∧ｂ∧ｃ」が、それぞれノード集合｛ａ｝、｛ｃ｝、｛ａ，ｂ｝、｛ａ，ｂ，ｃ｝を示している。これら「ａ」、「ｃ」、「ａ∧ｂ」、「ａ∧ｂ∧ｃ」が「∨」で接続されて積和標準形の論理関数を形成している。
【００４２】
式（１）は、｛ａ，ｂ，ｃ｝の部分集合を要素とする集合を示している。言い換えれば、式（１）は、ノードａ、ｂ、ｃの３つのノードから任意個を選んだ組み合わせの集合を要素とする集合を示している。このように、ｎ個（ｎは正整数）のアイテムから任意個を選ぶ組み合わせを要素とする集合を、組み合わせ集合と称する。組み合わせ集合は、式（１）の例のように積和標準形の論理関数で示すことができる。
【００４３】
また、組み合わせ集合ＰとＱとの和集合をＰ∪Ｑと表記する。例えば、組み合わせ集合｛ａ，ｃ，ａｂｃ｝と｛ｂ，ａｂｃ｝との和集合は、式（２）のように示される。
【００４４】
【数２】
2019176108.tif 000004
【００４５】
また、組み合わせ集合ＰとＱとの共通集合をＰ∩Ｑと表記する。例えば、組み合わせ集合｛ａ，ａｂ，ａｂｃ｝と｛ｂ，ａｂｃ｝との共通集合は、式（３）のように示される。
【００４６】
【数３】
2019176108.tif 000005
【００４７】
また、組み合わせ集合ＰとＱとの直積集合をＰ＊Ｑと表記する。例えば、組み合わせ集合｛ａ，ｂ｝と{λ，ｂｃ}との直積集合は、式（４）のように示される。
【００４８】
【数４】
2019176108.tif 000006
【００４９】
λは、直積集合の演算「＊」における単位元として作用する要素である。任意の集合Ｓｅｔに対し、Ｓｅｔ＊｛λ｝＝Ｓｅｔである。
【００５０】
推移閉包情報の二分決定木表現は、例えば、有向ハイパーグラフのノードに対応する二分決定木を作っておき、得られた積和標準形の各項に基づいて葉の値を決定することで得られる。
具体的には、図６の例のように、有向ハイパーグラフのノードｖ１、ｖ２、ｖ３、・・・、ｖ｜ｖ｜の有無に応じて分岐する二分決定木を生成する。上記の積和標準形の論理関数の各項は、二分決定木の根から葉への経路のいずれか１つに相当する。そこで、二分決定木の葉のうち、相当する項がある葉の値を「１」にし、相当する項がない葉の値を「０」にする。
【００５１】
入出力部１１０は、他の装置と通信を行う。特に、入出力部１１０は、グラフ取得部の例に該当し、推移閉包情報生成装置１００が推移閉包情報を生成する対象の有向ハイパーグラフを取得する。例えば、推移閉包情報生成装置１００に対するクライアント装置が、推移閉包情報の生成要求に有向ハイパーグラフのデータを含めて送信し、入出力部１１０が、その生成要求を受信するようにしてもよい。
【００５２】
但し、入出力部１１０が有向ハイパーグラフを取得する方法は、他の装置から通信で取得する方法に限定されない。例えば、入出力部１１０が、ＵＳＢ（Universal Serial Bus）ポートなど外部メモリの接続を受けるインタフェースを有し、外部メモリから有向ハイパーグラフを取得するようにしてもよい。あるいは、入出力部１１０が、例えばキーボードおよびマウス等の入力デバイスを備え、ユーザ操作にて有向ハイパーグラフの入力を受けるようにしてもよい。
【００５３】
また、入出力部１１０は、推移閉包情報生成装置１００が生成した推移閉包情報を、要求元のクライアント装置など他の装置へ送信する。あるいは、推移閉包情報生成装置１００が外部メモリの接続を受けるインタフェースを有し、推移閉包情報を外部メモリへ書き込むようにしてもよい。あるいは、推移閉包情報生成装置１００自らが到達可能性判定問題を解くなど、推移閉包情報生成装置１００の内部で推移閉包情報を使用するようにしてもよい。この場合、入出力部１１０が推移閉包情報を推移閉包情報生成装置１００の外部へ出力する必要はない。
【００５４】
記憶部１８０は、各種データを記憶する。例えば、推移閉包情報生成装置１００が有向ハイパーグラフのノード毎に推移閉包情報を生成し、記憶部１８０が、推移閉包情報をノードと対応付けて記憶するようにしてもよい。
記憶部１８０は、到達可能性判定装置２００が備える記憶デバイスを用いて構成される。
制御部１９０は、推移閉包情報生成装置１００の各部を制御して各種処理を行う。制御部１９０は、推移閉包情報生成装置１００が備えるＣＰＵ（Central Processing Unit、中央処理装置）が記憶部１８０からプログラムを読み出して実行することで実現される。
【００５５】
推移閉包情報生成部１９２は、推移閉包情報の生成を実行する。特に、推移閉包情報生成部１９２は、有向ハイパーグラフのノードのうち少なくとも１つのノードについて、そのノードへ到達可能なノード集合を示す推移閉包情報を、そのノードの親ノード（Parent Node）の推移閉包情報を用いて生成する。
あるノードの親ノードとは、そのノードに隣接する（Adjacent）祖先ノード（Ancestor Node）である。あるノードの祖先ノードとは、そのノードへの道（Path）が存在するノードである。従って、あるノードの祖先ノードは、そのノードへの道の上流側に位置する。また、１つのエッジの上流側接続ノードは、そのエッジの下流側接続ノードの親ノードに該当する。
あるノード自らも、そのノードの祖先ノードに該当するものとする。
【００５６】
図７は、親ノードの例を示す図である。図７の例で、ノードａから１つのエッジを経由してノードｄに至る。従って、ノードａはノードｄの親ノードに該当する。親ノードは祖先ノードの一種なので、ノードａはノードｄの祖先ノードである。
また、ノードｃからは、ノードａを経由してノードｄに至る道がある。従って、ノードｃはノードａの祖先ノードである。
図７の例で、ノードｃ、ａのそれぞれがノードｄの祖先ノードである。
【００５７】
道にハイパーエッジが含まれる場合、到達可能性判定問題で到達可能と判定されるためには、そのハイパーエッジの全ての上流側接続ノードに到達可能である必要がある。これに対し、祖先の関係または親の関係に関しては、ハイパーエッジの上流側接続ノードの何れか１つへの道があればよく、全ての上流側接続ノードに到達可能である必要はない。言い換えれば、あるノードｘの祖先ノードは、図１１および１２を参照して後述するようにハイパーエッジを単エッジに置き換えたグラフで、ノードｘを終端とする道の始点となり得る任意のノードである。
図７の例で、ノードｄはノードｉの親ノードである。ノードｅもノードｉの親ノードである。また、ノードｃ、ａ、ｄ、ｅのそれぞれがノードｉの祖先ノードである。
【００５８】
推移閉包情報生成部１９２が、ノード集合の要素が推移閉包情報における到達先のノードの祖先ノードに限定された推移閉包情報を生成するようにしてもよい。ノード集合の要素が推移閉包情報における到達先のノードの祖先ノードに限定された推移閉包情報を、祖先推移閉包情報と称する。
【００５９】
図８は、祖先推移閉包情報の例を示す図である。図８では、図７のノードｄの祖先推移閉包情報の木構造表現の例を示している。
図７のグラフでノードｄの先祖ノードはノードｃ、ａ、ｄの各々である。これに対応して、図８の木は、ノード「ｃ」、「¬ｃ」、「ａ」、「¬ａ」、「ｄ」、「¬ｄ」の各々のを有している。ノード「ｃ」は、出発元ノード集合にノードｃが含まれることを示す。ノード「¬ｃ」は、出発元ノード集合にノードｃが含まれないことを示す。ノード「ａ」は、出発元ノード集合にノードａが含まれることを示す。ノード「¬ａ」は、出発元ノード集合にノードａが含まれないことを示す。ノード「ｄ」は、出発元ノード集合にノードｄが含まれることを示す。ノード「¬ｄ」は、出発元ノード集合にノードｄが含まれないことを示す。
【００６０】
図７の例では、ノードｃ、ａ、ｄのうち何れか１つ以上が出発元ノード集合に含まれていることが、ノードｄに到達可能であるための必要十分条件である。これに対応して、図８の木の葉のうち、根からノード「¬ｃ」、「¬ａ」、「¬ｄ」を経由して至る葉のみ値が「０」になっており、それ以外の葉の何れも値が「１」になっている。
【００６１】
また、図７の例で、祖先ノード以外のノードであるノードｅからノードｘまでは、そのノードが出発元ノード集合に含まれているか否かがノードｄへの到達可能性に影響しない。
このように、到達先ノードの祖先ノード以外のノードは、そのノードが出発元ノード集合に含まれているか否かが到達先ノードへの到達可能性に影響しないドントケア（Don't Care）として扱うことができる。これにより、祖先推移閉包情報を用いて、祖先ノードに限らず有向ハイパーグラフの任意のノードを要素とする出発元ノード集合から到達先ノードへの到達可能性を示すことができる。
【００６２】
例えば、出発元ノート集合に対して到達先ノードの祖先ノードを抽出するフィルタリングを行うことで、到達先ノードの祖先ノードに要素が限定された出発元ノード集合を得られる。この場合、フィルタリング前の出発元ノード集合から到達先ノードへの到達可能性は、フィルタリング後の出発元ノード集合から到達先ノードへの到達可能性と同じである。従って、フィルタリング後の出発元ノード集合を祖先推移閉包情報に適用することで、フィルタリング前の出発元ノード集合から到達先ノードへの到達可能性を知ることができる。
【００６３】
あるいは、推移閉包情報生成部１９２が、有向ハイパーグラフの全てのノードの部分集合の各々から到達先ノードへの到達可能性を示す推移閉包情報を生成するようにしてもよい。すなわち、推移閉包情報生成部１９２が、有向ハイパーグラフの全てのノードのうち１つ以上のノードの任意の組み合わせについて、その組み合わせによるノード集合から到達先のノードへの到達可能性を示す推移閉包情報を生成するようにしてもよい。
【００６４】
有向ハイパーグラフの全てのノードのうち１つ以上のノードの任意の組み合わせについて、その組み合わせによるノード集合から到達先のノードへの到達可能性を示す推移閉包情報を、全推移閉包情報と称する。  ｘを有向ハイパーグラフにおける任意のノードとして、ノードｘの全推移閉包情報をａｌｌｃｏｍｂ（ｘ）と表記する。例えば、図７のノードｄの全推移閉包情報ａｌｌｃｏｍｂ（ｄ）は、式（５）のように示される。
【００６５】
【数５】
2019176108.tif 000007
【００６６】
また、ノードｘの祖先推移閉包情報をｃｏｍｂ（ｘ）と表記する。例えば、図７のノードｄの祖先推移閉包情報ｃｏｍｂ（ｄ）は、式（６）のように示される。
【００６７】
【数６】
2019176108.tif 000008
【００６８】
推移閉包情報生成部１９２が、到達先ノードの親ノードの祖先推移閉包情報を用いて到達先ノードの祖先推移閉包情報を生成するようにしてもよい。
図９は、到達先ノードに対する親ノードの構成の第１例を示す図である。図９の例で、ノードｘは、推移閉包情報生成部１９２が祖先推移閉包情報を生成する対象の到達先ノードである。ノードｘを下流側接続ノードとして、エッジｅ１からｅｍまで（ｍは正整数）がノードｘに接続している。エッジｅｊ（ｊは、１≦ｊ≦ｍの正整数）が単エッジである場合、エッジｅｊの上流側接続ノードは１つであり、これを「ｔｊ（ｅｊ）」と表記する。エッジｅｊがハイパーエッジである場合、エッジｅｊの上流側接続ノードの数をｎ（ｎは、ｎ≧２の正整数）として、上流側接続ノードを「ｔ１（ｅｊ）」、・・・、「ｔｎ（ｅｊ）」と表記する。
【００６９】
推移閉包情報生成部１９２は、以下のようにしてノードｘの祖先推移閉包情報ｃｏｍｂ（ｘ）を生成することができる。
ノードｘの入次数０の場合、推移閉包情報生成部１９２は、ｃｏｍｂ（ｘ）を式（７）のように算出する。
【００７０】
【数７】
2019176108.tif 000009
【００７１】
ノードの入次数とは、そのノードを下流側接続ノードとしてそのノードに接続するエッジの数である。従ってノードｘの入次数０は、ノードｘに到達する道が１つも存在しないことを示す。
一方、ノードｘの入次数が１以上である場合、推移閉包情報生成部１９２は、ｃｏｍｂ（ｘ）を式（８）のように算出する。
【００７２】
【数８】
2019176108.tif 000010
【００７３】
図９を参照して説明したように、ｍはエッジの数を示す。
Π（Ａ）は、集合Ａのべき集合を示す。
ａｎｃ（ｘ）は、祖先ノードの集合からノードｘを除いた集合を示す。すなわち、ａｎｃ（ｘ）の説明においてはノードｘの祖先ノードにノードｘ自らを含まないものとして、ａｎｃ（ｘ）はノードｘの祖先ノードを示す。
式（８）におけるエッジｅｊをｅと表記し、エッジｅの上流側接続ノードの数を｜ｅ｜と表記して、「＊ｉ＝１｜ｅ｜ｃｏｍｂ’（ｔｉ（ｅ））」は、式（９）のように示される。
【００７４】
【数９】
2019176108.tif 000011
【００７５】
また、「＊ｊ＝１｜ｅ｜ｃｏｍｂ’（ｔｉ（ｅ））」をＳｊで表して、「∨ｊ＝１ｍＳｊ」は、式（１０）のように示される。
【００７６】
【数１０】
2019176108.tif 000012
【００７７】
ｃｏｍｂ’（ｔｉ（ｅ））は、式（１１）のように示される。
【００７８】
【数１１】
2019176108.tif 000013
【００７９】
ｃｏｍｂ（ｔｉ（ｅｊ））は、ノードｔｉ（ｅｊ）の祖先ノードからノードｔｉ（ｅｊ）を除いたノードを出発元ノード集合の対象とした場合の、ノードｔｉ（ｅｊ）に到達可能なノード集合を示す。ｃｏｍｂ’（ｔｉ（ｅｊ））は、ノードｘの祖先ノードからノードｘを除いたノードを出発元ノード集合の対象とした場合の、ノードｔｉ（ｅｊ）に到達可能なノード集合を示す。推移閉包情報生成部１９２は、式（１１）の演算にて、ｃｏｍｂ（ｔｉ（ｅｊ））に基づいてｃｏｍｂ’（ｔｉ（ｅｊ））を算出する。
【００８０】
そして、推移閉包情報生成部１９２は、式（８）の「＊ｉ＝１｜ｅｊ｜ｃｏｍｂ’（ｔｉ（ｅｊ））」の演算にて、エッジｅｊを経由可能なノード集合を算出する。特に、推移閉包情報生成部１９２は、エッジｅｊがハイパーエッジである場合に、エッジｅｊの全ての上流側接続ノードに到達可能なノード集合を算出する。
【００８１】
そして、推移閉包情報生成部１９２は、式（８）の「∨ｊ＝１ｍ＊ｉ＝１｜ｅｊ｜ｃｏｍｂ’（ｔｉ（ｅｊ））」の演算にて、何れか１つ以上のエッジを経由してノードｘに到達可能なノード集合を算出する。
また、推移閉包情報生成部１９２は、式（８）の「Π（ａｎｃ（ｘ））＊｛ｘ｝の演算にて、ノードｘに到達可能なノード集合のうちノードｘ自身を含むノード集合を算出する。
【００８２】
そして、推移閉包情報生成部１９２は、式（８）の「∨」に示されるように、何れか１つ以上のエッジを経由してノードｘに到達可能なノード集合と、ノードｘに到達可能なノード集合のうちノードｘ自身を含むノード集合とを組み合わせることで、ノードｘの祖先推移閉包情報ｃｏｍｂ（ｘ）を算出する。
なお、祖先推移閉包情報を求める演算で、１つの集合内に同じノードまたは同じノード集合が現れた場合は、同一のものなので統合する。具体的には、同じノードまたは同じノード集合のうちいずれか１つを残して他を削除する。例えば、推移閉包情報生成部１９２は、演算結果が｛・・・，ｘ，ｘ，・・・｝となった場合、この演算結果を｛・・・，ｘ，・・・｝に更新する。
【００８３】
図１０に示す例を用いて、推移閉包情報生成部１９２が祖先推移閉包情報を生成する処理について、より具体的に説明する。
図１０は、到達先ノードに対する親ノードの構成の第２例を示す図である。図１０の例で、ノードｘは、推移閉包情報生成部１９２が祖先推移閉包情報を生成する対象の到達先ノードである。エッジＥ３１とエッジＥ３２とが、ノードｘを下流側接続ノードとしてノードｘに接続している。エッジＥ３１は、ノードａおよびｂを上流側接続ノードとするハイパーエッジである。エッジＥ３２は、ノードｃを上流側接続ノードとする単エッジである。
従って、ノードａ、ｂ、ｃの各々が、ノードｘの親ノードである。
ノードａの入次数を０として、ノードａの祖先推移閉包情報ｃｏｍｂ（ａ）が式（１２）のように示されるものとする。
【００８４】
【数１２】
2019176108.tif 000014
【００８５】
ノードｂの入次数を０として、ノードｂの祖先推移閉包情報ｃｏｍｂ（ｂ）が式（１３）のように示されるものとする。
【００８６】
【数１３】
2019176108.tif 000015
【００８７】
ノードｃの入次数を０として、ノードｃの祖先推移閉包情報ｃｏｍｂ（ｃ）が式（１４）のように示されるものとする。
【００８８】
【数１４】
2019176108.tif 000016
【００８９】
この場合、推移閉包情報生成部１９２は、ｃｏｍｂ’（ａ）を式（１５）のように算出する。
【００９０】
【数１５】
2019176108.tif 000017
【００９１】
また、推移閉包情報生成部１９２は、ｃｏｍｂ’（ｂ）を式（１６）のように算出する。
【００９２】
【数１６】
2019176108.tif 000018
【００９３】
また、推移閉包情報生成部１９２は、ｃｏｍｂ’（ｃ）を式（１７）のように算出する。
【００９４】
【数１７】
2019176108.tif 000019
【００９５】
推移閉包情報生成部１９２は、ｃｏｍｂ’（ａ）、ｃｏｍｂ’（ｂ）およびｃｏｍｂ’（ｃ）を用いて、ｃｏｍｂ（ｘ）を式（１８）のように算出する。
【００９６】
【数１８】
2019176108.tif 000020
【００９７】
あるいは、推移閉包情報生成部１９２が、到達先ノードの親ノードの全推移閉包情報を用いて到達先ノードの全推移閉包情報を生成するようにしてもよい。
推移閉包情報生成部１９２が到達先ノード（ノードｘ）の全推移閉包情報ａｌｌｃｏｍｂ（ｘ）を生成する場合、例えば以下のようにする。
ノードｘの入次数０の場合、推移閉包情報生成部１９２は、ａｌｌｃｏｍｂ（ｘ）を、有向ハイパーグラフの全てのノードを要素とする集合の部分集合のうち、ノードｘを含む全ての部分集合の集合とする。この場合、ａｌｌｃｏｍｂ（ｘ）は、式（１９）のように示される。
【００９８】
【数１９】
2019176108.tif 000021
【００９９】
Ｓａｌｌは、有向ハイパーグラフの全てのノードの集合である。
一方、ノードｘの入次数が１以上である場合、推移閉包情報生成部１９２は、ａｌｌｃｏｍｂ（ｘ）を式（２０）のように算出する。
【０１００】
【数２０】
2019176108.tif 000022
【０１０１】
式（２０）で、「∨ｊ＝１ｍ」および「＊ｉ＝１｜ｅｊ｜」は、式（８）の場合と同様である。
全推移閉包情報の場合、到達先ノードが何れのノードであっても、有向ハイパーグラフの全てのノードが、出発元ノード集合の対象となっている。従って、祖先推移閉包情報の場合にｃｏｍｂからｃｏｍｂ’を算出するような、出発元ノード集合の対象の変更は生じない。そこで、推移閉包情報生成部１９２は、ａｌｌｃｏｍｂ（ｔｉ（ｅｊ））をそのまま式（２０）の右辺に用いて、ａｌｌｃｏｍｂ（ｘ）を算出する。
【０１０２】
推移閉包情報生成部１９２は、式（２０）の「＊ｉ＝１｜ｅｊ｜ａｌｌｃｏｍｂ（ｔｉ（ｅｊ））」の演算にて、エッジｅｊを経由可能なノード集合を算出する。特に、推移閉包情報生成部１９２は、エッジｅｊがハイパーエッジである場合に、エッジｅｊの全ての上流側接続ノードに到達可能なノード集合を算出する。
【０１０３】
そして、推移閉包情報生成部１９２は、式（２０）の「∨ｊ＝１ｍ＊ｉ＝１｜ｅｊ｜ａｌｌｃｏｍｂ（ｔｉ（ｅｊ））」の演算にて、何れか１つ以上のエッジを経由してノードｘに到達可能なノード集合を算出する。
また、推移閉包情報生成部１９２は、式（２０）の「Π（Ｓａｌｌ＼｛ｘ｝）＊｛ｘ｝の演算にて、ノードｘに到達可能なノード集合のうちノードｘ自身を含むノード集合を算出する。
【０１０４】
そして、推移閉包情報生成部１９２は、式（２０）の「∨」に示されるように、何れかの１つ以上のエッジを経由してノードｘ自身を含まないノード集合と、ノードｘに到達可能なノード集合のうちノードｘ自身を含むノード集合とを組み合わせることで、ノードｘの祖先推移閉包情報ｃｏｍｂ（ｘ）を算出する。
なお、祖先推移閉包情報の場合と同様、全推移閉包情報を求める演算で、１つの集合内に同じノードまたは同じノード集合が現れた場合は、同一のものなので統合する。具体的には、推移閉包情報生成部１９２は、同じノードまたは同じノード集合のうちいずれか１つを残して他を削除する。
【０１０５】
順番決定部１９１は、有向ハイパーグラフのノードの順番を決定する。推移閉包情報生成部１９２は、順番決定部１９１が決定した順番で、各ノードの祖先推移閉包情報または全推移閉包情報を生成する。
順番決定部１９１は、有向ハイパーグラフのノードの順番を、祖先ノードが先になる順番に決定する。これにより、推移閉包情報生成部１９２は、到達先ノードの全ての親ノードについて祖先推移閉包情報または全推移閉包情報が得られた状態で、到達先ノードの祖先推移閉包情報または全推移閉包情報を生成することができる。
【０１０６】
順番決定部１９１がノードの順番を決定する方法として、トポロジカルソート（Topological Sort）を用いることができる。トポロジカルソートは、単エッジの有向グラフのノードの順番を決定するための公知の方法である。
トポロジカルソートを用いるために、順番決定部１９１は、有向ハイパーグラフのハイパーエッジを単エッジの組み合わせに置き換える。
【０１０７】
図１１は、ハイパーエッジから単エッジへの置き換え前のグラフの例を示す図である。図１１に示すグラフは、エッジＥ４１などハイパーエッジを含んでいる。
図１２は、ハイパーエッジから単エッジへの置き換え後のグラフの例を示す図である。図１２は、図１１に示すグラフのハイパーエッジを単エッジに置き換えた例を示している。例えば、図１１のエッジＥ４１は、図１２ではエッジＥ５１とＥ５２とに置き換えられている。このように、ハイパーエッジを、その上流側接続ノードから下流側接続ノードへの、上流側接続ノードの数と同数の単エッジに置き換えることで、親の関係を保ってエッジを置き換えることができる。
【０１０８】
順番決定部１９１は、例えば、エッジの置き換え後のグラフにトポロジカルソートを適用して、ノードの順番を式（２１）に示される順番に決定する。
【０１０９】
【数２１】
2019176108.tif 000023
【０１１０】
このように、順番決定部１９１は、有向ハイパーグラフのハイパーエッジを単エッジに置き換えた有向グラフに対するトポロジカルソートにより、有向ハイパーグラフのノードの順番を決定する。推移閉包情報生成部１９２は、順番決定部１９１が決定した順番で各ノードの推移閉包情報を生成する。  推移閉包情報生成部１９２が式（１７）に示される順番で祖先推移閉包情報または全推移閉包情報を生成することで、全ての親ノードについて祖先推移閉包情報または全推移閉包情報がある状態で、祖先推移閉包情報または全推移閉包情報を生成することができる。例えば、推移閉包情報生成部１９２がノードｉの祖先推移閉包情報を生成する際、親ノードであるノードｄ、ｅ、ｈの何れについても祖先推移閉包情報を生成済みである。
【０１１１】
但し、順番決定部１９１がノードの順番を決定する方法は、トポロジカルソートを用いる方法に限定されない。順番決定部１９１がノードの順番を決定する方法は、祖先ノードに先の順番が割り当てられる方法であればよい。
【０１１２】
次に、図１３から図１５までを参照して、推移閉包情報生成装置１００の動作について説明する。図１３は、推移閉包情報生成装置１００が有向ハイパーグラフの各ノードについて推移閉包情報を生成する処理手順の例を示すフローチャートである。
図１３の処理で、入出力部１１０は、有向ハイパーグラフを取得する（ステップＳ１１）。順番決定部１９１は、ステップＳ１１で得られた有向ハイパーグラフのノードをソートする（ステップＳ１２）。ここでいうソートは、ノードの順番付けを行うことである。順番決定部１９１が、有向ハイパーグラフのノードをトポロジカルソートするようにしてもよい。
【０１１３】
次に、制御部１９０は、有向ハイパーグラフの各ノードに対する処理を行うループＬ１を開始する（ステップＳ１３）。制御部１９０は、ループＬ１で、有向ハイパーグラフの各ノードを、順番決定部１９１によるソートの順番で処理する。ループＬ１で処理対象になっているノードを対象ノードと称する。
ループＬ１の処理で、推移閉包情報生成部１９２は、対象ノードの推移閉包情報を生成する（ステップＳ１４）。
【０１１４】
そして、制御部１９０は、ループＬ１の終端処理を行う（ステップＳ１５）。具体的には、制御部１９０は、有向ハイパーグラフの全てのノードに対してループＬ１の処理を完了したか否かを判定する。未処理のノードがあると制御部１９０が判定した場合、処理がステップＳ１３へ戻り、制御部１９０は、未処理のノードに対して引き続きループＬ１の処理を行う。
一方、全てのノードに対してループＬ１の処理を完了したと判定した場合、制御部１９０は、ループＬ１を終了する。
【０１１５】
制御部１９０がループＬ１を終了すると、入出力部１１０が、得られた推移閉包情報を出力する（ステップＳ１６）。
ステップＳ１６の後、制御部１９０は、図１３の処理を終了する。
【０１１６】
図１４は、推移閉包情報生成部１９２が１つのノードの祖先推移閉包情報を生成する処理手順の例を示すフローチャートである。推移閉包情報生成部１９２は、図１３のステップＳ１４で図１４の処理を行う。
図１４の処理で、推移閉包情報生成部１９２は、到達先ノードを下流側接続ノードとして到達先ノードに接続しているエッジを検出する（ステップＳ２１）。図１４の処理の説明、および、図１５の処理の説明では、到達先ノードを下流側接続ノードとして到達先ノードに接続しているエッジを、対象のエッジと称する。
【０１１７】
そして、推移閉包情報生成部１９２は、対象エッジの有無を判定する（ステップＳ２２）。
対象のエッジが無いと判定した場合（ステップＳ２２：ＮＯ）、到達先ノード（ノードｘ）の入次数は０であり、推移閉包情報生成部１９２は、式（７）を用いて祖先推移閉包情報を生成する（ステップＳ２７）。
ステップＳ２７の後、推移閉包情報生成部１９２は、図１４の処理を終了する。
【０１１８】
一方、ステップＳ２２で、対象エッジが有ると判定した場合（ステップＳ２２：ＹＥＳ）、推移閉包情報生成部１９２は、到達先ノードの親ノードの各々に対して処理を行うループＬ２を開始する（ステップＳ２３）。対象エッジの上流側接続ノードの各々が、到達先ノードの親ノードの各々に該当する。
ループＬ２の処理で、推移閉包情報生成部１９２は、式（１１）に基づいて「ｃｏｍｂ’（ｔｉ（ｅｊ））」の演算を行う（ステップＳ２４）。
【０１１９】
そして、推移閉包情報生成部１９２は、ループＬ２の終端処理を行う（ステップＳ２５）。具体的には、推移閉包情報生成部１９２は、全ての親ノードについてループＬ２の処理を完了したか否かを判定する。未処理の親ノードがあると推移閉包情報生成部１９２が判定した場合、処理がステップＳ２３へ戻り、推移閉包情報生成部１９２は、未処理の親ノードについて引き続きループＬ２の処理を行う。
一方、全ての親ノードについてループＬ２の処理を完了したと判定した場合、推移閉包情報生成部１９２は、ループＬ２を終了する。
【０１２０】
ループＬ２を終了すると、推移閉包情報生成部１９２は、式（８）の親ノード毎に算出したｃｏｍｂ’（ｔｉ（ｅｊ））を用いてｃｏｍｂ（ｘ）の演算を行う（ステップＳ２６）。
ステップＳ２６の後、推移閉包情報生成部１９２は、図１４の処理を終了する。
【０１２１】
図１５は、推移閉包情報生成部１９２が１つのノードの全推移閉包情報を生成する処理手順の例を示すフローチャートである。推移閉包情報生成部１９２は、図１３のステップＳ１４で、図１４の処理に代えて図１５の処理を行う。
図１５のステップＳ３１からＳ３２までは、図１４のステップＳ２１からＳ２２までと同様である。
【０１２２】
ステップＳ３２で対象のエッジが無いと判定した場合（ステップＳ３２：ＮＯ）、到達先ノード（ノードｘ）の入次数は０であり、推移閉包情報生成部１９２は、式（１９）を用いて全推移閉包情報ａｌｌｃｏｍｂ（ｘ）を算出する（ステップＳ３４）。この場合、推移閉包情報生成部１９２は、全推移閉包情報ａｌｌｃｏｍｂ（ｘ）を、到達先ノード（ノードｘ）を含む全ての始点ノード集合の集合に設定する。
ステップＳ３４の後、推移閉包情報生成部１９２は、図１５の処理を終了する。
【０１２３】
一方、ステップＳ３２で、対象エッジが有ると判定した場合（ステップＳ３２：ＹＥＳ）、推移閉包情報生成部１９２は、式（２０）を用いて全推移閉包情報ａｌｌｃｏｍｂ（ｘ）を算出する（ステップＳ３３）。
ステップＳ３３の後、推移閉包情報生成部１９２は、図１５の処理を終了する。
【０１２４】
以上のように、入出力部１１０は、有向ハイパーグラフを取得する。推移閉包情報生成部１９２は、得られた有向ハイパーグラフのノードのうち少なくとも１つのノードについて、そのノードへ到達可能なノード集合を示す推移閉包情報を、そのノードの親ノードの推移閉包情報を用いて生成する。
推移閉包情報生成部１９２は、親ノードの推移閉包情報を利用することで、到達可能性の判定に用いるための推移閉包情報を比較的効率よく生成できる。特に、推移閉包情報生成部１９２は、親ノードの推移閉包情報を利用せず実際に有向ハイパーグラフを辿って到達先ノードに到達可能な出発元ノード集合を検出する処理を繰り返す場合よりも、推移閉包情報を効率よく生成できる。  
【０１２５】
また、順番決定部１９１は、有向ハイパーグラフのハイパーエッジを単エッジに置き換えた有向グラフに対するトポロジカルソートにより、有向ハイパーグラフのノードの順番を決定する。推移閉包情報生成部１９２は、順番決定部１９１が決定した順番で各ノードの推移閉包情報を生成する。
これにより、推移閉包情報生成部１９２は、何れのノードの推移閉包情報を生成する場合も、そのノードに親ノードがあれば、親ノードの推移閉包情報を生成済みである。従って、推移閉包情報生成部１９２は、親ノードの推移閉包情報を利用可能であり、この点で、推移閉包情報を効率よく生成できる。  
【０１２６】
また、推移閉包情報生成部１９２は、祖先推移閉包情報を生成する。
祖先推移閉包情報は、全推移閉包情報よりも小さいデータ容量で、全推移閉包情報と同内容の情報を示すことができる。推移閉包情報生成部１９２は、祖先推移閉包情報を生成することで、必要な記憶容量が比較的小さくて済む。  
【０１２７】
また、推移閉包情報生成部１９２は、全推移閉包情報を生成する。
全推移閉包情報を用いて到達可能性の判定を行う場合、始点ノード集合から終点ノードの祖先ノードを抽出するフィルタリング処理が不要である。この点で、到達可能性の判定を行う際の処理を簡単化できる。  
【０１２８】
次に、図１６を参照して本発明の実施形態の構成について説明する。
図１６は、本発明の実施形態に係る推移閉包情報生成装置の構成の例を示す図である。図１６に示す推移閉包情報生成装置１０は、グラフ取得部１１と、推移閉包情報生成部１２とを備える。
かかる構成にて、グラフ取得部１１は、有向ハイパーグラフを取得する。推移閉包情報生成部１２は、得られた有向ハイパーグラフのノードのうち少なくとも１つのノードの推移閉包情報を、そのノードの親ノードの推移閉包情報を用いて生成する。
これにより、推移閉包情報生成装置１０は、親ノードの推移閉包情報を利用することで、推移閉包情報を比較的効率よく生成できる。特に、推移閉包情報生成装置１０は、親ノードの推移閉包情報を利用せず実際に有向ハイパーグラフを辿って到達先ノードに到達可能な出発元ノード集合を検出する処理を繰り返す場合よりも、推移閉包情報を効率よく生成できる。
【０１２９】
なお、制御部１９０の全部または一部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することで各部の処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【０１３０】
以上、本発明の実施形態を図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【産業上の利用可能性】
【０１３１】
本発明の実施形態は、推移閉包情報生成装置、推移閉包情報生成方法および記録媒体に適用してもよい。
【符号の説明】
【０１３２】
１、１００  推移閉包情報生成装置
１１  グラフ取得部
１２、１９２  推移閉包情報生成部
１１０  入出力部
１８０  記憶部
１９０  制御部
１９１  順番決定部
【図１】
2019176108.tif 000024
【図２】
2019176108.tif 000025
【図３】
2019176108.tif 000026
【図４】
2019176108.tif 000027
【図５】
2019176108.tif 000028
【図６】
2019176108.tif 000029
【図７】
2019176108.tif 000030
【図８】
2019176108.tif 000031
【図９】
2019176108.tif 000032
【図１０】
2019176108.tif 000033
【図１１】
2019176108.tif 000034
【図１２】
2019176108.tif 000035
【図１３】
2019176108.tif 000036
【図１４】
2019176108.tif 000037
【図１５】
2019176108.tif 000038
【図１６】
2019176108.tif 000039
【手続補正書】
【提出日】令和2年8月20日(2020.8.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
有向ハイパーグラフを取得するグラフ取得部と、
前記有向ハイパーグラフのノードのうち少なくとも１つのノードについて、そのノードへ到達可能なノード集合を示す推移閉包情報を、そのノードの親ノードの推移閉包情報を用いて生成する推移閉包情報生成部と、
を備える推移閉包情報生成装置。
【請求項２】
前記有向ハイパーグラフのハイパーエッジを単エッジに置き換えた有向グラフに対するトポロジカルソートにより、前記有向ハイパーグラフのノードの順番を決定する順番決定部をさらに備え、
前記推移閉包情報生成部は、前記順番で各ノードの前記推移閉包情報を生成する、
請求項１に記載の推移閉包情報生成装置。
【請求項３】
前記推移閉包情報生成部は、前記ノード集合の要素が前記推移閉包情報における到達先のノードの祖先ノードに限定された前記推移閉包情報を生成する、
請求項１または請求項２に記載の推移閉包情報生成装置。
【請求項４】
前記推移閉包情報生成部は、前記有向ハイパーグラフの全てのノードのうち１つ以上のノードの任意の組み合わせについて、その組み合わせによる前記ノード集合から前記推移閉包情報における到達先のノードへの到達可能性を示す前記推移閉包情報を生成する、
請求項１または請求項２に記載の推移閉包情報生成装置。
【請求項５】
有向ハイパーグラフを取得する工程と、
前記有向ハイパーグラフのノードのうち少なくとも１つのノードについて、そのノードへ到達可能なノード集合を示す推移閉包情報を、そのノードの親ノードの推移閉包情報を用いて生成する工程と、
を含む推移閉包情報生成方法。
【請求項６】
コンピュータに、
有向ハイパーグラフを取得する工程と、
前記有向ハイパーグラフのノードのうち少なくとも１つのノードについて、そのノードへ到達可能なノード集合を示す推移閉包情報を、そのノードの親ノードの推移閉包情報を用いて生成する工程と、
を実行させるためのプログラム。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は、推移閉包情報生成装置、推移閉包情報生成方法およびプログラムに関する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
本発明の目的の一例は、上述の課題を解決することのできる、推移閉包情報生成装置、推移閉包情報生成方法およびプログラムを提供することである。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
本発明の第３の態様によれば、プログラムは、コンピュータに、有向ハイパーグラフを取得する工程と、前記有向ハイパーグラフのノードのうち少なくとも１つのノードについて、そのノードへ到達可能なノード集合を示す推移閉包情報を、そのノードの親ノードの推移閉包情報を用いて生成する工程と、を実行させるためのプログラムである。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
上記した推移閉包情報生成装置、推移閉包情報生成方法およびプログラムによれば、到達可能性の判定に用いるための情報を比較的効率よく生成できる。
【国際調査報告】
2019176108.tif 000040
2019176108.tif 000041
2019176108.tif 000042
2019176108.tif 000043