JPH11144071A - グラフ描画装置、グラフ描画方法、グラフ描画インターフェース - Google Patents

Abstract

(57)【要約】 【課題】 ユーザーが容易に所望の条件を自由に重ねて
導入して所望のグラフ描画ができる対話型のグラフ描画
装置、方法、インターフェースを得る。 【解決手段】 視覚的に所望の表示を得るために束縛条
件を適用する。ユーザーはグラフにノードとエッジとを
追加、視覚編成機構(ＶＯＦ)束縛条件がノードに適用さ
れる。束縛条件を適用するために一般化スプリング・ア
ルゴリズムを使用する。束縛条件が適用される選択され
たノードにスプリングが付けられる。各スプリングの長
さと第２端点とは適用されるべき束縛条件に基づいて設
定される。次にスプリングに基づいて全てのノードの安
静位置をシミュレーションによって決定する。ユーザー
がＶＯＦを付加し、変更し或は削除し又はノードの位置
を変更すると、グラフは束縛条件に基づいて自動的に再
構成される。インターフェースはグラフとＶＯＦ適用用
の選択ボタンとを表示するディスプレイを提供する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、グラフを描くため
のコンピュータ化されたシステム、特に、対話型の、束
縛条件に基づいてグラフを描くためのグラフ描画装置、
グラフ描画方法およびグラフ描画インターフェースに関
する。

【０００２】

【従来の技術】刊行物やプレゼンテーションに出てくる
ような小さなグラフの殆どは、マイクロソフトのパワー
ポイント(PowerPoint)やクラリスドロー(Claris Draw)
などの、市販されている旧式の描画ツールで描かれてい
る。それらの描画ツールは、グラフィック・デザイナー
が通常自分たちの作品に利用する精巧な対称性、間隔及
びアライメントを導入し維持することを容易にするもの
ではない。通常、それらのツールは、スクリーン上のノ
ードと、それらのノード間の接続線とを配置することを
可能にするに過ぎない。ユーザーは、グラフの見栄えを
よくするためにスクリーン上でノードを対話的に動かす
ことができる。しばしば、ユーザーは、簡単な束縛条件
を適用してスクリーン上のノードを編成することもでき
る。例えば、ユーザーは、後に水平又は垂直に一線上に
並べられることになるノードの集合を選択することがで
きる。しかし、グラフを描くアルゴリズムはその束縛条
件を１回適用するだけであって、もしユーザーが後にノ
ードを変更しても、システムはノードを自動的に再整列
させるわけではない。

【０００３】他のもっと複雑なシステムは、グラフのレ
イアウトについての一定の束縛条件又は目標を設定する
ためにレイアウト・アルゴリズムを使用する。それらの
束縛条件又は目標は、グラフのいろいろな部分を自動的
に配置することを可能にするものである。一般に、グラ
フ・レイアウト・アルゴリズムは、グラフの読みとり易
さと美観とを良くするために、特定の固定された特性を
最小にする。その特性は、表示の対称性を最大にするこ
と、エッジの横断又はエッジの曲がりを最小限にするこ
と、より均一となるようにエッジの長さを制限するこ
と、及びノードを均一に分布させること、を含んでい
る。しかし、これらの特性を最小化することは、極端に
難しい計算問題であるかも知れない。従って、その様な
システムでグラフをレイアウトする操作は極めて長くて
退屈なものであるかも知れない。更に、特性を容易に最
小化できても、許容できるようなグラフが得られるとは
限らない。主として、それは、自動化されたレイアウト
はユーザーが重要であると考えているものを考慮しない
からである。全ての種類のグラフに関連するような特別
なレイアウト構造は無い。最良のレイアウトは、ディス
プレイの普遍的に適切な幾何学的性質ではなくて、その
グラフについてのユーザーの目的に依存する。このこと
に関しては、ユーザーによる入力が重要である。

