(57)【要約】【課題】  視認性が高い有向グラフを、少ない処理量で生成できる有向グラフ生成方法を提供する。【解決手段】  子孫関係調査手続き１１２は、有向グラフを構成する各ノードと、各ノードの子孫ノードを対応付けた子孫関係ハッシュテーブル１２１を作成する。階層決定手続き１３１は、既に階層が決定した階層のうちで最下位の階層のノードの子ノードを抽出し、子孫関係ハッシュテーブル１２１を参照して、抽出した子ノードに、既に階層が決定した階層のうちで最下位の階層の１つ下の階層を決定可能か否かを判断し、階層決定可能と判断された子ノードに、階層を決定する。【選択図】    図１
2005044172.tif 000002
【特許請求の範囲】
【請求項１】
方向性を持つアークで親ノードと子ノードとを連結し、先頭ノードを最上位の階層のノードとして複数のノードを階層に従って配列する有向グラフの生成方法であって、
各ノードについて子孫ノードを調査し、各ノードと子孫ノードとを対応付けた子孫関係テーブルを作成する子孫調査ステップと、
既に階層が決定したノードの内で最下位の階層のノードの子ノードを抽出する子ノード抽出ステップと、
前記子孫関係テーブルを参照して、前記ノード抽出ステップで抽出された子ノードのそれぞれについて階層が決定可能であるか否かを判断する階層決定可能判断ステップと、
前記階層決定可能判断ステップで階層決定可能と判断された子ノードを、前記最下位の階層の１つ下の階層に決定する階層決定ステップと備えることを特徴とする有向グラフ生成方法。
【請求項２】
前記子孫調査ステップは、前記各ノードに一意のＩＤ番号を割り当てるＩＤ番号割当ステップを有し、前記子孫関係テーブルは、前記子孫ノードをＩＤ番号で示す、請求項１に記載の有向グラフ生成方法。
【請求項３】
前記抽出された子ノードが１つのとき、前記階層決定可能判断ステップは、当該子ノードの階層を決定可能と判断する、請求項１又は２に記載の有向グラフ生成方法。
【請求項４】
前記抽出された子ノードが複数あるとき、前記階層決定可能判断ステップは、前記抽出された複数の子ノードのうち、他の子ノードの子孫ノードではないノードの階層を決定可能と判断する、請求項１〜３の何れか一に記載の有向グラフ生成方法。
【請求項５】
前記階層決定可能判断ステップは、前記抽出された子ノードが、互いに子孫関係にある複数のノードを含むときには、該子孫関係にある複数のノードの内の１つを階層決定可能と判断する、請求項４に記載の有向グラフの生成方法。
【請求項６】
前記子孫調査ステップは注目ノードを与えると該注目ノードの子孫ノードを返却する子孫ノード取得ステップを有し、該子孫ノード取得ステップは、１つの注目ノードを調査済みにするステップと、該１つの注目ノードの子ノードを抽出するステップと、該抽出された子ノードのうち、調査済みではない子ノードを新たな注目ノードとして再帰的に子孫ノード取得ステップを呼び出すステップと、該再帰的に呼び出された子孫ノード取得ステップから返却されたノードを、当該調査済みではない子ノードの子孫ノードとして、子孫関係テーブルに登録するステップと、前記１つの注目ノードの子ノード及び当該子ノードの子孫ノードを返却するステップとを有する、請求項１〜５の何れか一に記載の有向グラフ生成方法。
【請求項７】
請求項１〜６の何れか一に記載の有向グラフ生成方法を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有向グラフ生成方法及びプログラムに関し、更に詳しくは、与えられたノードの接続情報から有向グラフを自動的に生成する有向グラフ生成方法及びプログラムに関する。
【背景技術】
【０００２】
有向グラフは、ノード（節）間を、方向性を有するアーク（弧）で接続したグラフである。有向グラフでは、アークの出力元のノードは親ノードと呼ばれ、アークの出力先のノードは子ノードと呼ばれる。また、あるノードから見て、そのノードの子ノード側を子孫と呼び、親ノード側を先祖と呼ぶ。一般に、有向グラフでは、先頭ノード又は末端ノード以外の中間ノードは、自身のノードに向けて出力されるアークと、自身のノードから出力されるアークとを有する。有向グラフでは、アークの向きが同じ方向となるように各ノードを整列させると、親ノードと子ノードとの関係が判り易くなって、有向グラフの視認性が向上する。
【０００３】
有向グラフでは、複数のノード間でループが構成されるとき、例えばあるノードの子孫に他のノードが含まれ、同時に、その他のノードの子孫に、先のあるノードが含まれるとき、言い換えると、あるノードと別のノードとが、それぞれの子孫でもあり先祖でもあるときには、アークの向きを全て同じ方向に整列させることはできず、視認性が低下する。この場合、出来るだけ多くのアークの向きが揃うように、各ノードを整列すると、視認性の低下が抑制されるため好ましい。
【０００４】
有向グラフを生成する技術としては、例えば特許文献１に記載された技術がある。この技術では、有向グラフにループが含まれるときには、ループを解除して各ノードを整列し、視認性が良好な有向グラフを生成している。図１９は、特許文献１に記載された有向グラフ表示システムの構成を機能ブロック図として示している。この有向グラフ表示システム２０は、ノード整列手段２１と、ループ検出手段２２と、ループ子ノード検出手段２３と、ループ親ノード検出手段２４と、ループ表示手段２５と、表示形態比較手段２６とから構成されている。
【０００５】
ノード整列手段２１は、各ノードを、アークの向きが同じ方向となるように整列させる。ループ検出手段２２は、複数ノードによるループを検出し、ループを構成する各ノードにループ検出フラグを設定する。ループ子ノード検出手段２３は、ループ検出フラグが設定されたノードから、複数の親を有してループを形成しているループ子ノードを検出する。ループ親ノード検出手段２４は、ループ子ノードの親となるループ親ノードを検出する。ループ表示手段２５は、ループ子ノードとループ親ノード間でループを形成するアークの方向を反転させ、ループを解除する。表示形態比較手段２６は、１つのループ内で複数のループ子ノードを検出すると、ループ子ノードがループ内で最も下位に位置するようにする。
【０００６】
上記のような構成を有する有向グラフ表示システム２０は、概ね、以下のように動作する。まず、各ノードのＹ座標を計算する。次に、親ノードから順に子ノードをたどっていき、各ノードのＸ座標を決定する。このとき、複数の親を持つノードのＸ座標は、親ノードのうち、最も下位に位置する親ノードのＸ座標から算出するが、ノードがそれぞれの子孫でもあり先祖でもある場合は、Ｘ座標を決定することができない。そこで、ループ検出手段２２は、ループを構成するノードにループ検出フラグを設定する。このループ検出フラグから、ループ子ノード検出手段２３は、ループ子ノードを検出し、ループ親ノード検出手段２４は、ループ親ノードを検出する。そして、ループ表示手段２５は、アークの向きを子方向へ向かうように、子ノードを移動させ、ループを解除する。
【特許文献１】特開平４-１０７７８９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところで、上記従来の有向グラフ表示システム２０では、先頭ノードから順次に縦型検索を行ってＸ座標を設定しているため、親ノードよりも先に、子ノードの座標を設定しなければならない場合があり、その場合、複数のノードを親に持つ子ノードのＸ座標は、複数の親ノードのうち、最も下位に位置する親ノードのＸ座標から算出する必要があるため、何度も複数の親ノードのＸ座標を調査し、最も下位に位置する親ノードのＸ座標が決定済みであるかどうかを調査する必要があり、有向グラフの生成に時間が掛かかるという問題があった。以下、この問題点について説明する。
【０００８】
図２０（ａ）〜（ｅ）は、有向グラフ表示システム２０を利用して有向グラフを生成する様子を段階ごとに示している。生成すべき有向グラフのノード間の親子関係は、図２０（ａ）に示すような関係であり、ノードＢ、Ｃ、Ｄがループを構成している。ループ表示手段２５により、ノードＢ、Ｃ、Ｄのループを解除すると、図２０（ｂ）に示すように、今度はノードＣ、Ｄ、Ｅがループ関係となる。この場合、同図（ｃ）に示すように、ノードＥの位置を移動しなくてはならず、さらに、同図（ｄ）に示すようにノードＤも移動しなくてはならない。
【０００９】
有向グラフ表示システム２０による有向グラフの生成では、最終的に、同図（ｅ）に示すようにノードＢを移動して、可能な限りアークが一定方向を向いた有向グラフを生成する。有向グラフ表示システム２０では、１つのノードの移動が、そのノードの下位のノードに影響を及ぼすため、座標を移動しなければならないノード数が指数関数的に増えることになる。有向グラフ表示システム２０では、各ノードのＸ座標が決定した後にループを解除しなければいけない方法であるため、ノード間の親子関係が複雑であり、ループが多数形成されるような有向グラフを生成する際には、ループの解除に時間が掛かるという問題がある。
【００１０】
ここで、有向グラフ表示システム２０によって、例えば図２０に示すような、ノードＡを先頭ノードとする有向グラフを生成した後に、先頭ノードを、ノードＡ以外の他のノードを変更した有向グラフを生成したい場合がある。この場合、先頭ノードがノードＡであるときと、先頭ノードがノードＡ以外のノードであるときとでは、ループの形成状況が変化し、ノードＡを先頭ノードとするときには形成されたループが、他のノードを先頭ノードにすると発生しないことがある。このため、有向グラフ表示システム２０では、先頭ノードを変更すると、ループを形成していたノードに対するフラグの設定が意味を成さず、もう一度ループ検査を行う必要があり、先頭ノードを変更する前の有向グラフの生成で得たループ検査の結果を利用して、効率的に有向グラフを生成することができない。
【００１１】
本発明は、複数の親ノードを有する子ノードの座標を簡易に決定でき、有向グラフに多数のループが含まれる場合であっても、有向グラフの生成に要する処理量が増大しない有向グラフ生成装置を提供することを目的とする。
また、本発明は、上記目的を達成した上で、有向グラフの生成後に、有向グラフの先頭ノードを変更したときに、先頭ノード変更前の有向グラフ生成における情報を利用して、簡易に、先頭ノード変更後の有向グラフを再生成できる有向グラフ生成装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するために、本発明の有向グラフ生成方法は、方向性を持つアークで親ノードと子ノードとを連結し、先頭ノードを最上位の階層のノードとして複数のノードを階層に従って配列する有向グラフの生成方法であって、各ノードについて子孫ノードを調査し、各ノードと子孫ノードとを対応付けた子孫関係テーブルを作成する子孫調査ステップと、既に階層が決定したノードの内で最下位の階層のノードの子ノードを抽出する子ノード抽出ステップと、前記子孫関係テーブルを参照して、前記ノード抽出ステップで抽出された子ノードのそれぞれについて階層が決定可能であるか否かを判断する階層決定可能判断ステップと、前記階層決定可能判断ステップで階層決定可能と判断された子ノードを、前記最下位の階層の１つ下の階層に決定する階層決定ステップと備えることを特徴とする。
【００１３】
本発明の有向グラフ生成方法では、有向グラフを構成する各ノードと、各ノードの子孫にあたるノードとを対応付けた子孫関係テーブルを作成し、その子孫関係テーブルを参照して、対象とするノードに階層が決定可能であるか否かを判断する。
グラフ中にループが形成される場合、従来の有向グラフ生成方法では、一度ノードを配置した後に、ループを検出し、ループが検出されたときには、配置したノードを移動して、アークの向きができるだけ同じ方向を向くようにしていたが、この場合には、ノードを移動したことに伴って、他のノードの配置位置を調整する必要が生じるため、処理量が増大する。本発明では、ノードを配置する前に、ノードに階層を決定可能か否かを判断して、ノードの階層を決定し、決定された階層に従ってノードを配置するため、各ノードが、アークの向きができるだけ同じ方向を向くように配列された、視認性が高い有向グラフを、従来に比して、少ない処理量で生成することができる。
【００１４】
本発明の有向グラフ生成方法では、前記子孫調査ステップは、前記各ノードに一意のＩＤ番号を割り当てるＩＤ番号割当ステップを有し、前記子孫関係テーブルは、前記子孫ノードをＩＤ番号で示すことが好ましい。この場合、階層決定可能判断ステップでは、子孫関係テーブルの参照を簡易に行うことができる。
【００１５】
本発明の有向グラフ生成方法では、前記抽出された子ノードが１つのとき、前記階層決定可能判断ステップは、当該子ノードの階層を決定可能と判断することができる。
【００１６】
本発明の有向グラフ生成方法では、前記抽出された子ノードが複数あるとき、前記階層決定可能判断ステップは、前記抽出された複数の子ノードのうち、他の子ノードの子孫ノードではないノードの階層を決定可能と判断することができる。この場合、同じ階層に決定可能か否かが判断される複数の子ノード間で子孫・先祖関係が生じていないノードを階層決定可能と判断することで、アークの向きができるだけ同じ向きとなるような有向グラフを得ることができる。
【００１７】
本発明の有向グラフ生成方法では、前記階層決定可能判断ステップは、前記抽出された子ノードが、互いに子孫関係にある複数のノードを含むときには、該子孫関係にある複数のノードの内の１つを階層決定可能と判断することができる。有向グラフにループが含まれるときには、同じ階層に決定可能か否かが判断される複数の子ノード間で、相互に子孫・先祖関係が生じることがあるが、この場合には、相互に子孫・先祖関係が生じている複数の子ノードのうちの何れかを階層決定可能とするとよい。
【００１８】
本発明の有向グラフ生成方法では、前記子孫調査ステップは、注目ノードを与えると該注目ノードの子孫ノードを返却する子孫ノード取得ステップを有し、該子孫ノード取得ステップは、１つの注目ノードを調査済みにするステップと、該１つの注目ノードの子ノードを抽出するステップと、該抽出された子ノードのうち、調査済みではない子ノードを新たな注目ノードとして再帰的に子孫ノード取得ステップを呼び出すステップと、該再帰的に呼び出された子孫ノード取得ステップから返却されたノードを、当該調査済みではない子ノードの子孫ノードとして、子孫関係テーブルに登録するステップと、前記１つの注目ノードの子ノード及び当該子ノードの子孫ノードを返却するステップとを有することが好ましい。この場合、調査済みのノードについては、再び子孫ノード取得ステップが実行されないため、ノード数が多い場合であっても、子孫ノード調査ステップの処理時間が増大しない。
【００１９】
本発明の有向グラフ生成方法は、上記本発明の有向グラフ生成方法を記述したことを特徴とする。
【発明の効果】
【００２０】
本発明の有向グラフ生成方法は、有向グラフを構成する各ノードと、各ノードの子孫にあたるノードとを対応付けた子孫関係テーブルを作成し、その子孫関係テーブルを参照して、ノードに階層を決定可能であるか否かを判断するため、各ノードが、アークの向きができるだけ同じ方向を向くように配列された、視認性が高い有向グラフを、従来に比して、少ない処理量で生成することができる。また、本発明のプログラムは、本発明の有向グラフの生成方法を、コンピュータ上で実行させることができる。
【発明を実施するための最良の形態】
【００２１】
以下、図面を参照し、本発明の実施形態例に基づいて、本発明を更に詳細に説明する。図１は、本発明の一実施形態例の有向グラフ生成装置の構成を機能ブロック図として示している。有向グラフ生成装置１０は、プログラム制御により動作するコンピュータ１００と、ディスプレイ装置や印刷装置などの出力装置２００からなる。コンピュータ１００は、ノード情報格納部１２０と、ソフトウェアプログラムで実現される、ハッシュテーブル設定手続き１１０、有向グラフ生成手続き１３０、子孫ノード判断手続き１４０、及び、出力手続き１５０とを備える。有向グラフ生成装置１０は、以下に述べるように、ノード間を接続するアークの向きが可能な限り同じ方向を向くようにした有向グラフを、与えられたノード間の接続情報に基づいて生成し、その有向グラフを出力装置２００上に表示する。
【００２２】
ハッシュテーブル設定手続き１１０は、ノードＩＤ設定手続き１１１と、子孫関係調査手続き１１２とを備える。ノードＩＤ設定手続き１１１は、ノード情報記憶部１２２からグラフを構成するすべてのノードを取得し、各ノードに一意のＩＤ番号を割り当てる。子孫関係調査手続き１１２は、各ノードについて、そのノードと子孫関係にあるノードを調査する。例えば、ノードＡ〜Ｃの３つのノードがあり、ノードＡの子ノードがノードＢであり、ノードＢの子ノードがノードＣであるときには、ノードＡの子孫ノードは、ノードＢ及びノードＣとなる。子孫関係調査手続き１１２は、各ノードについて、子孫ノードのＩＤ番号を子孫関係ハッシュテーブル１２１へ格納する。
【００２３】
ノード情報格納部１２０は、子孫関係ハッシュテーブル１２１、ノード情報記憶部１２２、及び、出力ノードリスト１２３を備える。子孫関係ハッシュテーブル１２１は、グラフを構成する各ノードについて、そのノードの子孫となるノードを格納する。ノード情報記憶部１２２は、グラフを構成する各ノードについて、親ノードと子ノードとに関する情報、つまり、ノード間の接続状況に関する情報を格納する。出力ノードリスト１２３は、各ノードについて、ノードＩＤ番号、ノードの階層、グラフ上でのＸＹ座標、及び、出力装置２００の表示画面上での出力座標を格納する。
【００２４】
有向グラフ生成手続き１３０は、階層決定手続き１３１、ＸＹ座標決定手続き１３２、及び、座標変換手続き１３３を備える。階層決定手続き１３１は、有向グラフの先頭ノードを最上位の階層として、各ノードに設定する階層を決定する。ＸＹ座標決定手続き１３２は、生成される有向グラフにおいて、各ノードが、階層決定手続き１３１で設定された階層に基づいて整列されるように、各ノードのＸＹ座標を決定する。座標変換手続き１３３は、各ノードについて、ＸＹ座標決定手続きで決定されたＸＹ座標から、出力装置２００上での出力座標への座標変換を行う。
【００２５】
子孫ノード判断手続き１４０は、階層決定手続き１３１から呼び出され、あるノードが、別のあるノードの子孫であるかを、子孫関係ハッシュテーブル１２１を参照して調べる。出力手続き１５０は、座標変換されたノードの出力座標にノードを配置し、ノード間をアークで接続して有向グラフを生成し、その有向グラフを出力装置２００へ出力する。
【００２６】
図２は、有向グラフ生成装置１０の処理手順例を示している。ノードＩＤ設定手続き１１１は、有向グラフを構成すべき全てのノードを、ノード情報記憶部１２２から取得する（ステップＳ２１）。ノードＩＤ設定手続き１１１は、取得した各ノードに、一意のノードＩＤ番号を設定し、そのノードＩＤ番号を、出力ノードリスト１２３に登録する（ステップＳ２２）。ノードＩＤ設定手続き１１１は、例えば、ノードを取得した順に、ＩＤ番号を１から順に割りあて、そのＩＤ番号を出力ノードリスト１２３へ登録する。
【００２７】
子孫関係調査手続き１１２は、子孫ノード調査処理を行い、各ノードについて、子孫関係にあるノードのＩＤ番号を、子孫関係ハッシュテーブル１２１に格納する（ステップＳ２３）。階層決定手続き１３１は、階層決定処理を行い、先頭ノードの階層を最上位（１）とし、子孫関係ハッシュテーブル１２１を参照して、先頭ノード側からから順に、各ノードに階層を設定する（ステップＳ２４）。
【００２８】
ＸＹ座標決定手続き１３２は、各ノードについて、最上位の階層側から順に、そのノードを配置すべきＸＹ座標を決定する（ステップＳ２５）。ステップＳ２５では、各ノードのＸ座標が、そのノードの階層に基づいて決定される。座標変換手続き１３３は、ノードを配置すべきＸＹ座標を、出力装置２００上での座標に変換する（ステップＳ２６）。出力手続き１５０は、各ノードを、ステップＳ２６で変換された座標に従って、出力装置２００の表示画面上に配置し、ノード間を、ノード間の親子関係に従ってアークで接続して、有向グラフを出力装置２００に表示させる。
【００２９】
図３は、図２のステップＳ２３の子孫ノード調査処理の手順例を示している。子孫関係調査手続き１１２は、まず、各ノードにどのような子孫ノードが存在するかの情報を蓄えるための、空の子孫関係ハッシュテーブル１２１を作成する（ステップＳ３１）。子孫関係調査手続き１１２は、ノードの中から先頭に配置する先頭ノードを選択し（ステップＳ３２）、その先頭ノードを注目ノードとして、子孫ノード取得処理を呼び出す（ステップＳ３３）。
【００３０】
図４は、図３のステップＳ３３の子孫ノード取得処理の手順例を示している。子孫ノード取得処理は、再帰呼び出しにより、注目ノードについての全ての子孫ノードを取得する。子孫関係調査手続き１１２は、呼び出し側から引き渡された注目ノードを子孫調査済みとし（ステップＳ４１）、注目ノードの子ノードを全て取得する（ステップＳ４２）。子孫関係調査手続き１１２は、ステップＳ４２で子ノードが１つ以上取得されたか否かを調べ（ステップＳ４３）、注目ノードに子ノードがあるときには、その中から子ノードを１つ選択する（ステップＳ４４）。注目ノードに子ノードが１つもないときには、ステップＳ４３からステップＳ４９へ進み、子孫関係調査手続き１１２は、注目ノードには子孫ノードがない旨を返却する。
【００３１】
子孫関係調査手続き１１２は、ステップＳ４４で選択した子ノードが調査済みにされているか否かを調べ（ステップＳ４５）、その子ノードが調査済みでないときには、ステップＳ４４で選択した子ノードを注目ノードとして、子孫ノード取得処理を再帰的に呼び出す（ステップＳ４６）。子孫関係調査手続き１１２は、ステップＳ４６で再帰的に呼び出した子孫ノード取得処理から返却された子孫ノードのＩＤ番号を、子孫関係ハッシュテーブル１２１のステップＳ４４で選択された子ノードに対応する項目に登録する（ステップＳ４７）。子孫関係調査手続き１１２は、ステップＳ４４〜Ｓ４７までの処理を、注目ノードのすべての子ノードについて行う（ステップＳ４８）。そして、注目ノードの各子ノードに、各子ノードの子孫ノードを加えたものを返却し（ステップＳ４９）、処理を終了する。
【００３２】
図３に戻り、ステップＳ３３の、先頭ノードについての子孫ノード取得処理が終了すると、子孫ノード取得処理からは、先頭ノードについてのすべての子孫ノードに関する情報が返却される。子孫関係調査手続き１１２は、子孫関係ハッシュテーブル１２１の先頭ノードの項目に、ステップＳ３３で返却されたすべての子孫ノードのＩＤ番号を登録し（ステップＳ３４）、子孫ノード調査処理を終了する。子孫関係調査手続き１１２は、調査済みの子ノードについては子孫ノードを再度調査せず、各ノードの子ノードを一度調べるだけで処理が完了するため、最小限の処理量で、各ノードの子孫ノードを調査可能である。
【００３３】
図５は、図２のステップＳ２４の階層決定処理の手順例を示している。子孫ノードの調査が終了すると、先頭ノードから順に、各ノードに階層を設定する。まず、階層決定手続き１３１は、先頭ノードを、最上位の階層に設定する（ステップＳ５１）。次いで、先頭ノードを親ノードとして、その親ノードの子ノードのうち、階層がまだ設定されていない子ノードを、その親ノードの１つ下の階層に設定するノードの候補として取得する（ステップＳ５２）。階層決定手続き１３１は、ステップＳ５２で取得された、階層未決定の子ノードが存在するか否かを調べ（ステップＳ５３）、取得された子ノードが存在しないときには、階層決定処理を終了する。
【００３４】
ステップＳ５３で、階層未決定の子ノードが存在すると判断されたときには、階層決定手続き１３１は、ステップＳ５２で取得された各子ノードについての階層決定可能判断処理を行い、各子ノードに階層を設定可能か否かを判断する（ステップＳ５４）。ここで、ステップＳ５２で取得された子ノードが１つであるときには、その子ノードの階層は決定可能であるとする。階層決定手続き１３１は、ステップＳ５２で取得された、親ノードの１つ下の階層に設定されるノードの候補のうち、ステップＳ５４で階層を設定可能と判断された各子ノードに、設定済みの親ノードの階層よりも１つ低い階層を設定する（ステップＳ５５）。このとき階層決定手続き１３１は、出力ノードリスト１２３の階層が設定された子ノードの項目に、設定された階層を登録する。
【００３５】
階層決定手続き１３１は、ステップＳ５５で階層が設定された子ノードの個数Ｍをカウントし（ステップＳ５６）、Ｍ＝０であるか否か、つまり、階層が設定された子ノードがあるか否かを判断する（ステップＳ５７）。ステップＳ５７で、Ｍ≠０であると判断されたときには、ステップＳ５５で階層が設定されたノードを親ノードとして（ステップＳ５８）、ステップＳ５２に戻り、階層がまだ決定されていないノードについて、階層決定処理を続行する。ステップＳ５７で、Ｍ＝０と判断されたときには、階層決定処理は終了する。
【００３６】
図６は、図５のステップＳ５４の階層決定可能判断処理の処理手順例を示している。階層決定手続き１３１は、ステップＳ５２で取得された、階層未決定の子ノードの中から、調査対象のノードを１つ選択する（図６のステップＳ６１）。階層決定手続き１３１は、ステップＳ６１で選択された調査対象のノードと、図５のステップＳ５２で取得された各子ノードとを引数として子孫ノード判断手続き１４０を呼び出し、子孫ノード判断手続き１４０は、子孫ノード判断処理を行う（ステップＳ６２）。子孫ノード判断手続き１４０は、調査対象のノードが、図５のステップＳ５２で取得された他の子ノードの子孫に含まれるか否かを返却する。
【００３７】
図７は、図６のステップＳ６２の子孫ノード判断処理の処理手順例を示している。子孫ノード判断処理では、上記のように、階層決定手続き１３１から、子孫ノード判断手続き１４０に、図５のステップＳ５２で取得された各子ノードと、その各子ノードのうち、図６のステップＳ６１で選択された調査対象のノードとが引き渡される。子孫ノード判断手続き１４０は、調査対象のノードを除く、階層決定手続き１３１から引き渡された各ノードについてのハッシュテーブルを、子孫関係ハッシュテーブル１２１から取得する（図７のステップＳ７１）。
【００３８】
子孫ノード判断手続き１４０は、ステップＳ７１で取得したハッシュテーブルに、調査対象のノードのＩＤ番号が含まれているか否かを調査する（ステップＳ７２）。言い換えると、子孫ノード判断手続き１４０は、図５のステップＳ５２で取得された子ノード間で、子孫・先祖関係が生じているか否かを、子孫関係ハッシュテーブル１２１を検索して調べる。子孫ノード判断手続き１４０は、子孫・先祖関係が生じているか否かを、ハッシュテーブルを用いて検索するため、調査対象のノードの量にかかわらず、一定かつ短い時間で子孫関係の調査を可能である。
【００３９】
子孫ノード判断手続き１４０は、ステップＳ７２の調査の結果を判断し（ステップＳ７３）、調査対象のノードのＩＤ番号が、ステップＳ７１で取得したハッシュテーブルに含まれるときには、調査対象のノードが、図５のステップＳ５２で取得された、何れかの子ノードの子孫に含まれる旨を、階層決定手続き１３１に返却する。これとは逆に、調査対象のノードのＩＤ番号が、ステップＳ７１で取得したハッシュテーブルに含まれないときには、子孫ノード判断手続き１４０は、調査対象のノードが、図５のステップＳ５２で取得された子ノードの子孫には含まれない旨を、階層決定手続き１３１に返却する。
【００４０】
図６に戻り、階層決定手続き１３１は、子孫ノード判断手続き１４０から、調査対象のノードが、図５のステップＳ５２で取得された他の子ノードの子孫に含まれる旨が返却された否かを判断し（ステップＳ６３）、子孫に含まれる旨が返却されたときには、調査対象のノードの階層は、決定不可能であるとする（ステップＳ６４）。これとは逆に、子孫ノード判断手続き１４０から、子孫に含まれない旨が返却されたときには、調査対象のノードの階層は、決定可能であるとする（ステップＳ６４）。ここで、例外として、調査対象のノードが、他のノードの子孫に含まれる場合でも、調査対象のノードの子孫に、その他のノードが含まれているとき、つまり、お互いが先祖でもあり子孫でもあるときであって、その他の子ノードの階層が未決定であるときには、調査対象のノードの階層は、決定可能であるとする。
【００４１】
階層決定手続き１３１は、図５のステップＳ５２で取得した子ノードのうち、まだ、ステップＳ６２の子孫ノード判断処理を行っていない子ノードがあるか否か、つまり、階層の決定可能、又は、不可能の判断がされていない子ノードがあるか否かを判断する（ステップＳ６６）。階層決定手続き１３１は、子孫ノード判断処理を行っていない子ノードがあるときには、ステップＳ６１へ戻り、次の子ノードを選択して、それを調査対象のノードとする。ステップＳ６６で、子孫ノード判断処理を行っていない子ノードがないと判断されたときには、階層決定可能判断処理は終了する。
【００４２】
図８は、図２のステップＳ２５のＸＹ座標決定処理の手順例を示している。ＸＹ座標決定処理では、各ノードのＸ座標が、階層が高い側から順に設定される。ＸＹ座標決定手続き１３２は、最上位の階層のＸＹ座標を、任意の座標に設定する（ステップＳ８１）。ＸＹ座標決定手続き１３２は、すべての階層のノードにＸＹ座標を設定したか否か、言い換えると、まだ座標が決定していない階層が残っているか否かを判断し（ステップＳ８２）、座標が決定していない階層が残っているときには、ステップＳ８３へ進み、下位側の階層のノードのＸＹ座標を設定する。
【００４３】
ＸＹ座標決定手続き１３２は、座標が未設定である階層のうち、最も階層が高い階層Ｌを取得する（ステップＳ８３）。１回目のループのステップＳ８２では、階層Ｌとして、最上位階層「１」の１つ下の階層「２」が取得される。ＸＹ座標決定手続き１３２は、階層Ｌの１つ上位の階層のＸ座標に基づいて、階層ＬのＸ座標を決定する（ステップＳ８４）。このとき、階層ＬのＸ座標は、１つ上位の階層のＸ座標よりも、値が増加する方向の位置となるように設定される。ＸＹ座標決定手続き１３２は、階層Ｌに設定された各ノードについて、Ｙ座標を決定する（ステップＳ８５）。
【００４４】
ＸＹ座標決定手続き１３２は、ステップＳ８３〜ステップＳ８５を繰り返し実行し、すべてのノードのＸＹ座標を決定する。ＸＹ座標決定手続き１３２は、すべての階層について座標を決定すると、ステップＳ８２からステップＳ８６へ進み、決定した各ノードのＸＹ座標を出力ノードリスト１２３に登録し（ステップＳ８６）、ＸＹ座標決定処理を終了する。
【００４５】
図９は、図２のステップＳ２６の座標変換処理の手順例を示している。座標変換処理得は、上記のようにして決定された各ノードのＸＹ座標を、出力装置２００の表示画面上での座標である出力座標に変換する。ＸＹ座標を出力座標に変換することにより、出力装置２００上の原点から有向グラフを表示できるようになる。座標変換手続き１３３は、まず、すべてのノードのＸＹ座標を調べ、Ｘ座標の最小値ＸｍｉｎとＹ座標の最小値Ｙｍｉｎとを求める（図９のステップＳ９１）。
【００４６】
座標変換手続き１３３は、上記のようにして求めたＸ座標の最小値ＸｍｉｎとＹ座標の最小値Ｙｍｉｎとを用いて、各ノードのＸＹ座標を出力座標に変換する（ステップＳ９２）。具体的には、以下の式に基づいて、各ノードのＸＹ座標を出力座標に変換する。
出力座標（Ｘ）＝Ｘ−Ｘｍｉｎ
出力座標（Ｙ）＝Ｙ−Ｙｍｉｎ
座標変換手続き１３３は、出力ノードリスト１２３に、変換後の出力座標を登録し（ステップＳ９３）、座標変換処理を終了する。
【００４７】
図１０は、図２のステップＳ２７の出力処理の手順例を示している。出力処理は、ノード図形と、ノード名と、ノード同士の親子関係を示すためのアーク図形とを、出力装置２００の表示画面上に表示させる。出力手続き１５０は、出力ノードリスト１２３から、まだ出力されていない階層のうち最も高い階層に設定されているノードを取得する（ステップＳ１０１）。出力手続き１５０は、１回目のループのステップＳ１０１では、最上位の階層のノード、つまり、先頭ノードを取得する。
【００４８】
出力手続き１５０は、ステップＳ１０１で取得したノードの出力座標を、出力ノードリスト１２３から取得し、その座標位置に、ノード図形及びノード名を出力する（ステップＳ１０２）。出力手続き１５０は、ノード情報記憶部１２２を参照し、ステップＳ１０１で取得したノードの親ノードを取得し（ステップＳ１０３）、その親ノードから、ステップＳ１０１で取得したノードに向かうアーク図形を出力する（ステップＳ１０４）。出力手続き１５０は、ステップＳ１０３で親ノードが取得されないときには、ステップＳ１０４でアーク図形を出力しない。出力手続き１５０は、ステップＳ１０１からステップＳ１０４までを、すべてのノードが出力装置２００の表示画面上に表示されるまで繰り返し行い（ステップＳ１０５）、すべてのノードを出力し終えると、出力処理を終了する。
【００４９】
以下、図２〜図１０に示す、有向グラフ生成装置１０の処理手順について、具体例を挙げつつ詳細に説明する。図２のステップＳ２１では、例えば、ノード情報記憶部１２２記憶されている、以下の表１に示す情報を参照して、ノードＡからノードＥまでが取得される。
【表１】
2005044172.tif 000003
図２のステップＳ２２では、ノードＡからノードＥまでにノードＩＤ番号が設定され、以下に示す表２のような出力ノードリスト１２３が得られる。
【表２】
2005044172.tif 000004
【００５０】
図１１は、子孫ノード取得処理の再帰呼び出しの様子を示している。図２のステップＳ２３の子孫ノード調査処理（図３）では、図３のステップＳ３３（図１１のＰ０）から、ノードＡを注目ノードにして、子孫ノード取得処理（Ｐ１）が呼び出される（ｃａｌｌ（１））。ノードＡの子孫ノード取得処理（Ｐ１）のステップＳ４１（図４）では、ノードＡが子孫調査済みにされ、ステップＳ４２では、ノードＡの子ノードであるノードＢ及びノードＣが取得される。ステップＳ４４では、まず、ノードＢが選択され、ステップＳ４５では、ノードＢが調査済みであるか否かが調べられる。ここで、ノードＢは子孫調査済みではないため、ステップＳ４６へ進み、ノードＢを注目ノードにして、子孫ノード取得処理が再帰的に呼び出される（ｃａｌｌ（２））。
【００５１】
再帰呼び出しされたノードＢの子孫ノード取得処理（Ｐ２）では、ノードＢが調査済みにされ、ノードＢの子ノードであるノードＣ及びノードＥが取得される。ノードＢの子孫ノード取得処理（Ｐ２）において、ノードＢの子ノードであるノードＣ及びノードＥは調査済みではないため、まず、ステップＳ４４でノードＣが選択され、ステップＳ４６で、ノードＣを注目ノードとして、子孫ノード取得処理が再帰的に呼び出される（ｃａｌｌ（３））。
【００５２】
再帰呼び出しされたノードＣの子孫ノード取得処理（Ｐ３）では、ノードＣは子孫調査済みにされ、ノードＣの子ノードとして、ノードＤが取得される。そして、ステップＳ４６で、ノードＤを注目ノードとして、ノードＤの子孫ノード取得処理が再帰的に呼び出される（ｃａｌｌ（４））。ノードＤの子孫ノード取得処理（Ｐ４）では、ノードＤは子孫調査済みにされるが、ノードＤには子ノードがないため、そのまま処理が終了し、ノードＣの子孫ノード取得処理（Ｐ３）には、ノードＤの子孫ノード取得処理（Ｐ４）から、子孫なしを意味するＮＵＬＬが返却される（ｒｅｔ（４））。
【００５３】
ノードＣの子孫ノード取得処理（Ｐ３）に戻り、そのステップＳ４７では、子孫関係ハッシュテーブル１２１に、ノードＤの子孫ノードとして、ステップＳ４６でノードＤの子孫ノード取得処理（Ｐ４）から返却されたＮＵＬＬが登録される。そして、ステップＳ４９で、ノードＣの子孫ノードとしてノードＤが返却され（ｒｅｔ（３））、ノードＣの子孫ノード取得処理（Ｐ３）が終了して、ノードＢの子孫ノード取得処理（Ｐ２）に戻る。ノードＢの子孫ノード取得処理（Ｐ２）では、ステップＳ４６で返却されたノードＤのＩＤ番号「４」が、子孫関係ハッシュテーブル１２１のノードＣの項目に登録される。
【００５４】
ノードＢの子孫ノード取得処理（Ｐ２）では、２回目のループのステップＳ４６で、残りの子ノードであるノードＥを注目ノードとして、子孫ノード取得処理が再帰的に呼び出される（ｃａｌｌ（５））。このノードＥの子孫ノード取得処理（Ｐ５）では、ノードＥが子孫調査済みにされ、ノードＥの子ノードとして、ノードＤが取得される。ここで、ノードＤは、ノードＣの子孫ノード取得処理（Ｐ３）において子孫調査済みにされているため、ノードＥの子孫ノード取得処理（Ｐ５）では、ステップＳ４５からステップＳ４８へ進み、ノードＤについての再度の子孫ノード取得処理は行われない。ステップＳ４９では、ノードＥの子孫ノードとしてノードＤが返却され（ｒｅｔ（５））、ノードＥの子孫ノード取得処理（Ｐ５）が終了して、ノードＢの子孫ノード取得処理（Ｐ２）に戻る。
【００５５】
ノードＢの子孫ノード取得処理（Ｐ２）では、２回目のループのステップＳ４６で返却されたノードＤのＩＤ番号「４」が、子孫関係ハッシュテーブル１２１のノードＥの項目に登録される。そして、ステップＳ４９では、１回目のループのステップＳ４６で返却されたノードＣの子孫ノードと、２回目のループのステップＳ４６で返却されたノードＤの子孫ノードとをまとめたものに、ノードＢの子ノードであるノードＣ及びノードＥを加えたものが、ノードＢの子孫ノードとして返却され（ｒｅｔ（２））、ノードＢの子孫ノード取得処理（Ｐ２）が終了し、ノードＡの子孫ノード取得処理（Ｐ１）に戻る。
【００５６】
ノードＡの子孫ノード取得処理（Ｐ１）では、そのステップＳ４６で、ノードＢの子孫ノード取得処理から返却された子孫ノードのＩＤ番号が、子孫関係ハッシュテーブル１２１のノードＢの項目に登録される。具体的には、子孫関係ハッシュテーブル１２１のノードＢに対応する項目に、その子孫ノードのＩＤ番号「３」「４」、及び「５」が登録される。
【００５７】
ノードＡの子孫ノード取得処理（Ｐ１）では、２回目のループのステップＳ４４で、ノードＡのもう１つの子ノードであるノードＣが選択されるが、ノードＣは、ノードＢの子孫ノード取得処理（Ｐ２）において子孫調査済みにされているため、ステップＳ４５からステップＳ４９へ進み、ノードＣについて、再度の子孫ノード取得処理は行われない。このような処理を経て、ノードＡの子孫ノード取得処理（Ｐ１）からは、ノードＡの子孫ノードとして、ノードＡの子ノードであるノードＢ及びノードＣに、各子ノードの子孫ノードを加えた、ノードＢ、Ｃ、Ｄ、及びＥが返却され（ｒｅｔ（１））、子孫ノード調査処理（Ｐ０）の図３のステップＳ３４では、子孫関係ハッシュテーブル１２１のノードＡの項目にそれら子孫ノードのＩＤ番号が登録される。以上のような処理により、子孫関係ハッシュテーブル１２１の登録内容は、以下に示す表のようになる。
【表３】
2005044172.tif 000005
【００５８】
図１２は、各ノードの階層決定の様子を示している。上記のような子孫ノード調査処理が終了すると、図２のステップＳ２４の階層決定処理に移行する。図５に示す階層決定処理のステップＳ５１では、ノードＡが最上位の階層「１」に設定され、ステップＳ５２では、ノードＡの子ノードであり、かつ、まだ階層が設定されていないノードＢ及びノードＣが取得され（図１２のステップＳ１２０１）、ノードＢ及びノードＣについての階層決定可能判断処理が行われる。
【００５９】
階層決定可能判断処理では、まず、図６のステップＳ６１で、調査対象のノードとしてノードＢが選択され（ステップＳ１２０２）、子孫ノード判断処理が実行される。この子孫ノード判断処理では、図７のステップＳ７１で、子孫関係ハッシュテーブル１２１のノードＣの登録内容である「４」（表３）が取得され、ステップＳ７２で、ノードＢのＩＤ番号「２」が、ステップＳ７１で取得されたノードＣの登録内容に含まれるか否かが調査される。
【００６０】
子孫ノード判断処理では、子孫関係ハッシュテーブル１２１（表３）が参照され、ノードＣの子孫に、ノードＢが含まれるか否かが調査される。表３を参照すると、ノードＣの子孫ノードＩＤにノードＢのＩＤ番号が含まれておらず、ノードＢは、先祖にノードＣを有していないため、ノードＢはノードＣの子孫とはなっていない旨の調査結果が得られる（ステップＳ１２０３）。この調査結果に基づいて、階層決定可能判断処理では、ノードＢの階層は決定可能と判断される（ステップＳ１２０４）。
【００６１】
階層決定可能判断処理では、次いで、図６のステップＳ６１で、ノードＣが選択され（ステップＳ１２０５）、上記と同様にして、子孫ノード判断処理が実行される。子孫ノード判断処理において、子孫関係ハッシュテーブル１２１を参照して、ノードＢの子孫にノードＣが含まれるか否かを調査すると、ノードＢの子孫ノードＩＤに、ノードＣのＩＤ番号が含まれる。このため、ノードＣは、その先祖にノードＢを有しており、ノードＣはノードＢの子孫である旨の調査結果が得られる（ステップＳ１２０６）。この調査結果に基づいて、階層決定可能判断処理では、ノードＣの階層は決定不可能と判断される（ステップＳ１２０７）。
【００６２】
階層決定可能判断処理での判断結果を受けて、階層決定処理では、図５のステップＳ５５で、ノードＡの２つの子ノードのうち、ノードＢのみが階層「２」に設定される（ステップＳ１２０８）。階層決定処理では、２回目のループのステップＳ５１で、階層が設定されたノードＢの子ノードであるノードＣ及びノードＥが取得される（ステップＳ１２０９）。ステップＳ１２０１で取得されたノードＢ及びノードＣのときと同様にして、ノードＣ及びノードＥについて、階層決定可能判断処理が行われる。
【００６３】
階層決定可能判断処理では、まず、ノードＣが選択され（ステップＳ１２１０）、子孫ノード判断処理によって、ノードＣはノードＥの子孫ではない旨の調査結果が得られる。（ステップＳ１２１１）、これにより、階層決定可能判断処理では、ノードＣは階層決定可能と判断される（ステップＳ１２１２）。次いで、ノードＥが選択され（ステップＳ１２１３）、子孫ノード判断処理によって、ノードＥはノードＣの子孫ではない旨の調査結果が得られる（ステップＳ１２１４）。これにより、階層決定可能判断処理では、ノードＥについても階層決定可能と判断される（ステップＳ１２１５）。
【００６４】
階層決定可能判断処理での判断結果を受けて、階層決定処理では、ノードＣ及びノードＥが、共に、階層「３」に設定される（ステップＳ１２１６）。階層決定処理では、３回目のループのステップＳ５１で、階層が設定されたノードＣ及びノードＥの子ノードであるノードＤが取得される（ステップＳ１２０９）。ノードＤについては、ステップＳ１２０９で取得された子ノードが他にないため、階層決定可能判断処理を経ずに、階層決定が可能であり、階層決定処理では、ノードＤが階層「４」に設定される（ステップＳ１２１８）。以上のような処理により、上位側から順に、すべてのノードに階層が設定され、以下の表４に示すような出力ノードリスト１２３が得られる。
【表４】
2005044172.tif 000006
【００６５】
各ノードに階層が設定されると、ＸＹ座標決定処理により、各ノードにＸＹ座標が設定される。ＸＹ座標決定処理では、図８のステップＳ８１で、最上位の階層に設定されるノードＡのＸＹ座標が、任意の値、例えば、（−１０，０）に設定される。そして、ステップＳ８３で階層「２」が取得され、ステップＳ８４で、階層「２」に設定されたノードのＸ座標が、１つ上位の階層のＸ座標に、所定の値、例えば「１０」を加えた座標（０）に設定される。次いで、ステップＳ８５では、階層「２」であるノードＢのＹ座標が設定されるが、階層「２」に設定されるノードはノードＢのみであるため、ノードＢのＹ座標は、ノードＡのＹ座標と同じ座標（０）に設定される。
【００６６】
階層「２」に設定されるノードのＸＹ座標が決定すると、２回目のループのステップＳ８３で、階層「３」が取得され、ステップＳ８４で、階層「３」に設定されたノードのＸ座標が、階層「２」に設定されたノードのＸ座標に所定の値「１０」を加えた座標（１０）に設定される。次いで、ステップＳ８５では、階層「３」であるノードＣ及びノードＥのＹ座標が設定されるが、階層「２」に設定されるノードは２つであるため、ノードＣのＹ座標とノードＥのＹ座標とは、互いに異なる値に設定される。例えば、ノードＣのＹ座標は座標（−１０）に設定され、ノードＥのＹ座標は座標（１０）に設定される。
【００６７】
階層「３」に設定されるノードのＸＹ座標が決定すると、３回目のループのステップＳ８３で、階層「４」が取得される。ステップＳ８４では、階層「４」に設定されたノードＤのＸ座標が、階層「３」に設定されたノードのＸ座標に、所定の値「１０」を加えた座標（２０）に設定され、ステップＳ８５では、ノードＢのＹ座標が、ノードＡのＹ座標と同じ座標（０）に設定される。以上のような処理により、各ノードのＸＹ座標が決定し、以下の表５に示すような出力ノードリスト１２３が得られる。
【表５】
2005044172.tif 000007
【００６８】
各ノードのＸＹ座標が決定すると、座標変換処理により、各ノードのＸＹ座標が、出力装置２００の表示画面上での座標に変換される。座標変換処理では、図９のステップＳ９１で、ＸＹ座標の最小値がそれぞれ求められる。表５の例では、Ｘ座標の最小値Ｘｍｉｎは−１０であり、Ｙ座標の最小値Ｙｍｉｎは−１０である。ステップＳ８２での座標変換を経て、以下の表６に示すような出力ノードリスト１２３が得られる。
【表６】
2005044172.tif 000008
【００６９】
図１３は、出力装置の表示画面上に表示される有向グラフを示している。各ノードの、表示装置２００の表示画面上での出力座標が決定すると、出力処理により、図１３に示すような有向グラフが出力装置２００の表示画面上に出力される。出力処理では、まず、図１０のステップＳ１０１で、最上位のノードＡが取得され、ステップＳ１０２で、出力ノードリスト１２３のノードＡの出力座標が参照され、出力装置２００の表示画面の座標（０，１０）に、ノード図形（□）と、ノード名（Ａ）とが表示される。ノードＡには親ノードが存在しないため、アーク図形が出力されずに、ステップＳ１０５からステップＳ１０１にそのまま戻る。
【００７０】
２回目のループのステップＳ１０１では、階層「２」のノードＢが取得され、ステップＳ１０２で、出力装置の座標（１０，１０）に、ノード図形（□）と、ノード名（Ｂ）とが表示される。ステップＳ１０３では、ノード情報記憶部１２２が参照され、ノードＢの親ノードとしてノードＡが取得され、ステップＳ１０４では、出力装置２００の表示画面上のノードＡのノード図形から、ノードＢのノード図形に向かうアーク図形（ａｒｃ１）が表示される。
【００７１】
３回目のループのステップＳ１０１では、階層「３」のノードＣ及びノードＥが取得され、ステップＳ１０２では、座標（２０，０）にノード図形とノード名（Ｃ）が表示され、座標（２０，２０）にノード図形とノード名（Ｅ）が表示される。ステップＳ１０３で、ノードＣの親ノード、及び、ノードＥの親ノードがそれぞれ取得され、ステップＳ１０４で、それぞれの親ノードからノードＣ及びノードＥに向けてアーク図形（ａｒｃ２〜ａｒｃ４）が表示される。４回目のループでは、ノードＤの出力座標に、ノード図形及びノード名が表示され、ノードＤの親ノードからノードＤに向かうアーク図形（ａｒｃ５及びａｒｃ６）が表示される。このような過程を経て、出力装置２００の表示画面上には、図１３に示すような有向グラフが表示される。
【００７２】
本実施形態例では、図５に示す階層決定処理において、ステップＳ５２で取得された、親ノードの階層よりも１つ下の階層を設定するノードの候補のうち、その候補間で子孫・先祖関係が生じていないノードを階層決定可能なノードとして、そのノードに、親ノードより１つ下の階層を設定する。図５のステップＳ５４の階層決定可能判断処理（図６）では、ステップＳ５２で取得された子ノード間で子孫・先祖関係が生じているか否かを、子孫関係ハッシュテーブル１２１を用いて調査しているため、階層を決定可能か否かの判断に要する処理量が少なく、子ノードが複数の親ノードを有している場合であっても、その子ノードの階層決定可能判断処理に、時間がかからない。
【００７３】
ここで、図１４は、比較例の有向グラフを示している。この比較例の有向グラフは、図５の階層決定処理において、ステップＳ５４で階層決定可能判断処理を行わずに、親ノードの子ノードに、親ノードよりも１つ下の階層を設定することで得られる。具体的には、図１４に示す比較例の有向グラフは、ノードＡを最上位の階層に設定し、ノードＡの子ノードであるノードＢ及びノードＣを、階層決定可能判断処理を行うことなく、共に階層「２」に設定し、ノードＢ及びノードＣの子ノードを、階層決定可能判断処理を行うことなく、共に階層「３」に設定することで得られる。
【００７４】
一般に、有向グラフでは、ノードの左側又は上側にそのノードの親ノードが配置され、ノードの右側又は下側にそのノードの子ノードが配置されていると、ノード間の親子関係が把握しやすい。図１４に示す比較例の有向グラフでは、ノードＢからノードＣに向かうアーク（ａｒｃ１２）と、ノードＥからノードＤに向かうアーク（ａｒｃ１６）とが、右側から左側に向かう向きとなっているため、ノードＢ及びノードＥの子ノードが把握しにくい。
【００７５】
本実施形態例の有向グラフ生成装置１０で得られる有向グラフ（図１３）では、アークの向きが全て左側から右側に向かう向きとなっており、図１４に示す比較例の有向グラフに比して、ノード間の親子関係が把握しやすく、視認性が向上している。また、上記のようにして階層を決定し、グラフ中で、階層の上位側から順に整列するように各ノードを配置して、ノード間をアークで接続するため、可能な限り子ノードはその親ノードの１つ下の階層に配置されることになる。このため、親ノードと子ノードとの間の距離が可能な限り最小となり、アークが他のノードやアークと交差しにくくなって、これによっても視認性が向上する。
【００７６】
特許文献１に記載の技術を含む従来技術において、有向グラフを生成した後に、有向グラフの先頭ノードを、他のノードに変更するときには、先頭ノードを変更することで、ループ形成の状況等が変化するため、ループ解除処理等のノードの配置処理を一からやり直す必要がある。本実施形態例では、ノード間の子孫関係が、先頭ノードがどのノードであるかにかかわらず不変であるため、子孫関係の調査をやり直す必要がない。従って、本実施形態例では、有向グラフの先頭ノードを変更する際には、図２のステップＳ２４から先をやり直せばよく、従来技術に比して、先頭ノード変更時の有向グラフ生成の処理量が低減できる。
【００７７】
従来技術では、グラフにループが形成されるときには、一度ノードを配置し、配置したノードの位置を何度も修正している。これに対して、本実施形態例では、ある親ノードの子ノードのうち、各子ノードに親ノードの１つ下の階層を設定可能か否かを調査し、設定可能とされた子ノードに親ノードの１つ下の階層を設定し、各ノードに設定された階層に基づいて、そのノードの配置位置を決定する。このように、本実施形態例では、ループを解除せずに、ノードの配置位置を変更しなくてもよいように、ノードの階層を決定していくため、上記のような視認性が高い有向グラフを、従来技術に比して少ない処理量で生成することができる。
【００７８】
具体的に、本実施形態例での有向グラフの生成と、特許文献１に記載の技術を含む従来技術との双方について、計算量（処理量）のオーダーを、オーダー記法を使って比較する。オーダー記法とは、計算に必要な要素の数を大きくしていたときの漸近的計算量を示す、アルゴリズムの計算量を表す手法の１つである。本実施形態例では、図２のステップＳ２３で、ノードの子孫関係の調査を行っている。この子孫関係調査処理では、最上位側のノードから、子ノードを順次に一度だけ調査しているため、この処理の計算量のオーダーは、Ｏ（ｎ）（ｎ：ノード数）となる。一方、従来技術では、ノードの子孫関係調査処理は行われていないため、この処理の計算量のオーダーは、Ｏ(０)である。
【００７９】
従来技術では、一度ノードを配置してから、アークの向きが揃わないノードの位置を適切な位置に移動し、出来るだけ多くのアークが同じ方向を向くようにするループ解除処理を行うが、この処理では、ループを解除するために、あるノード座標を変更すると、そのノードの座標が変更されたことで、今度は、他ノードがループを形成することがあるため、再度のループの調査が必要となる。従来技術でのループ解除処理の計算量のオーダーは、Ｏ(ｎ2)となる。本実施形態例では、ループ解除処理を行わないため、ループ解除処理の計算量のオーダーは、Ｏ（０）である。
【００８０】
ノードの配置可能調査処理では、従来技術、本発明ともにハッシュリストによる手法を用いているとすると、何れも、すでに配置済みのノードの調査にＯ(１)のオーダーが必要である。また、このとき、本発明では子孫ノードの存在調査を行う（図７）が、この調査もハッシュリストによる調査であるため、結局、ノードの配置可能調査処理の計算量は、Ｏ(１)のオーダーとなる。
【００８１】
上記した本実施形態例での計算量と、特許文献１に記載の技術での計算量とをまとめると、以下に示す表７のようになる。
【表７】
2005044172.tif 000009
表７からわかるように、出来るだけ多くのアークの向きが揃うように有向グラフを生成するとき、従来技術ではＯ(ｎ2)のオーダーの処理が必要であるのに対し、本実施形態例ではＯ(ｎ)のオーダーで処理が可能である。つまり、本実施形態例では、従来技術に比して、有向グラフの生成に必要な処理量を削減して、有向グラフの生成を簡易に行うことができる。
【００８２】
以下、有向グラフ生成装置１０が、グラフ中にループが形成される有向グラフを生成する際の処理について説明する。図１５（ａ）は、ノード情報記憶部１２２に記憶されているノードの親子関係の別の例を表として示し、同図（ｂ）は、同図（ａ）に示す表から得られる子孫関係ハッシュテーブル１２１を示し、同図（ｃ）は、同図（ａ）に示す表から得られる出力ノードリスト１２３を示し、同図（ｄ）は、同図（ａ）に示す表から図２に示す手順に従って生成された有向グラフを示している。
【００８３】
図１６は、子孫ノード取得処理の再帰呼び出しの様子を示している。子孫ノード取得処理（図３）では、ノード間の親子関係が図１５（ａ）に示すような関係であると、図３のステップＳ３３から、先頭ノードであるノードＡの子孫ノード取得処理（Ｐ１１）が呼び出され（ｃａｌｌ（１１））、次いで、ノードＢの子孫ノード取得処理（Ｐ１２）、ノードＣの子孫ノード取得処理（Ｐ１３）、及び、ノードＤの子孫ノード取得処理（Ｐ１４）が順次に呼び出される。
【００８４】
ノードＤの子孫ノード取得処理（Ｐ１４）では、ノードＤの子ノードであるノードＢが選択されるが（図４のステップＳ４４）、ノードＢは、ノードＢの子孫ノード取得処理（Ｐ１２）で調査済みにされている。このため、ノードＤの子孫ノード取得処理（Ｐ１４）は、ノードＢの子孫ノード取得処理を呼び出すことなく、ノードＢと、この時点でのノードＢの子孫ノード、つまりは子孫ノードなしとを、ノードＣの子孫ノード取得処理（Ｐ１３）に返却する（ｒｅｔ（１４））。
【００８５】
ノードＣの子孫ノード取得処理（Ｐ１３）からは、ノードＣのもう１つの子ノードであるノードＥの子孫ノード取得処理（Ｐ１５）が呼び出され、ノードＥの子孫ノード取得処理（Ｐ１５）は、ノードＥの子孫ノードとして、ノードＤと、ノードＤの子孫ノードであるノードＢとを返却する（ｒｅｔ（１５））。ノードＣの子孫ノード取得処理（Ｐ１３）は、ノードＣの子孫ノードとして、ノードＢ、ノードＤ、及び、ノードＥを返却し（ｒｅｔ（１３））、ノードＢの子孫ノード取得処理（Ｐ１２）は、ノードＢの子孫ノードとして、ノードＢ、ノードＣ、ノードＤ、及び、ノードＥを返却する（ｒｅｔ（１２））。このような処理により、図１５（ｂ）に示すような子孫関係ハッシュテーブル１２１が得られる。
【００８６】
各ノードの階層決定処理（図５）では、先頭ノードであるノードＡが階層「１」に設定され、ステップＳ５２では、階層「２」の候補として、ノードＡの子ノードであるノードＢ、ノードＣ、及び、ノードＥが取得される。これらのノードに対して、階層決定可能判断処理（図６）を行うと、何れもノード間で子孫・先祖関係が生じているため階層決定不可能であるが、例外である、お互いが先祖でもあり子孫でもあるときであって、その他の子ノードの階層が未決定であるときに該当するため、ノードＢ、ノードＣ、及び、ノードＥの何れかは、階層決定可能である。ここでは、子ノードを２つ有するノードＣを階層決定可能として階層「２」に設定し、ノードＢ及びノードＥを、それぞれ階層決定不可能とする。
【００８７】
ノードＣが階層「２」に設定されると、ノードＣの子ノードであるノードＤ及びノードＥの階層が決定可能であるか否かが判断される。このとき、ノードＤは、ノードＥの子孫に含まれているため、ノードＥのみが階層決定可能であると判断され、ノードＥが階層「３」に設定される。その後、ノードＤが階層「４」に設定され、ノードＢが階層「４」に設定され、ＸＹ座標及び出力座標が設定されて、図１５（ｃ）に示すような出力ノードリスト１２３が得られる。この出力ノードリスト１２３に基づいて、出力装置２００の表示画面上には、図１５（ｄ）に示すような有向グラフが出力される。従来の有向グラフ表示システム２０では、図２０（ａ）〜（ｅ）に示すような複雑な過程を経て、各ノードの配置位置が同図（ｅ）に示す位置に決定されるが、本実施形態例では、上記のようにして階層を決定することで、簡易に、各ノードの配置位置が、図１５（ｄ）に示す位置に決定される。つまりは、視認性が高い有向グラフを、簡易に得ることができる。
【００８８】
なお、上記実施形態例では、図２のステップＳ２５のＸＹ座標決定処理（図８）において、各ノードを、そのノードに設定した階層に基づいて、Ｘ方向に整列させて、出力装置２００の表示画面上に表示する例について説明したが、これに代えて、Ｘ座標とＹ座標の関係を入れ替えて、各ノードを、設定した階層に基づいて、Ｙ方向に整列させて表示してもよい。図１７は、図２のステップＳ２５のＸＹ座標決定処理の別の手順例を示している。この例では、有向グラフの整列方向をＸ方向とするか、或いは、Ｙ方向とするかを、オペレータにより、選択可能としている。
【００８９】
ＸＹ座標決定手続き１３２は、図８のステップＳ８１〜Ｓ８３と同様にして、階層未決定の階層Ｌを取得する。オペレータは、有向グラフにおけるノードの配列方向をＸ方向又はＹ方向に設定することができ、ＸＹ座標決定手続き１３２は、オペレータが配列方向をＸ方向に設定していると判断する（ステップＳ１７１）と、ステップＳ８４へ進み、図８の例と同様にして、各ノードのＸＹ座標を決定する。ステップＳ１７１で、配列方向がＹ方向であると判断すると、ＸＹ座標決定手続き１３２は、配列方向がＸ方向であるときのＸ座標と同様にして、階層ＬのＹ座標を決定し（ステップＳ１７２）、配列方向がＸ方向であるときのＹ座標と同様にして、階層Ｌに設定される各ノードのＸ座標を設定する。
【００９０】
図１８は、配列方向をＹ方向とした有向グラフの例を示している。この例のように、アークの向きが、Ｙ方向に揃うようにしても、図１３の例と同様に、ノード間の親子関係が把握しやすくなる。ＸＹ座標決定手続き１３２を、図１７に示す手順例のように構成することで、オペレータは、出力装置の表示画面の構成や、作成する有向グラフの外観に応じて、図１３に示す有向グラフ、又は、図１７に示す有向グラフを選択して表示させることができる。
【００９１】
以上、本発明をその好適な実施形態例に基づいて説明したが、本発明の有向グラフ生成方法及びプログラムは、上記実施形態例にのみ限定されるものではなく、上記実施形態例の構成から種々の修正及び変更を施したものも、本発明の範囲に含まれる。
【図面の簡単な説明】
【００９２】
【図１】本発明の一実施形態例の有向グラフ生成装置の構成を示す機能ブロック図。
【図２】有向グラフ生成装置１０の処理手順例を示すフローチャート。
【図３】図２のステップＳ２３の子孫ノード調査処理の手順例を示すフローチャート。
【図４】図３のステップＳ３３の子孫ノード取得処理の手順例を示すフローチャート。
【図５】図２のステップＳ２４の階層決定処理の手順例を示すフローチャート。
【図６】図５のステップＳ５４の階層決定可能判断処理の処理手順例を示すフローチャート。
【図７】図６のステップＳ６２の子孫ノード判断処理の処理手順例を示すフローチャート。
【図８】図２のステップＳ２５のＸＹ座標決定処理の手順例を示すフローチャート。
【図９】図２のステップＳ２６の座標変換処理の手順例を示すフローチャート。
【図１０】図２のステップＳ２７の出力処理の手順例を示すフローチャート。
【図１１】子孫ノード取得処理の再帰呼び出しの様子を示すブロック図。
【図１２】各ノードの階層決定の様子を示すフローチャート。
【図１３】出力装置の表示画面上に表示される有向グラフを示すブロック図。
【図１４】比較例の有向グラフを示すブロック図。
【図１５】図１５（ａ）は、ノード情報記憶部１２２に記憶されているノードの親子関係の別の例を示す表、同図（ｂ）は、同図（ａ）に示す表から得られる子孫関係ハッシュテーブル１２１を示す表、同図（ｃ）は、同図（ａ）に示す表から得られる出力ノードリスト１２３を示す表、同図（ｄ）は、同図（ａ）に示す表から図２に示す手順に従って生成された有向グラフを示すブロック図。
【図１６】子孫ノード取得処理の再帰呼び出しの様子を示すブロック図。
【図１７】図２のステップＳ２５のＸＹ座標決定処理の手順例を示すフローチャート。
【図１８】配列方向をＹ方向とした有向グラフの例を示すブロック図。
【図１９】従来の有向グラフ表示システムの構成を示す機能ブロック図。
【図２０】図２０（ａ）〜（ｅ）は、有向グラフ表示システム２０を利用して有向グラフを生成する様子を段階ごとに示すブロック図。
【符号の説明】
【００９３】
１０：有向グラフ生成装置
１００：コンピュータシステム
１１０：ハッシュテーブル設定手続き
１１１：ノードＩＤ設定手続き
１１２：子孫関係調査手続き
１２０：ノード情報格納部
１２１：子孫関係ハッシュテーブル
１２２：ノード情報記憶部
１２３：出力ノードリスト
１３０：有向グラフ生成手続き
１３１：階層決定手続き
１３２：ＸＹ座標決定手続き
１３３：座標変換手続き
１４０：子孫ノード判断手続き
１５０：出力手続き
２００：出力装置
【図１】
2005044172.tif 000010
【図２】
2005044172.tif 000011
【図３】
2005044172.tif 000012
【図４】
2005044172.tif 000013
【図５】
2005044172.tif 000014
【図６】
2005044172.tif 000015
【図７】
2005044172.tif 000016
【図８】
2005044172.tif 000017
【図９】
2005044172.tif 000018
【図１０】
2005044172.tif 000019
【図１１】
2005044172.tif 000020
【図１２】
2005044172.tif 000021
【図１３】
2005044172.tif 000022
【図１４】
2005044172.tif 000023
【図１５】
2005044172.tif 000024
【図１６】
2005044172.tif 000025
【図１７】
2005044172.tif 000026
【図１８】
2005044172.tif 000027
【図１９】
2005044172.tif 000028
【図２０】
2005044172.tif 000029