(57)【要約】【課題】ノード数が多い場合でも、ノードの配置計算を迅速かつ効率的におこなうノード位置算出プログラム、ノード位置算出方法およびノード位置算出装置を提供すること。【解決手段】ノード位置算出部１５が、親ノードが子ノードよりも上位のレイヤに割り当てられた有向グラフに含まれるノードの各レイヤ内での１次元位置情報を遺伝的アルゴリズムで用いられる遺伝子とし、遺伝子により構成される配列を遺伝的アルゴリズムで用いられる染色体として主記憶部１２に記憶し、記憶された染色体に基づいてレイヤごとのノードの配置位置を遺伝的アルゴリズムにより算出する。【選択図】        図１
2005323109.tif 000002
【特許請求の範囲】
【請求項１】
２つのノードを連結する方向性のあるエッジ、連結元となる親ノードおよび連結先となる子ノードにより構成される有向グラフにおけるノードの配置位置を算出する処理で用いられるノード位置算出プログラムであって、
前記親ノードが子ノードよりも上位の階層に割り当てられた有向グラフに含まれるノードの各階層内での１次元位置情報を遺伝的アルゴリズムで用いられる遺伝子とし、該遺伝子により構成される配列を遺伝的アルゴリズムで用いられる染色体として記憶する記憶手順と、
前記記憶手順により記憶された染色体に基づいて階層ごとのノードの配置位置を遺伝的アルゴリズムにより算出する算出手順と、
をコンピュータに実行させることを特徴とするノード位置算出プログラム。
【請求項２】
親ノードと子ノードとの間の連結関係に基づいて有向グラフに含まれる各ノードを前記親ノードが子ノードよりも上位の階層に属するように各階層に割り当てるノード割当手順をさらに含み、前記記憶手順は、前記ノード割当手順により各階層に割り当てられたノードの各階層内での１次元位置情報を前記遺伝子とし、該遺伝子により構成される配列を前記染色体として記憶することを特徴とする請求項１に記載のノード位置算出プログラム。
【請求項３】
前記ノード割当手順は、親ノードと子ノードとが複数の階層をまたいで連結されている場合に、該親ノードと子ノードとの双方に連結されるダミーのノードを該親ノードおよび子ノードの組に対して１つ生成し、生成したダミーのノードを前記複数の階層に割り当てることを特徴とする請求項２に記載のノード位置算出プログラム。
【請求項４】
前記ノード割当手順は、有向グラフに含まれる複数のノードの連結関係がループ状態にあり、親ノードが子ノードよりも上位の階層に割り当てることができない場合に、該親ノードと子ノードとの間の連結元および連結先の連結関係を逆転させ、該連結関係を逆転させた親ノードおよび子ノードを各階層に割り当てることを特徴とする請求項２または３に記載のノード位置算出プログラム。
【請求項５】
２つのノードを連結する方向性のあるエッジ、連結元となる親ノードおよび連結先となる子ノードにより構成される有向グラフにおけるノードの配置位置を算出するノード位置算出装置であって、
前記親ノードが子ノードよりも上位の階層に割り当てられた有向グラフに含まれるノードの各階層内での１次元位置情報を遺伝的アルゴリズムで用いられる遺伝子とし、該遺伝子により構成される配列を遺伝的アルゴリズムで用いられる染色体として記憶する記憶手段と、
前記記憶手段により記憶された染色体に基づいて階層ごとのノードの配置位置を遺伝的アルゴリズムにより算出する算出手段と、
を備えたことを特徴とするノード位置算出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、２つのノードを連結する方向性のあるエッジ、連結元となる親ノードおよび連結先となる子ノードにより構成される有向グラフにおけるノードの配置位置を算出するノード位置算出プログラム、ノード位置算出方法およびノード位置算出装置に関し、特に、ノード数が多い場合でも、ノードの配置計算を迅速かつ効率的におこなうことができるノード位置算出プログラム、ノード位置算出方法およびノード位置算出装置に関する。
【背景技術】
【０００２】
従来、プロジェクトなどで発生する各作業の流れや作業の依存関係を容易に把握するために、ＰＤＭ（Precedence Diagram）やＡＤＭ（Arrow Diagram）、ＰＥＲＴ（Program Evolution and Review Technique）図などのネットワーク状の有向グラフが頻繁に用いられている。
【０００３】
図１４に、このようなネットワーク状の有向グラフの一例を示す。図１４に示すように、この有向グラフでは、ノード間の依存関係が方向性をもつエッジ（枝）で表されている。ここで、ノードａからノードｄに伸びるエッジは、ノードｂからノードｆに伸びるエッジと交差して見にくいため、ノードの再配置をおこなって有向グラフを見やすくする方法が開発されている。
【０００４】
たとえば、非特許文献１には、ノードの再配置をおこなって見やすい有向グラフを作成するノード配置アルゴリズムが開示されている。図１５は、この従来のノード配置アルゴリズムを説明する説明図である。
【０００５】
図１５に示すように、このノード配置アルゴリズムでは、各ノードａ〜ｆをいくつかのレイヤに割り当てて階層化し、各レイヤにおいてノードの位置を入れ替え、ノードを連結しているエッジの長さを最小にすることにより、エッジどうしの交差の数を減少させる。
【０００６】
また、このノード配置アルゴリズムでは、ノードｂからノードｆ、あるいは、ノードｄからノードｆのように、ノードがレイヤをまたいで連結されている場合に、レイヤごとにダミーノードＤ１〜Ｄ３を挿入し、ノード間を連結しているエッジを分割する。ダミーノードを挿入する理由は、レイヤをまたいでノード間を連結しているエッジが他のエッジと交差してしまうことを防止するためである。
【０００７】
そして、各レイヤにおいてダミーノードＤ１〜Ｄ３を含めたノードの位置の入れ替え処理をおこなってエッジどうしの交差の数を減少させ、最後に、ダミーノードＤ１〜Ｄ３を取り除いて、見やすい有効グラフを作成する。
【０００８】
【非特許文献１】Kozo Sugiyama, Shojiro Tagawa and Mitsuhiko Toda, "Methods for visual understanding of hierarchical system structures", IEEE Trans. on Systems, Man, and Cybernetics, vol.SMC-11, no.2, pp.109-125, 1981.
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、上記非特許文献１の従来技術では、エッジどうしの交差の数を最小化するようノードの最適な配置位置を算出するが、ノード数が増加するにしたがって計算時間が急激に増大し、最適解を迅速に得ることができなくなるため、実用上問題があった。
【００１０】
すなわち、有向グラフの見やすさを改善する場合、長時間計算をおこなってエッジどうしの交差数が最小となる最適解を得ることが必ずしも望ましいわけではなく、最適解に近い解を短時間で効率よく得ることが実用上望ましい場合も多い。
【００１１】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、ノード数が多い場合でもノードの配置計算を迅速かつ効率的におこなうことができるノード位置算出プログラム、ノード位置算出方法およびノード位置算出装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するため、本発明は、２つのノードを連結する方向性のあるエッジ、連結元となる親ノードおよび連結先となる子ノードにより構成される有向グラフにおけるノードの配置位置を算出する処理で用いられるノード位置算出プログラムであって、前記親ノードが子ノードよりも上位の階層に割り当てられた有向グラフに含まれるノードの各階層内での１次元位置情報を遺伝的アルゴリズムで用いられる遺伝子とし、該遺伝子により構成される配列を遺伝的アルゴリズムで用いられる染色体として記憶する記憶手順と、前記記憶手順により記憶された染色体に基づいて階層ごとのノードの配置位置を遺伝的アルゴリズムにより算出する算出手順と、をコンピュータに実行させることを特徴とする。
【００１３】
また、本発明は、親ノードと子ノードとの間の連結関係に基づいて有向グラフに含まれる各ノードを前記親ノードが子ノードよりも上位の階層に属するように各階層に割り当てるノード割当手順をさらに含み、前記記憶手順は、前記ノード割当手順により各階層に割り当てられたノードの各階層内での１次元位置情報を前記遺伝子とし、該遺伝子により構成される配列を前記染色体として記憶することを特徴とする。
【００１４】
また、本発明は、前記ノード割当手順は、親ノードと子ノードとが複数の階層をまたいで連結されている場合に、該親ノードと子ノードとの双方に連結されるダミーのノードを該親ノードおよび子ノードの組に対して１つ生成し、生成したダミーのノードを前記複数の階層に割り当てることを特徴とする。
【００１５】
また、本発明は、前記ノード割当手順は、有向グラフに含まれる複数のノードの連結関係がループ状態にあり、親ノードが子ノードよりも上位の階層に割り当てることができない場合に、該親ノードと子ノードとの間の連結元および連結先の連結関係を逆転させ、該連結関係を逆転させた親ノードおよび子ノードを各階層に割り当てることを特徴とする。
【００１６】
また、本発明は、２つのノードを連結する方向性のあるエッジ、連結元となる親ノードおよび連結先となる子ノードにより構成される有向グラフにおけるノードの配置位置を算出するノード位置算出方法であって、前記親ノードが子ノードよりも上位の階層に割り当てられた有向グラフに含まれるノードの各階層内での１次元位置情報を遺伝的アルゴリズムで用いられる遺伝子とし、該遺伝子により構成される配列を遺伝的アルゴリズムで用いられる染色体として記憶する記憶工程と、前記記憶工程により記憶された染色体に基づいて階層ごとのノードの配置位置を遺伝的アルゴリズムにより算出する算出工程と、を含んだことを特徴とする。
【００１７】
また、本発明は、２つのノードを連結する方向性のあるエッジ、連結元となる親ノードおよび連結先となる子ノードにより構成される有向グラフにおけるノードの配置位置を算出するノード位置算出装置であって、前記親ノードが子ノードよりも上位の階層に割り当てられた有向グラフに含まれるノードの各階層内での１次元位置情報を遺伝的アルゴリズムで用いられる遺伝子とし、該遺伝子により構成される配列を遺伝的アルゴリズムで用いられる染色体として記憶する記憶手段と、前記記憶手段により記憶された染色体に基づいて階層ごとのノードの配置位置を遺伝的アルゴリズムにより算出する算出手段と、を備えたことを特徴とする。
【発明の効果】
【００１８】
本発明によれば、親ノードが子ノードよりも上位の階層に割り当てられた有向グラフに含まれるノードの各階層内での１次元位置情報を遺伝的アルゴリズムで用いられる遺伝子とし、遺伝子により構成される配列を遺伝的アルゴリズムで用いられる染色体として記憶し、記憶された染色体に基づいて階層ごとのノードの配置位置を遺伝的アルゴリズムにより算出することとしたので、ノード数が多い場合でもノードの配置計算を迅速かつ効率的におこなうことができるという効果を奏する。
【００１９】
また、本発明によれば、親ノードと子ノードとの間の連結関係に基づいて有向グラフに含まれる各ノードを親ノードが子ノードよりも上位の階層に属するように各階層に割り当て、各階層に割り当てられたノードの各階層内での１次元位置情報を遺伝子とし、遺伝子により構成される配列を染色体として記憶することとしたので、有向グラフにおける各ノードを効率的に階層化し、ノードの配置計算を迅速かつ効率的におこなうことができるという効果を奏する。
【００２０】
また、本発明によれば、親ノードと子ノードとが複数の階層をまたいで連結されている場合に、親ノードと子ノードとの双方に連結されるダミーのノードを親ノードおよび子ノードの組に対して１つ生成し、生成したダミーのノードを複数の階層に割り当てることとしたので、追加するダミーのノードの数を少なくし、ノード数が多い場合でもノードの配置計算を迅速かつ効率的におこなうことができるという効果を奏する。
【００２１】
また、本発明によれば、有向グラフに含まれる複数のノードの連結関係がループ状態にあり、親ノードが子ノードよりも上位の階層に割り当てることができない場合に、親ノードと子ノードとの間の連結元および連結先の連結関係を逆転させ、連結関係を逆転させた親ノードおよび子ノードを各階層に割り当てることとしたので、ループ状態を一旦解消することによりノードの配置計算を容易かつ効率的に実行でき、配置計算の終了後、親ノードと子ノードとの間の連結関係を復元することにより、ノードの連結関係がループ状態にある場合でも、ノードの最適な配置を得ることができるという効果を奏する。
【発明を実施するための最良の形態】
【００２２】
以下に添付図面を参照して、本発明に係るノード位置算出プログラム、ノード位置算出方法およびノード位置算出装置の好適な実施例を詳細に説明する。
【実施例】
【００２３】
まず、本実施例に係るノード位置算出装置の機能的構成について説明する。図１は、本実施例に係るノード位置算出装置の機能的構成を示す機能ブロック図である。このノード位置算出装置は、有効グラフにおいて、ノード間を連結するエッジの交差を解消し、有向グラフが見やすくなるようノードの配置位置を算出する装置である。
【００２４】
このノード位置算出装置は、遺伝的アルゴリズムを用いて有効グラフのノードの配置位置を算出する。その際、親ノードが子ノードよりも上位のレイヤに属するように各ノードをレイヤに割り当て、各ノードの垂直位置座標を固定する。
【００２５】
そして、ノードの水平位置座標を遺伝的アルゴリズムで用いられる遺伝子とし、その遺伝子の配列を用いて遺伝的アルゴリズムで用いられる染色体を構成し、その染色体に対して交叉や突然変異、選択などの遺伝子操作をおこなうことにより、エッジの交差を解消するノードの位置を算出する。このように、ノードの水平位置座標のみを染色体の構成要素として考慮し、遺伝子操作をおこなうことにより、ノードの配置計算を迅速かつ効率的におこなうことができる。
【００２６】
図１に示すように、ノード位置算出装置は、入力部１０、表示部１１、主記憶部１２、補助記憶部１３、ノード割当部１４、ノード位置算出部１５、ノード配置部１６および制御部１７を有する。
【００２７】
入力部１０は、キーボードやマウスなどの入力デバイスである。表示部１１は、ディスプレイなどの表示デバイスである。主記憶部１２は、ＲＡＭ（Random Access Memory）などの主記憶装置であり、染色体などの各種データを一時的に記憶する処理をおこなう。
【００２８】
補助記憶部１３は、ハードディスク装置や光ディスク装置などの補助記憶装置であり、オペレーティングシステムや、各種プログラム、ノードの配置計算をおこなう有効グラフに係るデータなどを記憶する。この有向グラフに係るデータには、各ノードの位置情報や、エッジにより連結されている親ノードおよび子ノードの組み合わせの情報などが含まれる。
【００２９】
ノード割当部１４は、ノード間を連結するエッジの連結元となる親ノードおよび連結先となる子ノードの連結関係に基づいて、各ノードを各レイヤに割り当てる処理をおこなう。このノード割当部１４は、レイヤ設定部１４ａ、ダミーノード追加部１４ｂおよびループ切断部１４ｃを有する。
【００３０】
レイヤ設定部１４は、有向グラフに含まれる各ノードを複数のレイヤに割り当て、レイヤを設定する処理をおこなう。図２は、各ノードを複数のレイヤに割り当てる処理について説明する説明図である。
【００３１】
図２に示すように、レイヤ設定部１４は、エッジの連結元となる親ノードおよび連結先となる子ノードの連結関係に基づいて、親ノードが子ノードよりも上位のレイヤに属するようノードａ〜ｆを各レイヤ１〜３に割り当てる処理をおこなう。
【００３２】
図１の説明に戻ると、ダミーノード追加部１４ｂは、親ノードと子ノードとがレイヤをまたいで連結されている場合に、親ノードおよび子ノードの双方に連結されるダミーノードを親ノードおよび子ノードの組に対して１つ生成し、生成したダミーのノードを上記レイヤに割り当てる処理をおこなう。図３は、ダミーノードをレイヤに割り当てる処理について説明する説明図である。
【００３３】
図３に示すように、ダミーノード追加部１４ｂは、親ノードｂと子ノードｆ、または、親ノードｄと子ノードｆとがレイヤをまたいで連結されている場合に、それを検出し、ダミーノードＤ１およびＤ３を生成する。特に、親ノードｂと子ノードｆとが複数のレイヤ２および３をまたいで連結されている場合には、親ノードｂおよび子ノードｆの組に対してダミーノードＤ１を１つだけ生成し、レイヤ２および３に対してダミーノードＤ１を割り当てる処理をおこなう。
【００３４】
このように、レイヤ２および３に対してダミーノードＤ１を１つだけ割り当てることにより、ノードの数を減少させ、遺伝的アルゴリズムを適用した際の計算時間を削減することができる。
【００３５】
図１の説明に戻ると、ループ切断部１４ｃは、有向グラフに含まれる複数のノードの連結関係がループ状態にあり、ノードを連結するエッジが、下位のレイヤから上位のレイヤに伸びる場合に、エッジの方向を逆転することにより、連結元である親ノードと連結先である子ノードの連結関係を逆転させる。
【００３６】
すなわち、ループ切断部１４ｃは、親ノードが配置されるレイヤが、子ノードが配置されるレイヤよりも下位のレイヤとなってしまう場合に、子ノードを親ノードに、親ノードを子ノードに設定し、連結関係が逆転した親ノードおよび子ノードをレイヤに割り当てることにより、ループを切断する処理をおこなう。図４は、親ノードおよび子ノードの連結関係を逆転させる処理について説明する説明図である。
【００３７】
図４の例では、ノードｆとノードｃとの連結関係において、親ノードであるノードｆが配置されるレイヤ４が、子ノードであるノードｃが配置されるレイヤ２よりも下位のレイヤとなり、ノードｃ、ノードｅおよびノードｆがループを形成している。この場合、ループ切断部１４ｃは、ノードｆとノードｃとの間の連結関係を逆転し、ノードｃを親ノード、ノードｆを子ノードとして設定する処理をおこなう。
【００３８】
このように、親ノードと子ノードとの間の連結関係を逆転させることにより、複雑な処理を必要とせず、親ノードおよび子ノードをそれぞれ上位および下位のレイヤに割り当ててループ状態を解消することができ、以下に説明するノードの配置位置の計算を、通常のノードと同様のアルゴリズムを用いて容易に実行することができるようになる。
【００３９】
図１の説明に戻ると、ノード位置算出部１５は、ノードの各レイヤ内での１次元の水平位置座標を遺伝子とし、遺伝子により構成される配列を染色体として主記憶部１２に記憶し、記憶された染色体を用いて、エッジの交差の少ない、ノードの最適な配置位置を遺伝的アルゴリズムにより算出する処理をおこなう。
【００４０】
具体的には、ノード位置算出部１５は、遺伝的アルゴリズムにより交叉や突然変異、選択などの遺伝子操作をおこない、染色体の世代を交代させる。そして、染色体の世代が交代するごとに、ノード位置算出部１５は、染色体により指定されるノードの配置位置の評価を所定の評価関数を用いておこない、評価が低い染色体を淘汰する。そして、世代交代が所定の回数進んだら計算処理を終了する。この評価関数については、後に詳しく説明する。
【００４１】
図５は、ノードの最適な配置位置の算出例を示す図であり、図６は、図５に示したノード配置に対応する染色体の例を示す図である。図５の例では、ノードａからノードｄに伸びるエッジが、ノードｂからノードｅに伸びるエッジと交差している。このエッジどうしの交差を解消するため、ノード位置算出部１５は、遺伝的アルゴリズムを用いて最適なノードの配置位置を求める。
【００４２】
エッジが交差している場合の染色体６０は、図６に示すように、「１２１３２１」と表される。ここで、染色体６０の各数字は、レイヤごとのノードａ〜ｆの水平位置の情報であり、レイヤごとに図５の左側から数えたノードの順番を表している。そして、ノード位置算出部１５により遺伝的アルゴリズムが適用され、エッジどうしの交差が解消された後の染色体６１は、「１２１２３１」となる。
【００４３】
ここで、染色体により表現されるノードの配置位置を評価する評価関数について説明する。図７は、ノード間の連結関係を記憶したノードパスデータ７０の一例を示す図であり、図８は、ノードの配置状況を評価する評価処理について説明する図である。このノードパスデータ７０は、主記憶部１２に記憶される。
【００４４】
図７に示すように、ノードパスデータ７０は、親ノードと子ノードとの間の連結関係を記憶したデータであり、レイヤとパスの情報を記憶している。レイヤは、親ノードおよび子ノードが属するレイヤの情報である。たとえば、「１−２」は、親ノードがレイヤ１に、子ノードがレイヤ２に属することを示している。パスは、互いに連結されている親ノードと子ノードとの組み合わせを示す情報である。たとえば、（ａ，ｃ）は、親ノードａと子ノードｃとが連結されていることを示している。
【００４５】
また、ここでは、ノードの位置情報を指定する染色体を、以下の条件により評価する。「条件：親ノードと子ノードとが連結されたパスの組み合わせ（ｘ，ｙ）および（ｘ’，ｙ’）において、Ｐｘ、Ｐｙ、Ｐｘ’およびＰｙ’をｘ、ｙ、ｘ’およびｙ’の水平位置座標とした場合に、Ｐｘ≦Ｐｘ’かつＰｙ≦Ｐｙ’」。そして、この条件を満足しないパスの組み合わせの数を遺伝的アルゴリズムにおいて染色体を評価する際の評価関数として用いることとする。
【００４６】
この条件に基づいて、ノードの配置状況を評価した例が、図８に示されている。図８に示すように、ノード位置算出部１５は、すべてのパスの組み合わせに対してノードの水平位置座標の比較をおこない、上記条件が満足されるか否かを調べる処理をおこなう。
【００４７】
たとえば、パスの組み合わせ（ａ，ｃ）および（ａ，ｄ）においては、図６に示すように、ノードａの水平座標位置Ｐａは共通でＰａ＝Ｐａであり、ノードｃおよびノードｄの水平位置座標の関係はＰｃ＜Ｐｄであるので、上記条件を満足し、評価は「可」となる。
【００４８】
また、パスの組み合わせ（ａ，ｃ）および（ｂ，ｄ）においては、ノードａおよびノードｂの水平位置座標の関係はＰａ＜Ｐｂであり、ノードｃおよびノードｄの水平位置座標の関係はＰｃ＜Ｐｄであるので、上記条件を満足し、評価は「可」となる。以下同様にして、パスの組み合わせ（ａ，ｃ）および（ｂ，ｅ）、パスの組み合わせ（ａ，ｄ）および（ｂ，ｄ）についても、評価は「可」となる。
【００４９】
ところが、パスの組み合わせ（ａ，ｄ）および（ｂ，ｅ）については、ノードａおよびノードｂの水平位置座標の関係はＰａ＜Ｐｂであり、ノードｄおよびノードｅの水平位置座標の関係はＰｄ＞Ｐｅであるので、上記条件を満足せず、評価は「不可」となる。また、パスの組み合わせ（ｂ，ｄ）および（ｂ，ｅ）についても、評価は「不可」となる。
【００５０】
この例の場合、評価が不可であるパスの組み合わせの数は２であり、この値が評価関数の値となる。評価関数の値が大きい染色体は適応度が低いものとして、遺伝的アルゴリズムを適用した場合に淘汰され、評価関数の値が小さい染色体のみ残されるようになる。このようにして、ノードの配置位置の最適解を効率的に求めることができる。
【００５１】
なお、図５から図８では、ダミーノードがない場合について説明したが、ダミーノードがある場合も同様に、最適なノードの配置位置を求めることができる。図９は、ダミーノードがある場合のノードの最適な配置位置の算出例を示す図であり、図１０は、図９に示したノード配置に対応する染色体の例を示す図である。
【００５２】
図９には、ダミーノード追加部１４ｂにより追加されたダミーノードＤ１およびＤ３が示されている。ノード位置算出部１５は、図１０に示すように、このダミーノードＤ１およびＤ３の水平位置座標を追加して、染色体１００の配列「１２１３１２２３」を生成する。ここで、染色体１００の各数字は、レイヤごとのノードａ〜ｆおよびダミーノードＤ１、Ｄ３の水平位置の情報であり、レイヤごとに図９の左側から数えたノードの順番を表している。
【００５３】
そして、ノード位置算出部１５は、遺伝的アルゴリズム利用して、交叉や突然変異、選択の遺伝子操作をおこない、エッジの交差を解消するノードの配置位置を算出する。図１０には、エッジどうしの交差が解消された後の染色体１０１の配列「１２１２１２３２」が示されている。
【００５４】
ここで、ダミーノードＤ１は、レイヤ２とレイヤ３の２つのレイヤにまたがっているため、たとえば、ダミーノードＤ１とレイヤ２に属するノードｄとの水平位置が入れ替わる場合には、ダミーノードＤ１とレイヤ３に属するダミーノードＤ３との水平位置が重ならないように制御する。
【００５５】
図１の説明に戻ると、ノード配置部１６は、ノード位置算出部１５により算出されたノードの最適な座標位置の情報を基にして、ノードを配置した有効グラフを表示部１１に出力する処理をおこなう。
【００５６】
その際、ノード配置部１６は、ダミーノード追加部１４ｂにより追加されたダミーノードを削除して、図９に示すように、親ノードからダミーノードに伸びるエッジの終点とダミーノードから子ノードに伸びるエッジの始点を連結して１つのエッジとする処理をおこなう。また、ノード配置部１６は、ループ切断部１４ｃにより親ノードおよび子ノードの連結関係が逆転された箇所を、逆転処理以前の連結関係に復元する処理をおこなう。
【００５７】
制御部１７は、ノード位置算出装置を全体制御する制御部である。この制御部１７は、各機能部間のデータの授受などを司る。
【００５８】
つぎに、ノード位置算出装置がおこなうノード配置処理の処理手順について説明する。図１１は、ノード位置算出装置がおこなうノード配置処理の処理手順を示すフローチャートである。
【００５９】
図１１に示すように、まず、ノード位置算出装置のレイヤ設定部１４ａは、補助記憶部１３に記憶された各ノードの位置情報およびノード間の連結情報を取得する（ステップＳ１０１）。そして、レイヤ設定部１４ａは、取得した位置情報および連結情報に基づいて、親ノードが子ノードよりも上位のレイヤに属するように各ノードをレイヤに割り当てる階層化処理をおこなう（ステップＳ１０２）。
【００６０】
ここで、有向グラフに含まれる複数のノードの連結関係がループ状態にあり、親ノードが子ノードよりも上位のレイヤに割り当てられない場合には、レイヤ設定部１４ａは、親ノードを下位のレイヤに一時的に割り当てる。
【００６１】
続いて、ダミーノード追加部１４ｂは、親ノードと子ノードとがレイヤをまたいで連結されているかどうかを検出し、レイヤをまたいで連結されている場合に、親ノードおよび子ノードと連結されるダミーノードを親ノードおよび子ノードの組に対して１つ生成し、生成したダミーノードを上記レイヤに割り当てるダミーノード追加処理をおこなう（ステップＳ１０２）。
【００６２】
そして、ループ切断部１４ｃは、有向グラフに含まれる複数のノードの連結関係がループ状態にあるため、レイヤ設定部１４ａにより親ノードが子ノードよりも下位のレイヤに一時的に割り当てられたかどうかを検出し、下位のレイヤに一時的に割り当てられた場合に、親ノードと子ノードとの間の連結関係を逆転させ、子ノードを親ノードに、親ノードを子ノードに設定し、ループを切断する処理をおこなう（ステップＳ１０４）。
【００６３】
その後、ノード位置算出部１５は、各ノードの水平位置の座標から遺伝的アルゴリズムで用いる染色体を生成し（ステップＳ１０５）、遺伝的アルゴリズムにより交叉や突然変異、選択などの遺伝子操作をおこない、各ノードの最適な配置を得るための世代計算処理をおこなう（ステップＳ１０６）。
【００６４】
世代計算処理の終了後、ノード配置部１６は、ステップＳ１０４で逆転させた親ノードと子ノードとの間の連結関係を再び逆転させ、親ノードを子ノードに、子ノードを親ノードに設定することにより、切断したループを復元する処理をおこなう（ステップＳ１０７）。
【００６５】
さらに、ノード配置部１６は、ステップＳ１０３で追加したダミーノードを削除し、図９に示したように、ダミーノードに連結されていた親ノードおよび子ノードを連結する処理をおこなう（ステップＳ１０８）。
【００６６】
その後、ノード配置部１６は、ループが復元され、ダミーノードが除去された有効グラフを表示部１１に出力する処理をおこない（ステップＳ１０９）、このノード配置処理を終了する。
【００６７】
ところで、上記実施例で説明したノード位置算出装置およびノード位置算出方法は、あらかじめ用意されたプログラムをパーソナル・コンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することができる。
【００６８】
そこで、以下では、上記実施例で説明したノード位置算出装置（ノード位置算出方法）と同様の機能を有するノード位置算出プログラムを実行するコンピュータシステムについて説明する。
【００６９】
図１２は、本実施例に係るコンピュータシステム２００の構成を示すシステム構成図であり、図１３は、図１２に示したコンピュータシステム２００に係る本体部２０１の構成を示すブロック図である。
【００７０】
図１２に示すように、本実施例に係るコンピュータシステム２００は、本体部２０１と、本体部２０１からの指示によって表示画面２０２ａに画像などの情報を表示するためのディスプレイ２０２と、このコンピュータシステム２００に種々の情報を入力するためのキーボード２０３と、ディスプレイ２０２の表示画面２０２ａ上の任意の位置を指定するためのマウス２０４とを備える。
【００７１】
また、このコンピュータシステム２００における本体部２０１は、図１３に示すように、ＣＰＵ２２１と、ＲＡＭ２２２と、ＲＯＭ２２３と、ハードディスクドライブ（ＨＤＤ）２２４と、ＣＤ−ＲＯＭ２０９を受け入れるＣＤ−ＲＯＭドライブ２２５と、フレキシブルディスク（ＦＤ）２０８を受け入れるＦＤドライブ２２６と、ディスプレイ２０２、キーボード２０３ならびにマウス２０４を接続するＩ／Ｏインターフェース２２７と、ローカルエリアネットワークまたはワイドエリアネットワーク（ＬＡＮ／ＷＡＮ）２０６に接続するＬＡＮインターフェース２２８とを備える。
【００７２】
さらに、このコンピュータシステム２００には、インターネットなどの公衆回線２０７に接続するためのモデム２０５が接続されるとともに、ＬＡＮインターフェース２２８およびＬＡＮ／ＷＡＮ２０６を介して、他のコンピュータシステム（ＰＣ）２１１、サーバ２１２ならびにプリンタ２１３などが接続される。
【００７３】
そして、このコンピュータシステム２００は、所定の記録媒体に記録されたノード位置算出プログラムを読み出して実行することで、ノード位置算出装置（ノード位置算出方法）を実現する。
【００７４】
ここで、所定の記録媒体とは、フレキシブルディスク（ＦＤ）２０８、ＣＤ−ＲＯＭ２０９、ＭＯディスク、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」の他に、コンピュータシステム２００の内外に備えられるハードディスクドライブ（ＨＤＤ）２２４や、ＲＡＭ２２２、ＲＯＭ２２３などの「固定用の物理媒体」、さらに、モデム２０５を介して接続される公衆回線２０７や、他のコンピュータシステム２１１ならびにサーバ１１２が接続されるＬＡＮ／ＷＡＮ２０６などのように、プログラムの送信に際して短期にプログラムを保持する「通信媒体」など、コンピュータシステム２００によって読み取り可能なノード位置算出プログラムを記録する、あらゆる記録媒体を含むものである。
【００７５】
すなわち、ノード位置算出プログラムは、上記した「可搬用の物理媒体」、「固定用の物理媒体」、「通信媒体」などの記録媒体に、コンピュータ読み取り可能に記録されるものであり、コンピュータシステム２００は、このような記録媒体からノード位置算出プログラムを読み出して実行することでノード位置算出装置およびノード位置算出方法を実現する。
【００７６】
なお、ノード位置算出プログラムは、コンピュータシステム２００によって実行されることに限定されるものではなく、他のコンピュータシステム２１１またはサーバ２１２がノード位置算出プログラムを実行する場合や、これらが協働してノード位置算出プログラムを実行するような場合にも、本発明を同様に適用することができる。
【００７７】
上述してきたように、本実施例では、ノード位置算出部１５が、親ノードが子ノードよりも上位のレイヤに割り当てられた有向グラフに含まれるノードの各レイヤ内での１次元位置情報を遺伝的アルゴリズムで用いられる遺伝子とし、遺伝子により構成される配列を遺伝的アルゴリズムで用いられる染色体として主記憶部１２に記憶し、記憶された染色体に基づいてレイヤごとのノードの配置位置を遺伝的アルゴリズムにより算出することとしたので、ノード数が多い場合でもノードの配置計算を迅速かつ効率的におこなうことができる。
【００７８】
また、本実施例では、レイヤ設定部１４ａが、親ノードと子ノードとの間の連結関係に基づいて有向グラフに含まれる各ノードを親ノードが子ノードよりも上位のレイヤに属するように各レイヤに割り当て、各レイヤに割り当てられたノードの各レイヤ内での１次元位置情報を遺伝子とし、遺伝子により構成される配列を染色体として主記憶部１２に記憶することとしたので、有向グラフにおける各ノードを効率的に階層化し、ノードの配置計算を迅速かつ効率的におこなうことができる。
【００７９】
また、本実施例では、親ノードと子ノードとが複数のレイヤをまたいで連結されている場合に、ダミーノード追加部１４ｂが、親ノードと子ノードとの双方に連結されるダミーノードを親ノードおよび子ノードの組に対して１つ生成し、生成したダミーノードを複数のレイヤに割り当てることとしたので、追加するダミーノードの数を少なくし、ノード数が多い場合でもノードの配置計算を迅速かつ効率的におこなうことができる。
【００８０】
また、本実施例では、有向グラフに含まれる複数のノードの連結関係がループ状態にあり、親ノードが子ノードよりも上位のレイヤに割り当てることができない場合に、ループ切断部１４ｃが、親ノードと子ノードとの間の連結元および連結先の連結関係を逆転させ、連結関係を逆転させた親ノードおよび子ノードを各階層に割り当てることとしたので、ループ状態を一旦解消することによりノードの配置計算を容易かつ効率的に実行でき、配置計算の終了後、親ノードと子ノードとの間の連結関係を復元することにより、ノードの連結関係がループ状態にある場合でも、ノードの最適な配置を得ることができる。
【００８１】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、上記特許請求の範囲に記載した技術的思想の範囲内において種々の異なる実施例にて実施されてもよいものである。
【００８２】
たとえば、本実施例では、親ノードを配置する上位のレイヤが上方に、子ノードを配置する下位のレイヤが下方にある有向グラフに対して本発明を適用した場合について説明してきたが、本発明はこれに限定されず、上下が反転した有向グラフや、横向きになった有効グラフなどにも本発明を同様に適用することができる。
【００８３】
また、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。
【００８４】
この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００８５】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【００８６】
さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【００８７】
（付記１）２つのノードを連結する方向性のあるエッジ、連結元となる親ノードおよび連結先となる子ノードにより構成される有向グラフにおけるノードの配置位置を算出する処理で用いられるノード位置算出プログラムであって、
前記親ノードが子ノードよりも上位の階層に割り当てられた有向グラフに含まれるノードの各階層内での１次元位置情報を遺伝的アルゴリズムで用いられる遺伝子とし、該遺伝子により構成される配列を遺伝的アルゴリズムで用いられる染色体として記憶する記憶手順と、
前記記憶手順により記憶された染色体に基づいて階層ごとのノードの配置位置を遺伝的アルゴリズムにより算出する算出手順と、
をコンピュータに実行させることを特徴とするノード位置算出プログラム。
【００８８】
（付記２）親ノードと子ノードとの間の連結関係に基づいて有向グラフに含まれる各ノードを前記親ノードが子ノードよりも上位の階層に属するように各階層に割り当てるノード割当手順をさらに含み、前記記憶手順は、前記ノード割当手順により各階層に割り当てられたノードの各階層内での１次元位置情報を前記遺伝子とし、該遺伝子により構成される配列を前記染色体として記憶することを特徴とする付記１に記載のノード位置算出プログラム。
【００８９】
（付記３）前記ノード割当手順は、親ノードと子ノードとが複数の階層をまたいで連結されている場合に、該親ノードと子ノードとの双方に連結されるダミーのノードを該親ノードおよび子ノードの組に対して１つ生成し、生成したダミーのノードを前記複数の階層に割り当てることを特徴とする付記２に記載のノード位置算出プログラム。
【００９０】
（付記４）前記ノード割当手順は、有向グラフに含まれる複数のノードの連結関係がループ状態にあり、親ノードが子ノードよりも上位の階層に割り当てることができない場合に、該親ノードと子ノードとの間の連結元および連結先の連結関係を逆転させ、該連結関係を逆転させた親ノードおよび子ノードを各階層に割り当てることを特徴とする付記２または３に記載のノード位置算出プログラム。
【００９１】
（付記５）２つのノードを連結する方向性のあるエッジ、連結元となる親ノードおよび連結先となる子ノードにより構成される有向グラフにおけるノードの配置位置を算出するノード位置算出方法であって、
前記親ノードが子ノードよりも上位の階層に割り当てられた有向グラフに含まれるノードの各階層内での１次元位置情報を遺伝的アルゴリズムで用いられる遺伝子とし、該遺伝子により構成される配列を遺伝的アルゴリズムで用いられる染色体として記憶する記憶工程と、
前記記憶工程により記憶された染色体に基づいて階層ごとのノードの配置位置を遺伝的アルゴリズムにより算出する算出工程と、
を含んだことを特徴とするノード位置算出方法。
【００９２】
（付記６）２つのノードを連結する方向性のあるエッジ、連結元となる親ノードおよび連結先となる子ノードにより構成される有向グラフにおけるノードの配置位置を算出するノード位置算出装置であって、
前記親ノードが子ノードよりも上位の階層に割り当てられた有向グラフに含まれるノードの各階層内での１次元位置情報を遺伝的アルゴリズムで用いられる遺伝子とし、該遺伝子により構成される配列を遺伝的アルゴリズムで用いられる染色体として記憶する記憶手段と、
前記記憶手段により記憶された染色体に基づいて階層ごとのノードの配置位置を遺伝的アルゴリズムにより算出する算出手段と、
を備えたことを特徴とするノード位置算出装置。
【産業上の利用可能性】
【００９３】
以上のように、本発明にかかるノード位置算出プログラム、ノード位置算出方法およびノード位置算出装置は、ノード数が多い場合でもノードの配置計算を迅速かつ効率的におこなうことが必要なノード位置算出システムに有用である。
【図面の簡単な説明】
【００９４】
【図１】本実施例に係るノード位置算出装置の機能的構成を示す機能ブロック図である。
【図２】各ノードを複数のレイヤに割り当てる処理について説明する説明図である。
【図３】ダミーノードをレイヤに割り当てる処理について説明する説明図である。
【図４】親ノードおよび子ノードの連結関係を逆転させる処理について説明する説明図である。
【図５】ノードの最適な配置位置の算出例を示す図である。
【図６】図５に示したノード配置に対応する染色体の例を示す図である。
【図７】ノード間の連結関係を記憶したノードパスデータ７０の一例を示す図である。
【図８】ノードの配置状況を評価する評価処理について説明する図である。
【図９】ダミーノードがある場合のノードの最適な配置位置の算出例を示す図である。
【図１０】図９に示したノード配置に対応する染色体の例を示す図である。
【図１１】ノード位置算出装置がおこなうノード配置処理の処理手順を示すフローチャートである。
【図１２】本実施例に係るコンピュータシステム２００の構成を示すシステム構成図である。
【図１３】図１２に示したコンピュータシステム２００に係る本体部２０１の構成を示すブロック図である。
【図１４】ネットワーク状の有向グラフの一例を示す図である。
【図１５】従来のノード配置アルゴリズムを説明する説明図である。
【符号の説明】
【００９５】
１０    入力部
１１    表示部
１２    主記憶部
１３    補助記憶部
１４    ノード割当部
１４ａ    レイヤ設定部
１４ｂ    ダミーノード追加部
１４ｃ    ループ切断部
１５    ノード位置算出部
１６    ノード配置部
１７    制御部
６０、６１、１００、１０１    染色体
７０    ノードパスデータ
【図１】
2005323109.tif 000003
【図２】
2005323109.tif 000004
【図３】
2005323109.tif 000005
【図４】
2005323109.tif 000006
【図５】
2005323109.tif 000007
【図６】
2005323109.tif 000008
【図７】
2005323109.tif 000009
【図８】
2005323109.tif 000010
【図９】
2005323109.tif 000011
【図１０】
2005323109.tif 000012
【図１１】
2005323109.tif 000013
【図１２】
2005323109.tif 000014
【図１３】
2005323109.tif 000015
【図１４】
2005323109.tif 000016
【図１５】
2005323109.tif 000017