【０００４】Tyson R. HenryとScott E. Hudsonとは、
“対話型グラフ・レイアウト”と題された論文("Intera
ctive Graph Layout", Proceedings of the ACM Sympos
iumon User Interface Software and Technology, page
55 (November, 1991))において、レイアウトの或る程
度の自動化とユーザー制御とを提供するグラフ・レイア
ウトを構図するためのシステムを開示している。この論
文に開示されているように、ユーザーはそのシステムと
対話してレイアウト・アルゴリズムの階層構造を指定す
る。しかし、このシステムは大きなグラフ向けのもので
あって、極めて複雑である。このシステムは、アルゴリ
ズムを設定する際に階層関係を理解していることを必要
とする。束縛条件は永続性を有するけれども、最終レイ
アウトがその束縛条件自体から直感的に明らかになるわ
けではない。束縛条件は階層的に取り決められるので、
一部の束縛条件の効果は他の束縛条件の適用によって修
正されたり取り消されたりする。具体的には、許容でき
る束縛条件は或る距離を最大化してグラフを均一にする
ように思われる。時にはグラフを読みとりやすくするた
めに、ユーザーは或る領域を強調するためにグラフが不
均一であることを好む。

【０００５】Ed Dengler、Mark Friedell及びJoe Marks
は、“束縛条件駆動型ダイアグラム・レイアウト”と題
された論文("Constraint-Driven Diagram Layout", Pro
ceedings of the 1993 IEEE Symposium on Visual Lang
uages, pp 330-335 (August,1993))において、ダイアグ
ラム・レイアウトで束縛条件を使用するためのシステム
を開示している。このシステムは、視覚編成機構(visua
l organization features (ＶＯＦｓ))の使用に基づい
ている。ＶＯＦはダイアグラム中の関連するノードの特
定の配列である。この論文のシステムはＶＯＦがどこか
ら生じるかを記述もせず推定もしない。むしろ、それ
は、ノード、エッジ及びＶＯＦに基づいてレイアウト結
果を作るためのシステムに過ぎない。レイアウトは、束
縛条件を満たすためにシミュレーションと確率的調査と
の混成プロセスにより最適化される。また、漸増プロセ
スにおいて指定された順序でスプリング束縛条件が適用
される。その順序は、束縛条件の限定性の程度によって
決まる。これは、漸増改良アプローチが局所最適条件に
拘束されるのを防止しようとするものである。また、De
ngler等のアプローチでは、初期レイアウトがランダム
に選択される。性能を高めるために、数個の異なる初期
位置を使用することができる。束縛条件を満たすときに
全体における最適条件を決定するためにその初期位置の
各々から得られた最適条件同士が比較される。

【０００６】

【発明が解決しようとする課題】以上のように従来のグ
ラフ描画装置においては、小さなグラフ向けのもので
は、ユーザーが所望の条件を自由に導入してグラフ描画
ができるものはなく、また、大きいグラフ向けのものは
専門的で操作等が非常に複雑であるとい課題があった。

【０００７】この発明は、小さなグラフ向けのもので、
ユーザーが容易に所望の条件を自由に重ねて導入して満
足のできるグラフ描画ができるグラフ描画装置、グラフ
描画方法およびグラフ描画インターフェースを提供する
ことを目的とする。

【０００８】

【課題を解決するための手段】上記の目的に鑑み、この
発明は、グラフの複数のノードをそのグラフの視覚的表
示の指定された場所に作るための手段と、それらの複数
のノード間に複数のエッジを作るための手段と、前記の
指定された位置の前記の複数のノードと前記の複数のエ
ッジとを視覚的に表示するための手段と、前記の複数の
ノードのうちの選択されたノードに適用されるべき少な
くとも１つの視覚編成機構を特定するユーザー入力を受
け取るための手段と、前記の少なくとも１つの視覚編成
機構に従って前記の選択されたノードを編成するために
前記の複数のノードの位置を調整するための手段と、そ
の調整された位置に該ノードを視覚的に表示するための
手段と、を備えたことを特徴とするグラフ描画装置にあ
る。

【０００９】またこの発明は、前記の少なくとも１つの
視覚編成機構は、選択されたノードの順次配置、選択さ
れたノードの密集化、選択されたノードの前記視覚表示
の指定された部分への隔離区分、選択されたノードのＴ
形配置、線に沿っての選択されたノードのアライメン
ト、選択されたノード間の均等間隔配置、選択されたノ
ードの対照的配置、選択されたノードのハブ形配置、の
うちの少なくとも１つを含むことを特徴とするグラフ描
画装置にある。

