(57)【特許請求の範囲】
【請求項１】
グラフ図形配置部が、複数のノードと、これらのノード中、接続関係のあるノード間を結ぶ線として定義したアークとで構成されるグラフ図形をデータとして記憶するグラフデータ記憶部から前記グラフ図形を取り出し、アークの両端の各ノードに接続されるノードにそれぞれ隣接するノードの大きさの総和を加算した値を利用する算定式から算定したノード間の距離の設定目標値に基づいて、各ノードの配置を非階層的に決定することにより、前記グラフ図形の配置を行うグラフ図形配置法。
【請求項２】
グラフ図形配置部は、アークの両端の各ノードに接続されるノードにそれぞれ隣接するノードの大きさの総和を加算した値を利用する算定式として、前記ノードの大きさに関して増加傾向がある関数を用いることを特徴とする請求項１記載のグラフ図形配置法。
【請求項３】
グラフ図形配置部は、複数のアークを介して接続されるノード間の距離の設定目標値を、前記ノード間のパスを構成する各アークの両端のノード間の距離の設定目標値に基づいて算定することを特徴とする請求項１又は請求項２記載のグラフ図形配置法。
【請求項４】
グラフ図形配置部は、ノード間の距離の設定目標値と、対応する実際のノード間距離との相関を表す関数の、全てのノードについての和を評価関数として用い、この評価関数の値が平面配置上で小さくなるようにノード配置の変更を逐次的に行うことを特徴とする請求項１から請求項３のうちのいずれか１項記載のグラフ図形配置法。
【請求項５】
グラフ図形配置部は、ノード間の距離の設定目標値と、対応する実際のノード間の距離との差に基づいてノード間に働く力を定義した評価関数を用いて、図形配置の対象となるノード間に働く力が平面配置上で平衡状態になるようにノード配置の変更を逐次的に行うことを特徴とする請求項１から請求項３のうちのいずれか１項記載のグラフ図形配置法。
【請求項６】
グラフ図形配置部は、評価関数値に対するノード間の距離の設定目標値と、対応する実際のノード間の距離との相関の寄与率を、前記ノード間の距離の設定目標値又は前記対応する実際のノード間の距離の少なくとも一つに関して減少傾向がある関数としたことを特徴とする請求項４記載のグラフ図形配置法。
【請求項７】
グラフ図形配置部は、評価関数値に対するノード間の距離の設定目標値と、対応する実際のノード間の距離との相関の寄与率を、前記ノード間の距離の設定目標値、前記ノード間の距離又は前記対応する実際のノード間の距離の少なくとも一つに関して減少傾向がある関数としたことを特徴とする請求項５記載のグラフ図形配置法。
【請求項８】
複数のノードと、これらのノード中、接続関係のあるノード間を結ぶ線として定義したアークとで構成されるグラフ図形をデータとして記憶するグラフデータ記憶部から前記グラフ図形を取り出し、アークの両端の各ノードに接続されるノードにそれぞれ隣接するノードの大きさの総和を加算した値を利用する算定式から算定したノード間の距離の設定目標値に基づいて、各ノードの配置を非階層的に決定することにより、前記グラフ図形の配置を行うグラフ図形配置部としてコンピュータを機能させるプログラム。
【請求項９】
グラフ図形配置部は、アークの両端の各ノードに接続されるノードにそれぞれ隣接するノードの大きさの総和を加算した値を利用する算定式として、前記ノードの大きさに関して増加傾向がある関数を用いることを特徴とする請求項８記載のプログラム。
【請求項１０】
グラフ図形配置部は、複数のアークを介して接続されるノード間の距離の設定目標値を、前記ノード間のパスを構成する各アークの両端のノード間の距離の設定目標値に基づいて算定することを特徴とする請求項８又は請求項９記載のプログラム。
【請求項１１】
複数のノードと、これらのノード中、接続関係のあるノード間を結ぶ線として定義したアークとで構成されるグラフ図形をデータとして記憶するグラフデータ記憶部と、
前記グラフデータ記憶部から前記グラフ図形を取り出し、アークの両端の各ノードに接続されるノードにそれぞれ隣接するノードの大きさの総和を加算した値を利用する算定式から算定したノード間の距離の設定目標値に基づいて、各ノードの配置を非階層的に決定することにより、前記グラフ図形の配置を行うグラフ図形配置部とを備えたグラフ図形配置装置。
【請求項１２】
グラフ図形配置部は、アークの両端の各ノードに接続されるノードにそれぞれ隣接するノードの大きさの総和を加算した値を利用する算定式として、前記ノードの大きさに関して増加傾向がある関数を用いることを特徴とする請求項１１記載のグラフ図形配置装置。
【請求項１３】
グラフ図形配置部は、複数のアークを介して接続されるノード間の距離の設定目標値を、前記ノード間のパスを構成する各アークの両端のノード間の距離の設定目標値に基づいて算定することを特徴とする請求項１１又は請求項１２記載のグラフ図形配置装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、グラフ図形の配置方法に係り、特に非階層的にグラフ図形を配置するグラフ図形配置方法、この方法に従ってグラフ図形を配置するグラフ図形配置部としてコンピュータを機能させるプログラム及びその装置に関するものである。
【背景技術】
【０００２】
階層性を顕示するグラフ図形配置法は多く研究されており、様々なアルゴリズムが提案されている。これに対し、非階層的なグラフ図形の配置に関する研究は、あまり行われておらず、グラフ図形に含まれるノードの大きさを考慮せず、グラフ図形のノードを点として自動配置するアルゴリズムが提案されているにすぎない。例えば、非特許文献１に開示されるアルゴリズムでは、グラフ図形に含まれるノードを点として考え、ノード間に単純なバネの力を定義してノード間の理想的な距離をグラフ理論上の距離、即ちノード間の最短経路を構成するアークの数としてグラフ図形を自動描画する。
【０００３】
なお、特許文献１では、アークの両端のノードに接続される各々のアーク数についての増加関数として定義されたノード間の距離の設定目標値算定式から、ノード間距離の設定目標値を算出し、この設定目標値に基づいて各ノードの配置を非階層的に決定することにより、ノードの大きさが均一なグラフ図形をバランス良く配置することができる。
【０００４】
【非特許文献１】T. KAMADA and S. KAWAI, “An algorithm for drawing general undirected graphs”, Information Processing Letters, Vol. 31, NO.1(1989), pp. 7-15.
【特許文献１】特許第３３４６１３０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来の非階層的にグラフ図形を配置する方法では、ある程度の大きさを持ったノードを含むグラフ図形を配置するにあたり、ノードの大きさが考慮されない。このため、グラフ図形を配置した際、ノード同士が重なって配置されてグラフ図形が見難くなるという課題があった。
【０００６】
また、特許文献１は、ノードの大きさが均一なグラフ図形をバランス良く配置することができるが、ノードの大きさにばらつきがあるグラフ図形ではバランス良く描画することができない。
【０００７】
この発明は、上記のような課題を解決するためになされたもので、グラフ図形構造の特徴やノードの大きさに応じてグラフ図形を配置することにより、アークの交差やノードの重なりを防ぐことができ、見やすいグラフ図形描画を実現できるグラフ図形配置方法、この方法に従ってグラフ図形を配置するグラフ図形配置部としてコンピュータを機能させるプログラム及びその装置を得ることを目的とする。
【０００８】
また、この発明は、グラフ図形構造の特徴やノードの大きさに応じてグラフ図形を配置すると共に、対話的なグラフ図形の編集が可能なグラフ図形配置方法、この方法に従ってグラフ図形を配置するグラフ図形配置部としてコンピュータを機能させるプログラム及びその装置を得ることを目的とする。
【課題を解決するための手段】
【０００９】
この発明に係るグラフ図形配置方法は、グラフ図形配置部が、複数のノードと、これらのノード中、接続関係のあるノード間を結ぶ線として定義したアークとで構成されるグラフ図形をデータとして記憶するグラフデータ記憶部からグラフ図形を取り出し、アークの両端の各ノードに接続されるノードにそれぞれ隣接するノードの大きさの総和を加算した値を利用する算定式から算定したノード間の距離の設定目標値に基づいて、各ノードの配置を非階層的に決定することにより、グラフ図形の配置を行うものである。
【発明の効果】
【００１０】
この発明によれば、アークの両端の各ノードに接続されるノードの大きさと相関がある算定式から算定したノード間の距離の設定目標値に基づいて、各ノードの配置を非階層的に決定することから、アークの交差やノードの重なりが少なく見やすいグラフ図形の描画を実現できるという効果がある。
【発明を実施するための最良の形態】
【００１１】
実施の形態１．
図１は、この発明の実施の形態１によるグラフ図形配置装置の構成を示すブロック図である。本実施の形態１によるグラフ図形配置装置は、入力装置１、処理装置２及び出力装置８を備える。また、処理装置２は、管理部３、グラフ図形配置部４、グラフ図形編集部５、グラフ図形描画部６及びグラフデータ記憶部７を有する。なお、入力装置１側の機器と出力装置８側の機器とは、一つのＣＲＴ、ＬＣＤやキーボード、ハードディスク等を共有してもよく、入力データとグラフ図形の配置とをマルチウインドウ形式で表示することも自由である。
【００１２】
管理部３は、処理装置２全体の処理を管理する。即ち、管理部３は、入力装置１からの編集要求に従いグラフ図形編集部５へ処理を移し、グラフ図形編集部５によりグラフ図形の編集を行わせる。グラフ図形編集部５の処理が終了すると、管理部３は、その結果をグラフデータ記憶部７へ記憶させ、処理をグラフ図形描画部６へ移す。グラフ図形描画部６では、グラフデータ記憶部７のデータに従い出力装置８へグラフ図形を描画する。
【００１３】
また、管理部３は、入力装置１からのグラフ図形自動配置要求に従い、グラフ図形配置部４に処理を移し、グラフ図形配置部４によりグラフ図形の配置を決定させる。管理部３は、グラフ図形配置部４による配置結果をグラフデータ記憶部７に記憶させ、この後に処理をグラフ図形描画部６へ移す。グラフ図形描画部６では、グラフデータ記憶部７のデータに従い、出力装置８へグラフ図形を描画する。
【００１４】
グラフ図形配置部４は、管理部３の命令に従い、グラフデータ記憶部７のデータを基にグラフ図形の配置を自動的に見やすく再配置する手段を備えている。本実施の形態１では、グラフ図形の配置法として、予め決められたノード間の理想距離（設定目標値）に対して、できるだけ実際のノード間の距離が近くなるようにグラフ図形を配置する。
【００１５】
具体的には、グラフ図形の各連結成分に対し、平面上に配置するときのノード間の理想距離を決め、ノード間の理想距離と実際の距離との誤差の２乗に適当な関数値を掛けたものの全ノードの合計ができるだけ小さくなるような状態にノードを少しずつ動かしていくという配置法を用いる。但し、前処理としてグラフ中の多重枝、自己閉路は取り除き、後処理として前処理で取り除いた多重枝、自己閉路を復元してグラフ図形を描画する。
【００１６】
なお、本発明では、ノード間の理想距離を算出するにあたり、後述するように、ノードの大きさに関するパラメータを含む算定式を用いる。これにより、ある程度の大きさを有するノードを含むグラフ図形を配置する場合においても、ノード同士の重なりが少なくなるように配置することができる。
【００１７】
グラフ図形編集部５は、管理部３の命令に従い、グラフ図形の編集を行う処理手段を備えている。編集内容としては、ノードの追加、削除及び移動、アークの追加及び削除等があり、グラフ図形の配置を適当なノードあるいは適当な座標を中心に拡大又は縮小することもできる。
【００１８】
また、グラフ図形描画部６は、管理部３の命令に従い、グラフデータ記憶部７のデータを基にグラフ図形を出力装置８に描画する手段を備える。グラフデータ記憶部７は、グラフの構造と共に各要素の大きさや位置等のデータを記憶する手段を備える。例えば、処理装置２に搭載されたハードディスクや記憶媒体を再生するドライブ装置等により具現化される。
【００１９】
なお、管理部３、グラフ図形配置部４、グラフ図形編集部５、グラフ図形描画部６及びグラフデータ記憶部７は、例えば、本発明の趣旨に従う処理プログラムを、処理装置２を構成するコンピュータの演算処理装置に実行させてその動作を制御することにより、ソフトウエアとハードウエアとが協働した具体的な手段として実現することができる。
【００２０】
次に実施の形態１によるグラフ図形配置処理について説明する。
上述したように、本実施の形態１では、グラフの各連結成分に対し、平面上に配置するときのノード間の理想距離を決め、ノード間の理想距離と実際の距離との差の２乗に適当な関数値を掛けたもの（ノード間の距離の設定目標値と、対応する実際のノード間距離との相関を表す関数）の、全ノードの合計ができるだけ小さくなるような状態にノードを少しずつ動かしていく。この際、前処理としてグラフ図形における多重枝、自己閉路を取り除き、後処理として前処理で取り除いた多重枝、自己閉路を復元してグラフ図形を描画する。
【００２１】
図２は、実施の形態１のグラフ図形処理装置によるグラフ図形中の多重枝、自己閉路を取り除く処理の流れを示すフローチャートであり、この図及び図１に沿って説明する。
先ず、グラフ図形配置部４は、管理部３による制御の下、グラフデータ記憶部７からグラフ図形のデータを読み出し、グラフ図形から多重枝の組、即ち同じ２つのノードを両端とするアークの組を探索する（ステップＳＴ１）。この探索の方法としては、単純に２つの異なるアークを選ぶ全ての組についてその両端のノードを比較する方法が考えられる。
【００２２】
グラフ図形配置部４は、ステップＳＴ１での探索を開始すると、同じ２つのノードを両端とするアークの組の有無を判定する処理に移行する（ステップＳＴ２）。このとき、同じ２つのノードを両端とするアークの組が見つかると、グラフ図形配置部４は、当該アークの組のうち、どちらかのアークを取り除く処理を行う（ステップＳＴ３）。
【００２３】
一方、同じ２つのノードを両端とするアークの組が見つからなければ、グラフ図形配置部４は、当該グラフ図形から、自己閉路を作るアーク、即ち両端が同じ１つのノードであるアークを探索する（ステップＳＴ４）。なお、この探索の方法としては、全てのアークに対してその両端のノードを比較することが考えられる。
【００２４】
グラフ図形配置部４は、ステップＳＴ４での探索を開始すると、両端が同じ１つのノードであるアークの有無を判定する処理に移行する（ステップＳＴ５）。このとき、両端が同じ１つのノードであるアークが見つかると、グラフ図形配置部４は、このアークを取り除く処理を実行する（ステップＳＴ６）。また、見つからなかった場合は、処理を終了する。
【００２５】
なお、本実施の形態で用いる距離としては、ユークリッド距離を用いるが、ハミング距離等の他の距離を用いても同様の議論ができる。また、グラフ図形の描画を行う座標系の次元は、２次元でも３次元でもよく、一般にｎ次元でもよい（ｎ＝１，２，３，４，・・・）。
【００２６】
次にノード間の理想距離の算出処理について説明する。
先ず、グラフ図形配置部４には、アークａijの両端のノードｉ，ｊ間のグラフ図形上の理想的な距離ｅijが、ノードｉ及びノードｊの状態によって下記式（１）のように定義される。但し、下記式（１）において、αはノード間の長さの基準となるスケーリング定数である。また、Ｎiはノードｉに隣接するノードの集合、Ｎjはノードｊに隣接するノードの集合である。Ｒmはノードｍの半径であり、ｍ⊂Ｎi又はｍ⊂Ｎjである。右辺の第１項を２で割っているのは、ノードｉとノードｊに関して平均をとるという意味合いである。
【数１】
0004566928.tif 000002
【００２７】
上記式（１）により、アークａijの両端のノードｉ，ｊ間のグラフ図形上の理想的な距離は、ノードｉ、ノードｊに接続するノードの半径の総和が大きいほど長くなる。つまり、上記式（１）によってノードｉ，ｊ間の理想的な距離ｅijは、ノードｉ，ｊに接続するノードの半径の総和の増加関数になっている。
【００２８】
なお、本発明におけるノードｉ，ｊ間の理想的な距離（設定目標値）の定義は、上記式（１）で示される関係に限定されるものではない。例えば、１つのアークで結ばれるノード間の理想的な距離を、アークの両端の各ノードに隣接するノードの半径と相関がある数値（例えば、ノードの半径の総和のように当該ノードの大きさを規定するもの）に関して増加の傾向にある関数で定義する。この定義に合致する関数の算定式であれば、目的に応じて自由に設定することができる。
【００２９】
また、アークａijの理想的な距離を上記式（１）で定義されるｅijの値とし、１つのアークで結ばれない、隣接しないノードｍ，ｎ間の理想距離については、ノードｍ，ｎ間のパスを構成するアークの理想距離の合計の長さとする。これにより、グラフ図形の配置において、遠方に配置すべきノードを不合理に接近させることを防ぐことができる。
【００３０】
本実施の形態１によるグラフ配置アルゴリズムでは、アークの長さができるだけ理想的なアークの長さになるようにグラフ図形を配置するため、アークの長さをその両端のノードの状態によって決定することができる。また、アークの長さの定義が上記式（１）の場合は、大きな半径を持ったノード、及び、次数の高いノードを含むグラフ図形も見易く配置できることになる。
【００３１】
さらに、グラフ図形配置部４には、評価関数として、ノード間の理想距離と実際のノード間の距離との差の２乗（ノード間の距離の理想距離と対応する実際のノード間の距離との相関を表す関数）に適当な関数値を掛けた関数の、配置対象のグラフ図形の全ノードについての総和Ｅが、下記式（２）のように定義される。
但し、下記式（２）において、Ｎはグラフ図形の全ノードの集合であり、ｉ，ｊはＮの要素（但し、ｊ≠ｉ）である。また、ｋijはノードｉ，ｊ間のバネ定数であり、評価関数Ｅの値に対するノードｉ，ｊ間の距離の理想距離と実際のノードｉ，ｊ間の距離との相関の寄与率に相当する。また、ｅijはノードｉとノードｊと間のグラフ図形上の理想距離（設定目標値）、ｄijはノードｉ，ｊ間の距離である。
【数２】
0004566928.tif 000003
【００３２】
上述したように、本実施の形態１によるグラフ図形の非階層的自動配置法では、各ノード間の配置平面上の理想距離を、目的に応じた算定式（例えば、上記式（１））によって算出し、上記式（２）を例とするような評価関数Ｅの値がある程度小さくなるようにノードを少しずつ動かし、グラフ図形の配置を求める。上記式（２）で表される評価関数Ｅは、本実施の形態によるグラフ図形配置法において、結果的に各ノード間の相互作用の発生を規定している。つまり、このＥをできるだけ小さくすれば、各ノード間での相互作用が小さい、例えばノード同士の重なりがない配置を実現することができる。
【００３３】
評価関数Ｅをできるだけ小さくするノード配置を求める具体的な方法には各種の方法がある。例えば、最適化問題の解あるいは近似解を求める方法としてよく知られているシミュレーティッドアニーリング法を用いる場合について説明する。
グラフ図形配置部４において、上記式（２）のＥをノードｉのみに対して計算した下記式（３）を定義する。
【数３】
0004566928.tif 000004
【００３４】
グラフ図形配置部４は、グラフデータ記憶部７から読み出したグラフ図形データの配置にあたり、グラフ図形における全てのノードについて上記式（３）によるＥiを計算し、計算結果のうちＥiの値が最も大きかったノードｉについてノードｉの位置を少しだけ動かして、上記式（２）を目的関数としたシミュレーティッドアニーリング法の近似解を求める操作を１回適用する。この後、グラフ図形配置部４は、全てのノードについてＥiを再度計算し、計算結果のうちＥiが最も大きかったノードについて前述の操作と同様に近似解を求めるという操作を繰り返してＥができるだけ小さくなるようなノードの配置を求める。
【００３５】
上記式（２）のｋijとして適当な計算式を定義することにより、ノードｉ，ｊ間の理想距離が離れる程にＥに占める誤差（理想距離ｅijと実際の距離ｄijとの相関を表す関数値）の相対的な大きさを小さくすることができ、また、ノード同士が接近しすぎて重なることを少なくすることができる。これにより、グラフ図形全体のバランスに配慮しつつ、局所的なバランスのとれたグラフ図形の配置を行うことができる。本実施の形態１によるグラフ図形配置部４では、ｋijが下記式（４）で定義される。下記式（４）は、評価関数値に対するノードｉ，ｊ間の理想距離ｅijと実際のノードｉ，ｊ間距離ｄijとの相関の寄与率に相当するｋijが、実際のノードｉ，ｊ間距離ｄijとノードｉ，ｊ間の理想距離ｅijとに関して減少する減少関数で定義したものである。
【数４】
0004566928.tif 000005
但し、Ｋ1，Ｋ2は適当な定数である。ｔijはノードｉ，ｊにおいてグラフ図形の構造を考慮して定義される値であり、ノードｉ，ｊが隣接する場合は下記式（５）によって計算される。ここで、ｎiはノードｉの次数（ノードｉに隣接するアークの数）である。また、隣接しないノードｉ，ｊ間については、ｔijとしてノードｉ，ｊを結ぶ最短パスを構成するアークの両端のノードｍ，ｎのｔmnの合計の長さとする。
【数５】
0004566928.tif 000006
【００３６】
なお、本発明において、ｋijの定義は、上記式（４）の形だけに限るものではなく、隣接するノード間について、そのノードに接続するノードの大きさと相関がある関数、そのノードに接続するアークの数と相関がある関数、あるいはノード間の理想距離と相関がある関数のうちのいずれかであれば、目的に応じて自由に設定することができる。
【００３７】
上記式（５）により、最短パスに次数の高いノードを含むか、あるいはグラフ理論上の距離が離れる程にＥに占める誤差の相対的な大きさを小さくすることができ、グラフ図形全体のバランスを配慮しつつ、局所的なバランスのとれたグラフ図形の配置を行うことができる。
【００３８】
次に、グラフ図形配置部４によるグラフ図形配置処理の詳細について説明する。
図３は、実施の形態１のグラフ図形配置部によるグラフ図形配置の流れを示すフローチャートであり、この図及び図１を用いて説明する。
先ず、グラフ図形配置部４は、グラフデータ記憶部７からグラフ図形のデータを取り出す（ステップＳＴ１ａ）。続いて、グラフ図形配置部４は、グラフ図形中の連結成分毎にステップＳＴ２ａ以降の処理を行う。ステップＳＴ２ａにおいて、グラフ図形配置部４は、図２で示した流れでグラフ図形データから多重枝、自己閉路を探索して取り除く。
【００３９】
グラフ図形配置部４は、ある連結成分についてステップＳＴ２ａの処理を実行すると、ループ用のカウンタであるｃｏｕｎｔの値を０に初期化する（ステップＳＴ３ａ）。この後、グラフ図形配置部４は、例えば上記式（１）のような、アークの両端の各ノードに隣接するノードの半径に関して増加の傾向にある算定式を用いて、各ノード間の理想距離を算出する（ステップＳＴ４ａ）。
【００４０】
各ノード間の理想距離を算出すると、グラフ図形配置部４は、例えば上記式（２）で定義される評価関数Ｅの値が予め設定した基準値より小さくなった、又は、ｃｏｕｎｔの値が設定値より大きくなったかのいずれかの条件を満たすか否かにより、グラフ図形自動配置アルゴリズムの終了を判定する（ステップＳＴ５ａ）。ここで、上記いずれかの条件を満たし、グラフ図形の配置が決定されたと判断される場合、グラフ図形配置部４は、配置決定したグラフ図形データを、取り除いた多重枝、自己閉路を復元したグラフデータとしてグラフデータ記憶部７へ記憶する（ステップＳＴ６ａ）。
【００４１】
一方、上記条件のいずれも満たさない場合、グラフ図形配置部４は、ｃｏｕｎｔの値を１だけ増やし（ステップＳＴ７ａ）、上記式（２）による評価関数Ｅの値が小さくなるようにノードの位置を変更する（ステップＳＴ８ａ）。また、グラフ図形配置部４は、配置を決定したグラフ図形を逐次描画するか否かを設定する逐次描画フラグを有し、この逐次描画フラグがオンかオフであるかによって、ステップＳＴ８ａにおいてノードを移動したグラフ図形を逐次描画するか否かが判断される（ステップＳＴ９ａ）。
【００４２】
ステップＳＴ９ａにおいて逐次描画フラグがオンであれば、グラフ図形配置部４は、ｃｏｕｎｔの値が描画条件を満たすかを判断する（ステップＳＴ１０ａ）。例えば、ｃｏｕｎｔの値によるループを何回行う毎にグラフ図形を描画するのかを示す値Ｃを、逐次描画する割合を決める値として予め設定する。グラフ図形配置部４は、ｃｏｕｎｔの値がＣで割り切れた場合、描画条件を満たすと判断して、ステップＳＴ１１ａにおける描画処理に移行する。また、ｃｏｕｎｔの値がＣで割り切れなければ、描画条件を満たさないと判断して、ステップＳＴ５ａの処理に戻る。
【００４３】
グラフ図形配置部４は、ステップＳＴ１０ａで描画条件を満たしていると判断された場合、ステップＳＴ８ａでノードの位置が変更されたグラフ図形のデータをグラフデータ記憶部７に記憶する。この後、管理部３は、このグラフ図形データをグラフ図形描画部６に出力する。これにより、グラフ図形描画部６は、出力装置８を構成するＬＣＤ等の表示装置において、現在表示されているグラフ図形を消去し、かわりにステップＳＴ８ａでノードの位置が変更されたグラフ図形を表示する。このようにすることで、グラフ図形の自動配置処理によるグラフ図形の変化を適切な進度で連続的に表示することができる。
【００４４】
次にグラフ図形の編集処理について説明する。
図４は、実施の形態１のグラフ図形配置装置によるグラフ図形編集処理の流れを示すフローチャートであり、この図及び図１を用いて説明する。
グラフ図形の編集にあたり、処理装置２は、先ず、入力装置１を構成するマウス等のポインティングデバイスによってグラフ図形編集に関するコマンド又はデータの入力待ち状態にある（ステップＳＴ１ｂ）。ここで、入力装置１を用いてコマンド又はデータが入力されると、グラフ図形配置部４を介して管理部３に出力される。
【００４５】
管理部３では、入力されたコマンド又はデータがグラフ図形の編集に関するものであるか否かを判定する（ステップＳＴ２ｂ）。ここで、グラフ図形の編集に関するものでないと判定されると、ステップＳＴ３ｂの処理に移行し、グラフ図形の編集に関するものであれば、ステップＳＴ５ｂの処理に移行する。
【００４６】
ステップＳＴ３ｂにおいて、管理部３は、入力されたコマンド又はデータがグラフ図形の自動描画処理に関するものであるか否かを判定する。ここで、グラフ図形の自動描画に関するものでないと判定されると、ステップＳＴ４ｂの処理に移行し、グラフ図形の自動描画に関するものであれば、ステップＳＴ６ｂの処理に移行する。
【００４７】
ステップＳＴ４ｂでは、管理部３が、入力されたコマンドが処理の終了コマンドであるか否かを判定し、終了コマンドであれば処理を終了する。また、終了コマンドでなければ、グラフ図形の編集処理及びグラフ図形の自動描画処理以外の他の処理に関するコマンド又はデータであると判定してその処理を実行し、その後ステップＳＴ１ｂに戻ってコマンド又はデータの入力待ち状態になる。
【００４８】
管理部３は、ステップＳＴ２ｂで、入力されたコマンド又はデータがグラフ図形の編集に関するものであると判定すると、このコマンド又はデータをグラフ図形編集部５に出力する。グラフ図形編集部５は、管理部３から入力されたコマンド又はデータに従い、グラフ図形の編集処理を実行する（ステップＳＴ５ｂ）。編集内容としては、ノードの移動、削除及び拡大縮小、アークの追加及び削除等があり、グラフ図形の配置を適当なノードあるいは適当な座標を中心に拡大又は縮小することもできる。
【００４９】
また、管理部３は、ステップＳＴ３ｂで、入力されたコマンド又はデータがグラフ図形の自動描画処理に関するものであると判定すると、このコマンド又はデータをグラフ図形配置部４に出力する。グラフ図形配置部４では、管理部３から入力されたコマンド又はデータに従って、図３に示したような流れでグラフ図形の配置処理を実行し、配置決定されたグラフ図形のデータをグラフデータ記憶部７に記憶する。この後、グラフ図形描画部６は、自動描画すべきグラフ図形データをグラフデータ記憶部７から読み出して、出力装置８の表示装置に表示する（ステップＳＴ６ｂ）。
【００５０】
図５は、グラフ図形の描画例を示す図であり、図５（ａ）は本実施の形態を適用せずにグラフ図形を描画した場合を示し、図５（ｂ）は図５（ａ）と同一の構成要素を有するグラフ図形に対して本実施の形態によるグラフ図形配置方法を適用した場合の描画例を示している。図５に示すグラフ図形は、半径の小さい円で表記されるノードと、このノードより半径の大きい円で表記される、ある程度の大きさを持ったノードとを構成要素として含んでいる。このため、ノードの大きさを考慮しないと、グラフ図形を配置した際、例えば大きなノード同士が重なって配置されてしまう。
【００５１】
図５（ａ）の例は、ユーザが、グラフ図形エディタを用いて、上述のようなグラフ図形を入力した際の描画例であり、ユーザが思いつくままに描いたためアークの交差が多く、またノードの配置も見やすい配置になっておらず、ノード同士の重なりも生じている。
これに対して、本実施の形態１によるグラフ図形配置方法では、上記式（１）で定義されるような、アークの両端の各ノードに隣接するノードの半径と相関のある、例えば増加の傾向にある算定式を用いて各ノード間の理想距離を算出し、上記式（２）で定義されるようなノード間の相互作用の発生に関する評価関数Ｅの値がより小さくなるように配置位置を決定する。これにより、アークの交差やノードの重なりのないグラフ図形の配置が実現される。従って、図５（ｂ）に示すように、図５（ａ）と比較して各段に見やすい描画がなされる。
【００５２】
図６は、グラフ図形の描画の他例を示す図であり、図６（ａ）はある程度の大きさを持つノードを含む複数のノードを円周上に並べてアークで結んだグラフ図形の描画例を示しており、図６（ｂ）は図６（ａ）と同一の構成要素を有するグラフ図形に対して本実施の形態によるグラフ図形配置方法を適用した場合の描画例を示している。図６（ａ）のように、複数のノードを配置し、アークで接続してしまうと、アークの交差が非常に多く、ノードの重なりも生じており、ノード同士の接続関係が分かりにくい非常に見難い描画結果となる。
【００５３】
そこで、このグラフ図形に対して本実施の形態１によるグラフ図形配置方法を適用すると、上記式（１）や上記式（２）等を用いて、ノードの大きさを考慮し、重なり等のノード間の相互作用ができるだけ小さくなるようにグラフ図形の構成要素が配置される。これにより、図６（ｂ）に示す例では、図６（ａ）と同一構成のグラフ図形が例えば８つの大径の円の各ノードから放射状に小径のノードが接続する接続構造を含むグラフ図形が得られる。図６（ａ）と比較すると明らかなように、ノード間の重なりがなくなり、アークの交差がほとんど無い、非常に見やすい描画結果になっている。
【００５４】
以上のように、この実施の形態１によれば、グラフ図形配置部４が、複数のノードと、接続関係を有するノード間を結ぶ線として定義したアークとで構成されるグラフ図形を配置するにあたり、当該グラフ図形中のアーク両端の各ノードに接続されるノードの大きさと相関がある算定式、特にアーク両端の各ノードに接続されるノードの大きさに関して増加傾向がある算定式を用いて各ノード間の距離の設定目標値を算出し、算出されたノード間距離の設定目標値に基づいて、各ノードの配置を非階層的に決定するので、ノードの大きさに応じてグラフ図形が配置され、アークの交差やノードの重なりを防ぐことができ、見やすいグラフ図形の描画を実現することができる。
【００５５】
また、この実施の形態１によれば、グラフ図形配置部４が、グラフ図形を配置するにあたり、グラフ図形から複数のアークを介して接続される２つのノード間を多重枝として取り除き、これらノード間の距離について設定目標値を算出するので、グラフ図形の構成要素が全体としてバランスのとれた配置がなされ、見やすいグラフ図形の描画を実現することができる。
【００５６】
さらに、この実施の形態１によれば、グラフ図形配置部４が、ノード間の距離の設定目標値と、対応する実際のノード間距離との相関を表す関数値の、配置対象のグラフ図形における全てのノードについての和を評価関数として定義し、この評価関数の値が平面配置上で小さくなるようにノード配置の変更を逐次的に行うので、グラフ図形構造の特徴に応じてグラフ図形を配置することができ、見やすいグラフ図形の描画を実現することができる。
【００５７】
さらに、この実施の形態１によれば、評価関数Ｅの値に対するノードｉ，ｊ間の理想距離ｅijと実際のノードｉ，ｊ間の距離ｄijとの相関の寄与率ｋijを、ノードｉ，ｊ間の理想距離ｅij又は対応する実際のノードｉ，ｊ間の距離ｄijのいずれかに関して減少傾向がある関数とするので、ノードｉ，ｊ間の理想距離ｅijが離れる程に、評価関数Ｅの値に占める、理想距離ｅijと実際の距離ｄijとの相関を表す関数値（例えば、理想距離ｅijと実際の距離ｄijとの誤差）の相対的な大きさを小さくすることができ、また、ノード同士が接近しすぎて重なることを少なくすることができる。
【００５８】
実施の形態２．
本実施の形態２では、ノード間の距離の設定目標値と、対応する実際のノード間距離との差に基づいてノード間に働く力を定義し、図形配置の対象となるノード間に働く力が平面配置上で平衡になるようにノード配置を逐次的に変更するものである。
実施の形態２によるグラフ図形配置装置は、上記実施の形態１と基本的な構成は同様であるが、グラフ図形配置部４によりノード間に働く力を配置位置の判定パラメータとしてグラフ図形の配置処理がなされる点で異なる。
【００５９】
次に、実施の形態２によるグラフ図形配置処理の詳細について説明する。
グラフ図形配置部４は、上記実施の形態１と同様に、グラフ図形を自動的に見やすく配置する処理手段を備えている。本実施の形態２によるグラフ図形配置部４には、ノード間に働く力が定義されており、ノード間に働く力ができるだけ平衡する状態としてグラフ図形の配置を求める。
【００６０】
一方、実施の形態２のグラフ図形配置部４では、アークａijの両端のノードｉ，ｊ間のグラフ図形上の理想的な距離ｅijが下記式（６）のように定義される。但し、下記式（６）において、αはノード間の長さの基準となるスケーリング定数である。Ｎiはノードｉに隣接するノードの集合である。Ｒmはノードｍの半径であり、m⊂Ｎi又はm⊂Ｎjである。右辺の第１項を２で割っているのは、ノードｉとノードｊに関して平均をとるという意味合いである。Ｐはノード間の理想距離をある値以下にするための定数である。
【数６】
0004566928.tif 000007
【００６１】
上記式（６）により、アークの理想的な長さはノード半径Ｒmの増加関数となる。つまり、上記式（６）によって、ノードｉ，ｊ間の理想的な距離ｅijは、ノードｉ，ｊに半径の大きなノードが接続するほど長くなる傾向にある。
なお、本発明は、ノードｉ，ｊ間の理想的な距離を上記式（６）で求める場合に限定されるものではなく、１つのアークで結ばれるノード間の理想的な距離をノードの状態によって決定する関数の算定式であればよく、目的に応じて自由に設定することができる。
【００６２】
また、上記式（６）で定義される理想距離ｅijをアークａijの理想的な長さとし、１つのアークで結ばれない、隣接しないノードｍ，ｎ間の理想距離は、ノードｍ，ｎ間のパスを構成するアークの理想距離の合計の長さとして定義する。これにより、グラフ図形の配置において、遠方に配置すべきノードを不合理に接近させることを防ぐことができる。
【００６３】
本実施の形態２によるグラフ配置アルゴリズムが設定されたグラフ図形配置部４では、ノード間の距離ができるだけノード間の理想的な距離になるようにグラフを配置する。このため、ノード間の理想的な距離の定義に従い、ノード間の距離をグラフ図形の構造によって決定することができる。例えば、ノード間の距離の定義が上記式（６）である場合、次数の高いノードを含むグラフ図形も見やすく配置することができる。
【００６４】
さらに、グラフ図形配置部４には、評価関数として、ノードｉ，ｊ間の理想距離ｅijと実際のノードｉ，ｊ間の距離ｄijとの差（ノード間の距離の理想距離と対応する実際のノード間の距離との相関を表す関数）に適当な関数値を掛けた関数を、ノードｉ，ｊ間に働く力Ｆijとして下記式（７）のように定義されている。但し、下記式（７）において、ｆ（Ｉij）は常に正の値をとる適当な関数であり、評価関数Ｆijの値に対するノードｉ，ｊ間の理想距離ｅijと実際のノードｉ，ｊ間の距離ｄijとの相関の寄与率に相当する。Ｉijはノードｉ，ｊ間のグラフ理論上の距離である。ｅijはノードｉ，ｊ間のグラフ図形上の理想距離、ｄijはグラフ図形上のノードｉ，ｊ間の実際の距離である。
【数７】
0004566928.tif 000008
【００６５】
また、上記式（７）の右辺の第２項である（ｄij−ｅij）は、ノードｉ，ｊ間の距離がノードｉ，ｊ間の理想距離よりも小さい場合に負の値をとり、ノードｉ，ｊ間の距離がノードｉ，ｊ間の理想距離よりも大きい場合に正の値をとる。ここで、関数ｆ＞０なので、上記式（７）で定義される力はノードｉ，ｊ間の距離がノードｉ，ｊ間の理想距離よりも小さい場合に斥力となり、ノードｉ，ｊ間の距離がノードｉ，ｊ間の理想距離よりも大きいときには引力となる。
【００６６】
なお、上述の説明では、関数ｆ（Ｉij）として常に正の値をとる適当な関数を選択したが、非常に小さな範囲で負の値をとるような関数でもよい。また、上記式（７）におけるｆ（Ｉij）として適当な関数を定義することにより、ノード間のグラフ理論上の距離が離れるにつれてノード間に働く力Ｆをより小さくすることができる。これにより、グラフ図形全体でのノード間に働く力Ｆの平衡に配慮しつつ、局所的なノード間に働く力Ｆが平衡なグラフ図形配置を行うことができる。
【００６７】
また、グラフ図形配置部４にはノード間のグラフ理論上の距離を表す関数ｆ（Ｉij）が下記式（８）のように定義される。ここで、Ｋ3，Ｋ4は適当な正の定数である。ｄijはグラフ図形上のノードｉ，ｊ間の実際の距離である。
【数８】
0004566928.tif 000009
【００６８】
上記式（８）により、関数ｆ（Ｉij）は、ｄij＜Ｒi＋Ｒjの関係が成り立つ場合、ノードｉ，ｊ間の距離ｄijについての減少関数となり、ノード間が接近し過ぎるのを防ぐことができる。また、ｄij≧Ｒi＋Ｒjの場合には、関数ｆ（Ｉij）は、ノード間のグラフ理論上の距離Ｉijについての減少関数となり、ノード間のグラフ理論上の距離が離れるにつれて、ノード間の実際の距離とノード間の理想距離との誤差（ノード間の実際の距離とノード間の理想距離との相関を表す関数値）の大きさに対して相対的にノード間に働く力を小さくすることができる。これにより、グラフ図形全体でのノード間に働く力Ｆの平衡に配慮しつつ、局所的なノード間に働く力Ｆが平衡なグラフ図形配置を行うことができる。
【００６９】
なお、本発明は、ノード間の力の定義として上記式（７）、（８）に限るものではなく、ノード間のグラフ理論上の距離が離れるにつれてその大きさが適切な程度で小さくなるような（減少傾向にあるような）関数であればよい。上述したように、本実施の形態２のグラフ図形配置法では、上記式（７）で定義されるノード間に働く力が平衡状態になるようにノードの配置を逐次的に変えていく。
【００７０】
次にグラフ図形配置部４によるグラフ図形の配置処理について説明する。
図７は、実施の形態２のグラフ図形配置部によるグラフ図形配置の流れを示すフローチャートであり、この図及び図１を用いて説明する。
先ず、グラフ図形配置部４は、グラフデータ記憶部７からグラフ図形のデータを取り出す（ステップＳＴ１ｃ）。続いて、グラフ図形配置部４は、グラフ図形中の連結成分毎にステップＳＴ２ｃ以降の処理を行う。ステップＳＴ２ｃにおいて、グラフ図形配置部４は、上記実施の形態１で図２を用いて説明した流れでグラフ図形データから多重枝、自己閉路を探索して取り除く。
【００７１】
グラフ図形配置部４は、ある連結成分についてステップＳＴ２ｃの処理を実行すると、ループ用のカウンタであるｃｏｕｎｔの値を０に初期化する（ステップＳＴ３ｃ）。この後、グラフ図形配置部４は、例えば上記式（６）のような１つのアークで結ばれるノード間の理想的な距離をノードの状態によって決定する関数の算定式を用いて、各ノード間の理想距離を算出する（ステップＳＴ４ｃ）。
【００７２】
各ノード間の理想距離を算出すると、グラフ図形配置部４は、例えば上記式（７）で定義されるノードｉ，ｊ間に働く力Ｆijの値が予め設定した基準値より小さくなった、又は、ｃｏｕｎｔの値が設定値より大きくなったかのいずれかの条件を満たすか否かにより、グラフ図形自動配置アルゴリズムの終了を判定する（ステップＳＴ５ｃ）。ここで、上記いずれかの条件を満たし、グラフ図形の配置が決定されたと判断される場合、グラフ図形配置部４は、配置決定したグラフ図形データをグラフデータ記憶部７へ記憶する（ステップＳＴ６ｃ）。
【００７３】
一方、上記条件のいずれも満たさない場合、グラフ図形配置部４は、ｃｏｕｎｔの値を１だけ増やし（ステップＳＴ７ｃ）、上記式（７）による評価関数Ｆの値が小さくなるようにノードの位置を変更する（ステップＳＴ８ｃ）。また、グラフ図形配置部４は、配置を決定したグラフ図形を逐次描画するか否かを設定する逐次描画フラグを有し、この逐次描画フラグがオンかオフであるかによって、ステップＳＴ８ｃにおいてノードを移動したグラフ図形を逐次描画するか否かが判断される（ステップＳＴ９ｃ）。
【００７４】
ステップＳＴ９ｃにおいて逐次描画フラグがオンであれば、グラフ図形配置部４は、ｃｏｕｎｔの値が描画条件を満たすかを判断する（ステップＳＴ１０ｃ）。例えば、ｃｏｕｎｔの値によるループを何回行う毎にグラフ図形を描画するのかを示す値Ｃを、逐次描画する割合を決める値として予め設定する。グラフ図形配置部４は、ｃｏｕｎｔの値がＣで割り切れた場合、描画条件を満たすと判断して、ステップＳＴ１１ｃにおける描画処理に移行する。また、ｃｏｕｎｔの値がＣで割り切れなければ、描画条件を満たさないと判断して、ステップＳＴ５ｃの処理に戻る。
【００７５】
グラフ図形配置部４は、ステップＳＴ１０ｃで描画条件を満たしていると判断された場合、ステップＳＴ８ｃでノードの位置が変更されたグラフ図形のデータをグラフデータ記憶部７に記憶する。この後、管理部３は、このグラフ図形データをグラフ図形描画部６に出力する。これにより、グラフ図形描画部６は、出力装置８を構成するＬＣＤ等の表示装置において、現在表示されているグラフ図形を消去し、かわりにステップＳＴ８ｃでノードの位置が変更されたグラフ図形を表示する。このようにすることで、グラフ図形の自動配置処理によるグラフ図形の変化を適切な進度で連続的に表示することができる。
【００７６】
図８から図１０までは、実施の形態２によるグラフ図形配置処理を施したグラフ図形の描画例を示す図である。図８に示すグラフ図形は、２つの小径の円で表記されるノード（以下、小径ノードと称す）と１つの大径の円で表記されるノード（以下、大径ノードと称す）とを構成要素として含んでいる。本実施の形態では、ノード間に働く力が平衡状態になるようにノードを配置する。図８に示す例では、大径ノードと小径ノードの間で働く力は平衡状態にあることから、大径ノードと２つの小径ノードの間におけるアークの長さはそれぞれ略等しくなる。つまり、サイズが同様な２つの小径ノード間で大径ノードとの距離が異なるような不規則な配置をした場合に生じるであろう見づらさを解消することができる。
【００７７】
また、図９に示すグラフ図形は、２つの小径ノードと２つの大径ノードを構成要素として含んでいる。図９の例においてもノード間に働く力が平衡状態になるように配置する。このように配置することで、図９に示すように、例えば１つの小径ノードと２つの大径ノードとの間を接続する場合において１つの小径ノードと２つの大径ノードをそれぞれ接続するアークの長さが略等しい配置となる。また、大径ノード間のアークを対称線として小径ノードが線対称に配置される。これにより、見やすいグラフ図形の描画を実現できる。
【００７８】
図１０に示すグラフ図形は、３つの小径ノードと１つの大径ノードとを構成要素として含んでいる。図１０の例においてもノード間に働く力が平衡状態になるように配置する。このように配置することで、図１０に示すように、例えば３つの小径ノード間で大径ノードと接続する各アークの長さは略等しい配置になる。また、互いに接続する小径ノードに対し、大径ノード以外に接続を持たない小径ノードが大径ノードを介していずれかの小径ノードに偏ることなく配置される。これにより、アーク長さのばらつき等に起因するノードの重なり等を防ぐことができ、見やすいグラフ図形の描画を実現できる。
【００７９】
以上のように、この実施の形態２によれば、グラフ図形配置部４が、ノード間の距離の設定目標値と、対応する実際のノード間距離との差に基づいてノード間に働く力を定義し、図形配置の対象となるノード間に働く力が平面配置上でバランスするようにノード配置の変更を逐次的に行うことにより、グラフ図形構造の特徴に応じてグラフ図形を配置することができ、見やすいグラフ図形を得ることができる。
【００８０】
また、上記実施の形態２によれば、評価関数Ｆの値に対するノード間の距離の設定目標値と、対応する実際のノード間距離との相関の寄与率を、ノード間の距離の設定目標値又はノード間のグラフ理論上の距離又はノード間距離についての減少傾向にあるような関数を評価関数とするので、グラフ図形全体でのノード間に働く力Ｆの平衡に配慮しつつ、局所的なノード間に働く力Ｆが平衡なグラフ図形配置を行うことができる。
【００８１】
さらに、この実施の形態２によれば、評価関数Ｆijの値に対するノードｉ，ｊ間の理想距離ｅijと実際のノードｉ，ｊ間の距離ｄijとの相関の寄与率ｆ（Ｉij）を、実際のノードｉ，ｊ間の距離ｄij又はノードｉ，ｊ間のグラフ理論上の距離Ｉijのいずれかに関して減少傾向がある関数とするので、ノードｉ，ｊ間のグラフ理論上の距離Ｉijが離れる程に、評価関数Ｆijの値に占める、理想距離ｅijと実際の距離ｄijとの相関を表す関数値（例えば、理想距離ｅijと実際の距離ｄijとの誤差）の相対的な大きさを小さくすることができ、また、ノード同士が接近しすぎて重なることを少なくすることができる。
【００８２】
実施の形態３．
本実施の形態３は、上記実施の形態１、２によるグラフ図形の配置方法をネットワーク機器監視装置に適用することにより、監視対象のネットワーク機器の接続構造をグラフ図形として描画、編集するものである。
【００８３】
図１１は、この発明の実施の形態３によるグラフ図形配置装置の構成を示すブロック図であり、本発明をネットワーク機器監視装置に適用した場合を示している。本実施の形態３によるグラフ図形配置装置は、入力装置９、ネットワーク機器監視装置１０及び出力装置１１を含んで構成される。なお、入力装置９側の機器と出力装置１１側の機器とは、一つのＣＲＴ、ＬＣＤやキーボード、ハードディスク等を共有してもよく、入力データとグラフ図形の配置とをマルチウインドウ形式で表示することも自由である。
【００８４】
また、ネットワーク機器監視装置１０は、システム管理部１２、ネットワーク機器データ管理部１３、ネットワーク機器データ出力部１４、ネットワーク機器データ処理部１５、ネットワーク機器データ記憶部１６、グラフエディタ管理部１７、グラフ図形編集部１８、グラフ図形配置部１９、グラフ図形出力部２０、グラフデータ抽出部２１、及びグラフデータ記憶部２２を備えている。ネットワーク機器監視装置１０は、例えばネットワーク機器の状態を監視する従来のネットワーク機器監視装置に対し、ネットワーク上のネットワーク機器の接続構造をグラフ図形として描画、編集する機能を追加したものである。
【００８５】
システム管理部１２は、入力装置９を介して入力された情報に従う管理情報をネットワーク機器データ管理部１３又はグラフエディタ管理部１７に出力して、ネットワーク機器データ管理部１３又はグラフエディタ管理部１７による処理を管理する。
【００８６】
ネットワーク機器データ管理部１３は、システム管理部１２からの管理情報に従い、ネットワーク機器データ処理部１５に処理を移したり、ネットワーク機器データ出力部１４に処理を移す。また、ネットワーク機器データ出力部１４は、ネットワーク機器データ管理部１３からの情報（制御情報）に従って、ネットワーク機器データ記憶部１６からのネットワーク機器データを基に出力装置１１に出力する。
【００８７】
ネットワーク機器データ処理部１５は、ネットワーク機器データ管理部１３からの情報（制御情報）に従い、ネットワーク機器データ記憶部１６に記憶されるネットワーク機器データに対し、ネットワーク機器間の接続関係の変更等の各種処理を行う。ネットワーク機器データ記憶部１６は、ネットワーク機器データを記憶する手段を備えており、ネットワーク機器データの記憶、読み出しを行う。例えば、ネットワーク機器監視装置１０に搭載されたハードディスクや記憶媒体を再生するドライブ装置等により具現化される。また、ネットワーク機器データは、ネットワーク機器に対応するシンボル画像やネットワーク機器間の接続構造を規定するデータ等を含む。
【００８８】
グラフエディタ管理部１７は、システム管理部１２からの管理情報に従い、グラフ図形編集部１８、グラフ図形配置部１９、グラフ図形出力部２０又はグラフデータ抽出部２１に処理を移す。グラフ図形編集部１８は、グラフエディタ管理部１７からの情報（制御情報）に従い、グラフ図形の編集を行う手段を備えている。編集内容は、ノードの追加、削除及び移動、アークの追加及び削除等である。
【００８９】
グラフ図形配置部１９は、グラフエディタ管理部１７からの情報（制御情報）に従い、グラフ図形を配置する手段を備えている。このグラフ図形を配置する手段としては、上記実施の形態１で説明した、予め決められたノード間の理想距離にできるだけ実際のノード間の距離が近くなるようにグラフ図形を配置する方法や、上記実施の形態２で説明したように、ノード間の距離の設定目標値と対応する実際のノード間距離との差に基づいてノード間に働く力を定義し、図形配置の対象となるノード間に働く力が平面配置上で平衡になるように配置する方法で、グラフ図形の配置を行うものが考えられる。なお、本実施の形態３では、上記実施の形態２によるグラフ図形の配置方法において、後述する関数ｆ（Ｉij）が定義される。
【００９０】
グラフ図形出力部２０は、グラフエディタ管理部１７からの情報（制御情報）に従い、グラフデータ記憶部２２に記憶されたグラフ図形データを出力装置１１に出力する。グラフデータ抽出部２１は、グラフエディタ管理部１７からの情報（制御情報）に従って、ネットワーク機器データ記憶部１６に記憶されるネットワーク機器データからネットワーク上のネットワーク機器の接続構造を規定する情報を読み出し、グラフ図形データとして抽出する。グラフデータ記憶部２２は、グラフ図形データを記憶する手段を備えており、グラフエディタ管理部１７からの情報（制御情報）に従い、グラフ図形データの記憶、読み出しを行う。例えば、ネットワーク機器監視装置１０に搭載されたハードディスクや記憶媒体を再生するドライブ装置等により具現化される。
【００９１】
なお、システム管理部１２、ネットワーク機器データ管理部１３、ネットワーク機器データ管理部１３、ネットワーク機器データ出力部１４、ネットワーク機器データ処理部１５、ネットワーク機器データ記憶部１６、グラフエディタ管理部１７、グラフ図形編集部１８、グラフ図形配置部１９、グラフ図形出力部２０、グラフデータ抽出部２１及びグラフデータ記憶部２２は、例えば、本発明の趣旨に従う処理プログラムを、ネットワーク機器監視装置１０を構成するコンピュータの演算処理装置に実行させてその動作を制御することにより、ソフトウエアとハードウエアとが協働した具体的な手段として実現することができる。
【００９２】
次に動作について説明する。
図１２は、実施の形態３のグラフ図形配置装置によるグラフ図形の配置編集処理の流れを示すフローチャートであり、この図及び図１１を用いて説明する。
グラフ図形の編集にあたり、ネットワーク機器監視装置１０は、先ず、入力装置９を構成するマウス等のポインティングデバイスによってグラフ図形編集に関するコマンド又はデータの入力待ち状態にある（ステップＳＴ１ｄ）。
【００９３】
この後、入力装置９を用いてコマンド又はデータが入力されると、システム管理部１２は、入力されたコマンド又はデータがネットワーク機器データを処理するものであるか否かを判定する（ステップＳＴ２ｄ）。ここで、ネットワーク機器データを処理するものでないと判定されると、ステップＳＴ３ｄの処理に移行し、ネットワーク機器データを処理するものであれば、ステップＳＴ７ｄの処理に移行する。
【００９４】
ステップＳＴ３ｄにおいて、システム管理部１２は、入力されたコマンド又はデータがグラフ図形の処理に関するものであるか否かを判定する。ここで、グラフ図形の処理に関するものでないと判定されると、ステップＳＴ１４ｂの処理に移行し、グラフ図形の処理に関するものであれば、ステップＳＴ４ｄの処理に移行する。
【００９５】
システム管理部１２は、入力されたコマンド又はデータがグラフ図形の処理に関するものである場合、これらコマンド又はデータがグラフ図形の自動配置に関するものであるか否かを判定する（ステップＳＴ４ｄ）。このとき、グラフ図形の自動配置に関するものでないと判定されると、ステップＳＴ５ｄの処理に移行し、グラフ図形の自動配置に関するものであれば、ステップＳＴ１１ｄの処理に移行する。
【００９６】
ステップＳＴ５ｄにおいて、システム管理部１２は、入力されたコマンド又はデータがグラフ図形の自動配置に関するものでない場合、これらコマンド又はデータがグラフ図形の編集に関するものであるか否かを判定する。このとき、グラフ図形の編集に関するものでないと判定されると、ステップＳＴ６ｄの処理に移行し、グラフ図形の編集に関するものであれば、ステップＳＴ８ｄの処理に移行する。
【００９７】
ステップＳＴ６ｄでは、システム管理部１２は、入力されたコマンド又はデータが、グラフ図形の処理に関するものであり、グラフ図形の配置及び編集以外の処理を行わせる旨のものであると判断し、これをグラフエディタ管理部１７に出力する。これにより、グラフエディタ管理部１７が、動作管理する構成部１８〜２２のいずれかに対し、グラフ図形の自動配置、グラフ図形の編集以外のグラフ図形の処理を実行させる。例えば、逐次描画フラグのオンオフの設定等を行う。この処理の後、再びステップＳＴ１ｄの処理に戻り、コマンド又はデータの入力待ち状態に移行する。
【００９８】
システム管理部１２は、ステップＳＴ２ｄにおいて、入力されたコマンド又はデータが、ネットワーク機器データの処理に関するものであると判定すると、当該コマンド又はデータをネットワーク機器データ管理部１３に出力する。
【００９９】
ネットワーク機器データ管理部１３は、システム管理部１２から入力したコマンド又はデータに従って、ネットワーク機器データの処理を管理する。この処理の内容としては、ネットワーク機器間の接続を表すリンクの作成及び削除、ネットワーク機器の追加等が考えられる。システム管理部１２からの指示が上記処理内容であると、ネットワーク機器データ管理部１３は、ネットワーク機器データ処理部１５に上記処理を実行させる（ステップＳＴ７ｄ）。
【０１００】
例えば、ネットワーク機器データ処理部１５は、ネットワーク機器データ管理部１３から入力したコマンド又はデータに従い、ネットワーク機器データ記憶部１６より読み出したネットワーク機器データに対してネットワーク機器間の接続を表すリンクを作成したり、既存のリンクを削除する処理を行い、ネットワーク機器データ記憶部１６に記憶する。
【０１０１】
システム管理部１２は、ステップＳＴ５ｄにおいて、入力されたコマンド又はデータがグラフ図形の編集に関するものであると判定すると、当該コマンド又はデータをグラフエディタ管理部１７に出力する。
【０１０２】
グラフエディタ管理部１７は、システム管理部１２から入力したコマンド又はデータに従って、グラフ図形の編集処理を管理する。この編集内容としては、ノードの追加、削除及び移動、アークの追加及び削除等が考えられる。この場合、グラフエディタ管理部１７は、システム管理部１２からの指示に従い、グラフ図形編集部１８に上記編集処理を実行させる（ステップＳＴ８ｄ）。
【０１０３】
グラフ図形編集部１８は、グラフエディタ管理部１７から入力したコマンド又はデータに従って、上記実施の形態１で示した図４と同様の流れで、グラフデータ記憶部２２より読み出したグラフ図形データに対して編集処理を行い、グラフデータ記憶部２２に記憶する。
【０１０４】
一方、ステップＳＴ９ｄにおいて、グラフエディタ管理部１７は、システム管理部１２から入力したコマンド又はデータに従って、ステップＳＴ７ｄにおいてネットワーク機器データ処理部１５がネットワーク機器データを編集し、且つ逐次描画フラグがオンであるか否かを判定する。ここで、ネットワーク機器データが編集されていないか、逐次描画フラグがオフである場合、再びステップＳＴ１ｄの処理に戻り、コマンド又はデータの入力待ち状態に移行する。
【０１０５】
また、ネットワーク機器データが編集され、且つ逐次描画フラグがオンである場合、グラフエディタ管理部１７は、グラフデータ抽出部２１を制御して、ネットワーク機器データ記憶部１６から、ネットワーク機器データ処理部１５により編集されたネットワーク機器データにおけるネットワーク機器の画像及びその接続構造に関する情報を抽出させる。
【０１０６】
グラフデータ抽出部２１は、抽出したネットワーク機器の画像やその接続構造に関する情報を、グラフ図形データとしてグラフデータ記憶部２２に記憶する。これにより、グラフ図形配置部１９が、グラフデータ抽出部２１によりグラフデータ記憶部２２に記憶されたグラフ図形データを読み出して、上記実施の形態１、２と同様な方法でグラフ図形配置処理を実行し、再びグラフデータ記憶部２２に記憶する。なお、グラフ図形配置部１９により実行されるグラフ図形の配置法は、上記実施の形態１、２に示したようにいくつかあり、必要に応じて配置法を任意の数だけ用意すればよい。
【０１０７】
この実施の形態３では、グラフ図形配置部１９が、上記実施の形態２で示したグラフ図形配置法において上記式（８）のｆ（Ｉij）を下記式（９）で表したものを使用する。ここで、Ｋ5は適当な正の定数である。また、ｅijはノードｉ，ｊ間のグラフ図形上の理想距離、Ｉijはノードｉ，ｊ間のグラフ理論上の距離とする。
【数９】
0004566928.tif 000010
【０１０８】
これにより、（ｅij＋Ｉij）が大きいほどｆ（Ｉij）は小さくなり、ノード間のグラフ理論上の距離が離れるにつれてノード間の実際の距離とノード間の理想距離との誤差の大きさに対して相対的にノード間に働く力を小さくすることができる。従って、グラフ図形の全ノード間で働く力のバランスを配慮しつつ、局所的なノード間で働く力のバランスのとれたグラフ図形の配置を行うことができる。
【０１０９】
次に、グラフ図形出力部２０が、グラフエディタ管理部１７の指示に従い、グラフ図形配置部１９により配置決定されたグラフ図形データを、グラフデータ記憶部２２から読み出して、出力装置１１を構成するＬＣＤ等の表示装置の画面に描画する（ステップＳＴ１０ｄ）。この後、再びステップＳＴ１ｄの処理に戻り、コマンド又はデータの入力待ち状態に移行する。
【０１１０】
また、ステップＳＴ４ｄにおいて、システム管理部１２が、入力されたコマンド又はデータがグラフ図形の自動配置に関するものであると判定すると、入力されたコマンド又はデータをグラフエディタ管理部１７に出力する。グラフエディタ管理部１７は、システム管理部１２から入力されたコマンド又はデータに従って、グラフ図形配置部１９を制御してグラフ図形の配置処理を実行させる（ステップＳＴ１１ｄ）。
【０１１１】
例えば、グラフ図形配置部１９は、グラフエディタ管理部１７は、システム管理部１２から入力されたコマンドが特定のグラフ図形に対する配置指示命令であった場合、該当するグラフ図形データをグラフデータ記憶部２２から読み出して、ステップＳＴ１０ｄと同様にしてグラフ図形の配置処理を行い、グラフデータ記憶部２２に再び記憶する。
【０１１２】
また、グラフエディタ管理部１７は、ステップＳＴ１２ｄにおいてグラフ図形編集部１８がグラフ図形を編集すると、逐次描画フラグがオンであるか否かを判定する。ここで、逐次描画フラグがオンであれば、グラフエディタ管理部１７は、グラフ図形配置部１９を制御して、グラフ図形編集部１８により編集されたグラフ図形データをグラフデータ記憶部２２から読み出して、ステップＳＴ１０ｄと同様にしてグラフ図形の配置処理を行い、グラフデータ記憶部２２に再び記憶する。
【０１１３】
このようにして、グラフ図形配置部１９により配置決定されたグラフ図形データは、グラフエディタ管理部１７の制御の下、グラフ図形出力部２０に読み出され、出力装置１１を構成するＬＣＤ等の表示装置の画面に描画される。なお、この描画処理後又はステップＳＴ１２ｄで逐次描画フラグがオフであった場合、再びステップＳＴ１ｄの処理に戻り、コマンド又はデータの入力待ち状態に移行する。
【０１１４】
ステップＳＴ１４ｄにおいて、システム管理部１２は、入力されたコマンド又はデータが終了処理に関するものであるか否かを判定する。ここで、入力されたコマンドが終了コマンドであり、終了処理に関するものであれば、処理を終了する。一方、入力されたコマンド又はデータが終了処理に関するものでなければ、システム管理部１２は、入力されたコマンド又はデータがネットワーク機器データの処理に関するものでなく、且つグラフ図形の処理に関するものでなく、これら以外の処理に関するものであると判定し、当該他の処理に関する動作を不図示の他の構成要素に実行させる（ステップＳＴ１３ｄ）。この処理の後、再びステップＳＴ１ｄの処理に戻り、コマンド又はデータの入力待ち状態に移行する。
【０１１５】
図１３及び図１４は、実施の形態３によるグラフ図形配置処理を施したネットワーク機器のグラフ図形の描画例を示す図である。図１３に示すネットワーク機器のグラフ図形は、サイズが同じ１１台のパーソナルコンピュータのシンボル画像からなるノード（以下、ＰＣと称す）と、ＰＣよりサイズが大きい３台のサーバのシンボル画像からなるノード（以下、サーバと称す）と、ＰＣ及びサーバよりサイズの小さい２台のルータのシンボル画像からなるノード（以下、ルータと称す）とを構成要素として含んでいる。本実施の形態においても、上記実施の形態２と同様に、ノード間に働く力が平衡状態になるようにノードを配置する。
【０１１６】
ルータと１１台のＰＣとの各接続で働く力が平衡状態にあり、各ＰＣのノードサイズは略同一である。これにより、図１３に示す例では、ルータとＰＣとの間の各アークの長さは略等しく、ルータを中心にして放射状かつ点対称に１１台のＰＣが接続する配置を含んでいる。このように配置することにより、ＰＣごとにルータとの距離が異なる場合と比較して、ルータ、ＰＣの重なりやアークの交差を等を防ぐことができ、各段に見やすいグラフ図形の描画を実現できる。
【０１１７】
また、ルータと３台のサーバとの各接続で働く力が平衡状態にあり、各サーバのノードサイズは略同一である。このように配置することにより、図１３に示すように、ルータと３つのサーバの各接続に対応するアークの長さはそれぞれ等しくなる。つまり、サーバ毎にルータとの間の距離が異なることに起因するグラフ図形の見づらさを解消できる。
【０１１８】
図１４に示すネットワーク機器のグラフ図形は、サイズの同じシンボル画像のノードである９台のＰＣと、ＰＣよりサイズが大きいシンボル画像のノードであるシンボル画像である３台のサーバと、ＰＣ及びサーバよりサイズの小さいノードに該当するシンボル画像である２台のルータと、サイズがルータより大きくＰＣより小さいシンボル画像のノードであるハブと、ＰＣと同程度の大きさのシンボル画像であるノードとを構成要素として含んでいる。
【０１１９】
図１４に示す例では、図中手前のハブと４台のＰＣとの接続に働く力は平衡状態であることから、ハブと各ＰＣ間のアークの長さが略等しい配置になる。また、当該ハブに接続するルータにそれぞれ接続する３台のＰＣも、ルータとの接続に働く力は平衡状態であるので、ルータと３台の各ＰＣ間のアークの長さが略等しくなる。さらに、このルータに逐次接続するルータには２台のＰＣが同様に接続しており、ルータとＰＣとの間におけるアークの長さは略等しい配置となる。このように配置することで、ハブやルータ、ＰＣ毎にの間の距離が異なる場合に比べて、ハブ、ルータ、ＰＣの重なり等を防ぐことができる。これにより、見やすいグラフ図形の描画を実現できる。
【０１２０】
なお、図１３及び図１４におけるノード（各ネットワーク機器のシンボル画像）にネットワーク機器名やアークにリンクの情報等を表示すると、より一層わかりやすい図解となる。
【０１２１】
以上のように、この実施の形態３によれば、ネットワーク機器監視装置１０におけるグラフ図形配置部１９が、監視対象のネットワーク機器をノードとするグラフ図形の配置にあたり、ノード間の距離の設定目標値と、対応する実際のノード間距離との差に基づいてノード間に働く力を定義し、図形配置の対象となるノード間に働く力が平面配置上でバランスするようにノード配置の変更を逐次的に行うことにより、ネットワーク上のネットワーク機器の接続構造が視認し易い、配置を実現することができる。
【０１２２】
また、上記実施の形態３によれば、評価関数Ｆの値に対するノード間の距離の設定目標値と、対応する実際のノード間距離との相関の寄与率を、ノード間の距離の設定目標値又はノード間のグラフ理論上の距離又はノード間距離についての減少傾向にあるような関数を評価関数とするので、ネットワーク上のネットワーク機器間の接続に働く力Ｆの平衡に配慮しつつ、局所的なネットワーク機器間の接続に働く力Ｆが平衡なグラフ図形配置を行うことができる。
【０１２３】
さらに、この実施の形態３によれば、評価関数Ｆijの値に対するノードｉ，ｊ間の理想距離ｅijと実際のノードｉ，ｊ間の距離ｄijとの相関の寄与率ｆ（Ｉij）を、ノードｉ，ｊ間のグラフ理論上の距離Ｉij及びノードｉ，ｊ間の理想距離ｅijに関して減少傾向がある関数としたので、ノードｉ，ｊ間のグラフ理論上の距離Ｉijが離れる程に、評価関数Ｆijの値に占める、理想距離ｅijと実際の距離ｄijとの相関を表す関数値（例えば、理想距離ｅijと実際の距離ｄijとの誤差）の相対的な大きさを小さくすることができ、また、ノード同士が接近しすぎて重なることを少なくすることができる。
【０１２４】
実施の形態４．
本実施の形態４は、上記実施の形態１、２によるグラフ図形の配置方法をコミュニティＷｅｂサイト（Social Network Service）のサーバ装置に適用することにより、当該サイトを利用するユーザの端末を交友関係等の所定の関係に対応付けてグラフ図形として配置、描画するものである。
【０１２５】
実施の形態４によるサーバ装置は、上記実施の形態１の図１で示したグラフ図形配置装置の構成を含み、グラフ図形配置部４が上記実施の形態１、上記実施の形態２又は上記実施の形態３のいずれかに示したグラフ図形の配置処理を実行する。また、グラフ図形描画部６が、グラフ図形配置部４により配置決定されたグラフ図形データをＷｅｂ用のデータに変換する機能を有する。さらに、グラフデータ記憶部７は、コミュニティＷｅｂサイトを利用する各ユーザに対応付けたシンボル画像及びその交友関係等のシンボル画像間の接続を規定する所定の関係が記述されたグラフ図形データを記憶している。
【０１２６】
このグラフ図形配置部４やグラフ図形描画部６を含む上記実施の形態１、上記実施の形態２又は上記実施の形態３のいずれかに示したグラフ図形の配置、描画、編集に必要な構成要素は、例えば、本発明の趣旨に従うコミュニティＷｅｂサイトの交友関係表示プログラムを、実施の形態４によるサーバ装置を構成するコンピュータの演算処理装置に実行させてその動作を制御することにより、ソフトウエアとハードウエアとが協働した具体的な手段として実現することができる。
【０１２７】
次に動作について説明する。
図１５は、この発明の実施の形態４によるサーバ装置を実現するコミュニティＷｅｂサイトの交友関係表示プログラムの各処理モジュールを示す図であり、この図と図１を用いて詳細を説明する。
【０１２８】
処理モジュールＡは、コミュニティＷｅｂサイトを管理するサーバ装置であるコンピュータに実行されることにより、図１中の管理部３、グラフ図形配置部４及びグラフデータ記憶部７における、グラフデータを抽出する処理を具現化する。例えば、ユーザ端末からの交友関係表示要求を入力装置１等を介して管理部３が入力すると、管理部３は、入力された要求に応じて、グラフ図形配置部４に処理を移行する。グラフ図形配置部４では、管理部３による制御の下、要求に応じたユーザのシンボル画像及びその交友関係に関係するシンボル画像間の接続構造を規定するグラフ図形データをグラフデータ記憶部７から抽出する。
【０１２９】
次に、処理モジュールＢを、当該コミュニティＷｅｂサイトを管理するサーバ装置であるコンピュータが実行することにより、図１中の管理部３、グラフ図形配置部４及びグラフデータ記憶部７における、グラフ図形の配置処理が具現化される。例えば、上述のようにして、グラフデータ記憶部７から抽出したグラフ図形データを用い、グラフ図形配置部４が、管理部３による制御の下、上記実施の形態１、上記実施の形態２又は上記実施の形態３のいずれかに示したグラフ図形の配置処理を実行し、交友関係に応じた接続関係でユーザのシンボル画像であるノードの配置を自動的に決定する。グラフ図形配置部４により配置決定されたグラフ図形データは、グラフデータ記憶部７に記憶される。
【０１３０】
これに続いて、処理モジュールＣを、当該コミュニティＷｅｂサイトを管理するサーバ装置であるコンピュータが実行することにより、図１中の管理部３、グラフ図形描画部６及びグラフデータ記憶部７における、グラフ図形の描画処理が具現化される。例えば、グラフ図形描画部６が、上述のようにして配置決定されたグラフ図形データをグラフデータ記憶部７から読み出して、Ｗｅｂブラウザで表示可能なデータ形式に変換する。例えば、既存のマークアップ言語等に変換することが考えられる。
【０１３１】
この変換後のグラフ図形データを、出力装置８等を介して要求元のユーザ端末にダウンロードすることにより、ユーザ端末のＷｅｂブラウザにおいて当該コミュニティＷｅｂサイトの交友関係が表示される。この場合、上記実施の形態１、上記実施の形態２又は上記実施の形態３のいずれかに示したグラフ図形の配置処理によるため、各ユーザを示すノード間のアークの交差がなく、ノード同士の重なりもない見やすい表示が実現される。
【０１３２】
図１６は、実施の形態４によるグラフ図形配置処理を施したユーザ交友関係の描画例を示す図である。図１６に示す例では、同じ大きさのシンボル画像をユーザに対応するノードとし、各ユーザ間のアークは交友関係を示している。図１６に示すように、「Ａさん」、「Ｔさん」、「Ｘさん」のノードは、自ノードにのみ接続するノード間が重ならない程度の長さのアークによりそれぞれ接続されている。
【０１３３】
「Ｔさん」を示すノードにのみ接続する、「Ｆさん」、「Ｇさん」、「Ｈさん」、「Ｉさん」、「Ｊさん」、「Ｋさん」、「Ｕさん」、「Ｖさん」、「Ｗさん」は、それぞれ同じ長さのアークにより「Ｔさん」のノードを中心として放射状に接続して略点対称に配置されている。
また、「Ａさん」のノードにのみ接続する、「Ｂさん」、「Ｄさん」、「Ｅさん」はそれぞれ同じ長さのアークにより「Ａさん」のノードを中心に放射状に接続しているが、「Ｈさん」のノードに近い「Ｃさん」のノードについては、「Ｂさん」、「Ｄさん」、「Ｅさん」より短いアークで「Ａさん」に接続している。
さらに、「Ｘさん」のノードにのみ接続する、「Ｌさん」、「Ｙさん」はそれぞれ同じ長さのアークにより「Ｔさん」のノードを中心に放射状に接続しているが、「Ｗさん」のノードに近い「Ｚさん」のノードについては、「Ｌさん」、「Ｙさん」より短いアークで「Ｘさん」に接続している。
【０１３４】
本発明によるグラフ図形配置部は、アーク両端の各ノードに接続されるノードの大きさに関して増加傾向を示す算定式を用いて、各ノード間の距離の設定目標値を算出し、算出されたノード間距離の設定目標値に基づいて、各ノードの配置を非階層的に決定する。このため、図１６に示すように、ノードの大きさにかかわらずアークの交差やノードの重なりをできるだけ防ぐことができ、見やすいグラフ図形の描画を実現することができる。
【０１３５】
また、グラフ図形から複数のアークを介して接続される２つのノード間を多重枝として取り除き、これらノード間の距離について設定目標値を算出するので、図１６に示すように、各ユーザのノード全体としてバランスのとれた配置がなされ、見やすい交友関係表示を実現することができる。
【０１３６】
さらに、ノード間の距離の設定目標値と、対応する実際のノード間距離との相関を表す関数値の、配置対象のグラフ図形における全てのノードについての和を評価関数として定義し、この評価関数の値が平面配置上で小さくなるようにノード配置の変更を逐次的に行うことにより、各ユーザのノードとその交友関係に応じた接続構造の特徴に応じた配置を実現することができる。
【０１３７】
また、上記実施の形態２、３のように、評価関数Ｆの値に対するノード間の距離の設定目標値と、対応する実際のノード間距離との相関の寄与率を、ノード間の距離の設定目標値又はノード間のグラフ理論上の距離又はノード間距離についての減少傾向にあるような関数を評価関数とすれば、交友関係表示するユーザ全体の各接続に働く力Ｆの平衡に配慮しつつ、ユーザを示すノード間の局所的な接続に働く力Ｆが平衡なノード配置を行うことができる。
【０１３８】
上述のような配置方法により、例えば「Ａさん」のノードにのみ接続する、「Ｂさん」、「Ｄさん」、「Ｅさん」はそれぞれ同じ長さのアークで「Ａさん」に接続するが、「Ｈさん」のノードに近い「Ｃさん」のノードについては、互いに重ならないように「Ｂさん」、「Ｄさん」、「Ｅさん」より短いアークで「Ａさん」に接続するように配置される。
【０１３９】
なお、図１６に示すように、ユーザを表すノードに各ユーザ名を表記するようにしてもよく、各ノードに用いるシンボル画像として個人のホームページの画像イメージを使用するようにしても良い。これにより、コミュニティＷｅｂサイトの交友関係をわかりやすく、視覚的に表現することができる。
【０１４０】
以上のように、この実施の形態４によれば、コミュニティＷｅｂサイトを管理するサーバ装置におけるグラフ図形配置部が、コミュニティＷｅｂサイトのユーザをノードとするグラフ図形の配置にあたり、グラフ図形中のアーク両端の各ノードに接続されるノードの大きさと相関を規定する算定式、特にアーク両端の各ノードに接続されるノードの大きさに関して増加傾向を示す算定式を用いて各ノード間の距離の設定目標値を算出し、算出されたノード間距離の設定目標値に基づいて、各ノードの配置を非階層的に決定するので、各ユーザに該当するノードの大きさに応じてグラフ図形が配置され、アークの交差やノードの重なりが少ない態様でユーザの交友関係を表示することができる。
【０１４１】
また、上記実施の形態４によれば、コミュニティＷｅｂサイトのユーザをノードとするグラフ図形の配置にあたり、評価関数Ｆの値に対するノード間の距離の設定目標値と、対応する実際のノード間距離との相関の寄与率を、ノード間の距離の設定目標値又はノード間のグラフ理論上の距離又はノード間距離についての減少傾向にあるような関数を評価関数とすることで、コミュニティＷｅｂサイトのユーザを表すノード間に働く力Ｆの平衡に配慮しつつ、局所的なノード間に働く力Ｆが平衡なグラフ図形配置が行われ、見やすい交友関係表示を実現できる。
【０１４２】
さらに、上記実施の形態４によれば、コミュニティＷｅｂサイトのユーザをノードとするグラフ図形の配置にあたり、ノード間の距離の設定目標値と、対応する実際のノード間距離との相関を表す関数値の、配置対象のグラフ図形における全てのノードについての和を評価関数として定義し、この評価関数の値が平面配置上で小さくなるようにノード配置の変更を逐次的に行うので、ユーザ間の交友関係等の所定のノード間の関係に基づく接続構造の特徴に応じてグラフ図形が配置され、見やすい交友関係表示を実現できる。
【図面の簡単な説明】
【０１４３】
【図１】この発明の実施の形態１によるグラフ図形配置装置の構成を示すブロック図である。
【図２】実施の形態１のグラフ図形処理装置によるグラフ図形中の多重枝、自己閉路を取り除く処理の流れを示すフローチャートである。
【図３】実施の形態１のグラフ図形配置部によるグラフ図形配置の流れを示すフローチャートである。
【図４】実施の形態１のグラフ図形配置装置によるグラフ図形編集処理の流れを示すフローチャートである。
【図５】グラフ図形の描画例を示す図である。
【図６】グラフ図形の描画の他例を示す図である。
【図７】実施の形態２のグラフ図形配置部によるグラフ図形配置の流れを示すフローチャートである。
【図８】実施の形態２によるグラフ図形配置処理を施したグラフ図形の描画例を示す図である。
【図９】実施の形態２によるグラフ図形配置処理を施したグラフ図形の描画例を示す図である。
【図１０】実施の形態２によるグラフ図形配置処理を施したグラフ図形の描画例を示す図である。
【図１１】この発明の実施の形態３によるグラフ図形配置装置の構成を示すブロック図である。
【図１２】実施の形態３のグラフ図形配置装置によるグラフ図形の配置編集処理の流れを示すフローチャートである。
【図１３】実施の形態３によるグラフ図形配置処理を施したネットワーク機器のグラフ図形の描画例を示す図である。
【図１４】実施の形態３によるグラフ図形配置処理を施したネットワーク機器のグラフ図形の描画例を示す図である。
【図１５】この発明の実施の形態４によるサーバ装置を実現するコミュニティＷｅｂサイトの交友関係表示プログラムの各処理モジュールを示す図である。
【図１６】実施の形態４によるグラフ図形配置処理を施したユーザ交友関係の描画例を示す図である。
【符号の説明】
【０１４４】
１，９  入力装置、２  処理装置、３  管理部、４，１９  グラフ図形配置部、５，１８  グラフ図形編集部、６  グラフ図形描画部、７，２２  グラフデータ記憶部、８，１１  出力装置、１０  ネットワーク機器監視装置、１２  システム管理部、１３  ネットワーク機器データ管理部、１４  ネットワーク機器データ出力部、１５  ネットワーク機器データ処理部、１６  ネットワーク機器データ記憶部、１７  グラフエディタ管理部、２０  グラフ図形出力部、２１  グラフデータ抽出部。
【図１】
0004566928.tif 000011
【図２】
0004566928.tif 000012
【図３】
0004566928.tif 000013
【図４】
0004566928.tif 000014
【図５】
0004566928.tif 000015
【図６】
0004566928.tif 000016
【図７】
0004566928.tif 000017
【図８】
0004566928.tif 000018
【図９】
0004566928.tif 000019
【図１０】
0004566928.tif 000020
【図１１】
0004566928.tif 000021
【図１２】
0004566928.tif 000022
【図１３】
0004566928.tif 000023
【図１４】
0004566928.tif 000024
【図１５】
0004566928.tif 000025
【図１６】
0004566928.tif 000026