(57)【特許請求の範囲】
【請求項１】
階層型グラフデータに基づいて、所定の階層におけるノードと当該ノード間を接続するアークとを含むグラフィックス・イメージであるサブグラフを生成するサブグラフ生成部と、
前記サブグラフ生成部が既に生成されているサブグラフにおける所定のノードの下位階層のサブグラフを生成した場合に、当該既に生成されているサブグラフにおけるノードの位置を修正するサブグラフ修正部とを備え、
前記サブグラフ修正部は、新たに生成された前記下位階層のサブグラフに対応する前記ノードのサイズを変更して当該下位階層のサブグラフを包含させ、前記既に生成されているサブグラフにおける他のノードの位置をサイズ変更した前記ノードから遠ざけるように移動させることを特徴とするグラフィックス・イメージ作成装置。
【請求項２】
前記サブグラフ修正部は、サイズ変更した前記ノードと当該ノードに近接する他のノードとの間に局所的に力学モデルを適用して各ノードを再配置することを特徴とする請求項１に記載のグラフィックス・イメージ作成装置。
【請求項３】
グラフデータに基づいてノードと当該ノード間を接続するアークとを含むグラフィックス・イメージを生成する処理部と、
前記処理部にて生成されたグラフィックス・イメージを表示する表示部とを備え、
前記処理部は、階層型グラフデータの所定の階層におけるグラフィックス・イメージであるサブグラフを生成した場合に、当該サブグラフに対応するノードのサイズを変更して当該サブグラフを包含させ、サイズ変更した当該ノードの近隣のノードを移動させることを特徴とするグラフィックス・イメージ作成装置。
【請求項４】
前記処理部は、前記表示部に表示されるディスプレイ空間における前記サブグラフの占有面積を前記サブグラフに対応する前記ノードのサイズとすることを特徴とする請求項３に記載のグラフィックス・イメージ作成装置。
【請求項５】
前記処理部は、所定の階層のサブグラフが修正された場合に、修正後の当該サブグラフに対応して前記ノードのサイズを変更し、サイズ変更した当該ノードの近隣のノードを当該サブグラフと干渉しないように移動させることを特徴とする請求項３に記載のグラフィックス・イメージ作成装置。
【請求項６】
前記表示部は、前記処理部にて生成されたグラフィックス・イメージが階層構造を持つ場合に、任意の階層を表示画面に対応させた透視投影により表示することを特徴とする請求項３に記載のグラフィックス・イメージ作成装置。
【請求項７】
グラフデータに基づいてノードと当該ノード間を接続するアークとを含むグラフィックス・イメージを生成する処理部と、
前記処理部にて生成された第１のグラフィックス・イメージを構成するノードの選択を受け付けるノード選択受付部とを備え、
前記処理部は、前記ノード選択受付部にて選択を受け付けたノードに下位階層のグラフデータが存在する場合に、当該下位階層のグラフデータに基づく第２のグラフィックス・イメージを生成すると共に、前記第１のグラフィックス・イメージを構成するノードのうち当該下位階層のグラフデータに対応するノードのサイズを変更して当該第２のグラフィックス・イメージを包含させ、サイズ変更した当該ノードの近隣のノードを移動させることを特徴とするグラフィックス・イメージ作成装置。
【請求項８】
グラフデータに基づいてノードと当該ノード間を接続するアークとを含むグラフィックス・イメージを生成する処理部と、
前記処理部にて生成されたグラフィックス・イメージを構成するノードの選択を受け付けるノード選択受付部とを備え、
前記処理部は、前記グラフィックス・イメージが表示されるディスプレイ空間において、前記ノード選択受付部にて選択を受け付けたノードの座標値を中心点として、表示されている他のノードを中心点から離れる方向に移動することを特徴とするグラフィックス・イメージ作成装置。
【請求項９】
前記処理部は、前記ノード選択受付部にて選択を受け付けたノードからの距離及び前記グラフィックス・イメージの階層構造に基づいて前記ノードの移動距離を決定することを特徴とする請求項８に記載のグラフィックス・イメージ作成装置。
【請求項１０】
記憶装置から読み出されたグラフデータをデータ処理装置に入力して当該グラフデータに基づくグラフィックス・イメージを生成するグラフィックス・イメージ作成方法において、
前記グラフデータに基づいてグラフィックス・イメージを生成するステップと、
新たに生成されたグラフィックス・イメージが既に生成されている既存のグラフィックス・イメージの一部であり、当該既存のグラフィックス・イメージにおける所定のノードに対応づけられている場合に、当該既存のグラフィックス・イメージにおける当該新たに生成されたグラフィックス・イメージに対応するノードのサイズを変更して当該新たに生成されたグラフィックス・イメージを包含させるステップと、
前記既存のグラフィックス・イメージにおけるサイズ変更した前記ノード以外のノードの位置を、サイズ変更した前記ノードから遠ざけるように移動させるステップと
を含むことを特徴とするグラフィックス・イメージ作成方法。
【請求項１１】
記憶装置から読み出された階層型グラフデータをデータ処理装置に入力して当該階層型グラフデータに基づくグラフィックス・イメージを生成するグラフィックス・イメージ作成方法において、
前記階層型グラフデータにおける所定の階層のグラフィックス・イメージであるサブグラフを生成するステップと、
前記サブグラフにおける所定のノードに対する下位階層のサブグラフを生成するステップと、
前記下位階層のサブグラフが生成された前記ノードのサイズを、当該下位階層のサブグラフを包含するように変更するステップと、
前記サイズ変更したノードの近隣の他のノードを移動するステップとを含むことを特徴とするグラフィックス・イメージ作成方法。
【請求項１２】
記憶装置から読み出された階層型グラフデータをデータ処理装置に入力して当該階層型グラフデータに基づくグラフィックス・イメージを生成するグラフィックス・イメージ作成方法において、
表示装置に表示されたグラフィックス・イメージを構成する任意のノードの選択を受け付けるステップと、
選択された前記ノードの下位階層のグラフィックス・イメージを生成するステップと、
選択された前記ノードのサイズを、前記下位階層のグラフィックス・イメージを包含するように変更するステップと、
サイズ変更した前記ノードの近隣の他のノードを移動するステップとを含むことを特徴とするグラフィックス・イメージ作成方法。
【請求項１３】
記憶装置から読み出された階層型グラフデータをデータ処理装置に入力して当該階層型グラフデータに基づくグラフィックス・イメージを生成するグラフィックス・イメージ作成方法において、
表示装置に表示されたグラフィックス・イメージを構成する任意のノードの選択を受け付けるステップと、
選択された前記ノードの座標値を中心点として、表示されている他のノードを中心点から離れる方向に移動するステップとを含むことを特徴とするグラフィックス・イメージ作成方法。
【請求項１４】
コンピュータを制御して、ノードと当該ノード間を接続するアークとを含むグラフィックス・イメージを生成するプログラムであって、
記憶装置から読み出されたグラフデータに基づいてグラフィックス・イメージを生成する処理と、
新たに生成されたグラフィックス・イメージが既に生成されている既存のグラフィックス・イメージの一部であり、当該既存のグラフィックス・イメージにおける所定のノードに対応づけられている場合に、当該既存のグラフィックス・イメージにおける当該新たに生成されたグラフィックス・イメージに対応するノードのサイズを変更して当該新たに生成されたグラフィックス・イメージを包含させる処理と、
前記既存のグラフィックス・イメージにおけるサイズ変更した前記ノード以外のノードの位置を、サイズ変更した前記ノードから遠ざけるように移動させる処理と
を前記コンピュータに実行させることを特徴とするプログラム。
【請求項１５】
コンピュータを制御して、ノードと当該ノード間を接続するアークとを含むグラフィックス・イメージを生成するプログラムであって、
記憶装置から読み出された階層型グラフデータにおける所定の階層のグラフィックス・イメージであるサブグラフを生成する処理と、
前記サブグラフにおける所定のノードに対する下位階層のサブグラフを生成する処理と、
前記下位階層のサブグラフが生成された前記ノードのサイズを、当該下位階層のサブグラフを包含するように変更する処理と、
前記サイズ変更したノードの近隣の他のノードを移動する処理と
を前記コンピュータに実現させることを特徴とするプログラム。
【請求項１６】
コンピュータを制御して、ノードと当該ノード間を接続するアークとを含むグラフィックス・イメージを生成するプログラムであって、
表示装置に表示されたグラフィックス・イメージを構成する任意のノードの選択を受け付ける処理と、
選択された前記ノードの下位階層のグラフィックス・イメージを生成する処理と、
選択された前記ノードのサイズを、下位階層のグラフィックス・イメージを包含するように変更する処理と、
サイズ変更した前記ノードの近隣の他のノードを移動する処理と
を前記コンピュータに実行させることを特徴とするプログラム。
【請求項１７】
コンピュータを制御して、ノードと当該ノード間を接続するアークとを含むグラフィックス・イメージを生成するプログラムであって、
表示装置に表示されたグラフィックス・イメージを構成する任意のノードの選択を受け付ける処理と、
選択された前記ノードの座標値を中心点として、表示されている他のノードを中心点から離れる方向に移動する処理とを前記コンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ノードとノード間をつなぐアークとで構成されるグラフデータを視覚化するグラフィックス表示技術に関する。
【０００２】
【従来の技術】
組織全体を構成する要素の関係を示すグラフデータに関して、当該要素を示すノードとノード間をつなぐアークとで表すことにより視覚化することができる。このグラフデータを視覚化するグラフィックス表示は、ウェブページのリンク構造の表示、金融・通信・交通・社会組織などのネットワークの表示、化学・生物などのデータをグラフ化したものの表示、テキストデータや画像データを関連性で連結してできるグラフの表示、いくつかの関連あるモジュールの組み合わせで構成されるシステムの振舞いを表したグラフの表示（例えば並列計算機のプロセス）などのように、種々の用途が考えられる。そのため、コンピュータを用いたグラフデータのグラフィックス表示技術は、非常に幅広い分野で需要のある必要とされている。
【０００３】
これら、グラフデータの表示技術を必要とする分野では、データの大規模化が急速に進んでおり、数千、数万、それ以上のノード数を持つグラフデータが扱われる場合も生じている。しかし、限られたディスプレイ空間の中で、これらのノードを全て表示することは困難であり、また、表示したとしても、ノードやアークが込み入って相互関係を把握しにくく非現実的である。
このような大規模なグラフデータをグラフィックス表示するには、このグラフデータの構造的な関係に基づいて、グラフを構成するノードのいくつかをまとめてグループを作成し、さらにいくつかのグループをまとめて大きなグループを作成するというように階層化する技術が有用である。
【０００４】
グラフデータの階層化とは、
（１）グラフを構成するノード数個を１個のグループにまとめ、
（２）グループ内で１個のサブグラフを構成する、
という処理の反復によって、グラフデータ内部にいくつかのグループ（及びグループ内部に構成されるサブグラフ）を作成することである。このとき、各サブグラフを「下位階層のサブグラフ」と呼び、グループ間の接続関係をグラフ化したものを「上位階層のサブグラフ」と呼ぶ。上位階層のサブグラフを構成するグループ数個をさらに１個のグループにまとめる処理を反復することで、３階層以上で構成されるグラフをつくることもできる。図２７は、２３個のノードから構成されるグラフを８個グループａ〜ｈに分け（図２７（Ａ））、さらに、グループａ〜ｈを３個のグループＡ〜Ｃに分けて構成された（図２７（Ｂ）、（Ｃ））、３階層の階層型グラフデータに対するグラフィックス・イメージの例である。
【０００５】
階層化されたグラフデータを効果的に視覚化するためには、次のような処理の実現が要求される。
（１）各サブグラフを構成するノードおよびアークに対して、誤読を避ける適切な自動配置。
（２）ユーザの操作に応じて動的に下位階層まで自動配置して詳細表示する処理。
（３）各ノードの階層の深さを視覚的に認識しやすくする処理。
（４）ユーザの興味のある部分を対話的に拡大表示し、かつ拡大部分と周辺部分との干渉を同時に避ける処理。
【０００６】
処理（１）、（２）に対しては、ある程度良好な解を数秒〜数十秒程度の現実的な時間で得られる手法として、力学モデルを用いた手法が有用である。すなわち、グラフのノードに分子間力モデル、グラフのアークにバネモデルを適用し、運動方程式を解くことにより、各ノードの適切な位置を算出する手法である。
階層型のグラフデータに対して、力学モデルを適用してノードの配置を決定する手法は、例えば、下記の文献１に記載されている。
文献１：A. Quigley, et al., FADE: Graph drawing, clustering, and visual abstraction, Graph Drawing 2000.
【０００７】
また、処理（３）、（４）を実現する従来の手法としては、グラフを構成する各サブグラフがｘｙ平面上に既に展開されていると仮定して、その階層ごとに異なるｚ値を与えて立体的に表示する手法がある。
図２８は、グラフの階層構造を立体的に表示した表示例を示す図である。この種の従来技術は、例えば、下記の文献２に記載されている。
文献２：P. Eades, et al., Multilevel Visualization of Clustered Graphs, Graph Drawing 1996.
(http://www.cs.newcastle.edu.au/Research/qwfeng/RESEARCH/Multilevel/Multilevel.html)
【０００８】
一方、階層を表現する木構造の視覚化技術を用いて階層型グラフデータの視覚化を実現した従来技術もある。この種の従来技術は、下記の文献３に記載されている。
文献３：Hao M. C., Hsu M., Dayal U., and Krug A., Web-based Visualization of Large Hierarchical Graphs Using Invisible Links in a Hyperbolic Space, HP Laboratories Palo Alto, HPL-2000-2.
同文献に記載された従来技術は、ルートノードを中心として放射状に枝を伸ばすグラフィックス表示手法を用いて、ノード間の階層構造を表現する。
図２９は、図２７に示した階層型グラフデータを、文献３の従来技術による手法を用いて表現した例を示す図である。
図示のように、この手法では、異なる階層に属するノード間の上下関係がアークで表現されている。そして、同一の階層に属するノード間の接続関係は表現されていない。例えば、図２７によれば、ノードａは、ノードｂ、ｃ、ｄという３個の同一階層ノードと接続されている。しかしながら、図２９では、かかる接続関係は表示されていない。なお、文献３に示す従来技術では、任意のノードを選択することにより、当該ノード自体の接続関係やその下位階層のノードを表示するといったインターフェイスが提案されている。
【０００９】
【発明が解決しようとする課題】
しかし、上述した、階層型グラフデータをグラフィックス表示する従来の技術は、次のような欠点を有している。
図２７に示したように、グループ分けされた階層ごとに表示を行う場合において、上位階層からその一部（所定のグループ）の下位階層に向かって順に表示を行う場合がある（この場合の表示を行う下位階層を注視部分と称す）。この表示処理を対話的に実現するためには、まず上位階層のサブグラフだけを自動配置し、続いて当該上位階層のサブグラフにおける注視部分のグループ内に下位階層のサブグラフを自動配置するという機能の実装が求められる。
しかし、この場合、上位階層を自動配置する時点では、下位階層の占有面積は不明なので、ノードの占有面積を一定として上位階層から順に自動配置することとなる。そのため、同一階層における各グループ内のノードの数が均一でない階層型グラフに適用した場合（すなわち、下位階層のサブグラフに粗密（ノード数の差）がある場合や階層の深さが異なる場合）、下位階層のノードどうしや下位階層と上位階層のノード間に干渉を生じるような自動配置を行ってしまう場合があった。
【００１０】
反対に、下位階層から上位階層へ順に表示を行う場合、上位階層の自動配置を行う時には当該上位階層を構成する各ノードの面積が与えられているので、上記のようにノードの干渉を生じないように配置を制御することが可能である。しかし、上位階層になるほどノードの面積が大きくなるため、自動配置に用いる力学モデルが安定しにくく、良好な配置結果が得られにくかった。
【００１１】
また、従来の階層型グラフデータのグラフィックス表示技術では、グラフ配置の決定に時間を要することから、通常、前処理的にグラフ配置を行っておき、ユーザの操作にしたがって表示していた。そのため、ユーザの操作とグラフ配置とは連動しておらず、ユーザの操作によって動的に異なる階層のグラフを配置するというような柔軟な表示を行うことができなかった。
【００１２】
さらに、従来のグラフデータのグラフィックス表示技術では、一般に、階層型グラフの立体表現には平行投影が用いられている。しかし、平行投影による視覚化では、近くの物体も遠くの物体も同じ尺度で表示するため、ユーザがアクセスしている階層の深さを体感しにくかった。
そして、注視部分を詳細に表示しようとすると、その部分を表示するために広い領域が必要となるので、限られた画面スペースの中に当該注視部分の詳細な表示とグラフデータの全体像とを同時に表示することが困難であった。
【００１３】
さらにまた、文献３に示された従来技術は、所定のノードから放射状にのびるアークによりノード間の階層の上下関係を表現することを基本としている。そして、同一階層におけるノード間の接続関係についても表示は可能であるが、これらの表示を行うと、階層の上下関係の表現が優先されるために画面が混雑してしまい、ノード間の接続関係の把握が容易とは言えなくなる。
【００１４】
そこで、本発明は、階層型グラフデータのグラフィックス表示において、グラフデータの階層構造と所望のノード間の接続関係とを同時にかつ把握しやすい形態で表示することを目的とする。
【００１５】
また、本発明は、階層型グラフデータのグラフィックス表示において、ユーザの操作に応じて動的にグラフ配置を行い、ユーザの要求に応じた柔軟なグラフィックス表示を行うことを他の目的とする。
【００１６】
【課題を解決するための手段】
上記の目的を達成する本発明は、次のように構成されたことを特徴とするグラフィックス・イメージ作成装置を提供することができる。すなわち、このグラフィックス・イメージ作成装置は、階層型グラフデータに基づいて、所定の階層におけるグラフィックス・イメージであるサブグラフを生成するサブグラフ生成部と、このサブグラフ生成部が既に生成されているサブグラフにおける所定のノードの下位階層のサブグラフを生成した場合に、この既に生成されているサブグラフにおけるノードの位置を下位階層のサブグラフとの干渉を回避するように修正するサブグラフ修正部とを備えたことを特徴とする。
【００１７】
具体的には、このサブグラフ修正部は、新たに生成された下位階層のサブグラフに対応するノードのサイズを変更してこの下位階層のサブグラフを包含させ、既に生成されているサブグラフにおける他のノードの位置をサイズ変更したノードから遠ざけるように移動させることができる。
さらにここで、このサブグラフ修正部は、サイズ変更したノードとこのノードに近接する他のノードとの間に局所的に力学モデルを適用して各ノードを再配置することができる。
【００１８】
また、本発明は、次のように構成されたことを特徴とするグラフィックス・イメージ作成装置を提供することができる。すなわち、このグラフィックス・イメージ作成装置は、グラフデータに基づいてグラフィックス・イメージを生成する処理部と、この処理部にて生成されたグラフィックス・イメージを表示する表示部とを備え、この処理部は、階層型グラフデータの所定の階層におけるグラフィックス・イメージであるサブグラフを生成した場合に、このサブグラフに対応するノードのサイズを変更してこのサブグラフを包含させ、サイズ変更したノードの近隣のノードをこのサブグラフに対する干渉を回避するように移動させることを特徴とする。
【００１９】
ここで、この処理部は、ノードサイズを変更するにあたって、表示部に表示されるディスプレイ空間におけるこのサブグラフの占有面積をこのサブグラフに対応するノードのサイズとすることができる。
また、この処理部は、所定の階層のサブグラフが修正された場合に、修正後のサブグラフに対応してノードのサイズを変更し、サイズ変更したノードの近隣のノードをこのサブグラフと干渉しないように移動させることができる。
さらにまた、この表示部は、生成されたグラフィックス・イメージが階層構造を持つ場合に、任意の階層を表示画面に対応させた透視投影により表示することができる。
【００２０】
また、本発明は、次のように構成されたことを特徴とするグラフィックス・イメージ作成装置を提供することができる。このグラフィックス・イメージ作成装置は、グラフデータに基づいてグラフィックス・イメージを生成する処理部と、この処理部にて生成された第１のグラフィックス・イメージを構成するノードの選択を受け付けるノード選択受付部とを備え、この処理部は、このノード選択受付部にて選択を受け付けたノードに下位階層のグラフデータが存在する場合に、この下位階層のグラフデータに基づく第２のグラフィックス・イメージを生成すると共に、第１のグラフィックス・イメージを第２のグラフィックス・イメージに干渉しないように修正することを特徴とする。
【００２１】
さらにまた、本発明は、上記のような処理部とノード選択受付部とを備えたグラフィックス・イメージ作成装置において、この処理部は、グラフィックス・イメージが表示されるディスプレイ空間において、このノード選択受付部にて選択を受け付けたノードの座標値を中心点として、表示されている他のノードを中心点から離れる方向に移動することを特徴とする。
ここで、この処理部は、このノード選択受付部にて選択を受け付けたノードからの距離及び生成されたグラフィックス・イメージの階層構造に基づいて前記ノードの移動距離を決定することができる。
【００２２】
また、本発明は、記憶装置から読み出されたグラフデータをデータ処理装置に入力してグラフィックス・イメージを生成するグラフィックス・イメージ作成方法において、処理対象であるグラフデータに基づいてグラフィックス・イメージを生成するステップと、新たに生成されたグラフィックス・イメージが既に生成されている既存のグラフィックス・イメージの一部であり、この既存のグラフィックス・イメージにおける所定のノードに対応づけられている場合に、この既存のグラフィックス・イメージのノードを再配置するステップとを含むことを特徴とする。
【００２３】
さらに詳しくは、このノードを再配置するステップは、新たに生成されたグラフィックス・イメージに対応するノードのサイズを変更してこの新たに生成されたグラフィックス・イメージを包含させるステップと、既存のグラフィックス・イメージにおける他のノードの位置を、サイズ変更したノードから遠ざけるように移動させるステップとを含むことを特徴とする。
【００２４】
また、本発明は、グラフィックス・イメージ作成方法において、処理対象である階層型グラフデータにおける所定の階層のグラフィックス・イメージであるサブグラフを生成するステップと、このサブグラフにおける所定のノードに対する下位階層のサブグラフを生成するステップと、この下位階層のサブグラフが生成されたノードのサイズを、この下位階層のサブグラフを包含するように変更するステップと、サイズ変更したノードの近隣の他のノードをこの下位階層のサブグラフに干渉しないように移動するステップとを含むことを特徴とする。
【００２５】
さらにまた、本発明は、グラフィックス・イメージ作成方法において、表示装置に表示されたグラフィックス・イメージを構成する任意のノードの選択を受け付けるステップと、選択されたノードの下位階層のグラフィックス・イメージを生成するステップと、選択されたノードのサイズを、この下位階層のグラフィックス・イメージを包含するように変更するステップと、サイズ変更したノードの近隣の他のノードをこの下位階層のグラフィックス・イメージに干渉しないように移動するステップとを含むことを特徴とする。
【００２６】
また、本発明は、グラフィックス・イメージ作成方法において、表示装置に表示されたグラフィックス・イメージを構成する任意のノードの選択を受け付けるステップと、選択されたノードの座標値を中心点として、表示されている他のノードを中心点から離れる方向に移動するステップとを含むことを特徴とする。
【００２７】
さらに本発明は、上述したグラフィックス・イメージ作成方法の各ステップに相当する処理をコンピュータに実行させるプログラムとして提供することができる。かかるプログラムは、磁気ディスクや光ディスク、半導体、その他の記録媒体に格納して配布したり、ネットワークに接続されたプログラム伝送装置の記憶装置に格納しこのネットワークを介して配信したりすることができる。
【００２８】
【発明の実施の形態】
以下、添付図面に示す実施の形態に基づいて、この発明を詳細に説明する。
本実施の形態は、コンピュータシステムを用いて、組織全体を構成する要素の関係を示すグラフデータを、当該要素を示すノードとノード間をつなぐアークとで表すことにより視覚化するグラフィックス表示処理を行う。
なお、以下の説明において、階層型グラフデータにおける各階層の所定グループのグラフィックス・イメージを、階層の上下を区別することなくサブグラフと称す。これは、階層型グラフデータの階層構造を何層にするかは任意であり、各階層の上下関係は他の階層との相対的な関係に過ぎないためである。また、グループについても、単に「グループ」と表記した場合は、階層構造を意識していない。特に他の階層との関係で上下関係を区別する必要がある場合は、上位階層のサブグラフ、下位階層のグループなどと記す。
【００２９】
図１は、本実施の形態によるグラフデータのグラフィックス表示を行うグラフィックス・イメージ作成装置としてのコンピュータシステムの構成を示す図である。
図１を参照すると、コンピュータシステム１０は、グラフィックス表示処理をプログラム制御により実行する処理装置（ＣＰＵ）１１と、処理装置１１を制御するプログラムを格納した主メモリ１２と、処理装置１１により生成されたグラフデータのグラフィックス・イメージを表示するディスプレイ装置１３と、処理対象であるグラフデータを格納した記憶装置１４とを備える。
なお、図１には、本実施の形態を実現するための構成のみを図示してある。実際には、図示の構成の他に、各種の命令やデータを入力するためのキーボードやマウスなどの入力装置、音声出力機構や各種の周辺機器、ネットワークに対するインタフェースなどが設けられていることは言うまでもない。
【００３０】
図２は、本実施の形態によるグラフデータのグラフィックス表示を実行するグラフィックス・イメージ作成システムの構成を説明する図である。
図２を参照すると、本実施の形態によるグラフィックス作成システムは、階層型グラフデータにおける所定のグループのグラフデータに基づいてサブグラフを生成するサブグラフ生成部２１と、所定のサブグラフが新たに生成された場合に既存のサブグラフを修正するサブグラフ修正部２２と、サブグラフ生成部２１により生成されたサブグラフを構成するノード及びアークに対する操作を受け付けるグラフ操作受付部２３と、サブグラフ生成部２１にて生成されサブグラフ修正部２２にて必要な修正を施されたサブグラフのイメージデータをディスプレイ装置１３に送り表示させる表示制御部２４とを備える。
【００３１】
図２に示した各構成要素は、図１の主メモリ１２に保持されているコンピュータプログラムにより制御された処理装置１１にて実現される仮想的なソフトウェアブロックである。処理装置１１を制御する当該コンピュータプログラムは、ＣＤ−ＲＯＭやフロッピーディスクなどの記憶媒体に格納して配布したり、ネットワークを介して伝送したりすることにより提供される。そして、当該コンピュータプログラムは、主メモリ１２にロードされて処理装置１１を制御し、図１に示したコンピュータシステム１０において図２に示した各構成要素の機能を実現する。
【００３２】
本実施の形態では、図２のように構成されたグラフィックス作成システムが、
（１）所定のサブグラフＧａを自動配置し、
（２）サブグラフＧａの占有面積を当該サブグラフＧａに対応づけられた上位階層のノードＮａに与え、
（３）ノードＮａを含む上位階層のサブグラフＧ０の配置を修正する、
という処理を反復することにより、階層型グラフデータをディスプレイ空間に自動配置する。
次に、図２の構成要素ごとに、各機能及び動作を詳細に説明する。
【００３３】
図２に示した構成において、サブグラフ生成部２１は、処理対象である階層型グラフデータを記憶装置１４から入力し、その部分データである所定の階層分のグラフデータに基づいてサブグラフ（所定のグループのグラフィックス・イメージ）を生成する。サブグラフの生成手法としては、分子間力モデルやバネモデルなどの力学モデルを用いた手法など、既知の手法を用いることができる。また、サブグラフ生成部２１にて生成されるサブグラフ自体は、特定の階層に関するグラフィックス・イメージであるので、階層型グラフデータの階層構造を考慮して生成する必要はない。したがって、サブグラフを生成する際は、ノードのサイズ（面積）は一様として力学モデルを適用することができる。ノードサイズを一様としてサブグラフを生成することにより、力学モデルが安定しないといった事態を防止できる。
また、サブグラフの生成対象であるグループは、グラフ操作受付部２３にて指定される他、初期的には最上位の階層（すなわち、処理対象である階層型グラフデータの全体を包含するグループ）とすることができる。
【００３４】
サブグラフ修正部２２は、ディスプレイ装置１３に既に所定のサブグラフが表示されている状態で、サブグラフ生成部２１により下位階層のサブグラフが新たに生成された場合や、ノードが追加されたり削除されたりした場合に、ディスプレイ装置１３にすでに表示されているサブグラフ（以下、既存のサブグラフと称す）を修正する。
既存のサブグラフにおける所定のノードに対して下位階層のサブグラフが生成された場合、当該グループを示すノード（当該サブグラフに対応づけられたノード）のサイズ（面積）を広げて当該下位階層のサブグラフを包含するように変形する。これは、当該下位階層のサブグラフを視覚的にもグループ化するためである。具体的には、下位階層のサブグラフを生成した後、この下位階層のサブグラフの占有面積をノードに与えることにより行う。
また、下位階層のサブグラフを生成したノードのサイズが変化したことにより、当該ノードと近隣の他のノードとの位置関係（ノード間の距離など）が変化する。そこで、位置関係の変化したノード間に力学モデルを再度適用することによって、下位階層のサブグラフを含む全体のグラフィックス・イメージを修正する。
同様に、既存のサブグラフに対して新たなノードを追加したり、既存のサブグラフ中の所定のノードを削除した場合にも、ノードを追加または削除した後における近隣のノードの位置関係が変化するため、力学モデルを再度適用してサブグラフを修正する。そしてさらに、このサブグラフの修正により、当該サブグラフの占有面積が変化すると、当該サブグラフに対応づけられたノードのサイズも変更される。したがって、当該ノードと近隣の他のノードとの位置関係が変化するため、さらにこれらのノードに対しても力学モデルを再度適用し、全体のグラフィックス・イメージを修正する。
【００３５】
ここで、力学モデルを適用してグラフィックス・イメージを修正する場合、当該力学モデルを局所的に適用することができる。
例えば、上位階層のサブグラフがＮ個のノードで構成されており、そのうちの１個のノードに関して下位階層のサブグラフが生成され、当該ノードに下位階層のサブグラフの占有面積が与えられた場合を考える。このとき、サイズが変更されたノードとその近隣のノードに関して、ノードに分子間力モデル、アークにバネモデルを仮想し、ノード間の引力や斥力を算出し、運動方程式によって近隣ノードの位置を算出する。そして、移動量の大きなノードがある場合には、その大きく移動したノードとさらにその近隣ノードとの間で同様の処理を行う。
すなわち、下位階層のサブグラフの追加によりノードサイズを変化させたり、ノードの追加、削除を行ったりした場合、ノード間の位置関係が大きく変化するのは、サイズを変更したノードや追加、削除したノードの周辺である。したがって、この近隣のノードに対して局所的に力学モデルを適用してノード配置を修正し、その配置修正により一定以上の影響を受けるノードに対してさらに力学モデルを適用していくという作業を繰り返すことにより、グラフィックス・イメージを修正する。このようにすれば、ノード位置の再計算を行う処理を、ノードサイズの変化やノードの追加、削除が行われた場所の近辺に局所化し、その影響が小さい離れた場所ではノードの配置を修正しなくて済む。このため、グラフィックス・イメージの全体に対して力学モデルを適用して全てのノードを再配置する場合に比べ、少ない計算量（すなわち短い時間）でグラフィックス・イメージの修正を行うことができる。
【００３６】
さらに、サブグラフ修正部２２は、グラフ操作受付部２３からの指示に応じて、サブグラフが配置されるディスプレイ空間において、部分的な空間の膨張処理を行う。これは、サブグラフ中の指定されたノードの座標値を中心点として、表示されている他のノードを中心点から離れる方向に移動する処理である。この処理は、例えば、ユーザがサブグラフにおける特定の場所を注視しようとする場合に、その部分を拡大して視認性を高めるために用いることができる。各ノードにおける移動距離は、次のように決定される。
（ａ）ノードが、指定されたノードと同じグループに属する場合、中心点までの距離に比例する距離だけ当該中心点から離れる方向に移動する。
（ｂ）ノードが、指定されたノードと異なるグループ（上位階層のグループを含む）に属する場合、中心点までの距離の二乗に反比例する距離だけ当該中心点から離れる方向に移動する。
図６は、格子状のグラフィックス・イメージに対して部分的な空間の膨張処理を行った様子を説明する図である。図６（Ａ）のグラフィックス・イメージに対して、中心点６０１（図示の例ではノードではなく、ディスプレイ空間中の所定の座標である）を中心として部分的な空間の膨張処理を行った様子が図６（Ｂ）に示されている。
図示のように、空間の膨張処理は部分的なものであり、中心点６０１付近ではノードが大きく移動してノード間の距離を広げ、視認性を高めているのに対し、中心点から離れた位置のノードは大きな影響を受けず、移動距離も少ない。
【００３７】
なお、この部分的な空間の膨張処理を、下位階層のサブグラフを配置するための場所を確保するために用いることも可能である。
図７は、所定のノードに関して部分的な空間の膨張処理を施し、確保された空間に当該ノードの下位階層のサブグラフを配置した様子を示す図である。図７（Ａ）におけるノード７０１に対して部分的な空間の膨張処理を適用し、確保された空間に、図７（Ｂ）に示すように、ノード７０１の下位階層のサブグラフが生成されている。
このように、部分的な空間の膨張処理により、適切に空間を確保してサブグラフを配置できる場合には、上述したサブグラフ修正部２２による力学モデルを用いたノードの再配置を省略することもできる。ただし、部分的な空間の膨張処理によってサブグラフを配置する空間を適切に確保できるかどうかは、処理対象である階層型グラフデータの構造や、ユーザがいずれのノードにおける下位階層のサブグラフを生成しようとしたかなどの条件による。
【００３８】
グラフ操作受付部２３は、サブグラフ生成部２１により生成されたサブグラフに対する操作を受け付ける。サブグラフに対する操作としては、ノードの選択、削除、追加、アークの組み替えなどを挙げることができる。
ユーザは、サブグラフ生成部２１により生成されたサブグラフがディスプレイ装置１３に表示された場合に、マウスその他のポインティングデバイスやキーボードなどを用いて、当該サブグラフに対する種々の操作を行うことができる。具体的には、所望のノードをマウスクリックによって選択したり、選択されたノードを削除したり、サブグラフ中に新たなノードを追加したり、サブグラフ中のノード間に張られたアークを張り替えたりすることができる。グラフ操作受付部２３は、これらの操作を受け付け、受け付けた操作に応じてサブグラフ生成部２１及びサブグラフ修正部２２に対してサブグラフの生成及び修正の指示を行う。
【００３９】
表示制御部２４は、サブグラフ生成部２１により生成され、必要に応じてサブグラフ修正部２２により修正されたサブグラフをディスプレイ装置１３に表示する。本実施の形態では、サブグラフを表示する際の投影方法として、透視投影を用いることを標準とする。
一般に、グラフデータのグラフィックス表示の投影方法としては、平行投影が用いられている。しかし、平行投影は、視点に近い物体も視点から遠い物体も同じ大きさで表示されるので立体感を得ることが難しい。このため、この平行投影を階層型グラフデータのグラフィックス表示に用い、特定部分を異なる階層まで表示するような状況を想定した場合、表示された各部分の階層の深さを把握しにくいという欠点があった。
そこで、本実施の形態では、透視投影を用いて階層型グラフを表示する。
【００４０】
透視投影は、平行投影と共に、コンピュータグラフィックスの分野で広く用いられている投影方法であり、三次元空間を二次元のディスプレイに表示するときに用いる技術である。透視投影では、遠くのものが近くのものよりも小さく見え、視点から無限遠の位置のものが消失点と呼ばれる一点に集中するように表示される。これを実現するためには、視点からある角度を持った視野のつくる錐体内の空間を柱状の空間に歪めるように変換する。すなわち、視点に近い側を遠い側に対して相対的に広げるような変形が行われる。これにより、遠くのものを近くのものよりも小さく表示することとなり、遠近感を表現することができる。
【００４１】
階層型グラフデータのグラフィックス・イメージをディスプレイ空間に配置する場合、各階層におけるサブグラフのノードをｘｙ平面上にレイアウトし、グラフの階層の深さをｚ座標値とすることができる。ここでは、グラフの階層が深いほど大きなｚ値を与えるものとする。このようにして、レイアウトされたノードを三次元空間内に置いた状態で、ディスプレイ装置１３に透視投影を行う。
ディスプレイ装置１３にグラフィックス・イメージを表示する場合は、基本的にはｘｙ平面に垂直な向きからグラフィックス・イメージを見渡すような表示を行う。すなわち、ｚ軸の正の向きを向いたような視線を用いる（ただし、任意の視線を与えて、ｚ軸を斜め方向から見るような表示を行うこともできることは言うまでもない）。
また、視野は注視する階層のノードを十分表示できるような視野角とし、注視する階層よりも上の階層は表示しない。
【００４２】
図８は、透視投影を説明する図である。図８において、グラフデータはｚ＝０からｚ＝３までの４階層を持つ。このうち、前方投影面８０１から後方投影面８０２までをディスプレイ装置１３に表示する。この場合、注視している階層（ｚ＝１）に前方投影面８０１を置き、図示のように階層（ｚ＝１）内のノードが十分収まるような投影面を作成する。このとき、視点の位置が遠くにあるほど（ｚ値が小さいほど）、視野角は狭くなり、奥行き感が小さくなる。視点の位置を調整することで、下位階層のノードを表示した場合の奥行き感を調整することができる。
【００４３】
上述したように、透視投影では、図８に示した前方投影面８０１から後方投影面８０２までの角錐台形状の空間をディスプレイ装置１３の画面サイズに合わせた角柱状の空間に変換する。この変換は、視野角をθとしたとき、次の数１式にて得られる値を、ｘｙ平面におけるｘ座標及びｙ座標にそれぞれ乗算することで実行される。
【数１】
0003747404.tif 000002
これにより、得られるｘ座標及びｙ座標値は、−１〜１の値を持つこととなる（すなわち、視野による錐体内にある）。したがって、ディスプレイに表示するときは、この値を用いて、上述した角錐台形状の空間におけるｘｙ平面をディスプレイ装置１３における画面の幅に合わせるように変換することができる。
【００４４】
この透視投影の処理は、ノードの座標値のみならずノードのサイズにも影響する。したがって、ノードの位置に基づく遠近感と共にノードの大きさによる遠近感をも表現することができる。さらに、かかる透視と上の処理を、ノード間を接続するアークの太さに影響させることもできる。すなわち、視点から近いところ（上位階層）に位置するアークを太く、視点から遠いところ（下位階層）に位置するアークを細くする。アークの太さが１ピクセル分しかない場合、視点から遠いアークをさらに細く表示することはできないが、アークの色を背景色とブレンディングすることでさらに細い線であるかのように表現することは可能である。同様に、グラフィックス・イメージに対して所定のフィルタ処理を施すことにより、遠くのノードがかすんで見えるような視覚効果を与えることもできる。この場合、遠くにあるノードやアークほど背景色とブレンディングする際における背景色の色が強くなるようにする。
また、透視投影をサポートしているグラフィックスＡＰＩ（例えばOpenGL）を用いることにより、デプス効果機能を用いて遠方の物体を暗く表示するように制御すれば、より遠近感を表現しやすくなる。
【００４５】
また、透視投影を用いてノードを表示する場合、手前のノードと後ろのノードとが重なる部分では、後ろのノードは手前のノードに遮られて見えなくなるように表示しなければならない。これを実現するためには、既知の手法であるＺソート法を用いることができる。Ｚソート法は、Ｚ値の大きいもの、つまり後ろにあるものから順に描画し、手前のものは後ろのものを上書きするように描画する。ここでは、このＺソート法を用い、グラフデータにおける階層の深いものから順に描画していくことにより、グラフィックス・イメージを上位階層側から見た状態を表現することができる。
【００４６】
次に、上記のように構成されたグラフィックス作成システムによりグラフィックス・イメージを生成する処理について説明する。
図３は、図２に示したサブグラフ生成部２１、サブグラフ修正部２２及びグラフ操作受付部２３によって、ディスプレイ装置１３に表示されるべきグラフィックス・イメージが生成される手順を説明するフローチャートである。
また、図４は、図３に示す手順にてグラフィックス・イメージが生成される様子を例示する図である。
【００４７】
初期的に、サブグラフ生成部２１により、最上位のサブグラフ｛Ａ，Ｂ，Ｃ｝が自動配置される（図４（Ａ）参照）。このとき、下位階層のサブグラフの構造がわかっていないので、各ノードＡ、Ｂ、Ｃの面積は一定としている。
次に、図４（Ａ）の状態で、下位階層のサブグラフを表示するためにノードＣが指定され、この指定がグラフ操作受付部２３にて受け付けられたものとする（図３、ステップ３０１）。すると、グラフ操作受付部２３からサブグラフ生成部２１に対してサブグラフの生成が指示され、サブグラフ生成部２１により、指定されたノードＣが示すグループのサブグラフ｛ｆ，ｇ，ｈ｝が自動配置される（ステップ３０２）。この状態が図４（Ｂ）である。
【００４８】
次に、サブグラフ修正部２２により、ステップ３０２で生成されたサブグラフに対応づけられているノードＮａが存在するかどうか確認され、存在する場合は、当該サブグラフの占有面積がノードＮａに与えられる（ステップ３０３、３０４）。そして、ノードＮａの面積が変更され、ノードＮａを含むサブグラフの配置がノードＮａのサイズ変更に対応して修正される（ステップ３０５）。
図４に示した例では、ノードＣがステップ３０２で生成されたサブグラフ｛ｆ，ｇ，ｈ｝に対応づけられているので、当該サブグラフ｛ｆ，ｇ，ｈ｝の占有面積がノードＣに与えられる。そして、ノードＣの面積が変更されてサブグラフ｛ｆ，ｇ，ｈ｝を包含し、さらにノードＣを含むサブグラフ｛Ａ，Ｂ，Ｃ｝の配置が修正される。この状態が図４（Ｃ）である。
【００４９】
一方、ステップ３０３において、サブグラフに対応づけられているノードＮａが存在しないと判断された場合、すなわち、そのようなノードＮａに対して既にステップ３０４、３０５の処理が済んでいる場合は、処理が終了する。
以上の処理により生成されたグラフィックス・イメージは、表示制御部２４によりディスプレイ装置１３に表示される。
同様にして、ユーザが所望のノードを指定し、上記の処理を繰り返すことにより、ユーザが所望する情報を全て含んだグラフィックス・イメージを生成することができる。
図５は、このようにして最終的に生成されたグラフィックス・イメージを例示する図である。
図５を参照すると、図４（Ｃ）の状態から、さらにノードｆの下位階層のサブグラフが生成されており、またノードＡの下位階層のサブグラフ｛ａ，ｂ，ｃ｝及びその中のノードｃにおけるさらに下位階層のサブグラフが表示されている。
【００５０】
上述したように、本実施の形態は、階層型グラフデータのグラフィックス表示を行うにあたり、サブグラフを上位階層から順に自動配置する。そして、下位階層のサブグラフを生成した際に、当該下位階層のサブグラフの占有面積を上位階層に伝えることができる。このため、下位階層のノードどうし、または下位階層のサブグラフと上位階層のサブグラフとの間で干渉を起こすことがない。
また、サブグラフを自動配置する時点では、下位階層のサブグラフを意識せず、ノードの大きさを一定とする。このため、ノードの配置に用いる力学モデルが不安定になる事態を回避することができる。
【００５１】
次に、本実施の形態を種々の階層型グラフデータに適用してグラフィックス表示を実行した場合の実行例について説明する。
図９は、３５個のノードを持ち、３層の階層構造を持つ階層型グラフデータのグラフィック・イメージを生成する過程を示す図である。図９においては、最上位階層のサブグラフから順に全てのサブグラフを自動配置する過程を６段階に分けて示している。
図９において、（Ａ）は最上位の階層のサブグラフを配置した状態を示す図、（Ｂ）は（Ａ）の状態からノード９１０の下位階層のサブグラフを配置した状態を示す図、（Ｃ）は（Ｂ）の状態からさらにノード９２０、９３０、９４０の下位階層のサブグラフを配置した状態を示す図、（Ｄ）はノード９２０の下位階層のサブグラフを構成する各ノードに対してさらに下位の階層（最下位の階層）のサブグラフを配置した状態を示す図、（Ｅ）はノード９３０の下位階層のサブグラフを構成する各ノードに対してさらに下位の階層（最下位の階層）のサブグラフを配置した状態を示す図、（Ｆ）はノード９４０の下位階層のサブグラフを構成する各ノードに対してさらに下位の階層（最下位の階層）のサブグラフを配置した状態を示す図である。
図９（Ａ）〜（Ｆ）を通して参照すると、下位階層のサブグラフが追加生成されるたびに、上位階層のサブグラフにおけるノードのサイズ及び位置が変化していることがわかる。
【００５２】
図１０は、所定のウェブサイトにおけるページ間のリンク情報を示す階層型グラフデータのグラフィックス・イメージの例を示す図である。
図１０に示すように、本実施の形態のグラフィックス表示により、通常はツリー構造で示されるウェブページの階層構造に加え、各ウェブページに対応するノード間のリンク関係を視覚的に明示することができる。
さらに図１０において、ウェブページの属性（例えば言語、コンテンツ量、アクセス数、更新頻度、検索エンジンのスコアなど）に応じてノードを色分けすることにより、かかるグラフィックス・イメージをサイト管理などの用途に利用することができる。
【００５３】
図１１乃至図１３は、本実施の形態により、階層型グラフデータを、透視投影を用いて表示した例を示す図である。
図１１は上位階層に図８を参照して説明した前方投影面８０１を置いた状態のイメージであり、図１２は同じく上位階層に前方投影面を置いて視点の位置を変えた状態のイメージであり、図１３は下位階層（２番目の階層）に前方投影面を置いて図１１に示したグループ１１０１を注視した状態のイメージである。
図１１を参照すると、視点や注視位置を変えることによって下位階層のサブグラフの表示状態が変化し、この表示状態の変化が奥行きを表現して階層構造を理解しやすく表示することができる。
【００５４】
図１４、１５は、ウェブサイトの階層化されたグラフデータを、部分的な空間の膨張処理を用いて表示した例を示す図である。
図示の例では、図１４のノード１４０１を中心点にした空間の膨張処理を行っている。この結果として、中心点であるノード１４０１以外のノードが中心点から四方に離れ、ノード１４０１のまわりに隙間ができるので、図１５に示すように、当該ノード１４０１の下位階層のサブグラフを表示することが可能となる。なお、図１５において、ノード１４０１の下位階層のサブグラフを構成するノードは白抜きで示している。
【００５５】
図１６、１７は、www.trl.ibm.co.jpに公開されている全てのウェブページの接続（リンク）関係を示す階層型グラフデータを対象として本実施の形態により生成されたグラフィックス・イメージを示す図である。
図１６には、階層型グラフデータを構成する全てのサブグラフを自動配置した状態が示されている。また、図１７には、図１６の状態からいくつかのノードにおいて部分的な空間の膨張処理を行い、変形を施した状態が示されている。
【００５６】
図１８乃至図２０は、w3.trl.ibm.comに公開されているウェブページの接続（リンク）関係を示す階層型グラフデータを対象として本実施の形態により生成されたグラフィックス・イメージを示す図である。
図１８において、（Ａ）は最上位の階層のサブグラフを配置した状態を示す図、（Ｂ）は（Ａ）の状態からノード１８０１の下位階層のサブグラフを配置した状態を示す図、（Ｃ）は（Ｂ）の状態からさらにノード１８０２の開花層のサブグラフを配置した状態を示す図である。
図１８（Ａ）〜（Ｃ）を通して参照すると、下位階層のサブグラフが追加生成されるたびに、上位階層のサブグラフにおけるノードのサイズ及び位置が変化していることがわかる。
【００５７】
図１９において、（Ａ）は図１８（Ｃ）の状態から視点をずらした状態を示す図である。これにより、各ノードが立体的に表示される。ただし、ここまでの段階では、グラフィックス・イメージの表現に透視投影を用いていない。図１９（Ｂ）は、図１８（Ｃ）の状態に透視投影を適用した状態を示す図である。ここで、Ｚ軸は下位階層のサブグラフが遠方に見えるように設定してある。これにより、ノード１９０１のサブグラフが小さく表示されることとなる。図１９（Ａ）、（Ｂ）を比較すると、図１９（Ａ）の方が、最小単位のノードが同じ大きさであるため、ノード間の接続関係を理解するには有利である。一方、図１９（Ｂ）の方が、階層差を遠近の差で表現しているため、階層の深さを把握するのが容易である。
【００５８】
図２０において、（Ａ）は図１９（Ａ）の状態から、下位階層のサブグラフが手前に見えるようにＺ座標値を決めて、透視投影を適用した状態を示す図である。すなわち、この階層型グラフデータを下位階層側から見たグラフィックス・イメージとなる。図２０（Ｂ）は、図２０（Ａ）の状態で、ノード２００１の周囲における上位階層のサブグラフの空間を部分的に膨張させた状態を示す図である。これにより、ノード２００１の周囲に位置する上位階層のノードがノード２００１から離れるため、ノード２００１における下位階層のサブグラフとノード２００１を含む上位階層のサブグラフとの干渉を減少させることができる。
階層型グラフデータの種類や、グラフィックス・イメージから得ようとする情報の種類によっては、図２０（Ａ）（Ｂ）に示すような表示態様を取る方が、理解が容易となる場合もある。
【００５９】
図２１乃至図２３は、所定の会社のウェブサイトを仮想し、このウェブサイトにおけるウェブページのリンク構造を示す階層型グラフデータに基づいて生成されたグラフィックス・イメージを示す図である。
図２１は、最上位階層のサブグラフであり、「表紙ページ」、「会社概要」、「製品紹介」、「採用情報」、「リンク集」の５つのノードからなる。
図２２は、図２１のサブグラフにおける「製品紹介」ノードの下位階層のサブグラフを表示した状態を示す。
図２３は、図２２の状態からさらに「会社概要」ノードの下位階層のサブグラフを表示した状態を示す。図２３において、「会社概要」ノードと「製品紹介」ノードとの間のアークが、「会社概要」ノードの下位階層のサブグラフにおける「サプライ部門」ノードと「製品紹介」ノードの下位階層のサブグラフにおける「キャリーバッグ」ノード及び「ＰＣ机」ノードとの間のアークに入れ替わっている。すなわち、アークも下位階層のリンク関係を示していることがわかる。アークによってどちらの階層のリンク関係を示すかは、ユーザが任意に選択すれば良い。
図２１から図２３を通して参照すると、下位階層のサブグラフが追加生成されることによって、上位階層のサブグラフにおけるノードのサイズ及び位置が変化していることがわかる。
【００６０】
図２４は、図２３に示したグラフィックス・イメージに関して、上位階層が手前に、下位階層が奥に表示されるように配置し、透視投影で表示した様子を示す図である。
図２４において、破線で表示された部分が奥に表示されたサブグラフである。このように透視投影を用いることにより、階層の深さの把握が容易になるのみならず、下位階層のサブグラフを表示した状態でも上位階層に注目しやすい表示とすることができる。
【００６１】
図２５は、図２３に示したグラフィックス・イメージに関して、「製品紹介」ノードの下位階層にある「プリンタ」ノードを中心点として部分的な空間の膨張処理を施した状態を示す図である。
これにより、図２３と同様のグラフィックス・イメージ全体を表示しながら、「製品紹介」ノードに十分な表示スペースを与え、下位階層のサブグラフにおける複雑な接続関係を把握しやすく表示することが可能となっている。
【００６２】
図２６は、所定の会社における人事組織構造を仮想した階層型グラフデータに基づいて生成されたグラフィックス・イメージを示す図である。
図２６に示す例では、研究所に所属する社員間の仕事の関係と、研究所外の組織との関係を同時に表現している。研究所に相当するノードに対してのみ下位階層のサブグラフを生成し、他のノードに関しては上位階層のみを表示している。
【００６３】
なお、本実施の形態では、グラフィックス・イメージを表示する手法として、原則的に透視投影を用いることとしたが、透視投影に代えて平行投影を用いた方が好都合な場合もある。すなわち、透視投影はサブグラフの階層構造が立体的に表現されるため、階層の深さを把握するには適しているが、下位階層のサブグラフが小さく表示されてノードやアークが込み入ってしまうといった特徴がある。したがって、例えば、特定の階層のサブグラフのみに注視して、ノード間の複雑な接続関係を把握する場合などには、平行投影により表示した方が有利である。
【００６４】
本実施の形態を用いて有効な表示を実現できるデータの例として、上述したウェブページのリンク構造以外には、例えば会社の人事組織構造が考えられる。すなわち、組織の階層を反映させ、組織間あるいは社員間の仕事や金銭のやりとりをノード間の情報として含む階層型グラフデータを作成する。そして、所望の組織に関しては下位階層のサブグラフまで生成し、他の組織に関しては上位階層のみを表示する要にすれば、当該所望の組織の内部と、その周辺の組織との関係を表現することが可能となる。
さらに本実施の形態による階層型グラフデータのグラフィックス・イメージ作成技術は、次に示すような分野において利用し、組織構造を視覚化するのに好適である。
１．計算機システムのネットワークをグラフ化し、トラフィック量の管理や故障検知に用いる。
２．金融、交通、通信などのネットワークをグラフ化し、トランザクション量の理解や将来予測に用いる。
３．自治体や会社人事など、階層構造をもつ組織のネットワークをグラフ化し、人的リソースの最適化を図る。
４．テキストデータ群や画像データ群に対して、個々のデータをノードとし、それを関連性でリンクつけしてグラフ化し、データ全体の構成や傾向を理解する。
５．遺伝子データ中のシーケンスパターンをノードとし、それを関連性でリンクつけしてグラフ化し、特徴や法則を見つける。
６．ソフトウェアのプログラミング環境中で、関数やクラスをノードとし、それらの呼び出し関係などでリンクつけして、プロジェクト単位でサブグラフを構成し、ソフトウェアの開発状況を理解する。
【００６５】
【発明の効果】
以上説明したように、本発明によれば、階層型グラフデータのグラフィックス表示において、グラフデータの階層構造と所望のノード間の接続関係とを同時にかつ把握しやすい形態で表示することができる。
【００６６】
また、本発明によれば、階層型グラフデータのグラフィックス表示において、ユーザの操作に応じて動的にグラフ配置を行い、ユーザの要求に応じた柔軟なグラフィックス表示を行うことができる。
【図面の簡単な説明】
【図１】  本実施の形態によるグラフデータのグラフィックス表示技術を実現するコンピュータシステムの構成を示す図である。
【図２】  本実施の形態によるグラフデータのグラフィックス表示を実行するグラフィックス・イメージ作成システムの構成を説明する図である。
【図３】  本実施の形態のグラフィックス作成システムによるグラフィックス作成処理の全体的な流れを示すフローチャートである。
【図４】  図３に示す手順にてグラフィックス・イメージが生成される様子を例示する図である。
【図５】  本実施の形態により生成されたグラフィックス・イメージを例示する図である。
【図６】  格子状のグラフィックス・イメージに対して部分的な空間の膨張処理を行った様子を説明する図である。
【図７】  所定のノードに関して部分的な空間の膨張処理を施し、確保された空間に当該ノードの下位階層のサブグラフを配置した様子を示す図である。
【図８】  透視投影を説明する図である。
【図９】  ３５個のノードを持ち、３層の階層構造を持つ階層型グラフデータのグラフィック・イメージを生成する過程を示す図である。
【図１０】  所定のウェブサイトにおけるページ間のリンク情報を示す階層型グラフデータのグラフィックス・イメージの例を示す図である。
【図１１】  本実施の形態により、階層型グラフデータを、透視投影を用いて表示した例を示す図である。
【図１２】  図１１に対して視点の位置を変えた状態を示す図である。
【図１３】  図１１の所定の下位階層のサブグラフを注視した状態を示す図である。
【図１４】  階層化グラフデータから生成されたグラフィックス・イメージの例を示す図である。
【図１５】  図１４の所定のノードに部分的な空間の膨張処理を施し下位階層のサブグラフを表示した様子を示す図である。
【図１６】  ウェブページの接続関係を示す階層型グラフデータを対象として本実施の形態により生成されたグラフィックス・イメージを示す図である。
【図１７】  図１６の状態からいくつかのノードにおいて部分的な空間の膨張処理を行い、変形を施した状態を示す図である。
【図１８】  図１６とは異なるウェブページの接続関係を示す階層型グラフデータを対象として本実施の形態により生成されたグラフィックス・イメージを示す図である。
【図１９】  図１８の状態から透視投影を適用し、下位階層が遠くに見えるように表現した状態を示す図である。
【図２０】  図１８の状態から透視投影を適用し、下位階層が手前に見えるように表現した状態を示す図である。
【図２１】  所定の会社のウェブサイトに対応する階層型グラフデータに基づいて生成されたグラフィックス・イメージを示す図であり、最上位階層のサブグラフを示す図である。
【図２２】  所定の会社のウェブサイトに対応する階層型グラフデータに基づいて生成されたグラフィックス・イメージを示す図であり、「製品紹介」ノードの下位階層のサブグラフを表示した状態を示す図である。
【図２３】  所定の会社のウェブサイトに対応する階層型グラフデータに基づいて生成されたグラフィックス・イメージを示す図であり、さらに「会社概要」ノードの下位階層のサブグラフを表示した状態を示す図である。
【図２４】  図２３に示したグラフィックス・イメージに関して、上位階層が手前に、下位階層が奥に表示されるように配置し、透視投影で表示した様子を示す図である。
【図２５】  図２３に示したグラフィックス・イメージに関して、「製品紹介」ノードの下位階層にある「プリンタ」ノードを中心点として部分的な空間の膨張処理を施した状態を示す図である。
【図２６】  所定の会社における人事組織構造を仮想した階層型グラフデータに基づいて生成されたグラフィックス・イメージを示す図である。
【図２７】  ３階層の階層型グラフデータに対するグラフィックス・イメージの例を示す図である。
【図２８】  グラフの階層構造を立体的に表示した表示例を示す図である。
【図２９】  図２７に示した階層型グラフデータを、文献３の従来技術による手法を用いて表現した例を示す図である。
【符号の説明】
１０…コンピュータシステム、１１…処理装置（ＣＰＵ）、１２…主メモリ、１３…ディスプレイ装置、１４…記憶装置、２１…サブグラフ生成部、２２…サブグラフ修正部、２３…グラフ操作受付部、２４…表示制御部
【図１】
0003747404.tif 000003
【図２】
0003747404.tif 000004
【図３】
0003747404.tif 000005
【図４】
0003747404.tif 000006
【図５】
0003747404.tif 000007
【図６】
0003747404.tif 000008
【図７】
0003747404.tif 000009
【図８】
0003747404.tif 000010
【図９】
0003747404.tif 000011
【図１０】
0003747404.tif 000012
【図１１】
0003747404.tif 000013
【図１２】
0003747404.tif 000014
【図１３】
0003747404.tif 000015
【図１４】
0003747404.tif 000016
【図１５】
0003747404.tif 000017
【図１６】
0003747404.tif 000018
【図１７】
0003747404.tif 000019
【図１８】
0003747404.tif 000020
【図１９】
0003747404.tif 000021
【図２０】
0003747404.tif 000022
【図２１】
0003747404.tif 000023
【図２２】
0003747404.tif 000024
【図２３】
0003747404.tif 000025
【図２４】
0003747404.tif 000026
【図２５】
0003747404.tif 000027
【図２６】
0003747404.tif 000028
【図２７】
0003747404.tif 000029
【図２８】
0003747404.tif 000030
【図２９】
0003747404.tif 000031