【００１０】またこの発明は、前記の少なくとも１つの
視覚編成機構が複数の視覚編成機構からなり、前記調整
手段が、それらの視覚編成機構の全てを実質的に満たす
ために複数のノードの位置を調整する手段を含むことを
特徴とするグラフ描画装置にある。

【００１１】またこの発明は、前記の複数の視覚編成機
構のうちの少なくとも１つを除去するための手段を更に
備えたことを特徴とするグラフ描画装置にある。

【００１２】またこの発明は、前記の複数のノードのう
ちの少なくとも１つの指定された位置を変更するユーザ
ー入力を受け取るための手段を更に備えたことを特徴と
するグラフ描画装置にある。

【００１３】またこの発明は、複数のノードと、それら
のノード同士を結ぶエッジとを有するグラフを対話的に
作るためのグラフ描画方法であって、(ａ) 前記の複数
のノードの各々について位置を指定するユーザー入力を
受け取る工程と、(ｂ) 少なくとも１つのノードを選択
する工程と、(ｃ) その少なくとも１つの選択されたノ
ードに適用されるべき少なくとも１つの視覚編成機構を
指定するユーザー入力を受け取る工程と、(ｄ) その視
覚編成機構に従って複数のノードの位置を調整する工程
と、(ｅ) その調整された位置にノードのあるグラフを
表示する工程と、を備えたことを特徴とするグラフ描画
方法にある。

【００１４】またこの発明は、前記工程(ｂ)から(ｅ)が
複数回反復されることを特徴とするグラフ描画方法にあ
る。

【００１５】またこの発明は、前記調整工程が、選択さ
れたノードの各々を、前記の少なくとも１つの視覚編成
機構によって確定される位置に結びつける仮想スプリン
グの集合を決定するステップと、その仮想スプリングに
基づいて前記ノードの各々について安静位置を決定する
ステップと、を含むことを特徴とするグラフ描画方法に
ある。

【００１６】またこの発明は、少なくとも１つの視覚編
成機構を除去する工程と、除去された前記少なくとも１
つの視覚編成機構を含まない視覚編成機構に従って複数
のノードの位置を調整する工程と、その調整された位置
にノードがあるグラフを表示する工程と、を更に備えた
ことを特徴とするグラフ描画方法にある。

【００１７】またこの発明は、少なくとも１つのノード
の位置を変更する工程と、前記視覚編成機構と、その少
なくとも１つのノードの変更された位置とに基づいて複
数のノードの位置を調整する工程と、を更に備えたこと
を特徴とするグラフ描画方法にある。

【００１８】またこの発明は、複数のノードと複数のエ
ッジとを指定された位置に表示するためのグラフ表示領
域と、このグラフ表示領域に表示された少なくとも１つ
のノードを選択するための手段と、選択された少なくと
も１つのノードに適用される視覚編成機構のユーザー入
力を受け取るための束縛条件選択領域と、その視覚編成
機構に基づいて前記グラフ表示領域内の前記の複数のノ
ードの位置を調整するための手段と、を備えたことを特
徴とするグラフ描画インターフェースにある。

【００１９】またこの発明は、選択された少なくとも１
つのノードに関して前記視覚編成機構を前記グラフ表示
領域に表示するための手段を更に備えたことを特徴とす
るグラフ描画インターフェースにある

【００２０】小さなグラフを巧みに描くための公知シス
テムの欠陥は、束縛条件を使用してグラフを描くための
対話型システムに関する本発明によって実質的に克服さ
れる。このシステムでは、ユーザーによってインターフ
ェースを通して束縛条件、ノード及びエッジが、表示さ
れているグラフに追加されたり、表示されているグラフ
から削除されたりする。変更が加えられる毎に、システ
ムは束縛条件に基づいてノード及びエッジの位置を動的
に決定し直す。束縛条件を適用して、全ての束縛条件に
関して局所的に最適なノードの配置を与えるために、一
般化されたスプリング・アルゴリズムが使用される。更
に、本発明は、グラフに適用することのできるマクロ束
縛条件の小さな集合を含んでいる。それらの束縛条件
は、グラフを描くために特別に設計されている。それら
の束縛条件は、ノード上の指定された点同士の接触関係
や連続関係などの単純な幾何学的或いは位相幾何学的関
係よりはむしろ、ノード同士の対称性などの複雑な関係
に関連しているので、“マクロ(大型)”という形容詞が
付されている。

