(57)【要約】【課題】グラフ構造データの内容を更新した場合、共通ノードを更新前のグラフの位置関係と同じ位置関係になるようにレイアウトすることができるグラフ生成装置を提供する。【解決手段】記憶装置３０には、第一のグラフ構造データや、その第一のグラフ構造データに対するレイアウト元データが記憶されている。データ更新登録手段５１は、第一のグラフ構造データの内容を更新した第二のグラフ構造データが入力されたときに、その第二のグラフ構造データを記憶装置３０に記憶する。レイアウト位置算出手段５２は、第二のグラフ構造データに対するグラフを生成する場合、第二のグラフ構造データとそれに対する第一のグラフ構造データとに共通して記述されている共通ノードを特定し、各共通ノードについては第一のグラフ構造データに対するレイアウト元データによって定められる相対的な位置関係を維持するという条件の下で、グラフのレイアウトを行う。【選択図】図１
2015203883.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードとノード間を接続する複数のエッジとを含むグラフを、各ノードについてその形状及び大きさを示すデータと各エッジについてノードとの接続関係を示すデータとを含むグラフ構造データに基づいて生成し、表示手段の画面に表示するグラフ生成装置において、
生成済みのグラフに対応する前記グラフ構造データが第一のグラフ構造データとして記憶されると共に、グラフを生成するために前記第一のグラフ構造データに基づいて所定のグラフレイアウトアルゴリズムに従った処理を実行した際に生成された、当該第一のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含むレイアウト元データが記憶された記憶手段と、
ユーザが入力手段を用いて、前記生成済みのグラフに対応する前記第一のグラフ構造データの内容を更新することを指示したときに、その指示された更新の内容が反映された新たな前記グラフ構造データを、当該第一のグラフ構造データに対する第二のグラフ構造データとして前記記憶手段に記憶して登録するデータ更新登録手段と、
前記データ更新登録手段で登録された前記第二のグラフ構造データとそれに対する前記第一のグラフ構造データとに共通して記述されているノードを共通ノードとして特定し、その特定した前記各共通ノードについては、当該第一のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含む前記レイアウト元データによって定められる相対的な位置関係を維持するという条件の下で、当該第二のグラフ構造データに基づいて前記グラフレイアウトアルゴリズムに従った処理を実行することにより、当該第二のグラフ構造データに記述されている各ノードのレイアウト位置を算出するレイアウト位置算出手段と、
前記レイアウト位置算出手段で算出された、前記第二のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含む前記レイアウト元データを生成し、当該第二のグラフ構造データに対する更新後レイアウト元データとして前記記憶手段に記憶するレイアウト元データ生成手段と、
前記更新後レイアウト元データとそれに対する前記第二のグラフ構造データとに基づいてグラフを生成し、前記表示手段の画面に表示するグラフ表示処理手段と、
を備えることを特徴とするグラフ生成装置。
【請求項２】
ユーザが前記入力手段を用いて、前記表示手段の画面に表示されたグラフのレイアウトを変更することを指示したときに、その指示された変更の内容を示す変更データを生成し、当該グラフに対応する前記グラフ構造データと関連付けて前記記憶手段に記憶すると共に、その変更の指示に従ったレイアウトの変更を施したグラフを生成して前記表示手段の画面に表示するレイアウト変更手段を更に備えることを特徴とする請求項１記載のグラフ生成装置。
【請求項３】
前記レイアウト変更手段は、前記変更データを生成したときに、その変更データが関連付けられている前記グラフ構造データと関連付けられている全ての前記変更データによって示される内容の変更をグラフに施すという条件の下で、当該グラフ構造データに基づいて前記グラフレイアウトアルゴリズムに従った処理を実行することにより、当該グラフ構造データに記述されている前記各ノードのレイアウト位置を算出し、その算出された結果に基づいてグラフを生成することを特徴とする請求項２記載のグラフ生成装置。
【請求項４】
前記レイアウト変更手段は、ユーザからの変更の指示に従ったレイアウトの変更を施したグラフを生成した結果、そのレイアウト変更後のグラフに対応する前記グラフ構造データがそのレイアウト変更前のグラフに対応するものと異なると判断したときに、当該レイアウト変更後のグラフに対応する前記グラフ構造データを新たに生成し、第一のグラフ構造データとして前記記憶手段に記憶することを特徴とする請求項２又は３記載のグラフ生成装置。
【請求項５】
コンピュータを利用して、複数のノードとノード間を接続する複数のエッジとを含むグラフを、各ノードについてその形状及び大きさを示すデータと各エッジについてノードとの接続関係を示すデータとを含むグラフ構造データに基づいて生成し、前記コンピュータの表示手段の画面に表示するグラフ生成方法において、
前記コンピュータが、生成済みのグラフに対応する前記グラフ構造データが第一のグラフ構造データとして記憶されると共に、グラフを生成するために前記第一のグラフ構造データに基づいて所定のグラフレイアウトアルゴリズムに従った処理を実行した際に生成された、当該第一のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含むレイアウト元データが記憶された記憶手段と、グラフを生成する処理を行う制御手段とを有する場合に、
ユーザが前記コンピュータの入力手段を用いて、前記生成済みのグラフに対応する前記第一のグラフ構造データの内容を更新することを指示したときに、前記制御手段が、その指示された更新の内容が反映された新たな前記グラフ構造データを、当該第一のグラフ構造データに対する第二のグラフ構造データとして前記記憶手段に記憶して登録するデータ更新登録ステップと、
前記制御手段が、前記データ更新登録手段で登録された前記第二のグラフ構造データとそれに対する前記第一のグラフ構造データとに共通して記述されているノードを共通ノードとして特定し、その特定した前記各共通ノードについては、当該第一のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含む前記レイアウト元データによって定められる相対的な位置関係を維持するという条件の下で、当該第二のグラフ構造データに基づいて前記グラフレイアウトアルゴリズムに従った処理を実行することにより、当該第二のグラフ構造データに記述されている各ノードのレイアウト位置を算出するレイアウト位置算出ステップと、
前記制御手段が、前記レイアウト位置算出ステップで算出された、前記第二のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含む前記レイアウト元データを生成し、当該第二のグラフ構造データに対する更新後レイアウト元データとして前記記憶手段に記憶するレイアウト元データ生成ステップと、
前記制御手段が、前記更新後レイアウト元データとそれに対する前記第二のグラフ構造データとに基づいてグラフを生成し、前記表示手段の画面に表示するグラフ表示処理ステップと、
を具備することを特徴とするグラフ生成方法。
【請求項６】
ユーザが前記入力手段を用いて、前記表示手段の画面に表示されたグラフのレイアウトを変更することを指示したときに、前記制御手段が、その指示された変更の内容を示す変更データを生成し、当該グラフに対応する前記グラフ構造データと関連付けて前記記憶手段に記憶すると共に、その変更の指示に従ったレイアウトの変更を施したグラフを生成して前記表示手段の画面に表示するレイアウト変更ステップを更に具備することを特徴とする請求項５記載のグラフ生成方法。
【請求項７】
前記レイアウト変更ステップでは、前記制御手段が、前記変更データを生成したときに、その変更データが関連付けられている前記グラフ構造データと関連付けられている全ての前記変更データによって示される内容の変更をグラフに施すという条件の下で、当該グラフ構造データに基づいて前記グラフレイアウトアルゴリズムに従った処理を実行することにより、当該グラフ構造データに記述されている前記各ノードのレイアウト位置を算出し、その算出された結果に基づいてグラフを生成することを特徴とする請求項６記載のグラフ生成方法。
【請求項８】
前記レイアウト変更ステップでは、前記制御手段が、ユーザからの変更の指示に従ったレイアウトの変更を施したグラフを生成した結果、そのレイアウト変更後のグラフに対応する前記グラフ構造データがそのレイアウト変更前のグラフに対応するものと異なると判断したときに、当該レイアウト変更後のグラフに対応する前記グラフ構造データを新たに生成し、第一のグラフ構造データとして前記記憶手段に記憶することを特徴とする請求項６又は７記載のグラフ生成方法。
【請求項９】
コンピュータを利用して、複数のノードとノード間を接続する複数のエッジとを含むグラフを、各ノードについてその形状及び大きさを示すデータと各エッジについてノードとの接続関係を示すデータとを含むグラフ構造データに基づいて生成し、前記コンピュータの表示手段の画面に表示するためのグラフ生成プログラムにおいて、
前記コンピュータが、生成済みのグラフに対応する前記グラフ構造データが第一のグラフ構造データとして記憶されると共に、グラフを生成するために前記第一のグラフ構造データに基づいて所定のグラフレイアウトアルゴリズムに従った処理を実行した際に生成された、当該第一のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含むレイアウト元データが記憶された記憶手段を有する場合に、
このコンピュータに、
ユーザが前記コンピュータの入力手段を用いて、前記生成済みのグラフに対応する前記第一のグラフ構造データの内容を更新することを指示したときに、その指示された更新の内容が反映された新たな前記グラフ構造データを、当該第一のグラフ構造データに対する第二のグラフ構造データとして前記記憶手段に記憶して登録するデータ更新登録機能と、
前記データ更新登録機能で登録された前記第二のグラフ構造データとそれに対する前記第一のグラフ構造データとに共通して記述されているノードを共通ノードとして特定し、その特定した前記各共通ノードについては、当該第一のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含む前記レイアウト元データによって定められる相対的な位置関係を維持するという条件の下で、当該第二のグラフ構造データに基づいて前記グラフレイアウトアルゴリズムに従った処理を実行することにより、当該第二のグラフ構造データに記述されている各ノードのレイアウト位置を算出するレイアウト位置算出機能と、
前記レイアウト位置算出機能で算出された、前記第二のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含む前記レイアウト元データを生成し、当該第二のグラフ構造データに対する更新後レイアウト元データとして前記記憶手段に記憶するレイアウト元データ生成機能と、
前記更新後レイアウト元データとそれに対する前記第二のグラフ構造データとに基づいてグラフを生成し、前記表示手段の画面に表示するグラフ表示処理機能と、
を実現させることを特徴とするグラフ生成プログラム。
【請求項１０】
ユーザが前記入力手段を用いて、前記表示手段の画面に表示されたグラフのレイアウトを変更することを指示したときに、その指示された変更の内容を示す変更データを生成し、当該グラフに対応する前記グラフ構造データと関連付けて前記記憶手段に記憶すると共に、その変更の指示に従ったレイアウトの変更を施したグラフを生成して前記表示手段の画面に表示するレイアウト変更機能を、前記コンピュータに更に実現させることを特徴とする請求項９記載のグラフ生成プログラム。
【請求項１１】
前記レイアウト変更機能は、前記変更データを生成したときに、その変更データが関連付けられている前記グラフ構造データと関連付けられている全ての前記変更データによって示される内容の変更をグラフに施すという条件の下で、当該グラフ構造データに基づいて前記グラフレイアウトアルゴリズムに従った処理を実行することにより、当該グラフ構造データに記述されている前記各ノードのレイアウト位置を算出し、その算出された結果に基づいてグラフを生成するものであることを特徴とする請求項１０記載のグラフ生成プログラム。
【請求項１２】
前記レイアウト変更機能は、ユーザからの変更の指示に従ったレイアウトの変更を施したグラフを生成した結果、そのレイアウト変更後のグラフに対応する前記グラフ構造データがそのレイアウト変更前のグラフに対応するものと異なると判断したときに、当該レイアウト変更後のグラフに対応する前記グラフ構造データを新たに生成し、第一のグラフ構造データとして前記記憶手段に記憶するものであることを特徴とする請求項１０又は１１記載のグラフ生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノードとノード間を接続する複数のエッジとを含むグラフを生成して表示装置の画面に表示するグラフ生成装置、グラフ生成方法及びグラフ生成プログラムに関するものである。
【背景技術】
【０００２】
従来、複雑なデータを目視で確認し易くするためにチャートや表やグラフが用いられている。ここでいうグラフとは、データ同士の関連を可視化するための図のことであり、統計データを表示するための図、例えば、データの時間変化を示すための折れ線グラフ、各データの大小関係や各データが全体に対して占める割合を表すための円グラフや棒グラフとは区別される。また、システム開発においては、例えば、システムの設計情報や構造を可視化するためにクラス図が用いられ、システムプログラムのサブルーチン同士の呼び出し関係を示すためにコールグラフが用いられるが、これらのクラス図やコールグラフもここでいうグラフの一種である。
【０００３】
一般に、グラフは複数のノードと複数のエッジとによって構成される。ノードとはデータを表す点のことであるが、グラフ上では、大抵、大きさを有する図形で表現される。エッジはノード間を繋ぐ辺であり、グラフ上では直線又は折れ線等で表現される。グラフを生成する際には、ユーザがグラフ構造を把握しやすいように複数のノード及び複数のエッジをレイアウトすることが望まれる。このため、例えばエッジが向きを持つ有向グラフを生成する場合には、「エッジの単一方向性」、「エッジの長さの最短性」、「エッジの交差数の最小性」、「エッジの垂直性」、「ノードの一貫性」といった条件を可能な限り満たすように複数のノード及び複数のエッジをレイアウトする必要がある。ここで、「エッジの単一方向性」とは、各エッジが同じ方向を向いていることであり、「エッジの長さの最短性」とは、各エッジをその長さができるだけ短くなるように表現することであり、「エッジの交差数の最小性」とは、交差しているエッジの数ができるだけ少なくすることであり、「エッジの垂直性」とは、各エッジを折れ線ではなく直線で表現することであり、そして、「ノードの一貫性」とは、グラフ内において同一のノードが複数箇所に現れず、一箇所だけに現れるようにすることである。
【０００４】
小規模なグラフに対しては、上記の各条件を満たすように複数のノード及び複数のエッジを手作業でレイアウトすることは可能であるが、大多数のノード及び大多数のエッジを含む大規模なグラフに対しては、複数のノード及び複数のエッジを手作業でレイアウトするのは困難である。このため、現在では、コンピュータを利用して、上記の各条件をできるだけ満たすようにグラフのレイアウトを自動で行うことが提案されている（例えば、特許文献１，２参照。）。この場合、グラフのレイアウトは、グラフレイアウトアルゴリズムに従って行われる。このようなグラフレイアウトアルゴリズムとしては様々なものがあるが、特に、有向グラフの階層レイアウトの分野においては、Sugiyamaアルゴリズムが有名である（例えば、非特許文献１，２参照。）。以下、Sugiyamaアルゴリズムの概要について説明する。
【０００５】
Sugiyamaアルゴリズムは、有向グラフの階層レイアウトを行うためのアルゴリズムである。このSugiyamaアルゴリズムでは、有向グラフとして有向非循環グラフを想定している。図１４はSugiyamaアルゴリズムを説明するための図である。図１４に示すように、Sugiyamaアルゴリズムは、階層割当てを行う第一ステップ（階層割当てステップ）、ノード順序付けを行う第二ステップ（順序付けステップ）、位置座標付与を行う第三ステップ（座標付与ステップ）という三つのステップから構成される。
【０００６】
まず、第一ステップでは、グラフ構造データに基づいて、エッジの長さの最短性やノードの一貫性等の条件をできる限り満たすように、各ノードに対してそれを配置すべき階層を割り当てる。ここで、グラフ構造データには、各ノードについてその形状及び大きさを示すデータ（ノードデータ）と、各エッジについてノードとの接続関係を示すデータ（エッジデータ）とが含まれている。かかるグラフ構造データは予めコンピュータに入力されている。次に、第二ステップでは、各階層において、エッジの単一方向性やエッジの交差数の最小性等の条件をできる限り満たすように、当該階層が割り当てられた各ノードに対してそれを配置する順序を決定する。そして、第三ステップでは、エッジの垂直性の条件をできる限り満たすように、各ノードの位置を決定し、当該ノードにその位置に関する情報（位置座標）を付与する。こうして、各ノードの位置座標が決定されると、コンピュータは、その各ノードの位置座標に関するデータとグラフ構造データとに基づいて有向グラフを生成し、表示装置の画面に表示することができる。
【０００７】
尚、Sugiyamaアルゴリズムでは、レイアウトを行う有向グラフとして有向非循環グラフを想定しているが、実際にレイアウトを行う有向グラフは有向循環グラフである場合もある。Sugiyamaアルゴリズムを用いて有向循環グラフのレイアウトを行う場合は、上記三つのステップによる処理を行う前に、循環削除(Cycle Remove)処理を行うようにすればよい。この循環削除処理では、有向循環グラフについてのグラフ構造データにおいて、エッジを「反転」（エッジの始点と終点を入れ替えること）もしくは「削除」することにより、有向非循環グラフについてのグラフ構造データを作成する。そして、この作成したグラフ構造データに対して上記三つのステップによる処理を行い、グラフのレイアウトを行う。最後に、「反転」若しくは「削除」したエッジを元に戻すことにより、有向循環グラフが生成される。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００２−３１２８０３号公報
【特許文献２】特開２００５−３２３１０９号公報
【非特許文献】
【０００９】
【非特許文献１】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.
【非特許文献２】Hugo A. D. do Nasciment and Peter Eades, “User Hints for Directed Graph Drawing”, Graph Drawing, pp.205-219, 2001.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
ところで、ユーザは、コンピュータを利用してグラフを生成した後、その生成したグラフを見て、例えばノードのレイアウト位置やエッジの接続関係等に修正を加えたいと考えることがある。この場合、ユーザは、入力装置を用いて表示装置の画面に表示された生成済みのグラフについてそのレイアウトを変更することを指示することができる。具体的には、ユーザが表示装置の画面に表示されたグラフにおいて入力装置を用いて自ら手作業でノードのレイアウト位置等を修正したり、ノードのレイアウト位置に課すべき制約の内容を表す制約条件（例えば、あるノードについてそれを配置する階層を指定する条件、二つのノードについてそれらの上下関係を指定する条件等）を入力したりすることができる。そして、コンピュータは、そのレイアウトの変更指示の内容に従ってグラフのレイアウトを実行し、これにより、グラフの内容が修正されることになる。
【００１１】
また、一度生成したグラフに対して、新たなノードの追加や不要なノードの削除等を行う場合には、ユーザは、入力装置を用いてそのグラフに対応するグラフ構造データの内容を更新することを指示して新たなグラフ構造データの入力を行うことができる。ここで、「グラフ構造データの内容を更新することを指示する」ことには、ユーザが直接、グラフ構造データを入力する場合だけでなく、ユーザが表示装置の画面に表示されたグラフにおいて入力装置を用いてノードやエッジの追加・削除やエッジの接続関係の修正を指示することが含まれる。そして、かかる指示がなされた場合には、コンピュータが、その指示の内容が反映された新たなグラフ構造データを生成することになる。そして、コンピュータは、その新たなグラフ構造データに基づいて再度、グラフレイアウトアルゴリズムに従った処理を行い、グラフを生成することになる。
【００１２】
以下では、生成済みのグラフに対応するグラフ構造データの内容の更新を指示することを、データの「更新」と称し、一方、データの更新とは異なり、生成済みのグラフについてそのレイアウトの変更を指示することを、レイアウトの「変更」と称することにする。データの更新及びレイアウトの変更のいずれの方法を用いても、生成済みのグラフに対して修正が施されたグラフ（修正グラフ）を生成することができる。尚、上述のように、通常は、生成済みのグラフにおいてノードやエッジを追加・削除したりエッジの接続関係を修正したりすると、コンピュータが新たなグラフ構造データを生成するため、ノードやエッジの追加・削除等については、データの更新の方法により修正グラフの生成が行われるが、ノードやエッジの追加・削除等の内容を表す制約条件を入力することにすれば、レイアウトの変更の方法により修正グラフを生成することも可能である。
【００１３】
グラフを修正する場合、ユーザがデータ更新の方法により新たなグラフ構造データを入力すると、コンピュータは、その入力された更新後のグラフ構造データに基づいて再度、グラフレイアウトアルゴリズムに従った処理を行い、グラフを生成する。しかしながら、このようにグラフ構造データの内容が更新されると、コンピュータは、更新前のグラフを生成したときと同じ処理を最初から実行して、新たに更新後のグラフを生成することになるので、データ更新後のグラフでは、更新に際して追加又は削除されたノード以外のノード（共通ノード）の位置関係は、データ更新前のグラフにおける位置関係と同じにならないことが多い。このため、共通ノードをデータ更新前のグラフと同じ位置関係に配置するには、データ更新後のグラフに対してレイアウトの変更を行う必要があり、手間がかかるという問題がある。また、膨大な数のノードを含むグラフを修正する場合には、更新後のグラフ構造データに基づいてグラフレイアウトアルゴリズムに従った処理を最初から実行すると、コンピュータの処理の負荷が大きくなるという問題がある。
【００１４】
本発明は上記事情に基づいてなされたものであり、グラフ構造データの内容を更新した場合に、データ更新後のグラフを容易に生成することができると共に共通ノードをデータ更新前のグラフにおける位置関係と同じ位置関係になるようにレイアウトすることができるグラフ生成装置、グラフ生成方法及びグラフ生成プログラムを提供することを目的とするものである。
【課題を解決するための手段】
【００１５】
上記の目的を達成するための本発明に係るグラフ生成装置は、複数のノードとノード間を接続する複数のエッジとを含むグラフを、各ノードについてその形状及び大きさを示すデータと各エッジについてノードとの接続関係を示すデータとを含むグラフ構造データに基づいて生成し、表示手段の画面に表示するグラフ生成装置において、生成済みのグラフに対応するグラフ構造データが第一のグラフ構造データとして記憶されると共に、グラフを生成するために第一のグラフ構造データに基づいて所定のグラフレイアウトアルゴリズムに従った処理を実行した際に生成された、当該第一のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含むレイアウト元データが記憶された記憶手段と、ユーザが入力手段を用いて、生成済みのグラフに対応する第一のグラフ構造データの内容を更新することを指示したときに、その指示された更新の内容が反映された新たなグラフ構造データを、当該第一のグラフ構造データに対する第二のグラフ構造データとして記憶手段に記憶して登録するデータ更新登録手段と、データ更新登録手段で登録された第二のグラフ構造データとそれに対する第一のグラフ構造データとに共通して記述されているノードを共通ノードとして特定し、その特定した各共通ノードについては、当該第一のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含むレイアウト元データによって定められる相対的な位置関係を維持するという条件の下で、当該第二のグラフ構造データに基づいてグラフレイアウトアルゴリズムに従った処理を実行することにより、当該第二のグラフ構造データに記述されている各ノードのレイアウト位置を算出するレイアウト位置算出手段と、レイアウト位置算出手段で算出された、第二のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含むレイアウト元データを生成し、当該第二のグラフ構造データに対する更新後レイアウト元データとして記憶手段に記憶するレイアウト元データ生成手段と、更新後レイアウト元データとそれに対する前記第二のグラフ構造データとに基づいてグラフを生成し、表示手段の画面に表示するグラフ表示処理手段と、を備えることを特徴とするものである。
【００１６】
上記の構成により、本発明に係るグラフ生成装置は、データ更新後のグラフを生成するときに、第二のグラフ構造データとそれに対する第一のグラフ構造データとに共通して記述されているノードを共通ノードとして特定し、その特定した各共通ノードについては当該第一のグラフ構造データに対応する生成済みのグラフについてのレイアウト元データによって定められる相対的な位置関係を維持するという条件の下で、当該第二のグラフ構造データに基づいて所定のグラフレイアウトアルゴリズムに従った処理を実行して、グラフのレイアウトを行う。このため、各共通ノードについてはグラフ上でレイアウトすべき位置を、当該生成済みのグラフについてのレイアウト元データに基づいて容易に決定することができるので、データ更新後のグラフ生成に際しての処理の負荷を大幅に軽減することができる。しかも、このデータ更新後のグラフでは、各共通ノードを、当該生成済みのグラフにおける位置関係と同じ位置関係になるようにレイアウトすることができる。
【００１７】
また、本発明に係るグラフ生成装置は、ユーザが入力手段を用いて、表示手段の画面に表示されたグラフのレイアウトを変更することを指示したときに、その指示された変更の内容を示す変更データを生成し、当該グラフに対応するグラフ構造データと関連付けて記憶手段に記憶すると共に、その変更の指示に従ったレイアウトの変更を施したグラフを生成して表示手段の画面に表示するレイアウト変更手段を更に備えることが望ましい。これにより、変更データをｕｎｄｏ等の処理に利用することができるので、例えば、生成済みのグラフに対して行われたレイアウトの変更をｕｎｄｏ等の処理により一旦元に戻した後に、改めて同じ変更を行う場合、この変更データを利用してグラフにその変更を反映させることが可能となる。
【００１８】
また、本発明に係るグラフ生成装置では、レイアウト変更手段は、変更データを生成したときに、その変更データが関連付けられているグラフ構造データと関連付けられている全ての変更データによって示される内容の変更をグラフに施すという条件の下で、当該グラフ構造データに基づいてグラフレイアウトアルゴリズムに従った処理を実行することにより、当該グラフ構造データに記述されている各ノードのレイアウト位置を算出し、その算出された結果に基づいてグラフを生成することが望ましい。これにより、ユーザが表示手段の画面に表示されたグラフのレイアウトを変更することを指示した場合、レイアウト変更手段は、当該グラフに対して過去にレイアウトの変更が施されていれば、今回の変更の内容を示す変更データに加えて過去に施された変更の内容を示す変更データを全て記憶手段から読み出し、その読み出した全ての変更データによって示される内容の変更を施すという条件の下で、所定のグラフレイアウトアルゴリズムに従った処理を実行する。このため、ユーザは、今回のレイアウトの変更だけでなく、過去に施されたレイアウトの変更も反映されたグラフを容易に得ることができる。
【００１９】
更に、本発明に係るグラフ生成装置では、レイアウト変更手段は、ユーザからの変更の指示に従ったレイアウトの変更を施したグラフを生成した結果、そのレイアウト変更後のグラフに対応するグラフ構造データがそのレイアウト変更前のグラフに対応するものと異なると判断したときに、当該レイアウト変更後のグラフに対応するグラフ構造データを新たに生成し、第一のグラフ構造データとして記憶手段に記憶することが望ましい。これにより、レイアウトの変更を行う場合には、そのレイアウト変更後のグラフに対応するグラフ構造データがそのレイアウト変更前のグラフに対応するものと異なるのであれば、レイアウト変更手段が当該レイアウト変更後の最新のグラフに対応するグラフ構造データを自動で生成することができるので、ユーザはグラフ構造データの内容を更新する必要がなくなる。
【００２０】
上記の目的を達成するための本発明に係るグラフ生成方法は、コンピュータを利用して、複数のノードとノード間を接続する複数のエッジとを含むグラフを、各ノードについてその形状及び大きさを示すデータと各エッジについてノードとの接続関係を示すデータとを含むグラフ構造データに基づいて生成し、コンピュータの表示手段の画面に表示するグラフ生成方法において、コンピュータが、生成済みのグラフに対応するグラフ構造データが第一のグラフ構造データとして記憶されると共に、グラフを生成するために第一のグラフ構造データに基づいて所定のグラフレイアウトアルゴリズムに従った処理を実行した際に生成された、当該第一のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含むレイアウト元データが記憶された記憶手段と、グラフを生成する処理を行う制御手段とを有する場合に、ユーザがコンピュータの入力手段を用いて、生成済みのグラフに対応する第一のグラフ構造データの内容を更新することを指示したときに、制御手段が、その指示された更新の内容が反映された新たなグラフ構造データを、当該第一のグラフ構造データに対する第二のグラフ構造データとして記憶手段に記憶して登録するデータ更新登録ステップと、制御手段が、データ更新登録手段で登録された第二のグラフ構造データとそれに対する第一のグラフ構造データとに共通して記述されているノードを共通ノードとして特定し、その特定した各共通ノードについては、当該第一のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含むレイアウト元データによって定められる相対的な位置関係を維持するという条件の下で、当該第二のグラフ構造データに基づいてグラフレイアウトアルゴリズムに従った処理を実行することにより、当該第二のグラフ構造データに記述されている各ノードのレイアウト位置を算出するレイアウト位置算出ステップと、制御手段が、レイアウト位置算出ステップで算出された、第二のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含むレイアウト元データを生成し、当該第二のグラフ構造データに対する更新後レイアウト元データとして記憶手段に記憶するレイアウト元データ生成ステップと、制御手段が、更新後レイアウト元データとそれに対する第二のグラフ構造データとに基づいてグラフを生成し、表示手段の画面に表示するグラフ表示処理ステップと、を具備することを特徴とするものである。
【００２１】
上記の構成により、本発明に係るグラフ生成方法では、データ更新後のグラフを生成するときに、コンピュータの制御手段が、第二のグラフ構造データとそれに対する第一のグラフ構造データとに共通して記述されているノードを共通ノードとして特定し、その特定した各共通ノードについては当該第一のグラフ構造データに対応する生成済みのグラフについてのレイアウト元データによって定められる相対的な位置関係を維持するという条件の下で、当該第二のグラフ構造データに基づいて所定のグラフレイアウトアルゴリズムに従った処理を実行して、グラフのレイアウトを行う。このため、各共通ノードについてはグラフ上でレイアウトすべき位置を、当該生成済みのグラフについてのレイアウト元データに基づいて容易に決定することができるので、データ更新後のグラフ生成に際しての処理の負荷を大幅に軽減することができる。しかも、このデータ更新後のグラフでは、各共通ノードを、当該生成済みのグラフにおける位置関係と同じ位置関係になるようにレイアウトすることができる。
【００２２】
また、本発明に係るグラフ生成方法は、ユーザが入力手段を用いて、表示手段の画面に表示されたグラフのレイアウトを変更することを指示したときに、制御手段が、その指示された変更の内容を示す変更データを生成し、当該グラフに対応するグラフ構造データと関連付けて記憶手段に記憶すると共に、その変更の指示に従ったレイアウトの変更を施したグラフを生成して表示手段の画面に表示するレイアウト変更ステップを更に具備することが望ましい。これにより、変更データをｕｎｄｏ等の処理に利用することができるので、例えば、生成済みのグラフに対して行われたレイアウトの変更をｕｎｄｏ等の処理により一旦元に戻した後に、改めて同じ変更を行う場合、この変更データを利用してグラフにその変更を反映させることが可能となる。
【００２３】
また、本発明に係るグラフ生成方法において、レイアウト変更ステップでは、制御手段が、変更データを生成したときに、その変更データが関連付けられているグラフ構造データと関連付けられている全ての変更データによって示される内容の変更をグラフに施すという条件の下で、当該グラフ構造データに基づいてグラフレイアウトアルゴリズムに従った処理を実行することにより、当該グラフ構造データに記述されている各ノードのレイアウト位置を算出し、その算出された結果に基づいてグラフを生成することが望ましい。これにより、ユーザは、今回のレイアウトの変更だけでなく、過去に施されたレイアウトの変更も反映されたグラフを容易に得ることができる。
【００２４】
更に、本発明に係るグラフ生成方法において、レイアウト変更ステップでは、制御手段が、ユーザからの変更の指示に従ったレイアウトの変更を施したグラフを生成した結果、そのレイアウト変更後のグラフに対応するグラフ構造データがそのレイアウト変更前のグラフに対応するものと異なると判断したときに、当該レイアウト変更後のグラフに対応するグラフ構造データを新たに生成し、第一のグラフ構造データとして記憶手段に記憶することが望ましい。これにより、レイアウトの変更を行う場合には、そのレイアウト変更後のグラフに対応するグラフ構造データがそのレイアウト変更前のグラフに対応するものと異なるのであれば、制御手段が当該レイアウト変更後の最新のグラフに対応するグラフ構造データを自動で生成することができるので、ユーザはグラフ構造データの内容を更新する必要がなくなる。
【００２５】
上記の目的を達成するための本発明に係るグラフ生成プログラムは、コンピュータを利用して、複数のノードとノード間を接続する複数のエッジとを含むグラフを、各ノードについてその形状及び大きさを示すデータと各エッジについてノードとの接続関係を示すデータとを含むグラフ構造データに基づいて生成し、コンピュータの表示手段の画面に表示するためのグラフ生成プログラムにおいて、コンピュータが、生成済みのグラフに対応するグラフ構造データが第一のグラフ構造データとして記憶されると共に、グラフを生成するために第一のグラフ構造データに基づいて所定のグラフレイアウトアルゴリズムに従った処理を実行した際に生成された、当該第一のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含むレイアウト元データが記憶された記憶手段を有する場合に、このコンピュータに、ユーザがコンピュータの入力手段を用いて、生成済みのグラフに対応する第一のグラフ構造データの内容を更新することを指示したときに、その指示された更新の内容が反映された新たなグラフ構造データを、当該第一のグラフ構造データに対する第二のグラフ構造データとして記憶手段に記憶して登録するデータ更新登録機能と、データ更新登録機能で登録された第二のグラフ構造データとそれに対する第一のグラフ構造データとに共通して記述されているノードを共通ノードとして特定し、その特定した各共通ノードについては、当該第一のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含むレイアウト元データによって定められる相対的な位置関係を維持するという条件の下で、当該第二のグラフ構造データに基づいてグラフレイアウトアルゴリズムに従った処理を実行することにより、当該第二のグラフ構造データに記述されている各ノードのレイアウト位置を算出するレイアウト位置算出機能と、レイアウト位置算出機能で算出された、第二のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含むレイアウト元データを生成し、当該第二のグラフ構造データに対する更新後レイアウト元データとして記憶手段に記憶するレイアウト元データ生成機能と、更新後レイアウト元データとそれに対する第二のグラフ構造データとに基づいてグラフを生成し、表示手段の画面に表示するグラフ表示処理機能と、を実現させることを特徴とするものである。
【００２６】
本発明に係るグラフ生成プログラムをコンピュータに適用すると、このコンピュータは、データ更新後のグラフを生成するときに、第二のグラフ構造データとそれに対する第一のグラフ構造データとに共通して記述されているノードを共通ノードとして特定し、その特定した各共通ノードについては当該第一のグラフ構造データに対応する生成済みのグラフについてのレイアウト元データによって定められる相対的な位置関係を維持するという条件の下で、当該第二のグラフ構造データに基づいて所定のグラフレイアウトアルゴリズムに従った処理を実行して、グラフのレイアウトを行う。このため、各共通ノードについてはグラフ上でレイアウトすべき位置を、当該生成済みのグラフについてのレイアウト元データに基づいて容易に決定することができるので、データ更新後のグラフ生成に際しての処理の負荷を大幅に軽減することができる。しかも、このデータ更新後のグラフでは、各共通ノードを、当該生成済みのグラフにおける位置関係と同じ位置関係になるようにレイアウトすることができる。
【００２７】
また、本発明に係るグラフ生成プログラムは、ユーザが入力手段を用いて、表示手段の画面に表示されたグラフのレイアウトを変更することを指示したときに、その指示された変更の内容を示す変更データを生成し、当該グラフに対応するグラフ構造データと関連付けて記憶手段に記憶すると共に、その変更の指示に従ったレイアウトの変更を施したグラフを生成して表示手段の画面に表示するレイアウト変更機能を、コンピュータに更に実現させるものであることが望ましい。これにより、変更データをｕｎｄｏ等の処理に利用することができるので、例えば、生成済みのグラフに対して行われたレイアウトの変更をｕｎｄｏ等の処理により一旦元に戻した後に、改めて同じ変更を行う場合、この変更データを利用してグラフにその変更を反映させることが可能となる。
【００２８】
また、本発明に係るグラフ生成プログラムでは、レイアウト変更機能は、変更データを生成したときに、その変更データが関連付けられているグラフ構造データと関連付けられている全ての変更データによって示される内容の変更をグラフに施すという条件の下で、当該グラフ構造データに基づいてグラフレイアウトアルゴリズムに従った処理を実行することにより、当該グラフ構造データに記述されている各ノードのレイアウト位置を算出し、その算出された結果に基づいてグラフを生成するものであることが望ましい。これにより、ユーザは、今回のレイアウトの変更だけでなく、過去に施されたレイアウトの変更も反映されたグラフを容易に得ることができる。
【００２９】
更に、本発明に係るグラフ生成プログラムでは、レイアウト変更機能は、ユーザからの変更の指示に従ったレイアウトの変更を施したグラフを生成した結果、そのレイアウト変更後のグラフに対応するグラフ構造データがそのレイアウト変更前のグラフに対応するものと異なると判断したときに、当該レイアウト変更後のグラフに対応するグラフ構造データを新たに生成し、第一のグラフ構造データとして記憶手段に記憶するものであることが望ましい。これにより、レイアウトの変更を行う場合には、そのレイアウト変更後のグラフに対応するグラフ構造データがそのレイアウト変更前のグラフに対応するものと異なるのであれば、コンピュータが当該レイアウト変更後の最新のグラフに対応するグラフ構造データを自動で生成することができるので、ユーザはグラフ構造データの内容を更新する必要がなくなる。
【発明の効果】
【００３０】
本発明に係るグラフ生成装置、グラフ生成方法及びグラフ生成プログラムによれば、データ更新後のグラフを生成するときに、第二のグラフ構造データとそれに対する第一のグラフ構造データとに共通して記述されている各共通ノードについてはグラフ上でレイアウトすべき位置を、当該第一のグラフ構造データに対応する生成済みのグラフについてのレイアウト元データに基づいて容易に決定することができるので、データ更新後のグラフ生成に際しての処理の負荷を大幅に軽減することができる。しかも、このデータ更新後のグラフでは、各共通ノードを、当該生成済みのグラフにおける位置関係と同じ位置関係になるようにレイアウトすることができる。
【図面の簡単な説明】
【００３１】
【図１】図１は本発明の一実施形態であるグラフ生成装置の概略ブロック図である。
【図２】図２はグラフ構造データの例を示す図である。
【図３】図３は図２のグラフ構造データに対するレイアウト元データの例を示す図である。
【図４】図４は本実施形態のグラフ生成装置において第一のグラフ構造データに基づいてグラフを生成して表示装置の画面に表示する処理の手順を説明するためのフローチャートである。
【図５】図５は図３のレイアウト元データと図２の第一のグラフ構造データとに基づいて生成されるグラフを示す図である。
【図６】図６は本実施形態のグラフ生成装置において第二のグラフ構造データに基づいてグラフを生成して表示装置の画面に表示する処理の手順を説明するためのフローチャートである。
【図７】図７は図２の第一のグラフ構造データに対する第二のグラフ構造データの例を示す図である。
【図８】図８はレイアウト位置算出手段によって修正された修正エッジデータの例を示す図である。
【図９】図９（ａ）はレイアウト位置算出手段が階層割当てステップに従った処理を行うことによって決定された各ノードの階層を示す図、図９（ｂ）はレイアウト位置算出手段が順序付けステップに従った処理を行うことによって決定された各ノードの階層及び階層内順序を示す図である。
【図１０】図１０は図７の第二のグラフ構造データに対するレイアウト元データの例を示す図である。
【図１１】図１１は図１０のレイアウト元データと図７の第二のグラフ構造データとに基づいて生成されるグラフを示す図である。
【図１２】図１２は従来のグラフ生成装置を用いて図７のグラフ構造データに基づいてSugiyamaアルゴリズムに従った処理を実行することにより生成したグラフを示す図である。
【図１３】図１３は本実施形態のグラフ生成装置においてレイアウトの変更が指示されたときにグラフを生成して表示装置の画面に表示する処理の手順を説明するためのフローチャートである。
【図１４】図１４はSugiyamaアルゴリズムを説明するための図である。
【発明を実施するための形態】
【００３２】
以下に、図面を参照して、本願に係る発明を実施するための形態について説明する。図１は本発明の一実施形態であるグラフ生成装置の概略ブロック図である。
【００３３】
本実施形態のグラフ生成装置は、複数のノードとノード間を接続する複数のエッジとを含むグラフを生成して画面に表示するものであり、図１に示すように、入力装置１０と、表示装置２０と、記憶装置３０と、制御部５０とを備える。かかるグラフ生成装置は、例えばパーソナルコンピュータにより実現される。
【００３４】
入力装置（入力手段）１０は、例えば、各種の指示やデータを入力するものである。この入力装置１０としては、キーボードやマウス等が用いられる。例えば、ユーザは入力装置１０を用いて、グラフを生成するのに必要なグラフ構造データを入力する。また、ユーザは入力装置１０を用いて、生成済みのグラフに対応するグラフ構造データの内容を更新する指示（データの更新）を行ったり、生成済みのグラフについてのレイアウトを変更する指示（レイアウトの変更）を行ったりすることができる。かかるデータの更新やレイアウトの変更を行うことにより、生成済みのグラフに修正を施すことができる。表示装置（表示手段）２０は、制御部５０によって生成されたグラフを表示するものである。
【００３５】
記憶装置（記憶手段）３０には、各種のデータ、具体的に、グラフ構造データ、レイアウト元データ、変更データ等が記憶される。グラフ構造データは、入力装置１０を用いてユーザにより入力される。そして、かかるグラフ構造データに基づいてグラフが生成される。本実施形態では、グラフ構造データは、有向非循環グラフに対するものである場合について説明する。図２はグラフ構造データの例を示す図である。かかるグラフ構造データには、図２に示すように、ノードデータと、エッジデータとが含まれる。ノードデータは、各ノードについてその形状及び大きさ（図形定義情報）を示すものである。例えば、グラフ上においてあるノードを円で表示する場合には、当該ノードについての図形定義情報には、当該ノードの形状が円である旨の内容とその円の半径とが含まれる。また、あるノードを長方形で表示する場合には、当該ノードについての図形定義情報には、当該ノードの形状が長方形である旨の内容とその長方形の縦の長さ及び横の長さとが含まれる。エッジデータは、各エッジについてノードとの接続関係を示すものである。有向グラフにおけるエッジは向きを持っており、この向きはエッジの始点から終点への向きとして特定される。具体的に、各エッジについてのエッジデータには、当該エッジの始点に接続されるノード（始点ノード）とその終点に接続されるノード（終点ノード）とを特定するデータが含まれる。また、グラフ構造データには、識別ＩＤが付与されている。グラフはグラフ構造データに基づいて生成されるので、グラフ構造データに付与された識別ＩＤは、当該グラフを識別するためのＩＤでもある。
【００３６】
本実施形態では、グラフ構造データを、第一のグラフ構造データと第二のグラフ構造データとに区別して管理している。具体的に、生成済みのグラフに対応するグラフ構造データは第一のグラフ構造データとして記憶装置３０に記憶される。また、ユーザは第一のグラフ構造データの内容を更新することを指示することにより、データの更新を行うことができるが、その指示された更新の内容が反映された新たなグラフ構造データは第二のグラフ構造データとして記憶装置３０に記憶される。すなわち、第一のグラフ構造データは、データ更新前のグラフに対応するグラフ構造データ（更新前のグラフ構造データ）であり、第二のグラフ構造データは、データ更新後のグラフに対応するグラフ構造データ（更新後のグラフ構造データ）である。そして、第一のグラフ構造データと第二のグラフ構造データとは互いに関連付けられる。例えば、第二のグラフ構造データに、第一のグラフ構造データに付与された識別ＩＤと同じ識別ＩＤを付することにより、両データを関連付けることができる。また、あるグラフ構造データが第一のグラフ構造データであるか第二のグラフ構造データであるかの区別は、例えばＩＤやフラグを用いて行うことができる。また、制御部５０が第二のグラフ構造データに基づいてデータ更新後のグラフを生成して表示装置２０の画面に表示すると、当該第二のグラフ構造データは第一のグラフ構造データとして管理されることになる。尚、第二のグラフ構造データではなく、新規に入力されたグラフ構造データであって未だそれに基づいてグラフが生成されていないものも第一のグラフ構造データとして扱われる。また、データの更新を行ったときには、その更新後に、最新のグラフ構造データである第二のグラフ構造データのみを保持するように構成してもよい。
【００３７】
レイアウト元データは、制御部５０がグラフを生成するためにグラフ構造データに基づいて所定のグラフレイアウトアルゴリズムに従った処理を実行したときに生成される。レイアウト元データには、当該グラフ構造データに記述されている各ノードのレイアウト位置に関するデータが含まれる。特に、第一のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含むレイアウト元データを、当該第一のグラフ構造データに対する更新前レイアウト元データとも称し、第二のグラフ構造データに記述されている各ノードのレイアウト位置に関するデータを含むレイアウト元データを、当該第二のグラフ構造データに対する更新後レイアウト元データとも称することにする。レイアウト元データは、その生成の際に用いたグラフ構造データと関連付けて記憶装置３０に記憶されている。レイアウト元データとグラフ構造データとの関連付けは、さまざまな方法で行うことができる。例えば、レイアウト元データとグラフ構造データとを直接互いに紐付けるようにしてもよい。また、レイアウト元データに、関連付けようとするグラフ構造データに付与された識別ＩＤと同じ識別ＩＤを付することにより、両データを関連付けるようにしてもよい。
【００３８】
本実施形態では、グラフ構造データが有向グラフに対するものであるので、上記グラフレイアウトアルゴリズムとしては、有向グラフの階層レイアウトを行うためのアルゴリズム、具体的にはSugiyamaアルゴリズムが用いられる。図３は図２のグラフ構造データに対するレイアウト元データの例を示す図である。レイアウト元データには、図３に示すように、各ノードについて、当該ノードに割り当てられた階層、階層内で当該ノードが配置される順序（階層内順序）、レイアウト位置座標（レイアウト位置に関するデータ）、図形定義情報といった各データが含まれている。ところで、実際、グラフ生成のためには、各ノードのレイアウト位置座標とグラフ構造データとがあればよい。本実施形態では、本発明の内容が容易に理解することができるように、レイアウト元データに、レイアウト位置座標の他に、階層、階層内順序、及び、図形定義情報をも含めている。したがって、レイアウト元データには、少なくとも各ノードのレイアウト位置座標が含まれていればよい。
【００３９】
本実施形態のグラフ生成装置では、データの更新の方法とは別に、レイアウトの変更の方法によりグラフを修正することが可能である。変更データは、ユーザがグラフのレイアウトを変更することを指示したときに生成される。この変更データは、その指示された変更の内容を示すものである。具体的に、変更データは、ユーザが入力装置１０を用いて表示装置２０の画面に表示されたグラフにおいてノードのレイアウト位置の変更等を指示したときに、制御部５０によって生成される。このとき、この変更データには、変更後のノードのレイアウト位置に関するデータ等が含まれる。特に、ノードやエッジの追加・削除又はエッジの接続関係の変更によるグラフの修正については、データの更新の方法に限らず、ノードやエッジの追加・削除の内容を表す制約条件、又はエッジの接続関係を変更する内容を表す制約条件を入力することにより、レイアウトの変更の方法で行うことができる。このため、変更データには、ノードやエッジの追加・削除の内容を表す制約条件、エッジの接続関係を変更する内容を表す制約条件も含まれることがある。
【００４０】
また、変更データは、当該変更を指示する際に画面に表示されていたレイアウト変更前のグラフに対応するグラフ構造データと関連付けて記憶装置３０に記憶されている。グラフはグラフ構造データに基づいて生成されるので、変更データはその変更前のグラフと関連付けられていると考えることもできる。変更データとグラフ構造データとの関連付けは、さまざまな方法で行うことができる。例えば、変更データとグラフ構造データとを直接互いに紐付けるようにしてもよい。また、変更データに、関連付けようとするグラフ構造データに付与された識別ＩＤと同じ識別ＩＤを付することにより、両データを関連付けるようにしてもよい。更に、あるグラフに対してレイアウトの変更が複数回行われた場合には、各回の変更時に生成された変更データには同じ識別ＩＤが付されることになる。ここで、これら複数の変更データには、その変更が行われた順序を特定するシーケンス番号を付与するようにしてもよい。このように、あるグラフ構造データには複数の変更データが関連付けられていることもあり得る。尚、あるグラフに対してレイアウトの変更が複数回行われた場合に、それら全ての変更の内容を一つの変更データとして集約可能であれば、その集約した一つの変更データを当該グラフに対応するグラフ構造データと関連付けるようにしてもよい。
【００４１】
また、記憶装置３０には、制御部５０に所定の処理を実行させるための各種のプログラムが記憶されている。例えば、Sugiyamaアルゴリズムに従った処理を行うことにより各ノードのレイアウト位置を算出するためのプログラム、グラフ構造データとレイアウト元データとに基づいてグラフを生成するプログラム、その生成したグラフを表示装置２０の画面に表示するプログラム等が記憶装置３０に記憶されている。
【００４２】
制御部（制御手段）５０は、本装置の各部を統括して制御するものである。この制御部５０は、図１に示すように、データ更新登録手段５１と、レイアウト位置算出手段５２と、レイアウト元データ生成手段５３と、グラフ表示処理手段５４と、レイアウト変更手段５５とを備える。制御部５０は、新たなグラフ構成データに基づいて新規のグラフを生成して表示装置２０の画面に表示するだけでなく、その生成済みのグラフに対して修正を施す処理を行う。
【００４３】
具体的に、本実施形態のグラフ生成装置には、生成済みのグラフを修正する機能として、データ更新によるグラフ修正機能と、レイアウト変更によるグラフ修正機能とが備わっている。既述のように、データの更新とは、ユーザが生成済みのグラフに対応するグラフ構造データの内容の更新を指示することをいい、レイアウトの変更とは、ユーザが生成済みのグラフについてそのレイアウトの変更を指示することをいう。データ更新によるグラフ修正機能は、データ更新登録手段５１、レイアウト位置算出手段５２、レイアウト元データ生成手段５３及びグラフ表示処理手段５４によって実現され、一方、レイアウト変更によるグラフ修正機能は、レイアウト変更手段５５によって実現される。尚、新規グラフを生成する機能は、レイアウト位置算出手段５２、レイアウト元データ生成手段５３及びグラフ表示処理手段５４によって実現される。
【００４４】
ユーザがレイアウト変更によるグラフ修正機能を用いてグラフレイアウトの変更を指示すると、その指示に従ったレイアウトの変更が施されたグラフが生成されることになる。この場合、その生成された修正グラフのレイアウトは、大抵、ユーザの指示通りになっている。これに対し、ユーザがデータ更新によるグラフ修正機能を用いてグラフ構造データの内容の更新を指示すると、その指示された更新の内容の新たなグラフ構造データに基づいてグラフが生成されるため、そのデータ更新後のグラフのレイアウトはデータ更新前のグラフのレイアウトと大幅に変わってしまうことがある。しかし、データ更新によりグラフの修正を行う場合、通常、ユーザは、データ更新後のグラフでは、更新に際して追加又は削除されたノード以外のノード（共通ノード）をデータ更新前のグラフと同じ位置関係に配置しておきたいと考えている。このため、本実施形態では、データ更新によるグラフ修正機能は、後述するように、共通ノードをデータ更新前のグラフにおける位置関係と同じ位置関係になるようにレイアウトするようにグラフの修正を行うことができるものになっている。
【００４５】
データ更新登録手段５１は、ユーザが入力装置１０を用いて、生成済みのグラフに対応する第一のグラフ構造データの内容を更新することを指示したときに、その指示された更新の内容が反映された新たなグラフ構造データを、当該第一のグラフ構造データに対する第二のグラフ構造データとして記憶装置３０に記憶して登録するものである。具体的に、ユーザが入力装置１０を用いて、記憶装置３０に記憶されているある一つの第一のグラフ構造データに対してノードやエッジの追加及び／又は削除が行われた新たなグラフ構造データを入力すると、データ更新登録手段５１は、その入力された新たなグラフ構造データを第二のグラフ構造データとし、当該第一のグラフ構造データと関連付けて記憶装置３０に記憶する。ここで、追加又は削除の対象とならなかったノード（エッジ）は、第二のグラフ構造データとそれに関連付けられた第一のグラフ構造データとに共通に記述されているノード（エッジ）である。追加の対象となったノード（エッジ）は、第二のグラフ構造データには記述されているが、それに関連付けられた第一のグラフ構造データには記述されていないノード（エッジ）であり、削除の対象となったノード（エッジ）は、第二のグラフ構造データには記述されていないが、それに関連付けられた第一のグラフ構造データには記述されているノード（エッジ）である。また、ユーザは、生成済みのグラフに対応する第一のグラフ構造データの内容を更新する指示として、表示装置２０の画面に表示されたグラフにおいて入力装置１０を用いてノードやエッジの追加・削除やエッジの接続関係の修正についての指示を行うことができる。この場合、データ更新登録手段５１は、その指示に従ってノードやエッジの追加・削除やエッジの接続関係の修正を行うことにより、その指示の内容が反映された新たなグラフ構造データを生成し、その生成した新たなグラフ構造データを、第二のグラフ構造データとして記憶装置３０に記憶して登録することになる。
【００４６】
具体的に、グラフ構造データの更新登録を行うには、例えば、ユーザは、表示装置２０の画面にグラフが表示されている状況で、所定の更新ボタンを押す。すると、グラフ構造データの入力画面が表示され、ユーザはその入力画面においてグラフ構造データを新たに入力する。そして、入力が終了した後、ユーザが所定の更新登録ボタンを押すと、データ更新登録手段５１は、その入力されたグラフ構造データを第二のグラフ構造データとし、この第二のグラフ構造データを、現在、表示装置２０の画面に表示されているグラフを生成する際に用いた第一のグラフ構造データと関連付けて記憶装置３０に記憶する。
【００４７】
尚、グラフ構造データの更新登録を行う方法としては上記の方法以外にさまざまな方法が考えられる。例えば、ユーザは、記憶装置３０に記憶されている第一のグラフ構造データの中から所望の第一のグラフ構造データを選択し、その選択した第一のグラフ構造データの内容を修正する。そして、修正が終了した後、ユーザが所定の更新登録ボタンを押すと、データ更新登録手段５１は、その修正された内容のグラフ構造データを第二のグラフ構造データとして、当該選択した第一のグラフ構造データと関連付けて記憶装置３０に記憶するようにしてもよい。また、グラフを利用してグラフ構造データの更新登録を行う方法もある。すなわち、この方法では、まず、ユーザは、表示装置２０の画面に表示されているグラフに対して、入力装置１０を用いて自ら手作業でノードやエッジを追加・削除したりエッジの接続関係を修正したりして、レイアウトの変更を指示する。その後、ユーザが所定の更新登録ボタンを押すと、データ更新登録手段５１は、その指示の内容が反映されたグラフ構造データを自動で生成し、第二のグラフ構造データとして、当該グラフに対応する第一のグラフ構造データと関連付けて記憶装置３０に記憶する。
【００４８】
レイアウト位置算出手段５２は、第一のグラフ構造データに基づいてグラフを生成する旨の指示を受けた場合、当該第一のグラフ構造データに基づいてSugiyamaアルゴリズムに従った処理を実行することにより、当該第一のグラフ構造データに記述されている各ノードのレイアウト位置を算出する。また、レイアウト位置算出手段５２は、第二のグラフ構造データに基づいてグラフを生成する旨の指示を受けた場合、当該第二のグラフ構造データとそれに対する第一のグラフ構造データとに共通して記述されているノードを共通ノードとして特定し、その特定した各共通ノードについては、当該第一のグラフ構造データと関連付けて記憶装置３０に記憶されているレイアウト元データ（更新前レイアウト元データ）によって定められる相対的な位置関係を維持するという条件の下で、当該第二のグラフ構造データに基づいてSugiyamaアルゴリズムに従った処理を実行することにより、当該第二のグラフ構造データに記述されている各ノードのレイアウト位置を算出する。したがって、当該第二のグラフ構造データに対するグラフを生成すれば、各共通ノードは、データ更新前のグラフにおける位置関係と同じ位置関係になるようにレイアウトされることになる。レイアウト位置算出手段によって算出された各ノードのレイアウト位置に関するデータ（レイアウト位置座標）は制御部５０に内蔵されたＲＡＭに一時記憶される。
【００４９】
レイアウト元データ生成手段５３は、レイアウト位置算出手段５２で算出された各ノードのレイアウト位置座標を含むレイアウト元データを生成し、その生成したレイアウト元データをそれに対するグラフ構造データと関連付けて記憶装置３０に記憶するものである。特に、レイアウト位置算出手段５２で第二のグラフ構造データに記述されている各ノードのレイアウト位置が算出された場合には、その算出された各ノードのレイアウト位置座標を含むレイアウト元データは、当該第二のグラフ構造データに対する更新後レイアウト元データとして記憶装置３０に記憶される。ここで、本実施形態では、上述したように、レイアウト元データには、レイアウト位置座標の他に、階層、階層内順序、及び、図形定義情報が含まれている。
【００５０】
グラフ表示処理手段５４は、レイアウト元データ生成手段５３で生成されたレイアウト元データとそれに関連付けられているグラフ構造データとに基づいてグラフを生成し、表示装置２０の画面に表示するものである。特に、レイアウト元データ生成手段５３で更新後レイアウト元データが生成された場合には、その更新後レイアウト元データとそれに関連付けられている第二のグラフ構造データとに基づいてデータ更新後のグラフが生成される。データ更新後のグラフを生成した場合、その生成したデータ更新後のグラフにおける各共通ノードの位置関係は、その第二のグラフ構造データに対する第一のグラフ構造データに対応するグラフにおける位置関係と同じになる。
【００５１】
レイアウト変更手段５５は、ユーザが入力装置１０を用いて、表示装置２０の画面に表示されたグラフに対応するグラフ構造データの内容を更新することを指示するのではなく、当該グラフのレイアウトを変更することを指示したときに、その指示された変更の内容を示す変更データを生成し、当該グラフに対応するグラフ構造データと関連付けて記憶装置３０に記憶すると共に、その変更の指示に従ったレイアウトの変更を施したグラフを生成して表示装置２０の画面に表示するものである。レイアウト変更の指示の例としては、表示装置２０の画面に表示されたグラフにおいてノードのレイアウト位置の変更を指示すること、そのグラフにおいてエッジの接続関係の変更を指示すること、そのグラフにおいてノードやエッジの追加・削除を指示すること等を挙げることができる。このように、本実施形態のグラフ生成装置には、表示装置２０の画面に表示されたグラフに対するグラフレイアウトを変更することによりグラフを修正する機能が付加されている。これにより、ユーザは、表示装置２０の画面に表示されたグラフに対してノードのレイアウト位置の変更やエッジの接続関係の変更等を容易に行うことができる。尚、あるグラフに対してレイアウトの変更が複数回行われた場合には、複数の変更データが同じ一つのグラフ構造データに関連付けられて記憶装置３０に記憶されることになる。
【００５２】
例えば、ユーザは、あるノードのレイアウト位置を変更する場合、マウスを用いて、表示装置２０の画面に表示されたグラフにおいて当該ノードをドラッグして所望の位置に移動することができる。このとき、レイアウト変更手段５５は、その移動後におけるノードのレイアウト位置座標を変更データとして生成する。また、ユーザは、ノードのレイアウト位置を変更する場合、その変更の内容を示す制約条件を入力することもできる。かかる制約条件には、階層に関する制約や、階層内における順序付けに関する制約等がある。階層に関する制約条件の例としては、あるノードを特定の階層に配置するという条件や、二つのノードについて一方のノードを他方のノードより一つ上位の階層に配置するという条件を挙げることができる。また、順序付けに関する制約条件の例としては、同一の階層に配置される二つのノードについて一方のノードを他方のノードの右隣りに配置するという条件を挙げることができる。ユーザにより制約条件が入力された場合には、レイアウト変更手段５５はその制約条件の内容を変更データとして生成する。このように、本実施形態では、変更データをグラフ構造データと関連付けて記憶装置３０に記憶しているので、かかる変更データをｕｎｄｏ等の処理に利用することができる。例えば、生成済みのグラフに対して行われたレイアウトの変更をｕｎｄｏ等の処理により一旦元に戻した後に、改めて同じ変更を行う場合、この変更データを利用してグラフにその変更を反映させることが可能である。
【００５３】
レイアウト変更手段５５は、ユーザによって表示装置２０の画面に表示されたグラフのレイアウトを変更することが指示され、その指示された変更の内容を示す変更データを生成すると、その変更データによって示される内容の変更をグラフに施すという条件の下で、当該変更データと関連付けられているグラフ構造データに基づいてSugiyamaアウトアルゴリズムに従った処理を実行することにより、そのグラフ構造データに記述されている各ノードのレイアウト位置を算出し、その算出された結果に基づいてグラフを生成する。特に、本実施形態では、記憶装置３０に記憶されている変更データを利用することにより、ユーザが過去に行った変更内容を反映させたグラフを自動で生成することにしている。具体的には、レイアウト変更手段５５は、変更データを生成したときに、その今回の変更データが関連付けられているグラフ構造データに他の変更データが関連付けられていれば、今回の変更の内容を示す変更データに加えて過去に施された変更の内容を示す変更データを記憶装置３０から読み出し、その読み出した全ての変更データによって示される内容の変更をグラフに施すという条件の下で、当該グラフ構造データに基づいてSugiyamaアルゴリズムに従った処理を実行することにより、当該グラフ構造データに記述されている各ノードのレイアウト位置を算出し、その算出された結果に基づいてグラフを生成する。これにより、ユーザは、今回のレイアウトの変更だけでなく、過去に施されたレイアウトの変更も反映されたグラフを容易に得ることができる。
【００５４】
上述したように、変更データとしては、ノードの位置座標を示すもの、エッジの接続関係を示すもの、ノードやエッジの追加・削除を示すもの、階層に関する制約条件や階層内における順序付けに関する制約条件を示すもの等がある。これら変更データの中には、その内容に従ってレイアウトの変更を行ったグラフに対応するグラフ構造データがレイアウト変更前のグラフに対応するグラフ構造データと異なってしまうような変更データがある。そこで、本実施形態では、レイアウト変更手段５５は、ユーザからの変更の指示に従ったレイアウトの変更を施したグラフを生成した結果、そのレイアウト変更後のグラフに対応するグラフ構造データがそのレイアウト変更前のグラフに対応するものと異なるようになると判断したときに、当該レイアウト変更後のグラフに対応するグラフ構造データを生成し、第一のグラフ構造データとして記憶装置３０に記憶することにしている。これにより、レイアウトの変更を行う場合、そのレイアウト変更後のグラフに対応するグラフ構造データがそのレイアウト変更前のグラフに対応するものと異なれば、レイアウト変更手段５５が当該レイアウト変更後の最新のグラフに対応するグラフ構造データを自動で生成することができるので、ユーザはグラフ構造データの内容を更新する必要がなくなる。
【００５５】
次に、本実施形態のグラフ生成装置においてグラフ構造データに基づいてグラフを生成して表示装置２０の画面に表示する処理の手順について説明する。
【００５６】
最初に、ユーザが新規にグラフ構造データ（第一のグラフ構造データ）を入力し、その第一のグラフ構造データに基づいてグラフを生成する場合の処理の手順について説明する。図４は本実施形態のグラフ生成装置において第一のグラフ構造データに基づいてグラフを生成して表示装置２０の画面に表示する処理の手順を説明するためのフローチャートである。
【００５７】
いま、ユーザが図２に示すグラフ構造データＧ１を新規に入力したとする。このグラフ構造データＧ１は、第二のグラフ構造データではなく、第一のグラフ構造データである。また、図２に示す第一のグラフ構造データＧ１のノードデータによれば、グラフには１１個のノード１〜１１が含まれ、いずれのノード１〜１１の形状も半径ｒの円である。また、そのグラフ構造データＧ１のエッジデータによれば、グラフには８つのエッジｅ１〜ｅ８が含まれている。
【００５８】
まず、ユーザは、入力装置１０を用いて、第一のグラフ構造データＧ１に対するグラフを生成する旨の指示を入力する。制御部５０のレイアウト位置算出手段５２は、かかる指示を受けると（Ｓ１）、第一のグラフ構造データＧ１に基づいてSugiyamaアルゴリズムに従った処理を実行することにより、第一のグラフ構造データＧ１に記述されている各ノード１〜１１のレイアウト位置を算出する（Ｓ２）。
【００５９】
いま、レイアウト位置算出手段５２が行うSugiyamaアルゴリズムに従った処理の内容を詳しく説明する。Sugiyamaアルゴリズムは、上述したように、第一ステップとしての階層割当てステップ、第二ステップとしての順序付けステップ、第三ステップとしての座標付与ステップからなる。まず、レイアウト位置算出手段５２は、Sugiyamaアルゴリズムにおける階層割当てステップに従った処理を行う。すなわち、レイアウト位置算出手段５２は、図２に示す第一のグラフ構造データＧ１のエッジデータに基づいて、エッジとノードとの接続関係をチェックした後、エッジの長さの最短性やノードの一貫性等の条件をできる限り満たすように、各ノード１〜１１に対してそれを配置すべき階層を割り当てる。
【００６０】
具体的に、この階層の割当ては次のようにして行われる。図２に示すエッジデータによれば、ノード１は、いずれのエッジの終点にも接続されていないので、最上位の第１階層に割り当てられることになる。このノード１はエッジｅ１の始点にのみ接続されている。そして、エッジｅ１の終点にはノード３が接続されているが、ノード３は、エッジｅ１の終点を除き、いずれのエッジの終点にも接続されていないので、ノード１よりも一つ下位の階層、すなわち第２階層に割り当てられることになる。また、ノード３はエッジｅ２の始点とエッジｅ３の始点に接続されている。このエッジｅ２の終点にはノード５が接続されているが、ノード５は、エッジｅ２の終点を除き、いずれのエッジの終点にも接続されていないので、ノード３よりも一つ下位の階層、すなわち第３階層に割り当てられることになる。そして、ノード５はエッジｅ４の始点に接続され、エッジｅ４の終点にはノード８が接続されているが、ノード８は、エッジｅ４の終点を除き、いずれのエッジの終点にも接続されていないので、第４階層に割り当てられることになる。一方、エッジｅ３の終点にはノード６が接続されているが、ノード６は、エッジｅ３の終点を除き、いずれのエッジの終点にも接続されていないので、第３階層に割り当てられることになる。
【００６１】
また、ノード２は、いずれのエッジの終点にも接続されていないので、第１階層に割り当てられることになる。このノード２はエッジｅ５の始点にのみ接続され、エッジｅ５の終点にはノード４が接続されているが、ノード４は、エッジｅ５の終点を除き、いずれのエッジの終点にも接続されていないので、第２階層に割り当てられることになる。また、ノード４はエッジｅ６の始点とエッジｅ７の始点とに接続されている。エッジｅ６の終点にはノード７が接続されているが、ノード７は、エッジｅ６の終点を除き、いずれのエッジの終点にも接続されていないので、第３階層に割り当てられることになる。一方、エッジｅ７の終点にはノード１１が接続されているが、ノード１１は、エッジｅ７の終点を除き、いずれのエッジの終点にも接続されていないので、第３階層に割り当てられることになる。
【００６２】
更に、ノード９は、いずれのエッジの終点にも接続されていないので、第１階層に割り当てられることになる。このノード９はエッジｅ８の始点にのみ接続され、このエッジｅ８の終点にはノード１０が接続されているが、ノード１０は、エッジｅ８の終点を除き、いずれのエッジの終点にも接続されていないので、第２階層に割り当てられることになる。こうして、各ノードに対してそれを配置すべき階層が決定される。
【００６３】
次に、レイアウト位置算出手段５２は、Sugiyamaアルゴリズムにおける順序付けステップに従った処理を行う。すなわち、レイアウト位置算出手段５２は、各階層において、エッジの単一方向性やエッジの交差数の最小性等の条件をできる限り満たすように、当該階層が割り当てられた各ノードに対してそれを配置する順序を決定する。ここでは、各階層においてノードを配置する順序を、全てのノードを一列に並べたときに当該ノードが左側から何番目に配置されているかによって表すことにする。例えば、第１階層においては、ノード９を１番目に、ノード２を２番目に、ノード１を３番目に配置することが決定され、第２階層においては、ノード１０を１番目に、ノード４を２番目に、ノード３を３番目に配置することが決定され、第３階層においては、ノード１１を１番目に、ノード７を２番目に、ノード６を３番目に、ノード５を４番目に配置することが決定される。そして、第４階層にはノード８が一つだけ配置されるので、ノード８を１番目に配置することが決定される。
【００６４】
次に、レイアウト位置算出手段５２は、Sugiyamaアルゴリズムにおける座標付与ステップに従った処理を行う。すなわち、レイアウト位置算出手段５２は、エッジの垂直性の条件をできる限り満たすように、各ノードの位置を決定し、当該ノードにレイアウト位置座標を付与する。ここで、レイアウト位置座標としては、例えば、ノードの形状が円である場合には中心の位置座標を用いることができ、ノードの形状が長方形である場合には例えば４つの頂点のうちいずれかの頂点（例えば左上の頂点）の位置座標を用いることができる。
【００６５】
こうして、レイアウト位置算出手段５２が、図２に示す第一のグラフ構造データＧ１に基づいてSugiyamaアルゴリズムに従った処理を実行することにより、各ノード１〜１１のレイアウト位置座標を算出すると、レイアウト元データ生成手段５３は、レイアウト位置算出手段５２による処理で得られたデータに基づいて、図３に示すレイアウト元データＬ１を生成する（Ｓ３）。レイアウト元データＬ１はグラフ生成に利用する中間的なデータである。レイアウト元データＬ１には、各ノードについて、当該ノードに割り当てられた階層、階層内で当該ノードが配置される順序（階層内順序）、レイアウト位置座標、図形定義情報といった各データが含まれている。レイアウト元データ生成手段５３は、その生成したレイアウト元データＬ１を第一のグラフ構造データＧ１と関連付けて記憶装置３０に記憶する。
【００６６】
その後、グラフ表示処理手段５４は、レイアウト元データ生成手段５３で生成されたレイアウト元データＬ１とそれと関連付けられている第一のグラフ構造データＧ１とに基づいてグラフを生成し、表示装置２０の画面に表示する（Ｓ４）。図５に、図３のレイアウト元データＬ１と図２の第一のグラフ構造データＧ１とに基づいて生成されるグラフを示す。この図５のグラフが表示装置２０の画面に表示される。ここで、グラフを生成する際、ノード上におけるエッジとの接続点は予め定められている。そして、ある階層のノードとそれより一つ下位の階層のノードとがエッジで接続される場合には、これら二つのノードの接続点間を矢印付きの直線で結ぶことにより、グラフを生成している。以上で、第一のグラフ構造データＧ１に対するグラフを生成する処理が終了する。
【００６７】
次に、ユーザが第一のグラフ構造データＧ１の内容を更新することを指示し、その指示された更新の内容が反映された第二のグラフ構造データに基づいてグラフを生成する場合の処理の手順について説明する。図６は本実施形態のグラフ生成装置において第二のグラフ構造データに基づいてグラフを生成して表示装置２０の画面に表示する処理の手順を説明するためのフローチャートである。
【００６８】
この場合、まず、ユーザは、第一のグラフ構造データＧ１を選択し、その第一のグラフ構造データＧ１に対するグラフを表示装置２０の画面に表示させる。次に、ユーザは、所定の更新ボタンを押し、グラフ構造データの入力画面を表示させる。そして、ユーザは、その入力画面において更新後のグラフ構造データ（第二のグラフ構造データ）を新たに入力する。図７は図２の第一のグラフ構造データＧ１に対する第二のグラフ構造データＧ２の例を示す図である。図７に示す第二のグラフ構造データＧ２は、図２に示す第一のグラフ構造データＧ１において、「ノード１の削除」、「ノード１１の削除」、「ノード１２の追加」がなされたものである。このとき、ノード１，１１の削除及びノード１２の追加に伴い、エッジについても、「エッジｅ１の削除」、「エッジｅ７の削除」、「エッジｅ９の追加」、「エッジｅ１０の追加」がなされている。ここで、エッジｅ９の始点ノードはノード４であり、その終点ノードはノード８である。また、エッジｅ１０の始点ノードはノード１０であり、その終点ノードはノード１２である。入力が終了した後、ユーザがグラフ構造データの更新登録を行う旨を指示する更新登録ボタンを押す。データ更新登録手段５１は、かかる指示を受けると（Ｓ１１）、その入力された第二のグラフ構造データＧ２を、第一のグラフ構造データＧ１と関連付けて記憶装置３０に記憶する（Ｓ１２）。
【００６９】
次に、ユーザは、入力装置１０を用いて、第二のグラフ構造データＧ２に対するグラフを生成する旨の指示を入力する。レイアウト位置算出手段５２は、第二のグラフ構造データＧ２に対するグラフの生成指示を受けると（Ｓ１３）、第二のグラフ構造データＧ２とそれに関連付けられた第一のグラフ構造データＧ１とに共通して記述されているノードを共通ノードとして特定する（Ｓ１４）。この場合は、ノード２〜１０が共通ノードとして特定される。
【００７０】
次に、レイアウト位置算出手段５２は、その特定した各共通ノード２〜１０については、第一のグラフ構造データＧ１と関連付けて記憶装置３０に記憶されているレイアウト元データ（更新前レイアウト元データ）Ｌ１によって定められる相対的な位置関係を維持するという条件の下で、第二のグラフ構造データＧ２に基づいてSugiyamaアルゴリズムに従った処理を実行することにより、第二のグラフ構造データＧ２に記述されている各ノード２〜１０，１２のレイアウト位置を算出する（Ｓ１５）。このように、上記条件を課すことにより、このレイアウト位置算出手段５２による処理では、各共通ノード２〜１０については、図３の更新前レイアウト元データＬ１に示される相対的な位置関係がそのまま維持されることになる。
【００７１】
ここで、レイアウト位置算出手段５２が行うステップＳ１５の処理の内容を詳しく説明する。まず、レイアウト位置算出手段５２は、Sugiyamaアルゴリズムにおける階層割当てステップに従った処理を行う。この階層割当てステップに従った処理では、各共通ノード２〜１０については、それを配置すべき階層が図３に示す更新前レイアウト元データＬ１に示される階層と同じ階層になるように、階層の割当てが行われる。すなわち、共通ノード２，９を第１階層に配置し、共通ノード３，４，１０を第２階層に配置し、共通ノード５，６，７を第３階層に配置し、そして、共通ノード８を第４階層に配置することが決定される。また、新たに追加されたノード１２については、第二のグラフ構造データＧ２のエッジデータに基づいて、エッジとノードとの接続関係をチェックした後、エッジの長さの最短性やノードの一貫性等の条件をできる限り満たすように、ノード１２を配置すべき階層を割り当てる。ノード１２は、エッジｅ１０の終点にのみ接続されているので、エッジｅ１０の始点ノードであるノード１０よりも一つ下位の階層、すなわち第３階層に割り当てられることになる。
【００７２】
ところで、レイアウト位置算出手段５２は、あるエッジについてその始点に接続されるノードに割り当てられた階層とその終点に接続されるノードに割り当てられた階層との間に１以上の階層が存在する場合には、その存在する階層の各々に、当該エッジの通過点を表すためのダミーのノードを追加する。第二のグラフ構造データＧ２のエッジデータによれば、エッジｅ９についてはその始点にノード４が接続され、その終点にノード８が接続されるが、上記の階層割当てステップに従った処理の結果、ノード４は第２階層に割り当てられ、ノード８は第４階層に割り当てられている。このため、第３階層にはダミーのノードｄ１が追加されることになる。また、このダミーノードｄ１の追加により、エッジｅ９は、ノード４とダミーノードｄ１とを接続するエッジｅ９’と、ダミーノードｄ１とノード８とを接続するエッジｅ９”とに分けられることになる。ここで、レイアウト位置算出手段５２は、ダミーノードを追加したときに、そのダミーノードの追加に応じた修正をエッジデータに加え、その修正を加えたエッジデータを修正エッジデータとして記憶装置３０に記憶しておく。図８にレイアウト位置算出手段５２によって修正された修正エッジデータの例を示す。こうしてレイアウト位置算出手段５２が階層割当てステップに従った処理を行うことによって決定された各ノード２〜１０，１２，ｄ１の階層を図９（ａ）に示す。
【００７３】
次に、レイアウト位置算出手段５２は、Sugiyamaアルゴリズムにおける順序付けステップに従った処理を行う。ここで、ダミーノードが存在する場合には、ダミーノードについても順序付けが行われている。この順序付けステップに従った処理では、全てのノードのうち、データ更新の際に追加されたノードを除いた共通ノード２〜１０については、各階層において当該階層に割り当てられた各共通ノードを配置する順序が図３に示すレイアウト元データＬ１に示される順序と同じになるように、順序付けが行われる。すなわち、第１階層においては、共通ノード９を１番目に、共通ノード２を２番目に配置し、第２階層においては、共通ノード１０を１番目に、共通ノード４を２番目に、共通ノード３を３番目に配置することが決定される。一方、第３階層には、共通ノード５，６，７と、新たに追加されたノード１２と、ダミーノードｄ１とが割り当てられている。この場合、まず、第３階層には共通ノード５，６，７のみが割り当てられていると考え、図３に示す更新前レイアウト元データＬ１の内容に基づいて、共通ノード７を１番目に、共通ノード６を２番目に、共通ノード５を３番目に配置することを仮決定する。そして、次に、このように各共通ノード５，６，７の順序が仮決定された第３階層において、エッジの単一方向性やエッジの交差数の最小性等の条件をできる限り満たすように、ノード１２とダミーノードｄ１を配置する順序を決定する。こうして、例えば、第３階層においては、ノード１２を１番目に、共通ノード７を２番目に、ダミーノードｄ１を３番目に、共通ノード６を４番目に、そして、共通ノード５を５番目に配置することが最終的に決定される。更に、第４階層には共通ノード８が一つだけ配置されるので、共通ノード８を１番目に配置することが決定される。こうしてレイアウト位置算出手段５２が順序付けステップに従った処理を行うことによって決定された各ノード２〜１０，１２，ｄ１の階層及び階層内順序を図９（ｂ）に示す。
【００７４】
次に、レイアウト位置算出手段５２は、Sugiyamaアルゴリズムにおける座標付与ステップに従った処理を行う。すなわち、エッジの垂直性の条件をできる限り満たすように、ダミーノードを含む各ノードの位置を決定し、各ノードのレイアウト位置座標を算出する。ここで、ダミーノードが存在する場合には、ダミーノードについてもそのレイアウト位置座標が付与される。実際、ダミーノードについてはその形状が所定の図形、例えば点とすることが予め定められており、ダミーノードについてのレイアウト位置座標としては、当該点の位置座標を用いることができる。
【００７５】
こうして、レイアウト位置算出手段５２が、各共通ノード２〜１０の相対的な位置関係を維持するという条件の下で、図７に示す第二のグラフ構造データＧ２に基づいてSugiyamaアルゴリズムに従った処理を実行することにより、各ノード２〜１０，１２，ｄ１のレイアウト位置座標を算出すると、レイアウト元データ生成手段５３は、このレイアウト位置算出手段５２による処理で得られたデータに基づいて、各ノード２〜１０，１２，ｄ１をレイアウトするためのレイアウト元データを生成する（Ｓ１６）。図１０は図７の第二のグラフ構造データＧ２に対するレイアウト元データ（更新後レイアウト元データ）Ｌ２の例を示す図である。ここで、ダミーノードの形状・大きさは予め定められているため、レイアウト元データＬ２にはダミーノードｄ１の図形定義情報は示されていない。レイアウト元データ生成手段５３は、その生成したレイアウト元データＬ２を第二のグラフ構造データＧ２と関連付けて記憶装置３０に記憶する。
【００７６】
その後、グラフ表示処理手段５４は、レイアウト元データ生成手段５３で生成された更新後レイアウト元データＬ２と図７の第二のグラフ構造データＧ２とに基づいてグラフを生成し、表示装置２０の画面に表示する（Ｓ１７）。ここで、グラフを生成する際、ダミーノードについては、それを表す図形である点がエッジとの接続点となる。また、このステップＳ１７の処理後、制御部５０は、第二のグラフ構造データＧ２に新たな識別ＩＤを付与し、第二のグラフ構造データＧ２を第一のグラフ構造データとして管理する（Ｓ１８）。このとき、第二のグラフ構造データＧ２に対する第一のグラフ構造データ（更新前のグラフ構造データ）Ｇ１を削除するようにしてもよい。すなわち、データ更新によるグラフ修正の処理後には、最新のグラフ構造データのみを記憶装置３０に記憶するようにしてもよい。以上で、第二のグラフ構造データＧ２に対するグラフを生成する処理が終了する。
【００７７】
グラフ表示処理手段５４が更新後レイアウト元データＬ２と第二のグラフ構造データＧ２とに基づいて生成するグラフの例を図１１に示す。ここで、本実施形態では、上述したようにダミーノードを点で表すことにしているが、図１１のグラフでは、ダミーノードの存在を明確に示すため、ダミーノードを黒丸（小さな円）で表現している。この図１１のグラフでは、共通ノード２〜１０は、図５のデータ更新前のグラフにおける位置関係と同じ位置関係にレイアウトされている。一方、従来のグラフ生成装置を用いて、図７のグラフ構造データＧ２に基づいてSugiyamaアルゴリズムに従った処理を実行することにより生成したグラフの例を図１２に示す。すなわち、この図１２に示すグラフは、更新前のグラフ構造データＧ１に関連付けられたレイアウト元データＬ１を利用せずに、生成されたものである。この図１２のグラフでは、共通ノード２〜１０の位置関係が、図１１のグラフにおける位置関係と異なっており、したがって、図５のデータ更新前のグラフにおける位置関係とも異なっている。具体的には、図１２のグラフにおいては、共通ノード３は第１階層に配置され、共通ノード５，６は第２階層に配置され、共通ノード８は第３階層に配置されている。このため、ユーザは、共通ノード３，５，６，８を、図５のデータ更新前のグラフにおける位置関係と同じ位置関係になるように配置しようと考えると、図１２のグラフの内容を大きく変更しなければならない。これに対し、本実施形態のグラフ生成装置を用いて、第二のグラフ構造データＧ２に対するグラフを生成すると、図１１に示すように、共通ノード２〜１０を、図５のデータ更新前のグラフにおける位置関係と同じ位置関係になるように配置することができるので、ユーザは共通ノード２〜１０のレイアウトを変更する必要がなく、手間がかからない。
【００７８】
尚、本実施形態のグラフ生成装置は、第二のグラフ構造データに対するグラフを生成する場合、各共通ノードについては第一のグラフ構造データと関連付けられた更新前レイアウト元データによって定められる相対的な位置関係を維持するという条件の下で、グラフのレイアウトを行う。このため、本実施形態では、第二のグラフ構造データの内容によっては、あるエッジの始点ノードとその終点ノードとが同一の階層に配置されることがあり得る。また、第二のグラフ構造データの内容によっては、あるエッジの終点ノードがその始点ノードよりも上位の階層に配置されることもあり得る。
【００７９】
次に、本実施形態のグラフ生成装置においてレイアウトの変更が指示されたときにグラフを生成して表示装置２０の画面に表示する処理の手順について説明する。図１３は本実施形態のグラフ生成装置においてレイアウトの変更が指示されたときにグラフを生成して表示装置２０の画面に表示する処理の手順を説明するためのフローチャートである。
【００８０】
ユーザは、表示装置２０の画面に表示されたグラフを見て、各ノードが適切に配置されているか等、グラフの内容を検討する。そして、例えばノードのレイアウト位置やエッジの接続関係等を変更した方がよいと考えると、ユーザはそのグラフにレイアウトの変更を加えることになる。例えばユーザは入力装置１０を用いて表示装置２０の画面に表示されたグラフにおいてノードのレイアウト位置の変更やエッジの接続関係の変更を指示する。レイアウト変更手段５５は、かかるグラフのレイアウトを変更する旨の指示を受けると（Ｓ２１）、その指示された変更の内容を示す変更データを生成し、その生成した変更データを当該グラフに対応するグラフ構造データと関連付けて記憶装置３０に記憶する（Ｓ２２）。
【００８１】
次に、レイアウト変更手段５５は、その生成した変更データが関連付けられているグラフ構造データと関連付けられている全ての変更データを記憶装置３０から読み出し、その読み出した全ての変更データによって示される内容の変更をグラフに施すという条件の下で、当該グラフ構造データに基づいてSugiyamaアルゴリズムに従った処理を実行することにより、当該グラフ構造データに記述されている各ノードのレイアウト位置を算出する（Ｓ２３）。そして、レイアウト変更手段５５は、その算出された結果に基づいてグラフを生成し、表示装置２０の画面に表示する（Ｓ２４）。こうして生成したレイアウト変更後のグラフには、過去に行った変更の内容が全て反映されている。
【００８２】
その後、レイアウト変更手段５５は、ステップＳ２４の処理によりグラフを生成した結果、その生成したレイアウト変更後のグラフに対応するグラフ構造データがレイアウト変更前のグラフに対応するものと異なるかどうかを判断する（Ｓ２５）。レイアウト変更手段５５は、このステップＳ２５の判断が否定的であれば、図１３のフローに従った処理フローを終了する。一方、レイアウト変更手段５５は、ステップＳ２５の判断が肯定的であれば、当該レイアウト変更後のグラフに対応するグラフ構造データを新たに生成し、第一のグラフ構造データとして記憶装置３０に記憶する（Ｓ２６）。これにより、ユーザはグラフ構造データの内容を更新する必要がなくなる。そして、その後、レイアウト変更手段５５は、図１３のフローに従った処理を終了する。
【００８３】
本実施形態のグラフ生成装置は、データ更新後のグラフを生成するときに、第二のグラフ構造データとそれに対する第一のグラフ構造データとに共通して記述されているノードを共通ノードとして特定し、その特定した各共通ノードについては当該第一のグラフ構造データに対応する生成済みのグラフについてのレイアウト元データによって定められる相対的な位置関係を維持するという条件の下で、当該第二のグラフ構造データに基づいてSugiyamaアルゴリズムに従った処理を実行して、グラフのレイアウトを行う。このため、各共通ノードについてはグラフ上でレイアウトすべき位置を、当該生成済みのグラフについてのレイアウト元データに基づいて容易に決定することができるので、データ更新後のグラフ生成に際しての処理の負荷を大幅に軽減することができる。しかも、このデータ更新後のグラフでは、各共通ノードを、当該生成済みのグラフにおける位置関係と同じ位置関係になるようにレイアウトすることができる。
【００８４】
また、本実施形態のグラフ生成装置は、ユーザが入力装置を用いて、表示装置の画面に表示されたグラフに対応するグラフ構造データの内容を更新することを指示するのではなく、当該グラフのレイアウトを変更することを指示したときに、その指示された変更の内容を示す変更データを生成し、当該グラフに対応するグラフ構造データと関連付けて記憶装置に記憶すると共に、その変更の指示に従ったレイアウトの変更を施したグラフを生成して表示装置の画面に表示するレイアウト変更手段を備えている。これにより、変更データをｕｎｄｏ等の処理に利用することができるので、例えば、生成済みのグラフに対して行われたレイアウトの変更をｕｎｄｏ等の処理により一旦元に戻した後に、改めて同じ変更を行う場合、この変更データを利用してグラフにその変更を反映させることが可能となる。
【００８５】
更に、本発明に係るグラフ生成装置では、レイアウト変更手段が、変更データを生成したときに、その変更データが関連付けられているグラフ構造データと関連付けられている全ての変更データによって示される内容の変更をグラフに施すという条件の下で、当該グラフ構造データに基づいてグラフレイアウトアルゴリズムに従った処理を実行することにより、当該グラフ構造データに記述されている各ノードのレイアウト位置を算出し、その算出された結果に基づいてグラフを生成することにより、ユーザは、今回のレイアウトの変更だけでなく、過去に施されたレイアウトの変更も反映されたグラフを容易に得ることができる。
【００８６】
尚、本発明は上記の実施形態に限定されるものではなく、その要旨の範囲内において種々の変形が可能である。
【００８７】
上記の実施形態では、説明を簡単にするために、ノードの数の少ないグラフを生成する場合について説明したが、ノードの数が数千〜数万であるようなグラフを生成する場合にも本発明のグラフ生成装置、グラフ生成方法及びグラフ生成プログラムを適用することができる。実際、本発明のグラフ生成装置、グラフ生成方法及びグラフ生成プログラムは、システムプログラムのサブルーチン同士の呼び出し関係を示すコールグラフ、ネットワーク上の機器構成や企業等の組織構成などを表すグラフ等、さまざまなグラフを生成する場合に適用することができる。
【００８８】
また、上記の実施形態では、グラフレイアウトアルゴリズムとしてSugiyamaアルゴリズムを用いた場合について説明したが、本発明で使用するグラフレイアウトアルゴリズムはSugiyamaアルゴリズムに限定されない。
【００８９】
更に、上記の実施形態では、有向非循環グラフを生成する場合について説明したが、本発明のグラフ生成装置、グラフ生成方法及びグラフ生成プログラムは、例えば、有向循環グラフを生成する場合や、有向グラフ以外のグラフを生成する場合にも適用することができる。
【産業上の利用可能性】
【００９０】
以上説明したように、本発明のグラフ生成装置、グラフ生成方法及びグラフ生成プログラムによれば、データ更新後のグラフを生成するときに、第二のグラフ構造データとそれに対する第一のグラフ構造データとに共通して記述されている各共通ノードについてはグラフ上でレイアウトすべき位置を、当該第一のグラフ構造データに対応する生成済みのグラフについてのレイアウト元データに基づいて容易に決定することができるので、データ更新後のグラフ生成に際しての処理の負荷を大幅に軽減することができる。しかも、このデータ更新後のグラフでは、各共通ノードを、当該生成済みのグラフにおける位置関係と同じ位置関係になるようにレイアウトすることができる。したがって、本発明は、例えば、システム開発において大規模なコールグラフ等を生成して表示手段の画面に表示する場合に用いることができる。
【符号の説明】
【００９１】
１０  入力装置（入力手段）
２０  表示装置（表示手段）
３０  記憶装置（記憶手段）
５０  制御部（制御手段）
５１  データ更新登録手段
５２  レイアウト位置算出手段
５３  レイアウト元データ生成手段
５４  グラフ表示処理手段
５５  レイアウト変更手段
【図１】
2015203883.tif 000003
【図２】
2015203883.tif 000004
【図３】
2015203883.tif 000005
【図４】
2015203883.tif 000006
【図５】
2015203883.tif 000007
【図６】
2015203883.tif 000008
【図７】
2015203883.tif 000009
【図８】
2015203883.tif 000010
【図９】
2015203883.tif 000011
【図１０】
2015203883.tif 000012
【図１１】
2015203883.tif 000013
【図１２】
2015203883.tif 000014
【図１３】
2015203883.tif 000015
【図１４】
2015203883.tif 000016