(57)【要約】【課題】非階層的なグラフ図形の自動配置を行った場合に、ユーザにとって分かり易い描画を行うことのできるグラフ図形配置装置を得る。【解決手段】グラフデータ記憶部１０６は、複数のノードと、これらのノード中、接続関係のあるノード間を結ぶ線として定義したアークとで構成されるグラフ図形をデータとして記憶する。グラフ図形配置部１０３は、グラフデータ記憶部１０６に記憶されたデータに基づき、複数のノードにおけるノード間の距離の設定目標値と、対応する実際のノード間距離との相関を表す関数の、全てのノードについての和を評価関数として定義する。また、評価関数の値が平面配置上で小さくなるようにノード配置の変更を逐次的に行う際に、予め指定されたノードについてはノード配置の変更を行わずにグラフ図形を配置する。【選択図】図１
2008262485.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードと、これらのノード中、接続関係のあるノード間を結ぶ線として定義したアークとで構成されるグラフ図形をデータとして記憶するグラフデータ記憶部と、
前記複数のノードにおけるノード間の距離の設定目標値と、対応する実際のノード間距離との相関を表す関数の、全てのノードについての和を評価関数として定義し、当該評価関数の値が平面配置上で小さくなるようにノード配置の変更を逐次的に行う際に、予め指定されたノードについてはノード配置の変更を行わずにグラフ図形を配置するグラフ図形配置部とを備えたグラフ図形配置装置。
【請求項２】
グラフ図形配置部は、ノード間の距離の設定目標値と、対応する実際のノード間距離との差に基づいてノード間に働く力を定義し、図形配置の対象となるノード間に働く力が平面配置上でバランスするようにノード配置の変更を逐次的に行うと共に、前記ノード間に働く力を求める場合、前記ノード間の距離の設定目標値と対応する実際のノード間距離との相関を表す関数と、予め指定されたノード配置の変更を行わないノードと一つまたは複数のアークを介して接続される他のノードとの間にこれらノード間の最短パスを構成するアークの数と相関を持つ重み付け関数とを用いることを特徴とする請求項１記載のグラフ図形配置装置。
【請求項３】
重み付け関数は、予め指定されたノード配置の変更を行わないノードと、一つまたは複数のアークを介して接続される他のノード間の最短パスを構成するアークの数に関する減少の傾向のある関数とすることを特徴とする請求項２記載のグラフ図形配置装置。
【請求項４】
コンピュータを、
複数のノードと、これらのノード中、接続関係のあるノード間を結ぶ線として定義したアークとで構成されるグラフ図形をデータとして記憶するグラフデータ記憶部のデータを用いて、前記複数のノードにおけるノード間の距離の設定目標値と、対応する実際のノード間距離との相関を表す関数の、全てのノードについての和を評価関数として定義し、当該評価関数の値が平面配置上で小さくなるようにノード配置の変更を逐次的に行う際に、予め指定されたノードについてはノード配置の変更を行わずにグラフ図形を配置するグラフ図形配置部として機能させるためのグラフ図形配置プログラム。
【請求項５】
コンピュータを、請求項２または請求項３に記載のグラフ図形配置部として機能させるための請求項４記載のグラフ図形配置プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数のノードと、これらのノード中、接続関係のあるノード間を結ぶ線として定義したアークとで構成されるグラフ図形を配置するグラフ図形配置装置およびグラフ図形配置プログラムに関するものである。
【背景技術】
【０００２】
階層性を顕示するようなグラフ図形配置法はこれまで多く研究され、アルゴリズムもいくつか提案されているが、非階層的なグラフ図形の配置に関する研究はほとんど行われておらず、ノードを大きさの無い点としたグラフ自動配置アルゴリズムが提案されているに過ぎない。例えば、非特許文献１では、ノード間に単純なバネの力を定義しノード間の理想的な距離をグラフ理論上の距離、即ちノード間の最短経路を構成するアークの数としたグラフ図形自動描画アルゴリズムが提案されているに過ぎなかった。
【０００３】
また、非階層的なグラフ図形の配置に関するアルゴリズムはいくつか提案されているが、例えば特許文献２に示されているように、全てのノードの位置を可変としたアルゴリズムが提案されているに過ぎなかった。
【０００４】
【非特許文献１】Information Processing Letters,Vol.31,NO.1(1989),pp.7-15.
【特許文献１】特許第３３４６１３０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
このようなグラフ図形の非階層的配置アルゴリズムにより、ある決まった位置関係を持ったノードを含むグラフ図形を自動配置すると、そのノードの位置関係が考慮されずに配置されるため、ユーザにとって必ずしも分かり易いとはいえないという問題点があった。
【０００６】
この発明は、上記のような課題を解決するためになされたもので、非階層的なグラフ図形の自動配置を行った場合に、ユーザにとって分かり易い描画を行うことのできるグラフ図形配置装置を得ることを目的とする。
【課題を解決するための手段】
【０００７】
この発明に係るグラフ図形配置装置は、複数のノードにおけるノード間の距離の設定目標値と、対応する実際のノード間距離との相関を表す関数の、全てのノードについての和を評価関数として定義し、評価関数の値が平面配置上で小さくなるようにノード配置の変更を逐次的に行う際に、予め指定されたノードについてはノード配置の変更を行わずにグラフ図形を配置するグラフ図形配置部を備えたものである。
【発明の効果】
【０００８】
この発明のグラフ図形配置装置は、ノード配置の変更を逐次的に行う際に、予め指定されたノードについてはノード配置の変更を行わずにグラフ図形を配置するようにしたので、ユーザにとって分かり易いグラフ図形の描画を行うことができる。
【発明を実施するための最良の形態】
【０００９】
実施の形態１．
図１は、この発明の実施の形態１によるグラフ図形配置装置を示す構成図である。
図において、グラフ図形配置装置はコンピュータで構成され、入力装置１００、処理装置１０１、および出力装置１０７からなり、処理装置１０１は、管理部１０２、グラフ図形配置部１０３、グラフ図形編集部１０４、グラフ図形描画部１０５およびグラフデータ記憶部１０６を備えている。入力装置１００は、キーボードやポインティングデバイス等の入力機器を備えた装置であり、処理装置１０１に対してグラフ図形の配置に関するコマンド入力やデータ入力を行うものである。出力装置１０７は、ＣＲＴや液晶ディスプレイといった表示装置やプリンタ等の出力機器を備えた装置であり、処理装置１０１から出力されたグラフ図形を出力するものである。尚、入力装置１００側の機器と出力装置１０７側の機器とは、一つのＣＲＴやキーボード、ハードディスク等を共有してもよく、入力データとグラフ図形の配置とをマルチウインドウ形式で表示することも自由である。
【００１０】
管理部１０２は、処理装置１０１全体の処理を管理するプロセッサ等からなる機能部である。例えば、管理部１０２は、入力装置１００からの編集要求に従いグラフ図形編集部１０４へ処理を移し、グラフ図形の編集を行う。グラフ図形編集部１０４の処理が終了すると、その結果をグラフデータ記憶部１０６へ記憶させ、処理をグラフ図形描画部１０５へ移す、といった制御を行うよう構成されている。また、管理部１０２は、入力装置１００からのグラフ図形自動配置要求があった場合は、これに従って、グラフ図形配置部１０３に処理を移し、グラフ図形の配置を決定させ、その結果をグラフデータ記憶部１０６に記憶させ、その後処理をグラフ図形描画部１０５へ移すよう制御を行う。
【００１１】
グラフ図形配置部１０３は、管理部１０２の命令に従い、グラフデータ記憶部１０６のデータを元にグラフの配置を自動的に見やすく再配置するよう構成されている。尚、この詳細については後述する。
グラフ図形編集部１０４は、管理部１０２の命令に従い、グラフ図形の編集を行う処理部である。その編集内容は、ノードの追加および削除および移動、アークの追加および削除などがあり、またグラフ図形の配置を適当なノードあるいは適当な座標を中心に拡大または縮小することも可能である。
【００１２】
グラフ図形描画部１０５は、管理部１０２の命令に従い、グラフデータ記憶部１０６のデータを元にグラフ図形を出力装置１０７に描画する機能部である。グラフデータ記憶部１０６は、グラフの構造と共に、各要素の大きさや位置などのデータを記憶する記憶部である。
【００１３】
尚、上記処理装置１０１における管理部１０２〜グラフ図形描画部１０５は、それぞれの機能に対応するソフトウェアと、これを実行するためのＣＰＵやメモリ等のハードウェアから構成されている。
【００１４】
次に、グラフ図形配置部１０３で用いられているグラフ図形配置法について詳細を説明する。グラフ図形配置部１０３は、グラフ図形を自動的に見やすく配置する処理手段を備えている。本実施の形態ではグラフ図形の配置法として、予め決められたノード間の理想距離（ノード間の距離の設定目標値）にできるだけ実際のノード間の距離が近くなるようにグラフを配置するグラフ配置法を用いる。具体的には、グラフの各連結成分に対し平面上に配置するときのノード間の理想距離を決め、このノード間の理想距離と実際の距離との誤差の２乗に予め適切に定められた関数値を掛けたものの、全ノードの合計ができるだけ小さくなるような状態にノードを少しずつ動かしていくという配置法を用いる。但し、前処理としてグラフ中の多重枝、自己閉路は取り除き、後処理として前処理で取り除いた多重枝、自己閉路を復元してグラフ図形を描画する。
【００１５】
図２は、グラフ中の多重枝、自己閉路を取り除く処理を示すフローチャートであり、このフローチャートに沿ってグラフ中の多重枝、自己閉路を取り除く処理について説明する。
先ず、ステップＳＴ１１０では、多重枝の組、即ち、同じ二つのノードを両端とするアークの組を探す。探索の方法としては単純に二つの異なるアークを選ぶ全ての組についてその両端のノードを比較する。ステップＳＴ１１１では、同じ二つのノードを両端とするアークの組が見つかったかどうかを判断する。見つかった場合は処理をステップＳＴ１１２に移し、見つかったアークの組のどちらかのアークを取り除く。同じ二つのノードを両端とするアークの組が見つからない場合は処理をステップＳＴ１１３に移す。ステップＳＴ１１３では、自己閉路を作るアーク、即ち、両端が同じ一つのノードであるアークを探す。尚、探索の方法としては、全てのアークに対してその両端のノードを比較する。ステップＳＴ１１４では、両端が同じ一つのノードであるアークが見つかったかどうかを判断する。見つかった場合は、処理をステップＳＴ１１５に移し、そのアークを取り除く。見つからなかった場合は、処理を終了する。
【００１６】
尚、本実施の形態で用いる距離としてはユークリッド距離を用いるが、ハミング距離等の他の距離を用いても同様の議論ができる。また、グラフ図形の描画を行う座標系の次元は２次元でも３次元でもよく、一般にｎ次元でもよい（ｎ＝１，２，３，４，…）。
まず、アークａijの両端のノードｉ、ｊ間のグラフ図形上の理想的な距離ｅijを、ノードｉおよびノードｊの状態によって
【数１】
2008262485.tif 000003
のように定義する。但し、式（１）において、Ｌはノード間の長さの基準となるスケーリング定数、ｎiはノードｉに接続するアークの数であり、ｎjも同様にノードｊに接続するアークの数である。式（１）によりノード間の理想的な距離は（ｎi＋ｎj）が大きいほど長くなる。つまり、式（１）によって、ノードｉ、ｊ間の理想的な距離ｅijは、ノードｉ、ｊに接続するアークの数の増加関数になっている。尚、ノードｉ、ｊ間の理想的な距離の定義は上記の式（１）の形だけに限るものではなく、他の適切な定義によるものでも良い。
【００１７】
また、アークａijの理想的な距離を式（１）で定義されるｅijの値とし、一つのアークで結ばれないような隣接しないノードｍ、ｎ間の理想距離については、ノードｍ、ｎ間のパスを構成するアークの理想距離の合計の長さとする。これにより、遠くのノードを不合理に接近させることを防止できる。
【００１８】
次に、評価関数として、ノード間の理想距離と実際のノード間の距離との誤差の２乗に適当な関数値を掛けたものの合計Ｅを
【数２】
2008262485.tif 000004
のように定義する。但し、式（２）において、Ｎはグラフの全ノードの集合である。ｉ、ｊはＮの要素であるがｊ≠ｉであり、予め指定されたノード間の位置関係を保ちたいノードは、iとしては含めないこととする。また、ｋは予め適切に決められた定数、ｆは予め適切に決められた関数、ｅijはノードｉとノードｊ間のグラフ図形上の理想距離、Ｒijはノードｉ、ｊ間の距離である。式（２）のように、１／ｅijを掛けることにより誤差を単位長さ当たりに換算でき、相対的に評価できる。
【００１９】
先に述べたように、本実施の形態のグラフの非階層的自動配置法では、先ず、各ノード間の配置平面上の理想距離を目的に応じた定式によって決め、式（２）のＥができるだけ小さくなるようにノードを少しずつ動かし、グラフの配置を求める。評価関数（式２）は、この図形配置法において、結果的に各ノード間に作用する相互作用を発生しているものである。ここでＩijをノード間のグラフ理論上の距離とし、式（２）のｆ(ｅij)の代わりにｆ（Ｉij）またはｆ（ｅij、Ｉij）としてもよい。ノード間のグラフ理論上の距離とは、ノードｉ、ｊ間を結ぶ最短経路上のアークの数である。このように、Ｅをできるだけ小さくするようなノードの配置を求める具体的な方法には各種の方法がある。例えば、最適化問題の解あるいは近似解を求める方法としてよく知られているシミュレーティッドアニーリング法を用いる場合の一例について説明する。
【００２０】
先ず、式（２）のＥをノードｉのみに対して計算した以下の式を定義する。
【数３】
2008262485.tif 000005
予め指定されたノード間の位置関係を保ちたいノード以外の全てのノードについてＥiを計算し、その中でＥiの値が一番大きかったノードｉについてノードｉの位置を少しだけ動かし、式（２）を目的関数としたシミュレーティッドアニーリング法の近似解を求める操作を１回適用する。その後、全てのノードについてＥiを再度計算し、その中でＥiが一番大きかったノードについて前述の操作と同様に近似解を求めるという操作を繰り返してＥができるだけ小さくなるようなノードの配置を求める。
【００２１】
式（２）のｆ(ｅij)として適当な関数を定義することにより、ノードｉ、ｊ間の理想距離が離れる程にＥに占める誤差の相対的な大きさを小さくすることができる。これによりグラフ全体のバランスに配慮しつつ、局所的なバランスのとれたグラフの配置を行うことができる。本実施の形態ではｆ(ｅij)を
【数４】
2008262485.tif 000006
のように定義する。これにより、ｆ(ｅij)はｅijの減少関数となり、ノード間の理想距離が離れる程にＥに占める誤差の相対的な大きさを小さくすることができ、グラフ全体のバランスに配慮しつつ、局所的なバランスのとれたグラフの配置を行うことができる。
このような操作では、予め指定されたノードの位置関係は変更されないため、予め指定されたノードの位置関係を保ちつつ、バランスのとれたグラフ配置を得ることができる。
【００２２】
次に、グラフ図形配置部１０３によるグラフ図形配置処理の詳細について説明する。
図３は、実施の形態１のグラフ図形配置部１０３によるグラフ図形配置の流れを示すフローチャートであり、この図３及び図１を用いて説明する。
先ず、グラフ図形配置部１０３は、グラフデータ記憶部１０６からグラフ図形のデータを取り出す（ステップＳＴ１２０）。続いて、グラフ図形配置部１０３は、グラフ図形中の連結成分毎にステップＳＴ１２１以降の処理を行う。ステップＳＴ１２１において、グラフ図形配置部１０３は、図２で示した流れでグラフ図形データから多重枝、自己閉路を探索して取り除く。
【００２３】
グラフ図形配置部１０３は、ある連結成分についてステップＳＴ１２１の処理を実行すると、ループ用のカウンタであるｃｏｕｎｔの値を０に初期化する（ステップＳＴ１２２）。この後、グラフ図形配置部１０３は、例えば上記式（１）のような、算定式を用いて、各ノード間の理想距離を算出する（ステップＳＴ１２３）。
【００２４】
各ノード間の理想距離を算出すると、グラフ図形配置部１０３は、例えば、上記の式（２）で定義される評価関数Ｅの値が予め設定した基準値より小さくなった、または、ｃｏｕｎｔの値が設定値より大きくなったかのいずれかの条件を満たすか否かにより、グラフ図形自動配置アルゴリズムの終了を判定する（ステップＳＴ１２４）。ここで、上記いずれかの条件を満たし、グラフ図形の配置が決定されたと判断される場合、グラフ図形配置部１０３は、配置決定したグラフ図形データを、取り除いた多重枝、自己閉路を復元したグラフデータとしてグラフデータ記憶部１０６へ記憶する（ステップＳＴ１２５）。
【００２５】
図４は、グラフデータ記憶部１０６に記憶されるデータの説明図である。
グラフデータ記憶部１０６に記憶されるデータは、例えば、ノードに関しては、図中の（ａ）のように、｛ノード番号、ｘ座標、ｙ座標、半径、移動フラグ｝の組が記憶され、アークに関しては、図中の（ｂ）のように、｛アーク番号、始点ノード番号、終点ノード番号｝の組が記憶される。
【００２６】
一方、上記条件のいずれも満たさない場合、グラフ図形配置部１０３は、ｃｏｕｎｔの値を１だけ増やし（ステップＳＴ１２６）、上記式（２）による評価関数Ｅの値が小さくなるようにノードの位置を変更する。但し、予め指定されたノード同士の位置関係を保ちたいノードは、上記の移動フラグにより判定し、移動フラグがＯＦＦのノードについては位置の変更からは除外する（ステップＳＴ１２７）。
【００２７】
また、グラフ図形配置部１０３は、配置を決定したグラフ図形を逐次描画するか否かを設定する逐次描画フラグを有し、この逐次描画フラグがオンかオフであるかによって、ステップＳＴ１２７においてノードを移動したグラフ図形を逐次描画するか否かが判断される（ステップＳＴ１２８）。ステップＳＴ１２８において逐次描画フラグがオンであれば、グラフ図形配置部１０３は、ｃｏｕｎｔの値が描画条件を満たすかを判断する（ステップＳＴ１２９）。例えば、ｃｏｕｎｔの値によるループを何回行う毎にグラフ図形を描画するのかを示す値Ｃを、逐次描画する割合を決める値として予め設定する。グラフ図形配置部１０３は、ｃｏｕｎｔの値がＣで割り切れた場合、描画条件を満たすと判断して、ステップＳＴ１３０における描画処理に移行する。また、ｃｏｕｎｔの値がＣで割り切れなければ、描画条件を満たさないと判断して、ステップＳＴ１２４の処理に戻る。
【００２８】
グラフ図形配置部１０３は、ステップＳＴ１２９で描画条件を満たしていると判断された場合、ステップＳＴ１２４〜ステップＳＴ１２５と進んで、ステップＳＴ１２７でノードの位置が変更されたグラフ図形のデータをグラフデータ記憶部１０６に記憶する。同時に、管理部１０２は、このグラフ図形データをグラフ図形描画部１０５に出力する。これにより、グラフ図形描画部１０５は、出力装置１０７を構成するＬＣＤ等の表示装置において、現在表示されているグラフ図形を消去し、代わりにステップＳＴ１２７でノードの位置が変更されたグラフ図形を表示する。このようにすることで、グラフ図形の自動配置処理によるグラフ図形の変化を適切な進度で連続的に表示することができる。
【００２９】
次にグラフ図形の編集処理について説明する。
図５は、実施の形態１のグラフ図形配置装置によるグラフ図形編集処理の流れを示すフローチャートであり、この図及び図１を用いて説明する。
グラフ図形の編集にあたり、処理装置１０１は、先ず、入力装置１００を構成するマウス等のポインティングデバイスによってグラフ図形編集に関するコマンド又はデータの入力待ち状態にある（ステップＳＴ１４０）。ここで、入力装置１００を用いてコマンド又はデータが入力されると、グラフ図形配置部１０３を介して管理部１０２に出力される。
【００３０】
管理部１０２では、入力されたコマンド又はデータがグラフ図形の編集に関するものであるか否かを判定する（ステップＳＴ１４１）。ここで、グラフ図形の編集に関するものでないと判定されると、ステップＳＴ１４２の処理に移行し、グラフ図形の編集に関するものであれば、ステップＳＴ１４４の処理に移行する。
【００３１】
ステップＳＴ１４２において、管理部１０２は、入力されたコマンド又はデータがグラフ図形の自動描画処理に関するものであるか否かを判定する。ここで、グラフ図形の自動描画に関するものでないと判定されると、ステップＳＴ１４３の処理に移行し、グラフ図形の自動描画に関するものであれば、ステップＳＴ１４５の処理に移行する。
【００３２】
ステップＳＴ１４３では、管理部１０２が、入力されたコマンドが処理の終了コマンドであるか否かを判定し、終了コマンドであれば処理を終了する。また、終了コマンドでなければ、グラフ図形の編集処理及びグラフ図形の自動描画処理以外の他の処理に関するコマンド又はデータであると判定してその処理を実行し（ステップＳＴ１４６）、その後ステップＳＴ１４０に戻ってコマンド又はデータの入力待ち状態になる。
【００３３】
管理部１０２は、ステップＳＴ１４１で、入力されたコマンド又はデータがグラフ図形の編集に関するものであると判定すると、このコマンド又はデータをグラフ図形編集部１０４に出力する。グラフ図形編集部１０４は、管理部１０２から入力されたコマンド又はデータに従い、グラフ図形の編集処理を実行する（ステップＳＴ１４４）。編集内容としては、ノードの移動、削除及び拡大縮小、アークの追加及び削除等があり、グラフ図形の配置を適当なノードあるいは適当な座標を中心に拡大又は縮小することもできる。また、ノードの位置関係を保ちたいノードには、それを示すフラグを設定することもできる。
【００３４】
また、管理部１０２は、ステップＳＴ１４２で、入力されたコマンド又はデータがグラフ図形の自動描画処理に関するものであると判定すると、このコマンド又はデータをグラフ図形配置部１０３に出力する。グラフ図形配置部１０３では、管理部１０２から入力されたコマンド又はデータに従って、図３に示したような流れでグラフ図形の配置処理を実行し、配置決定されたグラフ図形のデータをグラフデータ記憶部１０６に記憶する。この後、グラフ図形描画部１０５は、自動描画すべきグラフ図形データをグラフデータ記憶部１０６から読み出して、出力装置１０７の表示装置に表示する（ステップＳＴ１４５）。
【００３５】
図６および図７は、自動描画例を比較して示す説明図である。
図６の例は、ノード同士の位置関係を保ちたいノードとそれ以外のノードの区別なく、従来の非階層的なグラフ図形自動描画方法により、描画を行った例であり、ノードに対するアークの入出力関係がわかりにくいものとなっている。
これに対して、本実施の形態１によるグラフ図形配置方法では、ノード間の位置関係を保ちたいノード同士の位置関係を変更することなく、グラフ図形を自動配置する。
図７は、図６のグラフ図形を本実施の形態１によって自動配置したものである。左端と、右端のハッチングで示すノードは、ユーザがノード同士の位置関係を保つように指定したノードである。図７は、左端と右端のハッチングで示すノードの位置関係が保たれているために、アークの入出力関係が図６の場合と比較して格段に分かり易い描画となっている。
【００３６】
以上のように、実施の形態１のグラフ図形配置装置によれば、複数のノードと、これらのノード中、接続関係のあるノード間を結ぶ線として定義したアークとで構成されるグラフ図形をデータとして記憶するグラフデータ記憶部と、複数のノードにおけるノード間の距離の設定目標値と、対応する実際のノード間距離との相関を表す関数の、全てのノードについての和を評価関数として定義し、評価関数の値が平面配置上で小さくなるようにノード配置の変更を逐次的に行う際に、予め指定されたノードについてはノード配置の変更を行わずにグラフ図形を配置するグラフ図形配置部とを備えたので、予め指定したノードについてはその位置関係を保ちつつグラフ図形を配置することができ、ユーザにとって分かり易いグラフ図形の描画を行うことができる。
【００３７】
また、実施の形態１のグラフ図形配置プログラムによれば、コンピュータを、複数のノードと、これらのノード中、接続関係のあるノード間を結ぶ線として定義したアークとで構成されるグラフ図形をデータとして記憶するグラフデータ記憶部のデータを用いて、複数のノードにおけるノード間の距離の設定目標値と、対応する実際のノード間距離との相関を表す関数の、全てのノードについての和を評価関数として定義し、評価関数の値が平面配置上で小さくなるようにノード配置の変更を逐次的に行う際に、予め指定されたノードについてはノード配置の変更を行わずにグラフ図形を配置するグラフ図形配置部として機能させるようにしたので、コンピュータ上に、予め指定したノードについてはその位置関係を保ちつつグラフ図形を配置することができ、ユーザにとって分かり易いグラフ図形の描画を行うことができるグラフ図形配置装置を実現することができる。
【００３８】
実施の形態２．
本実施の形態２では、ノード間の距離の設定目標値と、対応する実際のノード間距離との差に基づいてノード間に働く力を定義し、図形配置の対象となるノード間に働く力が平面配置上で平衡になるようにノード配置を逐次的に変更するものである。
実施の形態２によるグラフ図形配置装置において、基本的な構成は実施の形態１と同様であるが、グラフ図形配置部１０３によりノード間に働く力を配置位置の評価関数としてグラフ図形の配置処理がなされる点が異なっている。即ち、実施の形態２におけるグラフ図形配置部１０３は、ノード間に働く力を求める場合、ノード間の距離の設定目標値と対応する実際のノード間距離との相関を表す関数と、予め指定されたノード配置の変更を行わないノードと一つまたは複数のアークを介して接続される他のノードとの間にこれらノード間の最短パスを構成するアークの数と相関を持つ重み付け関数とを用いるよう構成されている。その他の構成は実施の形態１と同様であるため、これらの説明は省略し、以下、図１を援用して説明する。
【００３９】
グラフ図形配置部１０３は、上記実施の形態１と同様に、グラフ図形を自動的に見やすく配置する処理手段を備えている。本実施の形態２によるグラフ図形配置部１０３には、ノード間に働く力が定義されており、ノード間に働く力ができるだけ平衡する状態としてグラフ図形の配置を求める。
【００４０】
一方、実施の形態２のグラフ図形配置部１０３では、アークａijの両端のノードｉ、ｊ間のグラフ図形上の理想的な距離ｅijを下記式（５）のように定義する。但し、下記式（５）において、αはノード間の長さの基準となるスケーリング定数である。Ｎiはノードｉに隣接するノードの集合である。Ｒmはノードｍの半径であり、m⊂Ｎi又はm⊂Ｎjである。右辺の第１項を２で割っているのは、ノードｉとノードｊに関して平均をとるという意味合いである。Ｐはノード間の理想距離をある値以下にするための定数である。
【数５】
2008262485.tif 000007
上記式（５）により、アークの理想的な長さはノード半径Ｒmの増加関数となる。つまり、上記式（５）によって、ノードｉ、ｊ間の理想的な距離ｅijは、ノードｉ、ｊに半径の大きなノードが接続するほど長くなる傾向にある。
尚、本発明は、ノードｉ、ｊ間の理想的な距離を上記式（５）で求める場合に限定されるものではなく、目的に応じて自由に設定することができる。
【００４１】
また、上記式（５）で定義される理想距離ｅijをアークａijの理想的な長さとし、一つのアークで結ばれない、隣接しないノードｍ、ｎ間の理想距離は、ノードｍ、ｎ間のパスを構成するアークの理想距離の合計の長さとして定義する。これにより、グラフ図形の配置において、遠方に配置すべきノードを不合理に接近させることを防ぐことができる。
【００４２】
本実施の形態２によるグラフ配置アルゴリズムが設定されたグラフ図形配置部１０３では、ノード間に働く力が平面配置上で平衡になるようにノード配置を逐次的に変更する際、予め指定されたノード同士の位置関係を保ちたいノードについては、配置を変更しないため、予め指定したノード同士の位置関係を保ちながら、ノード間の理想的な距離の定義に従い、ノード間の距離をグラフ図形の構造によって決定することができる。
【００４３】
更に、グラフ図形配置部１０３には、評価関数として、ノードｉ、ｊ間の理想距離ｅijと実際のノードｉ、ｊ間の距離ｄijとの差（ノード間の距離の設定目標値と対応する実際のノード間の距離との相関を表す関数）に適当な関数値ｆ(Ｉij)と重み付け関数ｇを掛けた関数が、ノードｉ、ｊ間に働く力Ｆijとして下記式（６）のように定義されている。但し、下記式（６）において、ｆ（Ｉij）は常に正の値をとる適当な関数であり、評価関数Ｆijの値に対するノードｉ、ｊ間の理想距離ｅijと実際のノードｉ、ｊ間の距離ｄijとの相関の寄与率に相当する。また、ｇも正の値をとる重み付け関数である。Ｉijはノードｉ、ｊ間のグラフ理論上の距離である。ｅijはノードｉ、ｊ間のグラフ図形上の理想距離、ｄijはグラフ図形上のノードｉ、ｊ間の実際の距離である。
Ｆij＝ｆ（Ｉij）・ｇ・（ｄij−ｅij）            （６）
また、上記式（６）の右辺の第３項である（ｄij−ｅij）は、ノードｉ、ｊ間の距離がノードｉ、ｊ間の理想距離よりも小さい場合に負の値をとり、ノードｉ、ｊ間の距離がノードｉ、ｊ間の理想距離よりも大きい場合に正の値をとる。ここで、関数ｆ＞０、ｇ＞０なので、上記式（６）で定義される力はノードｉ、ｊ間の距離がノードｉ、ｊ間の理想距離よりも小さい場合に斥力となり、ノードｉ、ｊ間の距離がノードｉ、ｊ間の理想距離よりも大きいときには引力となる。
【００４４】
尚、上述の説明では、関数ｆ（Ｉij）として常に正の値をとる適当な関数を選択したが、非常に小さな範囲で負の値をとるような関数でもよい。
また、グラフ図形配置部１０３には、ノード間のグラフ理論上の距離を表す関数ｆ（Ｉij）が下記式（７）のように定義される。ここで、Ｋ1は適当な正の定数である。
【数６】
2008262485.tif 000008
【００４５】
式（６）において、関数ｇは、ノードｉ間と、予め指定されたノード同士の位置関係を保ちたいノードとのグラフ理論上の距離に関する関数となる。具体的には、ノードｉとノードｊを結ぶ最短パスに含まれる予め指定されたノード同士の位置関係を保ちたいノードがｎ個含まれており、そのノードをｍ1、ｍ2、…、ｍnとしたとき、
【数７】
2008262485.tif 000009
と定義する。ここで、Ｋ2は適当な正の定数である。つまり、ｇはノードｉと、予め指定されたノード同士の位置関係を保ちたいノードのグラフ理論上の距離が近い程、大きな値をとる重み付け関数となる。また、予め指定されたノード配置の変更を行わないノードと、一つまたは複数のアークを介して接続される他のノード間の最短パスを構成するアークの数が増加するにつれて、その大きさが適切な程度で小さくなるような（減少傾向にあるような）重み付け関数となる。
これにより、予め指定されたノード同士の位置関係を保ちたいノードに近接するノードには、より大きな力が働くことになり、ノード同士の位置関係を保つことによるゆがみを生じにくくしている。
【００４６】
尚、本発明は、ノード間の力の定義として、上記式（６）、（７）、（８）に限るものではなく、ノードｉと、予め指定されたノード同士の位置関係を保ちたいノードのグラフ理論上の距離が増加するにつれて、その大きさが適切な程度で小さくなるような（減少傾向にあるような）重み付け関数を含む関数であればよい。上述したように、本実施の形態２のグラフ図形配置法では、上記式（６）で定義されるノード間に働く力が平衡状態になるようにノードの配置を逐次的に変えていく。
【００４７】
次に、グラフ図形配置部１０３によるグラフ図形の配置処理について説明する。
図８は、実施の形態２のグラフ図形配置部１０３によるグラフ図形配置の流れを示すフローチャートであり、この図８及び図１を用いて説明する。
先ず、グラフ図形配置部１０３は、グラフデータ記憶部１０６からグラフ図形のデータを取り出す（ステップＳＴ１２０）。続いて、グラフ図形配置部１０３は、グラフ図形中の連結成分毎にステップＳＴ１２１以降の処理を行う。ステップＳＴ１２１において、グラフ図形配置部１０３は、上記実施の形態１で図２を用いて説明した流れでグラフ図形データから多重枝、自己閉路を探索して取り除く。
【００４８】
次に、グラフ図形配置部１０３は、ある連結成分についてステップＳＴ１２１の処理を実行すると、ループ用のカウンタであるｃｏｕｎｔの値を０に初期化する（ステップＳＴ１２２）。この後、グラフ図形配置部１０３は、例えば上記式（５）のような一つのアークで結ばれるノード間の理想的な距離をノードの状態によって決定する関数の算定式を用いて、各ノード間の理想距離を算出する（ステップＳＴ１２３）。
【００４９】
各ノード間の理想距離を算出すると、グラフ図形配置部１０３は、例えば上記式（６）で定義されるノードｉ、ｊ間に働く力Ｆijの値が予め設定した基準値より小さくなった、又は、ｃｏｕｎｔの値が設定値より大きくなったかのいずれかの条件を満たすか否かにより、グラフ図形自動配置アルゴリズムの終了を判定する（ステップＳＴ１２４）。ここで、上記いずれかの条件を満たし、グラフ図形の配置が決定されたと判断される場合、グラフ図形配置部１０３は、配置決定したグラフ図形データをグラフデータ記憶部１０６へ記憶する（ステップＳＴ１２５）。グラフデータ記憶部に記憶されるデータは、実施の形態１と同様、ノードに関しては図４の（ａ）に示すように、｛ノード番号、ｘ座標、ｙ座標、半径、移動フラグ｝の組が記憶され、アークに関しては図４の（ｂ）に示すように、｛アーク番号、始点ノード番号、終点ノード番号｝の組が記憶される。
【００５０】
一方、上記条件のいずれも満たさない場合、グラフ図形配置部１０３は、ｃｏｕｎｔの値を１だけ増やし（ステップＳＴ１２６）、上記式（６）による評価関数Ｆの値が小さくなるようにノードの位置を変更する（ステップＳＴ２００）。但し、予め指定されたノード同士の位置関係を保ちたいノードは、上記の移動フラグにより判定し、位置の変更からは除外する。
【００５１】
また、グラフ図形配置部１０３は、配置を決定したグラフ図形を逐次描画するか否かを設定する逐次描画フラグを有し、この逐次描画フラグがオンかオフであるかによって、ステップＳＴ１２７においてノードを移動したグラフ図形を逐次描画するか否かが判断される（ステップＳＴ１２８）。このステップＳＴ１２８において逐次描画フラグがオンであれば、グラフ図形配置部１０３は、ｃｏｕｎｔの値が描画条件を満たすかを判断する（ステップＳＴ１２９）。例えば、ｃｏｕｎｔの値によるループを何回行う毎にグラフ図形を描画するのかを示す値Ｃを、逐次描画する割合を決める値として予め設定する。グラフ図形配置部１０３は、ｃｏｕｎｔの値がＣで割り切れた場合、描画条件を満たすと判断して、ステップＳＴ１３０における描画処理に移行する。また、ｃｏｕｎｔの値がＣで割り切れなければ、描画条件を満たさないと判断して、ステップＳＴ１２４の処理に戻る。
【００５２】
グラフ図形配置部１０３は、ステップＳＴ１２９で描画条件を満たしていると判断された場合、ステップＳＴ２００でノードの位置が変更されたグラフ図形のデータをグラフデータ記憶部１０６に記憶する。同時に、管理部１０２は、このグラフ図形データをグラフ図形描画部１０５に出力する。これにより、グラフ図形描画部１０５は、出力装置１０７を構成するＬＣＤ等の表示装置において、現在表示されているグラフ図形を消去し、代わりにステップＳＴ２００でノードの位置が変更されたグラフ図形を表示する。このようにすることで、グラフ図形の自動配置処理によるグラフ図形の変化を適切な進度で連続的に表示することができる。
【００５３】
図９および図１０は、自動描画例を比較して示す説明図である。
図９の例は、ノード同士の位置関係を保ちたいノードとそれ以外のノードの区別なく、従来の非階層的なグラフ図形自動描画方法により、描画を行った例であり、ノードに対するアークの入出力関係が分かりにくいものとなっている。
これに対して、本実施の形態２によるグラフ図形配置方法では、ノード間の位置関係を保ちたいノード同士の位置関係を変更することなく、グラフ図形を自動配置する。図１０は、図９のグラフ図形を本実施の形態２によって自動配置したものである。左端と、右端のハッチングで示すノードは、ユーザがノード同士の位置関係を保つように指定したノードである。図１０は、左端と右端のハッチングで示すノードの位置関係が保たれているために、アークの入出力関係が図９と比較して格段に分かり易い描画となっている。また、本実施例の形態２の効果として、ノード同士の位置関係を保つように指定したノードに比較的多くのアークが接続する場合でも見やすい描画を得ることができている。
【００５４】
以上のように、実施の形態２のグラフ図形配置装置によれば、グラフ図形配置部は、ノード間の距離の設定目標値と、対応する実際のノード間距離との差に基づいてノード間に働く力を定義し、図形配置の対象となるノード間に働く力が平面配置上でバランスするようにノード配置の変更を逐次的に行うと共に、ノード間に働く力を求める場合、ノード間の距離の設定目標値と対応する実際のノード間距離との相関を表す関数と、予め指定されたノード配置の変更を行わないノードと一つまたは複数のアークを介して接続される他のノードとの間にこれらノード間の最短パスを構成するアークの数と相関を持つ重み付け関数とを用いるようにしたので、グラフ図形構造の特徴に応じてグラフ図形を配置することができ、見やすいグラフ図形を得ることができる。
【００５５】
また、実施の形態２のグラフ図形配置装置によれば、重み付け関数は、予め指定されたノード配置の変更を行わないノードと、一つまたは複数のアークを介して接続される他のノード間の最短パスを構成するアークの数に関する減少の傾向のある関数としたので、グラフ図形全体でのノード間に働く力の平衡に配慮しつつ、予め指定されたノード同士の位置関係を保ちたいノードの局所的なノード間に働く力が平衡なグラフ図形配置を行うことができる。
【００５６】
また、実施の形態２のグラフ図形配置プログラムによれば、コンピュータを、ノード間の距離の設定目標値と、対応する実際のノード間距離との差に基づいてノード間に働く力を定義し、図形配置の対象となるノード間に働く力が平面配置上でバランスするようにノード配置の変更を逐次的に行うと共に、ノード間に働く力を求める場合、ノード間の距離の設定目標値と対応する実際のノード間距離との相関を表す関数と、予め指定されたノード配置の変更を行わないノードと一つまたは複数のアークを介して接続される他のノードとの間にこれらノード間の最短パスを構成するアークの数と相関を持つ重み付け関数とを用いるグラフ図形配置部として機能させるようにしたので、コンピュータ上に、グラフ図形構造の特徴に応じてグラフ図形を配置することができ、見やすいグラフ図形を得ることができるグラフ図形配置装置を実現することができる。
【００５７】
また、実施の形態２のグラフ図形配置プログラムによれば、重み付け関数は、予め指定されたノード配置の変更を行わないノードと、一つまたは複数のアークを介して接続される他のノード間の最短パスを構成するアークの数に関する減少の傾向のある関数としたので、コンピュータ上に、グラフ図形全体でのノード間に働く力の平衡に配慮しつつ、予め指定されたノード同士の位置関係を保ちたいノードの局所的なノード間に働く力が平衡なグラフ図形配置を行えるグラフ図形配置装置を実現することができる。
【図面の簡単な説明】
【００５８】
【図１】この発明の実施の形態１によるグラフ図形配置装置を示す構成図である。
【図２】この発明の実施の形態１のグラフ図形配置装置におけるグラフ中の多重枝、自己閉路を取り除く処理を示すフローチャートである。
【図３】この発明の実施の形態１のグラフ図形配置装置におけるグラフ図形配置の流れを示すフローチャートである。
【図４】この発明の実施の形態１のグラフ図形配置装置におけるグラフデータ記憶部に記憶されるデータの説明図である。
【図５】この発明の実施の形態１のグラフ図形配置装置におけるグラフ図形編集処理の流れを示すフローチャートである。
【図６】この発明の実施の形態１のグラフ図形配置装置における自動描画例の比較例を示す説明図である。
【図７】この発明の実施の形態１のグラフ図形配置装置における自動描画例を示す説明図である。
【図８】この発明の実施の形態２のグラフ図形配置装置におけるグラフ図形の配置処理を示すフローチャートである。
【図９】この発明の実施の形態２のグラフ図形配置装置における自動描画例の比較例を示す説明図である。
【図１０】この発明の実施の形態２のグラフ図形配置装置における自動描画例を示す説明図である。
【符号の説明】
【００５９】
１００  入力装置、１０１  処理装置、１０２  管理部、１０３  グラフ図形配置部、１０４  グラフ図形編集部、１０５  グラフ図形描画部、１０６  グラフデータ記憶部、１０７  出力装置。
【図１】
2008262485.tif 000010
【図２】
2008262485.tif 000011
【図３】
2008262485.tif 000012
【図４】
2008262485.tif 000013
【図５】
2008262485.tif 000014
【図６】
2008262485.tif 000015
【図７】
2008262485.tif 000016
【図８】
2008262485.tif 000017
【図９】
2008262485.tif 000018
【図１０】
2008262485.tif 000019