【００２１】

【発明の実施の形態】図１は、本発明を実施するのに使
えるコンピュータ・ハードウェア１を示している。中央
処理装置(ＣＰＵ)１０は、本発明のプロセスを実行する
ためにプログラム・ステップを処理する。ＣＰＵ１０
は、命令を実行するために汎用コンピュータで使用され
ている処理装置などの、如何なる種類の処理装置であっ
ても良い。メモリー２０は、プログラム・ステップを記
憶すると共に、本発明においてグラフを表すために使用
されるデータを記憶する。メモリー２０は、ＲＡＭ、Ｒ
ＯＭ、ＣＤ−ＲＯＭ、磁気ディスク又はその他のディジ
タル記憶媒体を含む如何なる種類のメモリーであっても
良い。グラフの状況を表示するときにユーザーと対話す
るためにディスプレイ３０がＣＰＵに接続されている。
ユーザーインターフェースに関して後述するように、こ
のディスプレイはグラフに課されている束縛条件も表示
する。ユーザーからの入力のためにキーボード４０とマ
ウス５０とがＣＰＵ１０に接続されている。ユーザーが
情報をキーボード４０又はマウス５０で入力すると、Ｃ
ＰＵ１０はその情報を処理して、それに応じてグラフを
修正する。完成したグラフのハードコピーを作るために
プリンタ６０もＣＰＵに接続することができる。

【００２２】図２はグラフの処理を実行するときに使用
することのできるユーザーインターフェース１００を示
している。インターフェース１００は、ＣＰＵ１０に接
続されているディスプレイ３０に現れる情報の表示を表
している。ユーザーインターフェース１００のグラフ表
示領域１１０は、グラフ中のノード及びエッジを表示す
る。メモリー２０の中のグラフ情報は、ディスプレイ３
０で表示されるべきノードの位置及びサイズ、ラベル及
びエッジを作るためにＣＰＵ１０によって処理される。
視覚編成機構(ＶＯＦ)を選択してグラフ中のいろいろな
ノードに適用するために一組のボタン１２０が使用され
る。ＶＯＦが適用される特定のノードを選択するために
ユーザーはマウス５０を操作する。ノードが選択される
と、ユーザーはボタン１２０を使って、適用する適当な
ＶＯＦを選択する。第２組のボタン１４０は、インター
フェースを操作する追加の機能を提供する。例えば、選
択ボタン１４１は、ＶＯＦをディスプレイ上に表示させ
るために使用されるものであり、選択されたり選択され
なかったりする。選択ボタン１４２はグラフをディスプ
レイの中心に置く。選択ボタン１４３はテキスト・ラベ
ルを付加したり変更したりするために使用される。選択
ボタン１４４は、ノードを特定の位置に係留する。選択
ボタン１４５は、ノードを削除するために使用される。
選択ボタン１４６は、適用された全てのＶＯＦを削除す
る。選択ボタン１４７は、指定されたノードの選択を解
除する。カーソルが適当なノードの上に位置していると
きにマウスボタンの１つをクリックすることによってノ
ードを選択することができる。もちろん、他のメカニズ
ムを使ってＶＯＦを選択してグラフに適用することもで
きる。例えば、表示される選択ボタンの代わりにプルダ
ウン・メニューを使うことができる。

