JP4864181B2 - ノード表示装置 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、双曲空間のような負曲率を有する空間へのノード−リンク構造のレイアウトに関する。
【０００２】
【従来の技術】
ジャーナル・オブ・ビジュアルランゲージズ・アンド・コンピューティング誌(Journal of Visual Languages and Computing)、1996年、第７巻、33頁−55頁の、ランピング(Lamping, J.)及びラオ(Rao, R.)の「双曲ブラウザ：大きな階層を視覚化するための焦点＋コンテキスト技術(“The Hyperbolic Browser: A Focus+Context Technique for Visualizing Large Hierarchies”)」は、双曲平面に、親子間及び同胞間の距離がどこでもほぼ同じように階層をレイアウトするための技術を開示している。再帰的アルゴリズムが、局所的情報に基づいて各ノードをレイアウトし、ノードの子孫に双曲平面の楔を割付ける。そのアルゴリズムは全ての子を、楔内の弧に沿って、親ノードから等距離であり且つ互いから少なくとも最小距離で離間するように配置する。ノードのレイアウトは、その親のレイアウト及びその親から始まる２又は３世代のノード構造だけに依存する。従って、レイアウトは、最初にルートに最も近いノードをレイアウトし、次に、構造が更に走査されるにつれて更にノードを追加することによって、増分的に行うことができる。ランピングら（Lamping et al.）の米国特許第5,590,250号は、各ノードが、そのノードの位置及び半径、及びそのノードが子を有する場合は子のリストへのリンクを含むデータ構造を有し、双曲平面での位置を表わすために複素数が用いられる、類似のレイアウト技術を開示している。
【０００３】
1995年のアメリカ計算機学会コンピュータグラフィックス分科会(ACM SIGGRAPH)のＶＲＭＬ'95シンポジウム（1995年12月13日−16日、カリフォルニア州サンディエゴにて）議事録の33頁−38頁の、ミュンツナー(Munzner, T.)及びバーチャード(Burchard, P.)の「３次元双曲空間におけるワールドワイドウェブ構造の視覚化(“Visualizing the Structure of the World Wide Web in 3D Hyperbolic Space”)」は、循環を有する有向グラフに用いることができる、双曲平面にグラフをレイアウトするための技術を開示している。２つのノードを結ぶエッジの双曲線の長さは、双曲線関数と２つのノードに入射するエッジ間の角度とを用いて入手される。循環を有する有向グラフは、バックリンクエッジのフィルイン(filling in)によって、空間がそれ自体を包んで閉鎖できる双曲マニホールド空間か、又は標準双曲空間に埋め込まれることが可能である。
【０００４】
本発明は、双曲空間のような負曲率を有する空間へのノードリンク構造のレイアウトにおける問題を扱う。
【０００５】
負曲率レイアウトのためのランピング及びラオによって述べられた技術及び他の従来の技術では、構造が表示後に変化する場合、その変更された構造の少なくとも大きな部分について新たなレイアウトが一般的になされなければならず、次に再表示されなければはならない。大きな構造にレイアウトを行うのは遅く、再表示と一緒に行うと、ユーザが変更された構造と効果的に対話するのを妨げることがある。これらの問題は、特に構造の変更に対して深刻であるのだが、静的構造又はその部分の頻繁なレイアウトを要求する操作が行われる際にも生じる。
【０００６】
ランピング及びラオによって述べられた、静的構造のためのレイアウト技術は、構造の少なくとも大きな部分のレイアウトを命令する特徴を有する。静的構造のためのレイアウト技術は、ツリー内のより上位のレイアウト決定に左右される各ノードでの、及びその同胞ノードでの決定を行い、その結果、あるノードの１つの子の追加又は削除が、そのノードの全ての子孫及び任意の同胞についてのレイアウトの再実行を命令する。また、この静的構造のためのレイアウト技術は、双曲平面内のノードの位置だけを保存し、ノードの位置を変えるであろう構造のいかなる変更も、そのノードの同胞及び全ての子孫のレイアウトの繰返しを要求する。
【０００７】
【発明が解決しようとする課題及び課題を解決するための手段】
本発明は、双曲空間又は双曲平面のような負曲率を有する空間へのノード−リンク構造の局所的なレイアウトの実行を可能にする技術の提供によって、大きな構造のレイアウトの結果生じる問題を軽減する。この技術は、要素について、近隣ノード−リンク関係に関する情報を示す近隣関係データを入手する。次に、この技術は近隣関係データを用いて、負曲率を有する空間でのその要素の親に対する相対位置を示す、レイアウトデータを入手する。
【０００８】
例えば、要素及び親がノードである場合は、レイアウトデータは、親の位置と要素の位置との間の距離を示す位置変位データと、親への入リンクと親から子への出リンクとの間の角度差を示す角度変位データとを含むことができる。特にエレガントな実施例では、レイアウトデータは位置変位データ及び角度変位データだけを含む。
【０００９】
近隣ノード−リンク関係は、親と、その親の子と孫との間の関係だけを含むことができる。
【００１０】
この新たな技術は、１つの要素が削除又は挿入されたときに少数の近隣要素だけ再レイアウトされればよいので、動的ノード−リンク構造のレイアウトにおいて有益である。また、この技術は、要素の絶対位置ではなく、親に対する相対位置を入手し、データ構造に単一の変更又は小さい一定数の局所的変更を行うことによって要素及び全ての子孫の位置の変更を可能にする。
【００１１】
また、この新たな技術は、ノード−リンク構造の一部をレイアウトすることが望ましい種々の状況で用いることができるので、有益である。従って、この新たな技術は動的ノード−リンク構造に適用可能なだけではなく、メモリ内で構造を全ては使用できないために断片的にレイアウトされて表示できるだけの静的構造にも適用可能である。この技術は、ノードが複数の入リンクを有する有向グラフの部分的表現であるツリーのレイアウトに特に有益である。そのようなツリーの共有ブランチは、発生ごとに一番上の要素の相対位置だけが異なるので、共有ブランチの全発生に対して1回完全にレイアウトされるだけでよい。
【００１２】
また、この技術は、構造の一部だけを含む変更のアニメーションにも有益である。例えば、構造に挿入又は削除がなされた場合、挿入又は削除に近い要素の位置を変えるだけの遷移のアニメーション化が望ましいかもしれない。この技術は、挿入又は削除に近い要素の位置だけが変更される、各アニメーションステップについて１回の、一連のレイアウトの急速な実行を可能にする。その結果、アニメーションのパフォーマンスが向上し、より単純なアニメーションアルゴリズムを用いることができる。アルゴリズムは、挿入又は削除に近い各ノードについての角度及び半径のような、少数の変数だけを続けて変更できる。
【００１３】
別の長所として、この新たな技術は、従来技術のように常に構造のルートノード又は基底のリーフで開始するのではなく、どの任意の要素で開始しても表示を生成できるレイアウトを提供する。
【００１４】
更に別の長所として、要素の、親に対する相対位置を、常に適度な精度をもって表わすことができる。それとは対照的に、要素の、双曲平面内の絶対位置が用いられる場合は、大きな構造は使用可能な浮動小数点数を使い果たすことがある。
【００１５】
本発明の態様は、負曲率を有する空間にノード−リンク構造をレイアウトする方法であって、構造内の要素について、近隣ノード−リンク関係に関する情報を示す近隣関係データを入手し、近隣関係データに基づいて、負曲率を有する空間での要素の親に対する相対位置を示すレイアウトデータを入手する、負曲率を有する空間にノード−リンク構造をレイアウトする方法である。
【００１６】
【発明の実施の形態】
以下の概念的構想は、米国特許第5,590,250号及び第5,619,632号で述べられた概念的構想と共に読むと、本発明の広い範囲を理解する上で役に立ち、以下に定義される用語は、特許請求の範囲を含む本出願を通して示された意味を有する。
【００１７】
“ノード−リンク構造”は、ノードとリンクとに区別できる項目を含み、各リンクが２つ以上のノードに関係している構造である。“グラフ”は、各リンクが２つのノードに関係しているノード−リンク構造である。“有向グラフ”は、各リンクが関係するノード間の方向を示し、一方のノードがリンクのソース又は“フロムノード”であり、他方のノードがリンクの宛先又は“ツーノード”であるグラフである。“非環式有向グラフ”は、リンクが、それらの示された方向に辿られたときに、任意のノードからそれ自体に戻るパスを提供しない有向グラフである。“ツリー”は、ツリー内の任意の非ルートノードについて、リンクが、その示された方向に辿られたときに、ルートノードで始まり非ルートノードへと導く１つのパスだけを提供するような、１つのルートノードだけを有する非環式有向グラフである。
【００１８】
ノード−リンク構造では、“ノード−リンク関係”は、要素間のノード及びリンクのパスに基づいた要素間の関係である。
【００１９】
ノード−リンク関係を、パスの長さがパス内の要素の数によって測定されるとき、要素間の最短パスの長さに基づいて区分することが有用である。有向グラフでは、例えば、あるノードの“最も近い”ノード−リンク関係は、その入及び出リンクとの関係であろうし、次に、そのノードの親及び子ノードである他のノードとの関係、その次に、そのノードの親及び子ノードの他の入及び出リンクとの関係、その次に、そのノードの親の親、同胞、孫、及び共親(co-parent)である他のノードとの関係、等であろう。ある要素の１組の“近隣”ノード−リンク関係は、要素間の全ての最短パスの長さが、比較的短い２、３、又は４のような最大長さより全て短いというような近さの適切な基準を満たす、１組の関係である。近隣ノード−リンク関係の有用なグループの例は、ある要素の親、親の子（その要素を含む）、及び親の孫の間の関係のグループである。
【００２０】
データが、親の絶対位置から要素の絶対位置を得るために用いることができる１つ以上の変位を示す場合、そのデータは要素の“親に対する相対位置”を示す。例えば、親の位置から要素の位置までのベクトルを定義する１組の変位は、要素の親に対する相対位置を示す。変位のタイプの例としては、座標軸に沿って又は大きさ（絶対値）でのいずれかで位置間の距離を示す位置変位、及び親への入リンクと親からその要素への出リンクとの間のような角度差を示す角度変位が挙げられる。
【００２１】
本明細書では、“ナビゲーション信号”という用語は、ユーザがノード−リンク構造のある部分に他の部分よりも高い興味を持っていることを示す信号を意味する。例えば“拡張信号”は、グラフのある要素の表現が拡張されているグラフ表現を表示する要求を示し、一方“収縮信号”は、グラフのある要素の表現が収縮されているグラフ表現を表示する要求を示す。他の例は、ノード−リンク構造の一部を特定の位置で表示する要求を含み、それはブックマーク等を選択することによって、又は指し示されたフィーチャを焦点の中心へと移動することを要求するポイント及びクリック動作によって可能である。
【００２２】
図１は、どのように負曲率を有する空間にノード−リンク構造１０内の要素をレイアウトできるかを示している。ボックス２０への点線で示されるように、ノード−リンク構造１０内の要素、例示的にノード２２は、幾つかの近隣ノード−リンク関係を有する。ボックス２０で示されるように、近隣ノード−リンク関係は、例えば、親ノード２４からノード２２へのリンク、親ノード２４から同胞ノード２６及び２８へのリンク、及びノード２２から子ノード３０及び３２へのリンクの結果生じる関係を含み得る。
【００２３】
ノード−リンク構造１０からの実線及びボックス２０からの点線によって示されるように、ノード２２の近隣ノード−リンク関係に関する情報を示す、近隣関係データ４０が入手される。次に、近隣関係データ４０に基づいて、ノード２２についてのレイアウトデータ４２を入手できる。ノード−リンク構造１０に関する他の情報も、レイアウトデータ４２を入手するために用いられ得るが、ノード２２が近隣ノード−リンク関係が変更されたときにのみ再レイアウトされればよいことを確実にするために、そのような他の情報は、好ましくは、遠いノード−リンク関係に関する情報を含むべきではない。
【００２４】
レイアウトデータ４２は、ノード２２と、負曲率を有する空間での少なくともノード２２の親ノード２４に対する相対位置を含むノード２２の位置とに関する、種々の情報を示してよい。例えば、ボックス４４で示されるように、レイアウトデータ４２は、負曲空間での親ノード２４からノード２２への距離及び方向を示すベクトルＤを示すことができる。子の位置を親の位置に対して相対的に定義できるように、親から子への方向を親の親から親への方向に対して相対的に（又は、親がルートである場合は、初期方向に対して相対的に）定義できる。従って、ベクトルＤは、親からの位置変位及び親の親から親への方向の角度変位を示すことができる。
【００２５】
図２では、処理ボックス１００の処理は、ノード−リンク構造内の要素について、その要素の近隣ノード−リンク関係に関する情報を示す、近隣関係データを入手することによって開始する。処理ボックス１００の周りの内側の点線で示されるように、近隣関係データは１組の要素のうちのそれぞれについて入手できる。
【００２６】
次に、処理ボックス１０２の処理は、処理ボックス１００で入手された近隣関係データに基づいて、負曲空間での要素の親に対する相対位置を示す、レイアウトデータを入手する。処理ボックス１０２の周りの内側の点線で示されるように、レイアウトデータも同様に、処理ボックス１００で近隣関係データが入手された１組の要素のそれぞれについて入手できる。処理ボックス１００及び１０２の周りの外側の点線で示されるように、要素のレイアウトデータ入手後、別の要素について又は別の組の要素について近隣関係データを入手できる。
【００２７】
図３の装置１５０は、ユーザ入力回路１５４からユーザ信号を示すデータを受信すると共にディスプレイ１５６に画像を定義するデータを供給するために接続された、プロセッサ１５２を含む。プロセッサ１５２は、ノード−リンク構造の少なくとも一部を定義するノード−リンクデータ１５８にアクセスするためにも接続されている。プロセッサ１５２は、例えば、メモリ１６４、記憶媒体アクセス装置１６６、又はネットワーク１６８への接続から受信した命令を供給できる命令入力回路１６２を介して、命令を示す命令データ１６０を受信するためにも接続されている。
【００２８】
命令データ１６０によって示される命令を実行する上で、プロセッサ１５２は要素について、その要素の近隣ノード−リンク関係に関する情報を示す、近隣関係データを入手する。プロセッサ１５２は、ノード−リンクデータ１５８にアクセスしてノード−リンク関係に関する情報を入手できる。次に、プロセッサ１５２は、近隣関係データに基づいて、負曲率を有する空間での要素の親に対する相対位置を示すレイアウトデータを入手する。
【００２９】
上述のように、図３は、命令入力回路１６２が命令を示すデータを受信し得る３つの可能なソース、即ちメモリ１６４、記憶媒体アクセス装置１６６、及びネットワーク１６８を示している。
【００３０】
メモリ１６４は、ランダムアクセスメモリ（ＲＡＭ）又は読取り専用メモリ（ＲＯＭ）を含む、装置１５０内の任意の従来のメモリか、又は任意の種類の周辺又は遠隔メモリ装置であってよい。より一般的には、メモリ１６４は１つ以上のタイプのメモリ構成要素の組合せであってよい。
【００３１】
記憶媒体アクセス装置１６６は、例えば１組の１つ以上のテープ、ディスケット、又はフロッピーディスクのような磁気媒体、１組の１つ以上のＣＤ−ＲＯＭのような光学媒体、又はデータを格納するための任意の他の適切な媒体であり得る記憶媒体１７０にアクセスするための、ドライブ又は他の適切な装置又は回路であってよい。記憶媒体１７０は、装置１５０の一部、サーバの一部、他の周辺又は遠隔メモリ装置、又はソフトウェア製品であってよい。これらの場合のそれぞれで、記憶媒体１７０は装置１５０内に用いることができる１つの製造品である。記憶媒体１７０の上にデータユニットを配置して、記憶媒体アクセス装置１６６がデータユニットにアクセスしてそれらを命令入力回路１６２を介してプロセッサ１５２にシーケンスで供給できるようにすることが可能である。データユニットは、シーケンスで供給されると、図示されるように命令を示す命令データ１６０を形成する。
【００３２】
ネットワーク１６８は、装置１８０から受信した命令データ１６０を供給できる。装置１８０内のプロセッサ１８２は、ネットワーク１６８を渡ってネットワーク接続回路１８４及び命令入力回路１６２を介して、プロセッサ１５２との接続を確立できる。どちらのプロセッサが接続を開始してもよく、接続は任意の適切なプロトコルで確立されてよい。次に、プロセッサ１８２はメモリ１８６に格納されている命令データにアクセスして命令データをネットワーク１６８を渡ってプロセッサ１５２に転送できるので、プロセッサ１５２はネットワーク１６８から命令データ１６０を受信できる。次に、命令データ１６０は、プロセッサ１５２によってメモリ１６４又はどこかに格納され、実行されることが可能である。
【００３３】
上述した全般的なフィーチャは、ノード−リンク表現を表示するための多くの方法で様々な装置上で実施されてよい。以下に述べる実施例は、マイクロソフトウインドウズ(Microsoft Windows)の32ビット版を走らせ、Ｃ++言語ソースコードからコンパイルされたコードを実行する、ＰＣに基づくシステム上で実施されたものである。
【００３４】
図４では、システム２００は、画像を表示するためのディスプレイ２０４、及びユーザから信号を供給するためのマウス２０８及びキーボード２０６に接続された、ＰＣプロセッサ２０２を含む。ＰＣプロセッサ２０２は、メモリ２１０及びクライアント２１２にアクセスできるようにも接続されている。メモリ２１０は、例示されているように、プログラムメモリ２１４及びデータメモリ２１６を含むことができる。クライアント２１２は、メモリ２１０に格納されたルーチン及びデータの組合せか、又は示されるようにメモリ２１０から独立していてよい、有向グラフに関する情報のソースである。例えば、プロセッサ２０２はネットワークを介してクライアント２１２と通信してもよい。
【００３５】
プログラムメモリ２１４に格納されているルーチンは、幾つかの機能にグループ化できる。グラファルーチン２２０は、クライアント２１２からの情報によって定義される有向グラフを表わすデータ構造を生成及び変更する。ウォーカルーチン２２２は、有向グラフデータ構造から情報を入手することによって、キーボード２０６及びマウス２０８からのナビゲーション信号及び他のユーザ信号に応答する。ペインタルーチン２２４は、ディスプレイ２０４に信号を提供して有向グラフデータ構造の表現を表示させる。数学ルーチン２２６は、レイアウト空間内の有向グラフの要素の位置を得るために呼出されることができる。
【００３６】
次に、データメモリ２１６は、プログラムメモリ２１４内のルーチンの実行中にプロセッサ２０２によってアクセスされるデータ構造を収容する。有向グラフデータ構造２３０は、上述のように、グラファルーチン２２０によって生成及び変更され得ると共に、ウォーカルーチン２２２及びペインタルーチン２２４によってアクセスされ得る。
【００３７】
有向グラフデータ構造２３０内にリンクされ得る又は含まれ得るノード位置データ２３２は、双曲平面のような負曲空間内、及び２次元ユニットディスク（単位円）のようなレンダリング空間内のノードの位置を含むことができる。ノード位置データ２３２はプログラムメモリ２１４内のルーチンによってアクセスされ得る。
【００３８】
プログラムメモリ２１４内のルーチンは、種々の雑データ構造２３４にもアクセスできる。データ構造２３４は、例えば、標準ヒープとして実施される、１対のノードＩＤからリンクＩＤへのマッピングのための予備データ構造を含んでもよい。即ち、この予備データ構造は、一定の期待時間内のリンクＩＤの検索及び挿入を可能にする。
【００３９】
図５は、どのように図４のシステムがグラフの表現を表示することによってイベントに応答できるかを示している。
【００４０】
処理ボックス３００では、クライアント２１２は、開始グラフを入手すると共に、例えばノード生成の呼出しを介して、要素の初期セットをメモリにロードすることによって開始する。拡張フラグは要素の初期セット内のツリーを定義する。クライアント２１２は、双曲平面にツリーをレイアウトし、ツリーを双曲平面からユニットディスクへと、ルートノードをディスクの中心においてマッピングし、マッピングされたツリーをペイントし、二重バッファをスワッピングすることによってペイントされたバージョンをディスプレイ２０４に表示することを、全て処理ボックス３００で行うために、メモリ２１４内のルーチンに対する適切な呼出しも行う。
【００４１】
処理ボックス３０２では、クライアント２１２はグラフに関係するイベントを受信する。イベントはナビゲーション信号、編集信号、又はユーザからの他のタイプの信号から生じ得る。或いは、イベントはシステム２００の内部又は外部いずれかの他のソースから受信されてもよい。いずれにせよ、イベントはクライアント２１２内から、メモリ２１４内のルーチンの１つから、又はプロセッサ２０２によって実行される他の命令からの呼出しの形態をとり得る。一連の受信されたイベントは、処理ボックス３０２がキューからのイベントの取り出しを含み得るように、キューの中に保持され得る。
【００４２】
処理ボックス３０２で受信されたイベントに応答して、クライアント２１２は、メモリ２１４内のルーチンに対して１つ以上の呼出しを行うことによって、適切な応答を開始する。判断ボックス３０４によって示されるように、応答はイベントのタイプによるので、イベントに基づいてブランチが選択される。
【００４３】
イベントは、オリエンテーション転換イベント、ストレッチイベント、又はドラッグイベントのような、非アニメーションイベントであってもよい。オリエンテーションイベントは、ユーザがルートノードに対して新たなオリエンテーションを示したときに生じ得る。ストレッチイベントは、ユーザが表示されている表現に対して新たなストレッチファクタを示したときに生じ得る。ドラッグイベントは、例えば、ユーザが、マウスダウン（マウスボタンを押したまま）クリック等によって表現内の位置を選択し、適切なジェスチャ又は他の信号によってその位置の移動を要求したときに生じ得る。
【００４４】
処理ボックス３１０では、クライアント２１２は、イベントへの応答に必要な任意の情報を入手することによって、非アニメーションイベントに対する応答を開始する。オリエンテーションイベントについては、処理ボックス３１０で入手された情報が新たなオリエンテーションを含むことができる。ストレッチイベントについては、処理ボックス３１０で入手された情報が新たなストレッチファクタを含むことができる。
【００４５】
ドラッグイベントについては、処理ボックス３１０での情報の入手は幾分複雑さが増す。クライアント２１２は、選択位置から最も近いノードのノード識別子（ノードＩＤ）を入手してもよく、また、要求された動きに関する情報を入手してもよい。情報のこれらの項目は、本明細書に参照として援用する米国特許第5,590,250号のコラム７１−７２及び図１４に関係して記載されている“最も近いノードを探索”という関数（機能）によって説明されているのとほぼ同じ方法で入手してもよい。
【００４６】
クライアント２１２が処理ボックス３１０で必要な情報を入手したら、クライアント２１２はレイアウト、マッピング及びペイントのためのウォーカルーチン２２２及びペインタルーチン２２４に対する適切な呼出しで締めくくることができる。オリエンテーションイベントについては、ルートノードは新たなオリエンテーションでレイアウトされなくてはならない。ストレッチイベント又はドラッグイベントについてはレイアウトは必要ない。しかしながら、ストレッチイベントについては、ウォーカルーチン２２２に対する呼び出しが、マッピングに用いるための新たなストレッチファクタを含まなければならない。同様に、ドラッグイベントについては、ウォーカルーチン２２２に対する呼び出しが、マッピングに用いるための最も近いノードのノードＩＤ及び動きのパスに沿った次の位置を含まなければならない。
【００４７】
処理ボックス３１２では、ウォーカルーチン２２２は、まず、双曲平面内に任意の必要なレイアウトを行ってもよく、また、ツリーの任意の保留中の編集をレイアウトしてもよい。次に、処理ボックス３１４では、ウォーカルーチン２２２は、開始ノードを開始位置において開始して、ツリーをユニットディスクにマッピングしてもよい。例えば、ドラッグイベントに応答して、開始ノードは処理ボックス３１０で識別された最も近いノードであってよく、開始位置は動きのパスに沿った次の位置であってよい。前にマッピングに用いられた開始ノード及び開始位置を、オリエンテーション又はストレッチイベントに応答して用いてもよい。
【００４８】
ツリーがマッピングされたら、処理ボックス３１６で、マッピングされたツリーを表示バッファにペイントするためにペインタルーチン２２４を呼出すことができる。ペイント中、ペインタルーチン２２４はノード生成の結果ツリー内で生じる新たな編集をマーキングできる。各編集は、フラグを設定することによって又は他の適切なデータを格納することによってマーキングできる。ペイントが完了すると、ペイントされたようにツリーを表示するために表示バッファのスワッピングを行うことができ、グラフの表現が供給される。
【００４９】
上述のように、これらのイベントは現在は非アニメーションイベントとして実施される。オリエンテーションイベントに応答して、表現は新たなオリエンテーションに、典型的には表示領域の焦点にあるノードの周りを、旋回する。同様に、ストレッチイベントに応答して、表現は半径方向に、典型的には焦点にあるノードの周りで、拡張又は収縮する。ドラッグイベントに応答して、表現は入力信号によって決定されたレートで移動する。しかしながら、クライアント２１２は、オリエンテーションイベント、ストレッチイベント、又はドラッグイベントに対して、要求された変更を同等のより小さなイベントのシーケンスに変換し、処理ボックス３１０で、１つの呼出しが個々のより小さなイベントに対する一連の呼出しを発することによって、アニメーション化された応答を供給してもよい。
【００５０】
図５は、現在の実施では常にアニメーション化して扱われる２つの異なるタイプのイベントに対する応答も示している。第１のタイプはブックマーク又はクリックイベントであり、それに応答して、アニメーションシーケンス中に１つのノードの位置が移動され、他の要素がその１つのノードの動きに合わせて移動する。第２のタイプは挿入/削除イベントであり、それに応答して、ある要素が収縮され別の要素が拡張されるアニメーションシーケンス中に、１つのノードは安定したままであるが、他の要素は収縮及び拡張に合わせて移動する。
【００５１】
ブックマーク又はクリックイベントは、ユーザがメニュー又は他のブックマークの集合の中の項目を選択したとき、又はマウスダウンアップ（マウスボタンを押して放す）クリックで表現内の位置を選択したときに生じ得る。このタイプのイベントに応答して、クライアント２１２はノードＩＤ及びユニットディスク内の宛先位置を入手する。ブックマークイベントの場合は、ノードＩＤ及び宛先位置は以前に格納されており、メモリから検索できる。クリックイベントの場合は、クライアント２１２は、本明細書に参照として援用する米国特許第5,590,250号のコラム７１−７２に関係して記載されている“最も近いノードを探索”という関数（機能）とほぼ同じ方法で、選択位置から最も近いノードのノードＩＤを入手してもよく、宛先はユニットディスクの中心のようなデフォルト位置であってよい。
【００５２】
処理ボックス３２０では、クライアント２１２はウォーカルーチン２２２をノードＩＤ及び宛先位置で呼出してもよい。ウォーカルーチン２２２は、ノードが前の位置から宛先位置へと移動する表現のシーケンスを表示するためのアニメーションループを実行することによって応答できる。処理ボックス３２０では、ウォーカルーチン２２２は、個々がノードＩＤ及びユニットディスク内の位置を含むノード/位置の対のシーケンスをセットアップすることによって開始する。位置は、米国特許第5,619,632号の図１２のボックス４７０、４７２、及び４８２に記載されているように、前の位置から宛先位置への総トランスレーション（移動路）を入手して、次に総トランスレーションのｎ番目のルートを入手して現在のトランスレーションと共に構成することを繰り返すことによって入手できる。ノード/位置の対の数は、アニメーション表示中に構造の要素を表わすフィーチャがオブジェクト不変性を維持しながら、前の位置から宛先位置への滑らかなアニメーションを確保するために、十分に大きくできる。ｎ番目ルートの方法の代わりに、前の位置から宛先位置へと双曲平面内で適切に選択された弧に沿って適切な数の点を選択することによって、位置を入手してもよい。弧は、不自然に見え得る直線と、ｎ番目ルートの方法でノードがとったであろう、滑らかに見えるには過度のアニメーションステップ数を必要とし得る弧との間を折衷するように選択されてもよい。点の数は、満足なアニメーションを確保するように選択されてもよい。
【００５３】
処理ボックス３２０で位置を入手する上で、オリエンテーションは米国特許第5,590,250号の図１５に関係して述べられているように保存できる。或いは、変形又は回転を、ユニットサークルの境界上の特定の点の位置が保存されるように選択できる。選択された点は、例えば、サークル上の、ルートの子がレイアウトされた方向から反対方向の点であってもよい。
【００５４】
次に、ウォーカルーチン２２２は、判断ボックス３２２で示されるように、シーケンス中のノード/位置の各対についてアニメーションループを反復する。処理ボックス３２４では、ウォーカルーチン２２２は、処理ボックス３１２に関係して上述したように、まず双曲平面にツリーの任意の保留中の編集をレイアウトしてもよい。次に、処理ボックス３２６では、ウォーカルーチン２２２は、処理ボックス３１４に関係して上述したように、ツリーをユニットディスクに、次のノード/位置の対からのノード及び位置を開始ノード及び開始位置として開始して、マッピングしてもよい。
【００５５】
ツリーがマッピングされたら、処理ボックス３２８でマッピングされたツリーを表示バッファにペイントするためにペインタルーチン２２４を呼出すことができる。ペイント中、ペインタルーチン２２４は、処理ボックス３１６に関連して上述されたように、ノード生成の結果ツリー内で生じる新たな編集をマーキングできる。ペイントが完了したら、ツリーをペイントされたように表示するために表示バッファのスワッピングを実行して、グラフの表現を提供することができる。
【００５６】
処理ボックス３２８でペインタルーチン２２４によって新たな編集がマーキングされると、次の反復中、処理ボックス３２４で、新たな編集がレイアウトされる。その結果、表現のアニメーション化されたシーケンスは、米国特許第5,629,632号のように静的ノード−リンク構造を示すのではなく、動的ノード−リンク構造を示す。しかしながら、この編集は、基本的には、表現が前の位置から宛先位置へと遷移するときに表現の外周に沿って新たなノードを表わすフィーチャを追加するために働く。その結果、追加されたフィーチャは、他の要素を表わすフィーチャについてのオブジェクト不変性の知覚を妨害又は低下させない。
【００５７】
挿入/削除イベントは、ユーザがノードの拡張又は収縮を要求したときに、又はグラフ又はツリーの何か他の変更を要求したときに生じ得る。挿入/削除イベントは、呼出しの形態でも受信されてもよく、従って、人の手による制御を並行させないグラフ又はツリーの自動変更のための機構を提供してもよい。
【００５８】
このタイプのイベントに応答して、クライアント２１２は、処理ボックス３３０で、要求されたグラフ又はツリーの変更が許容可能か否かを決定するために、まずメモリ２１４内のルーチンに対する適切な呼出しを行うことができる。
【００５９】
要求されたグラフ又はツリーの変更が許容可能な場合は、それに従って、クライアント２１２は、必要に応じてメモリ２１４内のルーチンを呼出して、グラフ又はツリーを変更できる。変更を行うプロセスでは、変更によって挿入、削除、又は変化させられ得る、本明細書では“影響された要素”と呼ぶ各要素が、フラグの設定又は他の適切なデータの格納等によってマーキングされる。あるノードが拡張信号又は収縮信号によって選択された場合は、その親に割当てられた領域が変化し得るので、その親も影響されたノードである。他の挿入/削除イベントのほとんどについては、挿入又は削除されたノードだけが影響される。クライアント２１２は、あるノードが、変更のアニメーション表示中もそのノードの前の位置に保持される、安定ノードとして選択できる。
【００６０】
多くの場合、前にマッピングに用いられた開始ノードを安定ノードとして選択することができ、そのノードを前の開始位置に保持することができる。他の場合には、クライアント２１２にとって、異なる安定ノードの選択が望ましいことがある。例えば、拡張されているノードを、現在の位置に保持される安定ノードとして選択してもよく、従ってそのノードが新たな開始位置となる。従って、クライアント２１２が異なる安定ノードを選択しない限り、通常は前の開始ノード及び開始位置が保たれる。しかし、前の開始ノードが削除されている場合は、他のノードがクライアント２１２によって変更されるデフォルト安定ノードとして選択されなければならない。
【００６１】
削除が行われているとき、削除中のノード及びマッピング中のツリー内に削除後も残る最も近い祖先のノードＩＤでウォーカルーチン２２２を呼出すことができる。この祖先は、削除中のノードから現在の挿入/削除イベントによって削除されていない祖先に到達するまで上向きに巡回する(walk)ことによって、見つけることができる。
【００６２】
この呼出しに応答して、ウォーカルーチン２２２は、削除中のノードが前の開始ノードか否かをテストできる。そうである場合は、識別された祖先を、開始ノードとして、削除中のノードと置換するために選択することができる。祖先が表示されている位置に最近マッピングされたものであり、それが使用可能な位置である場合は、その位置を開始位置として選択できる。祖先が最近マッピングされたものではない、又は、表示されない位置又は現在他の要素がマッピングされているために使用不可能な位置にマッピングされたものである場合は、開始位置をユニットディスクの中心にすることができる。
【００６３】
処理ボックス３３０でも、クライアント２１２は安定ノードのＩＤ及び位置でウォーカルーチン２２２を呼出してもよい。ウォーカルーチン２２２は、まず削除されたノードが前の位置で収縮され、次に挿入されたノードが新たな位置で拡張され、その間ずっと、安定ノードは前の位置に保持されるという、表現のシーケンスを表示するアニメーションループを実行することによって応答できる。安定ノードが、最近マッピングされたものではない、又は表示されない位置又は使用不可能な位置にマッピングされたものであるので前の位置に保持できない場合は、前の開始ノードが前の開始位置にある状態で、削除されたノードが収縮された後に、安定ノードをその位置に移動することができ、その結果、収縮と拡張との間の突然の動きが生じる。ウォーカルーチン２２２は、収縮及び拡張中、影響された各ノードに割当てられた領域が変化するレートを支配する、重みのシーケンスをセットアップすることによって開始する。重みは、アニメーション表示中のオブジェクト不変性を保つために、十分に小さい増分で区分されている。
【００６４】
次に、ウォーカルーチン２２２は、判断ボックス３３２で示されるように、シーケンス中の各重みについてアニメーションループを反復する。処理ボックス３３４では、ウォーカルーチン２２２は、反復の重みを用いて、まず双曲平面に影響されたノード及びツリーの任意の保留中の編集をレイアウトしてもよい。次に、処理ボックス３３６では、ウォーカルーチン２２２は、処理ボックス３１４に関係して上述されたように、ツリーをユニットディスクに、安定ノード及び位置で開始して、マッピングしてもよい。
【００６５】
ツリーがマッピングされたら、処理ボックス３３８で、マッピングされたツリーを表示バッファにペイントするために、ペインタルーチン２２４を呼出すことができる。ペイント中、ペインタルーチン２２４は、処理ボックス３１６及び３２８に関係して上述されたように、ノード生成の結果ツリー内で生じる新たな編集をマーキングできる。ペイントが完了したら、ツリーをペイントされたように表示するために表示バッファのスワッピングを実行して、グラフの表現を提供することができる。
【００６６】
保留中の編集が存在してもしなくても、判断ボックス３３２で開始するアニメーションループの一連の反復は、削除及び/又は挿入による動的ノード−リンク構造の表現を生成する。更に、影響された要素は、削除及び挿入の前の位置から新たな位置へと移動する。この技術は、これらの動きの間のオブジェクト不変性を生み出すために、うまく実現された。
【００６７】
処理ボックス３１６で表現が供給された後、又は判断ボックス３２２又は３３２でアニメーションシーケンスが完了した後、図５の“Ａ”と表示された円によって示されるように、処理ボックス３０２で別のイベントを受信できる。
【００６８】
図６は、図５の処理ボックス３００でレイアウトが最初にどのように実行できるかを示している。図７は、処理ボックス３１２、３２４、及び３３４で、変更されたノード−リンク構造のレイアウトがどのように実行できるかを示している。
【００６９】
処理ボックス３５０で示されるように、ウォーカルーチン２２２は、ルートノードＩＤを入手して有向グラフデータ構造２３２内のルートノードに関係するデータにアクセスするために用いることによって、最初のレイアウトを開始する。処理ボックス３５２では、ウォーカルーチン２２２は、角度幅で数学ルーチン２２６に対する呼出しを行うことによってルートノードをレイアウトする。この角度は、望ましい結果を生成する任意の適切な角度でよい。角度2π及びπ/2がうまく用いられ、2πを用いた場合は中心レイアウトスタイルに適しており、π/2を用いた場合は上、下、右、又は左レイアウトスタイルに適していた。望ましい結果を得るためにこの角度を修正するために、インタフェースが提供されてもよい。
【００７０】
応答では、数学ルーチン２２６はルートノードを、ユニットサークルの原点、即ち座標（0,0）に、上向きのオリエンテーションで座標（0,1）に、及び角度幅の半分の角度でレイアウトする。次に、処理ボックス３５４で、ウォーカルーチン２２２はルートノードＩＤをキューの前にプッシュする。
【００７１】
図６の残りでは、判断ボックス３６０で示されるように、ウォーカルーチン２２２は、有向グラフデータ構造２３２によって定義されるツリーの１組の要素を、キューが空になるまで、繰返し走査する。各反復は、キューの後からノードＩＤを入手し、それを有向グラフデータ構造２３２内の識別されたノードに関係するデータにアクセスするために用いることによって開始する。
【００７２】
各反復で、判断ボックス３７０でのテストは、ノードがこの走査で既に巡回されたか否かを決定する。巡回されていない場合は、ウォーカルーチン２２２は処理ボックス３７２で巡回済ノードをマーキングし、複数の子のノードＩＤを入手し、複数の子のうちの非拡張リーフ、即ち拡張された入リンクを持たないリーフノードを識別し、以下に説明するように可視ツリー内に存在する子の数を入手し、同じく以下に説明するように、可視ツリー内の複数の子についての角度及び半径のアレイを入手するために、可視ツリー内に存在するノードの子の数Ｎで数学ルーチン２２６を呼出す。
【００７３】
処理ボックス３７２での処理については、近隣関係データの１タイプである可視ツリー内の子の数Ｎは、２通りの方法のいずれかで計算できる。即ち、現在の走査がノード追加ステップのシーケンスの一部である場合は、Ｎは走査前の子の数と追加された子の数との合計に等しい。現在の走査がノード除去ステップのシーケンスの一部である場合は、Ｎは単に走査前の子の数に等しい。
【００７４】
処理ボックス３７２では、角度及び半径のアレイは様々な方法で入手できる。１つの成功した実施例では、各半径は0.7の値に設定され、一方、各角度は ((Ｎ*π)/18)とπとのより小さい方に設定される。従って、Ｎ<18については、ノードの角度は可視ツリー内に存在するそのノードの子の数に左右される。
【００７５】
次に、処理ボックス３７４で、ウォーカルーチン２２２は子をレイアウトするために数学ルーチン２２６を呼出す。
【００７６】
処理ボックス３７４を実施する際、レイアウトの２つの一般原則が適用される。第１に、ノード間の離間及び角度は、ツリー内の近隣要素に関する情報、即ち近隣関係データだけに基づいて決定される。第２に、各ノードについて入手されたレイアウト情報は、あるノード及びその全ての子の位置がデータ構造内の小さな変化で移動できるような方法で、ノード対その親の相対位置を示す。
【００７７】
従うことのできる一般戦略は、処理ボックス３７２からの子の半径及び角度で開始し、子が必要とする近似距離を入手し、近似距離を用いて親からの距離を入手し、親からの距離を用いて子についてのより正確な距離を入手し、次に、随意的により正確な距離を用いて更により正確な距離を入手する、等である。
【００７８】
一般戦略に従って、子が処理ボックス３７２からの半径R及び角度Θを有する場合は、近似距離D1及びD2をそれぞれsinh(R)及びtan(Θ/4)として計算できる。Nがレイアウト実行中の子の数であり、合計がi=1からN-1まで実行される場合に、それぞれの近接した子の対が、それぞれのD1及びD2の合計のより大きい距離、即ちDT=Σ(max(D1(i)+D1(i+1),D2(i)+D2(i+1))+max(D1(1),D2(1))+max(D1(N),D2(N))によって分けられているとき、D1及びD2を用いて、全ての子についての総距離DTを得ることができる。その親が使用可能な角度ωを有する場合、親からの距離DPはasinh(DT/ω)として計算できる。次に、子を、親を中心とする半径DPの円の円周に沿って、子の分割に比例する子の間の角度で配置できる。
【００７９】
次に、DPを用いて、子についてのより正確な距離を以下のように得ることができる。
D1'=sinh(DP)asin(sinh(R)/sinh(DP))、
D2'=2sinh(DP)atan(tan(Θ/4)/e^DP)
次に、D1'及びD2'を用いて、上述の方法等のように、所望のレベルの正確さに到達するまで、親までのより正確な距離DP'を得ることができる。その時点で、それぞれの子のオリエンテーションを親のオリエンテーションからの角度のずれとして計算できる。
【００８０】
上述の距離は双曲平面内の実際の計量で表わされていることに注目されたい。双曲平面内の距離Dは、ユニットサークル内の原点で開始してtanh(D/2)の距離を進むベクトルに対応する。
【００８１】
処理ボックス３７２に関係して上述したように、一般戦略はこのようにして、ノード、その親、及び可視ツリー内の同胞の子に関する情報を含む同胞に関する近隣関係情報だけに基づくレイアウト情報を入手する。一般戦略は、子からその親までの距離と、子とその親とのオリエンテーションの違いを表わす角度とを示す、レイアウト情報を入手する。
【００８２】
一般戦略は、全ての子について２つの反復ループを遂行するが、一般戦略に関係して上述した方法でより正確な距離を得る試みをせずに得られる最初の距離を用いるソフトウェアとして実施された。第１のループは、隣接する子の間の分離及び各子についての“スライスサイズ”を入手して一時的に保存し、分離の合計も入手する。次に、この情報を用いて親までの距離を得る。次に、第２ループは、各子の相対的なオリエンテーション及び領域を入手して保存する。
【００８３】
このソフトウェアとしての実施例では、子が処理ボックス３７２からの半径R及び角度Θを有する場合は、一般戦略に関係して上述したように距離D1及びD2が計算される。各子についてのD1及びD2を前の子についてのD1及びD2に加え、S1及びS2を得る。分離の合計STは、最初と最後の子についてを除き、子のS1及びS2の最大値に増加され、最初と最後の子については、STはその子のD1及びD2の最大値に増加される。
【００８４】
子のS1がその子のS2より大きい場合は、S1が子の分離として保存されると共にまずD1が子のスライスサイズとして保存され、２番目以降の子については、前の子のスライスサイズがその子の前のスライスサイズとその子のS1との最小値となるように調整される。逆に、子のS1がその子のS2より大きくない場合は、S2が子の分離として保存されると共にまずD2が子のスライスのサイズとして保存され、２番目以降の子については、前の子のスライスサイズがその子の前のスライスサイズとその子のS2との最小値となるように調整される。しかしながら、最後の子のスライスサイズは、その子の前のスライスサイズとその子のD1及びD2の最大値との最小値となるように調整され、第１の反復ループが完了する。
【００８５】
次に、親の角度ωを用いて、ユニットディスク内の親からの距離DPをtanh(asinh(ST/2ω)/2)又は0.5の大きい方として計算することができる。DPは親ノードに関連するデータの一部として保存される。
【００８６】
第２の反復ループは、各子について、Sが子についての保存された分離であるとき、角度(S/ST)2ωを計算することによって開始する。角度(S/ST)2ωは、-2ωで開始したランニングトータルに加えられる。ランニングトータルは子に関連する他のデータと共に保存される。
【００８７】
次に、数学ルーチン２２６は、米国特許第5,590,250号のコラム６７及び６８の“内角(inside-angle)”関数に類似の関数を呼出すことによって、子についての新たな角度を計算できる。この、本明細書では“インサイドアングル(InsideAngle)”と呼ぶ関数は、楔の中へと移動された距離(“dist”)及び楔の半分の角度で開始する。インサイドアングルは作動可能角度として、開始角度と、εが0.0001のような非常に小さい値を有し得るときの（π−ε）との、小さい方をとり、逆タンジェントの計算における問題を回避する。インサイドアングルは、ユニットサークル上の座標(dist,0)にある点を原点へと移動する変形を入手する。次に、インサイドアングルは、ユニットサークルの円周と、原点から発する、水平位置との角度が作動可能角度である放射線との交点にある点の複合座標に、この変換を適用する。インサイドアングルは、結果の角度として、原点から変換された点を通る放射線の水平位置からの角度を戻す。
【００８８】
子の角度を得るために、インサイドアングルは、距離DP及び第１反復からの子のスライスサイズを２ω/STで乗算することによって計算された角度で呼出される。インサイドアングルによって戻された角度はπ/2と比較され、子の角度はこの２つのうちの小さい方である。
【００８９】
子の新たな角度を保存する前に、数学ルーチン２２６は子の前の角度を保存する。古い角度と新しい角度との差の絶対値が最小値を越える場合は、数学ルーチン２２６は、以下に述べるように、レイアウトが継続すべきであることを示すデータも保存する。
【００９０】
最後に、第２反復ループは、米国特許第5,590,250号のコラム６７及び６８の“空間使用可能(room-available)”関数（機能）と類似の関数を呼出すことによって、子の領域又はサイドスペースを得る。本明細書では“ルームアベイラブル(RoomAvailable)”と呼ぶこの関数は、楔の中へと移動された距離D及び楔の半分の角度Φで開始する。ルームアベイラブルは、まず比(1-D²)/2Dを得ることによって、次に初期距離Sを得るために比をsinΦで割ることによって計算される、楔のエッジまでの距離を戻す。次に、ルームアベイラブルは距離((S²-1)^1/2-S)を戻す。子の領域を得るために、ルームアベイラブルは上述のインサイドアングルの呼出しに用いられたのと同じ距離及び角度で呼出される。ルームアベイラブルによって戻された距離は子の領域の尺度として保存される。
【００９１】
上述のソフトウェアとしての実施例は付加的なデータを保存できるにも関わらず、ソフトウェアとしての実施例は、本明細書に述べるように、レイアウト及びマッピングを実行できるためには、各ノードについて２項目のデータだけ格納される必要があるという発見に基づいている。一方の項目は、距離即ち双曲平面内のノードからその子ノードまでの位置変位を示す。他方の項目は、そのノードの親までの入リンク及びその親からそのノードへの出リンクの拡張の間の双曲平面内の角度変位である。これらの２項目のデータ、又はそれらにアクセスするために用いることができるハンドルは、有向グラフデータ構造内のリンクのデータ項目に含まれることができる。
【００９２】
判断ボックス３８０のテストは、ノードの次の世代までレイアウトを継続するか否かを決定するために適切な基準を適用する。処理ボックス３７４に関係して上述されたように、基準は、任意の子ノードの角度が0.00001のような小さな角度の違い以上の変更をされているか否かであり得る。そうである場合は、レイアウトを継続すべきである。
【００９３】
処理ボックス３８２では、ウォーカルーチン２２２は、拡張されている又はリーフではない各子ノードのIDを、キューの前にプッシュする。他の子ノードは、レイアウトされる子を持たないので、処理ボックス３８２でマーキング巡回されてよい。処理ボックス３８２が完了すると、又は判断ボックス３８０のテストが継続しないと決定すると、又は判断ボックス３７０のテストがノードがすでに巡回されたと決定すると、判断ボックス３６０に戻る前に処理ボックス３８４でキューの後のノードが取り出される。
【００９４】
図７は、図５の処理ボックス３１２、３２４、及び３３４で、どのように変更されたノード−リンク構造のレイアウトが実行できるかを示している。それぞれの場合に、レイアウトは、処理ボックス４００で示されるように、レイアウト及びマッピングへと導く呼出しに応答して開始する。しかしながら、判断ボックス４０２のブランチによって示されるように、レイアウトが実行される方法はノード−リンク構造になされた変更のタイプによる。
【００９５】
変更が、オリエンテーションイベントに応答したルートノードのオリエンテーションの変更である場合は、処理ボックス４０４で、ウォーカルーチン２２２は数学ルーチン２２６を呼出し、マッピング及びペイントの前にルートノードを新たなオリエンテーションにレイアウトすることができる。ルートノードは、新たなオリエンテーション以外では、図６の処理ボックス３５２に関係して上述されたようにレイアウトできる。次に新たなオリエンテーションがマッピングに用いられ、表現のオリエンテーションを変える。
【００９６】
変更が、ストレッチイベント、ドラッグイベント、ブックマークイベント、又は編集が保留中の場合のクリックイベントに対する応答で生じ得るように非アニメーション編集である場合は、ウォーカルーチン２２２は、処理ボックス４１０で、まず除去編集のリストをセットアップし、次に処理ボックス４１２で、マッピング及びペイント前に除去編集をレイアウトする。次に処理ボックス４１４で、ウォーカルーチン２２２は追加編集のリストをセットアップし、次に処理ボックス４１６で、マッピング及びペイント前に追加編集をレイアウトする。
【００９７】
この実施では、編集のリストは、グラファルーチン２２０及びペインタルーチン２２４を含むメモリ２１４内の種々のルーチンによって維持される編集ソースリストに基づいてセットアップされる。現在の実施は、拡張されたリンクによって定義されるツリーにも関係する。本明細書で“コラプストリンクス(CollapsedLinks)”及び“エキスパンデッドリンクス(ExpandedLinks)”と呼ぶ１対の編集ソースリストは、それぞれ収縮要求及び拡張要求によって選択されたリンクについての編集を含み、従って、図５の処理ボックス３３０でセットアップできる。本明細書で“リムーブドリンクス(RemovedLinks)”及び“アディッドリンクス(AddedLinks)”と呼ぶ他の対は、それぞれ削除及び挿入されたリンクについての編集を含む。編集ソースリストのコピーは、異なる目的で複数存在していてもよい。
【００９８】
処理ボックス４１０でセットアップされた除去編集のリストはリムーブドリンクスに基づいており、一方、処理ボックス４１４でセットアップされた追加編集のリストはアディッドリンクスに基づいている。処理ボックス４１０又は４１４でリストをセットアップする際に、ウォーカルーチン２２２は適切な編集ソースリスト内の各編集にアクセスし、その編集用いてセットアップ中のリストについての適切なエントリを入手する。それぞれの場合に、編集ソースリスト内の編集を用いて、編集のリンクの子ノードのノードＩＤ及び実行中の編集のタイプを示す編集識別子を入手する。
【００９９】
その子ノードの親は、既にリスト上に存在するのではない限り、影響されたノードのリストの後に加えられる。親は、その子ノードの拡張された親ノードか、又は、その子ノードの親ノードが現在どれも拡張されていない場合は、その子ノードの最初の親ノードである。編集ソースリストからの編集が親を持たない子ノードに関係する場合は、その編集はそのルートに関係しなければならず、従ってその場合は、そのルートノードが影響されたノードのリストの後に置かれる。
【０１００】
ソース編集リストからのリンクについての反復の最後に、次の反復に用いられる適切な編集ソースリスト内の次の編集にアクセスする前に、そのリンクの子ノードも子ノードリストに追加される。このように、影響されたノード及び子ノードのリストを完成するために全ての編集が処理されるまで、編集ソースリストの各編集について反復が行われる。
【０１０１】
次に、処理ボックス４１２又は４１６では、リストを用いて編集がレイアウトされ、影響されたノードのリスト内の各ノードについて図６の処理ボックス３５４から３８２のシーケンスに類似のシーケンスを辿り、ソフトウェアのノードをリストから、ルートノードよりもキューの前にプッシュし、処理ボックス３７２で、次のように幾つかの変更を行う。処理ボックス４１２及び４１６のレイアウトは、どの子が非拡張リーフであるかの識別に加えて、各子が子ノードリストに存在するか否かを決定する。そうである場合は、レイアウトはその子についての角度及び半径を重みで乗算する。処理ボックス４１２では、重みが０なので、処理ボックス３７４でその子はほぼその前の位置に角度及び半径が０でレイアウトされ、従って消滅する。処理ボックス４１６では、重みが１なので、処理ボックス３７４でその子は新たな位置に全角度及び全半径でレイアウトされる。
【０１０２】
処理ボックス４１０から４１６の操作もアニメーションシーケンス内で実施されてもよく、その場合は、除去編集はアニメーションシーケンスの最初の部分で処理されてもよく、追加編集はシーケンスの後続部分で処理されてもよい。一方、図５に関係して上述したように主にペイント中のノード生成から非アニメーション編集が生じる場合は、その編集は追加編集だけであってよく、アニメーションシーケンスの各ステップで全ての現在保留中の編集が処理されてもよい。
【０１０３】
要素を収縮又は拡張する要求のように挿入/削除イベントに応答して、変更がアニメーション化編集である場合は、ウォーカルーチン２２２は、処理ボックス４２０で、まずソース編集リストに基づいて除去及び追加される要素の数を入手する。除去される数は、コラプストリンクス及びリムーブドリンクス内の要素の数を加算することによって得ることができ、一方、追加される数は、エキスパンデッドリンクス及びアディッドリンクス内の要素の数を加算することによって得ることができる。次に、処理ボックス４２２で、ウォーカルーチン２２２は、除去ステップと追加ステップとの間に使用可能なアニメーションステップを割付け、幾分図７の処理ボックス４１０及び４１４のように、除去編集及び追加編集のリストもセットアップする。アニメーションステップの単純な割付けは、半分の除去ステップと半分の追加ステップであるが、除去される要素が無い場合は全てのステップが追加ステップとなり得、追加される要素が無い場合はその逆である。
【０１０４】
処理ボックス４２２での除去編集及び追加編集リストのセットアップにおいて、ウォーカルーチン２２２は、収縮又は拡張されたノードが存在しない限り、処理ボックス４１０及び４１４に関係して上述したように行うことができる。収縮又は拡張されたノードの場合は、ノード自体が、その親に加えて、影響されたノードリストの後にプッシュされ、次に、そのノード自体ではなくそのノードの子が、子ノードリストに加えられる。言い換えれば、収縮又は拡張は、１つのノードだけに影響する他の操作とは異なり、２世代のノードに影響すると考えることができる。ウォーカルーチン２２２は、影響されたノード及び子ノードの２対のリストをセットアップし、１対を除去編集に、もう１対を追加編集に用いる。
【０１０５】
次に、判断ボックス４３０で開始するループで、ノードを除去するアニメーションステップが実行され、処理ボックス４３２で、重みを入手し、重みを用いて除去編集をレイアウトし、アニメーションフレームをマッピング及びペイントする。同様に、次に判断ボックス４４０で開始するループでノードを追加するアニメーションステップが実行され、処理ボックス４４２で、重みを入手し、重みを用いて追加編集をレイアウトし、アニメーションフレームをマッピング及びペイントする。ノードを追加する前にノードを除去することによって、単一フレーム内で同一ノードが２箇所に出現する状況が防止される。ノードを除去した後に１つの最終ステップを重み０で実行し、ノードを追加した後にもう１つの最終ステップを重み１で実行することによって、この技術は最終重みがそれぞれ０又は１であることを確実にできる。
【０１０６】
処理ボックス４３２で、除去アニメーションステップ数から現在の除去アニメーションステップ番号を引き、次にその差を除去アニメーションステップ数で割ることによって、一連の除去アニメーションステップの間に重みが１から０になるように重みを入手できる。同様に、処理ボックス４４２で、現在の追加アニメーションステップ番号に１を加え、次にその合計を追加アニメーションステップ数で割ることによって、一連の追加アニメーションステップの間に重みが０から１になるように重みを入手できる。
【０１０７】
アニメーションステップの総数は、アニメーション速度と共に、アニメーション表示中のオブジェクト不変性の知覚への影響を助ける。上述の重みを得る方法の説明から理解できるように、アニメーションステップの総数は、除去又は追加された要素の領域が変化するレートを決定し、従って、他の要素が除去又は追加された要素の領域に関係して移動しなければならないレートを間接的に決定する。十分なアニメーション速度が維持されることを前提とすれば、除去ステップと追加ステップとの間に適切に割付けられたアニメーションステップ数が多い方が、オブジェクト不変性を生み出すのにより適している。
【０１０８】
図７の技術は、適切な速度の適切な数のアニメーションステップで実行されると、幾分閉じられたり広げられたりする扇のような、収縮及び拡張する１組のノードの知覚をうまく作り出した。ノードに割当てられた半径及び角度を調整することによって、削除されたノードがその親に引き込まれる又は無限へと絞り出される、又は挿入されたノードがその親から生え出る又は無限から引っぱり込まれるような、異なる知覚を得ることができる。１つの子のグループから１つの子だけ削除される場合には、その子が無限へと絞り出されるように見え、収縮のように１グループとして全ての子が削除される場合には、全ての子が親に引き込まれるように見えることが可能である。同様に、１つのグループに１つの子が追加される場合には、その子が無限から引っぱり込まれるように見え、拡張のように１グループとして全ての子が挿入される場合には、全ての子が親から生え出るように見えることが可能である。更に、孫が安定して見え、子だけが移動して見えるように調整されたレートで、子が親に引き込まれている間に孫を無限へと絞り出すことができる。
【０１０９】
上述の実施に類似の実施は、ＩＢＭ互換ＰＣのプロセッサ上でうまく実行されたが、実施は任意の適切なプロセッサを有する他の装置で実行されてもよい。
【０１１０】
上述の実施に類似の実施は、32ビットのウインドウズ(Windows)環境でＣ++言語を用いてうまく実行されたが、非オブジェクト指向環境を含む他のプログラム言語及び環境を用いてもよく、また、リスプ(Lisp)、ユニックス(Unix)環境、ANSI C、及びパスカル(Pascal)等のような他のプラットフォームを用いてもよい。
【０１１１】
上述の実施に類似の実施は、ＸＭＬ準拠フォーマット及びある実験的フォーマットで表示されるノード−リンクデータを用いてうまく実行されたが、本発明は、静的又は動的いずれかの、メモリ内又はネットワークを介してのように任意の適切な方法でアクセス可能な、任意の適切なタイプのノード−リンクデータを用いて実行されてもよい。
【０１１２】
上述の実施に類似の実施は、ナビゲーション信号に応答してグラフの１つの表現又はアニメーション化された一連の表現を準備及び表示する各反復を用いて実施されたが、本発明は他のタイプの信号又は呼出しによって呼出される他のタイプの反復を用いて実施されてもよい。
【０１１３】
上述の実施に類似の実施は、キーボード及びマウスから受信され、且つノード−リンク構造の表示された表現又はアニメーション化された一連の特定のタイプの表現に関係するナビゲーション信号を用いてうまく実行された。しかしながら、本発明は、ナビゲーション信号を用いて又は用いずに実施されてもよい。例えば、あるノードの子の異なるソーティングに応答して、又はある構造の要素への異なるフィルタの適用に応答して、要素を動き回らせてもよい。また、本発明は、任意の適切なタイプの拡張及び収縮信号、又は外部の照会、示されたノード又はリンクの下に拡張を要求するメニューエントリーのような項目の選択、又は現在の焦点の下に拡張を要求するメニューエントリーのような項目の選択から生じた信号を含む他のナビゲーション信号を用いて実施されてもよい。ナビゲーション信号は、代わりに、ビデオゲーム又はバーチャルリアリティ環境によって生成される空間のような現実には無い空間又はディスプレイ以外の表示空間に関係してもよく、また、ナビゲーション信号は、代わりに、他の種類の位置決め装置、及び英数字又は声、身振りのような言語的入力、又は他の様式のユーザ入力を受信するための他の種類の装置を含む、任意の適切なユーザ入力装置によって生成されてもよい。更に、本発明は他のタイプのノード−リンク構造の表現を用いて実施されてもよい。本発明はアニメーションなしで、又は任意の適切なアニメーション技術を用いて実施されてもよい。
【０１１４】
上述の実施では、親、子及び孫の間の関係に関する近隣関係データを入手するが、本発明は、レイアウト中の要素の、上位又は下位の追加の世代か又は横方向の追加の親戚かの、より遠い親戚を含む関係のような、異なる組の近隣ノード−リンク関係に関する近隣関係データを入手するように実施されてもよい。例えば、レイアウト中の要素の親の親が考えられる。
【０１１５】
上述の実施では、ノードについて、その親からの位置変位及び角度変位を示すレイアウトデータを入手する。しかしながら、本発明は、ノードではなく、又はノードに加えて、リンクについてのレイアウトデータを入手するように実施されてもよい。更に、本発明は、任意の他の適切な方法で相対位置を示すと共に付加的情報を示すレイアウトデータを入手するように実施されてもよい。
【０１１６】
上述の実施では、要素の親の孫の総数を入手し、次にその総数を用いて親の子の角度及び半径を入手し、次にその角度及び半径を用いて位置変位及び角度変位を入手する。この実施では上述のように特定の計算を行う。本発明は、任意の他の適切な方法で近隣関係データ及びレイアウトデータを入手するように実施されてもよい。例えば、親の各子が重みづけを有してもよく、子の相対的重みづけを用いて、各子が占めるスペースを決定又は子から親までの比例距離を決定してもよい。また、ノードの周りの使用可能領域に関する情報も、領域の重なりが最小のレイアウトを得ることによって、考慮されてもよい。反復計算を最小限にするために、レイアウトの結果をキャッシュに格納してもよい。
【０１１７】
上述の実施では、双曲平面にレイアウトされたノード−リンク構造は、次にユニットディスクにマッピングされ、次にペイントされるが、本発明に従ってレイアウトされたノード−リンク構造は、任意の他の適切な負曲空間にレイアウトされ、次に任意の他の適切な方法で、マッピングをして又はせずに処理されてもよく、又は、ノード−リンク構造を、３次元レンダリング空間及び表示空間を含む任意の他の適切なレンダリング空間にマッピングして任意の他の適切な表示空間に表示することを含む、任意の他の適切な方法でマッピング及び表示されてもよい。
【０１１８】
上述の実施では、あるノードについて入手した角度変位を前の角度変位と比較することによって、そのノードの子をレイアウトするか否かを決定するが、本発明は、レイアウトされた各ノードの全ての子孫をレイアウトすることによって、又はレイアウトする要素の決定に任意の他の適切な基準を適用することによって実施されてもよい。
【０１１９】
上述の実施はツリーの要素のレイアウトに適している。本発明は、一般的なグラフのような、他のタイプのノード−リンク構造の要素をレイアウトするのに用いられてもよい。
【０１２０】
上述の実施では、特定のタイプのメモリ管理を用いて、特定の方法でグラフ内のツリーを定義するためのリンクの拡張フラグを含むノード−リンクデータを用いるが、本発明は、任意の他の適切な方法で定義され、任意の適切な方法でメモリにロードされるノード−リンク構造を用いて実施されてもよい。
【０１２１】
上述の実施では、リンクが、１つのリストがそのフロムノードからの出リンクに対応し１つのリストがそのツーノードへの入リンクに対応する２つのリンクされたリスト内の項目として表わされる、有向グラフデータ構造を用いる。任意の他の適切なデータ構造を用いてもよい。
【０１２２】
上述の実施は、循環有向グラフを含む有向グラフを扱うことができるが、本発明は、他のタイプのリンクを有向グラフの適切な組合せに変換することによって、又は別様ではグラフの構造をツリーにマッピングするためのプロトコルを供給することによって、他のタイプのグラフ用に実施されてもよい。例えば、２つのノード間の無向リンクが、同じノードの間の１対の有向リンクに変換されてもよく、又は適切な基準に基づいて方向を割り当てられてもよい。一般的に、全ての無向リンクが１対の有向リンクへと変換されている表現は、結果的に有向リンクの各対が循環するので、視覚的に混乱させる傾向があるが、別の方法で循環を表示することによってこの混乱は克服されるかもしれない。
【０１２３】
上述の実施では、処理は多くの場合に変更されてもよい順位で行われる。例えば、図６では、幅優先巡回よりも深さ優先巡回が実行されてもよい。
【０１２４】
同じく、上述の実施では、幾つかのソフトウェアの部分が、グラファ、ウォーカ、ペインタ、及び数学ルーチン、並びにクライアントのように区別されるが、本発明は、ハードウェア及びソフトウェアの他の組合せ並びに任意の適切な方法で構成されたソフトウェアで実施されてもよい。
【０１２５】
本発明は、ノード−リンク構造の対話式ブラウザの提供に適用された。本発明は、ノード−リンク構造が視覚化のためにレイアウトされる様々なコンテキストに適用され得る。特に、本発明は、キャッシュに格納された１組のウェブページ又は他のウェブオブジェクトによって形成された構造のような、ウェブ関連構造の視覚化に適用され得る。
【０１２６】
より一般的には、本発明は、組織図、ファイルシステム階層、ハイパーテキスト階層、ワールドワイドウェブ接続性構造、パーツ分解、ＳＧＭＬ構造、又は任意の他の大きなノード−リンク構造のためのブラウザの提供に適用され得る。このブラウザは、構造又は構造の内容の編集に用いられてもよい。
【０１２７】
本発明は、ソフトウェアとしての実施例に関係して述べられてきたが、本発明は専用ハードウェアを用いて実施されてもよい。
【図面の簡単な説明】
【図１】ノード−リンク構造内の要素についてどのように局所的な相対的レイアウトが実行できるかを示す模式的なフロー線図である。
【図２】図１に示されるような局所的な相対的レイアウトの実行における一般的な処理を示すフロー図である。
【図３】図１に示されるような局所的な相対的レイアウトを実行する装置の一般的な構成要素を示す模式的な線図である。
【図４】システムの模式的な線図である。
【図５】どのように図４のシステムが有向グラフの表現を表示することによってイベントに応答できるかを示すフロー図である。
【図６】図５でどのように最初のレイアウトを実行できるかを示すフロー図である。
【図７】図５でどのように変更されたノード−リンク構造のレイアウトを実行できるかを示すフロー図である。
【符号の説明】
１０ ノード−リンク構造
２２ ノード
２４ 親ノード
２６−２８ 同胞ノード
３０−３２ 子ノード
４０ 近隣関係データ
４２ レイアウトデータ
２１２ クライアント
２２０ グラファルーチン
２２２ ウォーカルーチン
２２４ ぺインタルーチン
２２６ 数学ルーチン
２３０ 有向グラフデータ構造
２３２ ノード位置データ

Claims (1)

1. ノード表示装置であって、
   ノード−リンク構造内の要素について、近隣ノード−リンク関係に関する情報を示す近隣関係データを入手するための第１入手手段と、
   前記第１入手手段により入手した前記近隣関係データに基づいて、負曲率を有する空間での親ノードと子ノードとの間の距離と、前記親ノードへの入リンクと前記親ノードから前記子ノードへの出リンクとの間の角度差とを表したベクトルを示すレイアウトデータを入手するための第２入手手段と、
   前記第２入手手段により入手した前記レイアウトデータに基づいて、前記親ノードから前記子ノードへの前記ベクトルを表示するための表示手段と
   を具備することを特徴とする装置。

Images