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