【００２３】第１組の選択ボタン１２０の中の選択エレ
メントに対応するＶＯＦが図３の(ａ)〜(ｈ)に示されて
いる。図３の(ａ)は、ノードの順次配置を示している。
これは、水平方向(選択ボタン１３１)又は垂直方向(選
択ボタン１３２)に選択される。順次配置では、ノード
は指定された順序で選択される。この束縛条件が満たさ
れると、ノードはディスプレイ上でその順序で水平に又
は垂直に配置される。図３の(ｂ)は、選択された全ての
ノードを互いの近くに位置させる密集化(選択ボタン１
２３)を示している。図３の(ｃ)は、区分(選択ボタン１
２４)を示している。区分では、ノードは長方形の中に
封入される。選択された全てのノードがその長方形の中
に保たれ、選択されていない全てのノードがその長方形
の外に保たれる。図３の(ｃ)に示されているように、異
なるノードのグループのために区分を使用することがで
きる。図３の(ｄ)は、Ｔ形束縛条件(選択ボタン１２９)
を示している。Ｔ形では、中心のノードは、一線に並ん
だ他のノードの行の上又は下の中心に置かれる。或い
は、Ｔ形は、中心ノードをノードの行の左又は右に置い
ても良い。図３の(ｅ)は、水平方向(選択ボタン１２１)
又は垂直方向(選択ボタン１２２)の１本の線に沿って全
てのノードが配置されるアライメントを示している。図
３の(ｆ)は等間隔を示していて、全てのノードは水平方
向(選択ボタン１２５)又は垂直方向(選択ボタン１２６)
に同じ距離だけ離れている。図３の(ｇ)は対称を示して
いる。対称では、ユーザーが特定した一定の軸に関して
全てのノードが対称に配置される。その軸は、水平方向
(選択ボタン１２７)又は垂直方向(選択ボタン１２８)で
ある。最後に、図３の(ｈ)はハブ形のデザインを示して
おり、選択された全ての点が中心ノードから等距離にあ
る。ハブ型は選択ボタン１３０により選択される。中心
ノードがユーザーによって選択されると、選択された全
てのノードが、それらのノードの平均位置から等距離の
円周上の点となる。

【００２４】図４〜７は、グラフを設計するときのシス
テムの動作を示している。図４に示されているように、
グラフは、ノードと、ノード同士を結ぶエッジとのグル
ープから成っている。ユーザーはノードの特性と、ノー
ドについてのラベルとを特定する。ノードは、ラベルの
ために充分なスペースを有するように自動的に作られ
る。図４で、ノードはスクリーン上に幾分恣意的に配置
されている。ユーザーは、このグラフの外観を良くする
ためにいろいろなＶＯＦを適用する。図５に示されてい
るように、ユーザーは水平方向アライメント２１０，２
１１，２１２のために３つのＶＯＦを適用している。ノ
ードを選択すると共にＶＯＦ束縛条件を選択することに
よってＶＯＦが適用される。

【００２５】ＶＯＦ束縛条件が選択されると、システム
は、その束縛条件と、前から存在している束縛条件とを
満たすためにノードを自動的に調整し直す。上位レベル
の各束縛条件は、ノードに作用する特定の力の集合に変
換される。ノードの位置を決めるために、一般化された
スプリング・アルゴリズムが使用される。一般化された
スプリング・アルゴリズムは、適用された全ての束縛条
件を局所的に最適に満たす結果をもたらす。一般化され
たスプリング・アルゴリズムでは、全てのノードが、そ
れらのノードを互いに或るポイントに結びつける一組の
スプリングを持つものとして扱われる。スプリングは、
束縛条件の目的を満たすために定義される。例えば、ア
ライメントＶＯＦでは、一組の長さゼロのスプリングが
各ノードをポイントの中心軌跡(centroid)を通る水平又
は垂直の線に結びつける。密集化ＶＯＦは短い安静状態
の長さのスプリングをノード間に対をなすように配置す
る。

【００２６】スプリング・アルゴリズムを使用すれば、
束縛条件を固守せずに配置することが可能になる。各ノ
ードは、該ノードに作用する全ての力(束縛条件)に基づ
いて配置されることになり、どの束縛条件も完全には満
たさなくても良い。例えば、他に束縛条件がなければ、
アライメントＶＯＦが適用されている選択されたノード
の全てが中心軌跡を通る線上に位置する。更に束縛条件
が適用されると、他の束縛条件からの力がノードに作用
することになるので、一部のノードは実際には中心軌跡
を通る線上に位置しなくなるかも知れない。しかし、ア
ルゴリズムは、ノードに作用する全ての束縛条件を均衡
させる。

【００２７】本発明のシステムでは、選択されたＶＯＦ
の効果を図解するために質量−スプリング・モデルが連
続的にアニメ化される。従って、ユーザーがＶＯＦを付
け加えると(或いはそれらを除去すると)、その変更を反
映するようにノードがスクリーン上で動かされる。ユー
ザーはディスプレイ上でノード或いはノードのグループ
を動かすこともできる。ノードが動かされるとき、シス
テムは、スプリングの安静位置に基づいて配置を決定し
直す。ノードのユーザー移動は、システムが束縛条件に
対するより良い全体的解決を見いだすのをユーザーが援
助することを可能にする。質量−スプリング・シミュレ
ーションは、満足できるレイアウトを得るためのユーザ
ーとシステムとの協力関係を作るために使用される。シ
ステムはユーザーの変更の各々を解釈して全ての束縛条
件を同時になるべく良好に適用する。ユーザーは、一定
の指定された視覚的束縛条件を満たしながら所望の効果
を得るためにノード及び束縛条件を操作することができ
る。

【００２８】図６は、さらなる３つの束縛条件、即ち垂
直対称性２２０と、垂直アライメント２２１と、ハブ形
２２２とを示している。ハブ形２２２では、中心ノード
は選択されない。上記のように、各エレメントは、選択
された全てのノードの導出された中心軌跡から等距離に
置かれる。図７は、図２に示されているグラフ構造を得
るために更に追加された３つのＶＯＦを示している。左
側の３つのノードは、小さな点２３０で示されている密
集化ＶＯＦの作用を受ける。中央の３つのノードは等間
隔ＶＯＦ２３１の作用を受ける。水平アライメントＶＯ
Ｆは左下の２つのノードに適用される。

【００２９】図８は、本発明に従ってグラフを描くシス
テムの動作を記述した流れ図を示している。最初に描画
インターフェースが表示される(ステップ４００)。前か
ら存在するグラフが使用されるのであれば、グラフ用の
データがメモリーから検索され(ステップ４０５)、表示
される(ステップ４１０)。もし前から存在するグラフが
使用されないのであれば、ステップ４１０でインターフ
ェースのディスプレイの中の空白のスクリーンがユーザ
ーに呈示される。システムは、その後、ユーザー入力を
待つ(ステップ４１５)。ユーザーは、ノードを変更す
る、ノードを選択する、及び束縛条件を追加するステッ
プを含む、幾つかのステップを実行することができる。

【００３０】ユーザーがノード(ステップ４２０)又はテ
キスト・ラベルを追加したいときには、ユーザーは位置
と、ラベルの中のタイプとを選択する(ステップ４２
３)。所定の全体的束縛条件は、各ノードがラベルをは
め込むのに充分なサイズを持っていなければならないと
いうことである。ユーザーは、最小のサイズより大きな
異なるサイズを対話型で繰り返し設定することができる
(ステップ４２５)。各ノードは、ラベルを囲むボックス
を含んでおり、且つ、背景とは異なる色をそのボックス
の中に含むことができる。テキスト・ラベルはノードに
似ているけれども、周りを囲むボックスを含んではいな
い。しかし、ＶＯＦをノードと同じくテキスト・ラベル
にも適用することができる。

【００３１】ユーザーがノードを選択すると(ステップ
４３０)、そのノードはディスプレイ上で特別に明るく
されて強調される(ステップ４３５)。ＶＯＦを適用する
前にステップ４３０，４３５を用いてノードを選択して
おかなければならない。ＶＯＦが適用されるべき時(ス
テップ４４０)、選択されたノードの各々に適当なスプ
リングが付けられる(ステップ４４４，４４６，４４
８)。スプリングが付けられると、システムはノードに
かかる力を計算して(ステップ４７０)、ＶＯＦ束縛条件
の全部を表す全てのスプリングについての安定状態を決
定する。安定状態が計算されているとき、安定状態位置
へ動かされつつある中間位置を表示するようにディスプ
レイを更新することができる(４７２)。或いは、単にグ
ラフを最終位置で表示し直しても良い(ステップ４７
６)。

【００３２】ＶＯＦが除去されるべきときには(ステッ
プ４５０及びその次を参照)、スプリングが除去され、
そのグラフについての現在の安定状態を見いだすために
同じプロセス(ステップ４７０，４７２，４７６)が反復
される。また、ノードが除去されるならば(ステップ４
６０)、そのノードに対応するスプリングが除去されて
グラフが描き直される。スプリングはノード同士の間で
作用するので、ノードを除去すると他のノードの位置に
影響が及ぶことがある。

【００３３】以上の本発明の説明は単なる例示であっ
て、限定をするものではないことは専門家にとっては明
らかであるはずである。いろいろな修正や他の実施の形
態が当業者の範囲内にあって、添付の請求項で定義され
ている発明の範囲内に属すると考えられる。

【００３４】

【発明の効果】ユーザーによるグラフの対話型操作のた
めの本発明のシステムでは、視覚的に満足する表示を得
るために束縛条件を適用する。ユーザーはグラフにノー
ドとエッジとを追加する。視覚編成機構(Visual Organi
zation Feature (ＶＯＦ))束縛条件がノードに適用され
る。システムは、束縛条件を適用するために、一般化ス
プリング・アルゴリズムを使用する。束縛条件が適用さ
れる選択されたノードにスプリングが付けられる。各ス
プリングの長さと第２端点とは、適用されるべき束縛条
件に基づいて設定される。次にシステムはスプリングに
基づいて全てのノードの安静位置をシミュレーションに
よって決定する。ユーザーがＶＯＦを付加し、変更し或
いは削除し、又はノードの位置を変更すると、グラフは
束縛条件に基づいて自動的に再構成される。描画システ
ムと関連するユーザーインターフェースは、グラフとＶ
ＯＦを適用するための選択ボタンとを表示するためのデ
ィスプレイを提供する。これにより、小さなグラフ向け
のもので、ユーザーが容易に所望の条件を自由に重ねて
導入して満足のできるグラフ描画ができるグラフ描画装
置、グラフ描画方法およびグラフ描画インターフェース
を提供できる。

【図面の簡単な説明】

【図１】 本発明の対話型のグラフ描画装置を実現する
ために使用することのできるコンピュータ・ハードウェ
アを示す図である。

【図２】 本発明のグラフ描画インターフェースで動作
するユーザーインターフェースを示す図である。

【図３】 本発明における視覚編成機構の適用を説明す
るための図である。

【図４】 グラフを描いて本発明に従って束縛条件を適
用するときの過程を説明するための図である。

【図５】 グラフを描いて本発明に従って束縛条件を適
用するときの過程を説明するための図である。

【図６】 グラフを描いて本発明に従って束縛条件を適
用するときの過程を説明するための図である。

【図７】 グラフを描いて本発明に従って束縛条件を適
用するときの過程を説明するための図である。

【図８】 本発明の動作を記述したフローチャート図で
ある。

【符号の説明】

１ コンピュータ・ハードウェア、１０ ＣＰＵ、２０
メモリー、３０ ディスプレイ、４０ キーボード、
５０ マウス、１００ インターフェース。

───────────────────────────────────────────────────── フロントページの続き (71)出願人 597067574 201 ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩ ＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ 02139， Ｕ．Ｓ．Ａ. (72)発明者 カスリーン・リャル アメリカ合衆国、バージニア州、シャーロ ッツビル、コモンウェールス・ドライブ 2111 (72)発明者 ジョセフ・マークス アメリカ合衆国、マサチューセッツ州、ベ ルモント、ダルトン・ロード 61 (72)発明者 スチュアート・メリル・シーバー アメリカ合衆国、マサチューセッツ州、ケ ンブリッジ、コンコード・アベニュー 243、ナンバー２

Claims (12)

【特許請求の範囲】
1. 【請求項１】 グラフの複数のノードをそのグラフの視
   覚的表示の指定された場所に作るための手段と、 それらの複数のノード間に複数のエッジを作るための手
   段と、 前記の指定された位置の前記の複数のノードと前記の複
   数のエッジとを視覚的に表示するための手段と、 前記の複数のノードのうちの選択されたノードに適用さ
   れるべき少なくとも１つの視覚編成機構を特定するユー
   ザー入力を受け取るための手段と、 前記の少なくとも１つの視覚編成機構に従って前記の選
   択されたノードを編成するために前記の複数のノードの
   位置を調整するための手段と、 その調整された位置に該ノードを視覚的に表示するため
   の手段と、 を備えたことを特徴とするグラフ描画装置。
2. 【請求項２】 前記の少なくとも１つの視覚編成機構
   は、選択されたノードの順次配置、選択されたノードの
   密集化、選択されたノードの前記視覚表示の指定された
   部分への隔離区分、選択されたノードのＴ形配置、線に
   沿っての選択されたノードのアライメント、選択された
   ノード間の均等間隔配置、選択されたノードの対照的配
   置、選択されたノードのハブ形配置、のうちの少なくと
   も１つを含むことを特徴とする請求項１に記載のグラフ
   描画装置。
3. 【請求項３】 前記の少なくとも１つの視覚編成機構が
   複数の視覚編成機構からなり、前記調整手段が、それら
   の視覚編成機構の全てを実質的に満たすために複数のノ
   ードの位置を調整する手段を含むことを特徴とする請求
   項１に記載のグラフ描画装置。
4. 【請求項４】 前記の複数の視覚編成機構のうちの少な
   くとも１つを除去するための手段を更に備えたことを特
   徴とする請求項３に記載のグラフ描画装置。
5. 【請求項５】 前記の複数のノードのうちの少なくとも
   １つの指定された位置を変更するユーザー入力を受け取
   るための手段を更に備えたことを特徴とする請求項１に
   記載のグラフ描画装置。
6. 【請求項６】 複数のノードと、それらのノード同士を
   結ぶエッジとを有するグラフを対話的に作るためのグラ
   フ描画方法であって、 (ａ) 前記の複数のノードの各々について位置を指定す
   るユーザー入力を受け取る工程と、 (ｂ) 少なくとも１つのノードを選択する工程と、 (ｃ) その少なくとも１つの選択されたノードに適用さ
   れるべき少なくとも１つの視覚編成機構を指定するユー
   ザー入力を受け取る工程と、 (ｄ) その視覚編成機構に従って複数のノードの位置を
   調整する工程と、 (ｅ) その調整された位置にノードのあるグラフを表示
   する工程と、 を備えたことを特徴とするグラフ描画方法。
7. 【請求項７】 前記工程(ｂ)から(ｅ)が複数回反復され
   ることを特徴とする請求項６に記載のグラフ描画方法。
8. 【請求項８】 前記調整工程が、 選択されたノードの各々を、前記の少なくとも１つの視
   覚編成機構によって確定される位置に結びつける仮想ス
   プリングの集合を決定するステップと、 その仮想スプリングに基づいて前記ノードの各々につい
   て安静位置を決定するステップと、 を含むことを特徴とする請求項６に記載のグラフ描画方
   法。
9. 【請求項９】 少なくとも１つの視覚編成機構を除去す
   る工程と、 除去された前記少なくとも１つの視覚編成機構を含まな
   い視覚編成機構に従って複数のノードの位置を調整する
   工程と、 その調整された位置にノードがあるグラフを表示する工
   程と、 を更に備えたことを特徴とする請求項７に記載のグラフ
   描画方法。
10. 【請求項１０】 少なくとも１つのノードの位置を変更
    する工程と、前記視覚編成機構と、その少なくとも１つ
    のノードの変更された位置とに基づいて複数のノードの
    位置を調整する工程と、 を更に備えたことを特徴とする請求項６に記載のグラフ
    描画方法。
11. 【請求項１１】 複数のノードと複数のエッジとを指定
    された位置に表示するためのグラフ表示領域と、 このグラフ表示領域に表示された少なくとも１つのノー
    ドを選択するための手段と、 選択された少なくとも１つのノードに適用される視覚編
    成機構のユーザー入力を受け取るための束縛条件選択領
    域と、 その視覚編成機構に基づいて前記グラフ表示領域内の前
    記の複数のノードの位置を調整するための手段と、 を備えたことを特徴とするグラフ描画インターフェー
    ス。
12. 【請求項１２】 選択された少なくとも１つのノードに
    関して前記視覚編成機構を前記グラフ表示領域に表示す
    るための手段を更に備えたことを特徴とする請求項１１
    に記載のグラフ描画インターフェース。