(57)【要約】【課題】  グラフの可視描画像を単純化するための方法、装置、およびコンピュータ・プログラムを提供する。【解決手段】  上記課題は、グラフの可視描画像から除去するためのノードであって、少なくとも１つの残りのノードとの少なくとも２つの結合関係を有するノードを識別すること、除去のために識別されたノードを除去すること、除去されたノードの、その少なくとも１つの残りのノードとの結合関係に従って、その少なくとも１つの残りのノードに対して仮想結合関係を形成すること、およびその仮想結合関係を表示することによって達成される。【選択図】  図２
2007305134.tif 000002
【特許請求の範囲】
【請求項１】
グラフの可視描画像を単純化するための方法であって、
前記グラフの可視描画像から除去するためのノードで、少なくとも１つの残りのノードとの少なくとも２つの結合関係を有する前記ノードを識別することと、
除去のために識別されたノードを除去することと、
除去されたノードの、前記少なくとも１つの残りのノードとの結合関係に従って、前記少なくとも１つの残りのノードに対して仮想結合関係を形成することと、
前記仮想結合関係を表示することと、
を含む、前記方法。
【請求項２】
前記除去のために識別されたノードは包含ノードとの包含結合関係にある被包含ノードであり、
前記除去することは前記除去のために識別されたノードを消滅させて包含ノードにすることを含み、
前記少なくとも１つの残りのノードに対して仮想結合関係を形成することは、前記除去されたノードの、前記少なくとも１つの残りのノードとの結合関係に従って、前記包含ノードと少なくとも１つの他の残りのノードとの間に仮想結合関係を形成することを含む、
請求項１に記載の方法。
【請求項３】
前記除去のために識別されたノードは少なくとも１つの他のノードと従属結合関係にある従属ノードであり、除去されるべきノードは少なくとも１つの他のノードとの少なくとも１つの他の結合関係を有し、
前記除去することは前記従属ノードを除去することを含み、
前記少なくとも１つの残りのノードに対して仮想結合関係を形成することは、前記除去されたノードの、前記少なくとも１つの残りのノードとの結合関係に従って、前記従属結合関係の少なくとも１つの先行ノードと少なくとも１つの他の残りのノードとの間に仮想結合関係を形成することを含む、
請求項１に記載の方法。
【請求項４】
前記除去されたノードの、少なくとも１つの他のノードとの結合関係に従って、可視属性を前記仮想結合関係に割り当てることを更に含む、請求項１に記載の方法。
【請求項５】
前記除去されたノードの、少なくとも１つの残りのノードとの結合関係に従って、可視属性を前記少なくとも１つの残りのノードに割り当てることを更に含む、請求項１に記載の方法。
【請求項６】
前記識別することは、所定の選択基準に従って除去のためのノードを選択することを更に含む、請求項１に記載の方法。
【請求項７】
前記仮想結合関係は、前記除去されたノードの、少なくとも１つの残りのノードとの結合関係に関する情報を保持する前記少なくとも１つの残りのノードとの新しい結合関係である、請求項１に記載の方法。
【請求項８】
前記表示することは前記仮想結合関係を表す矢印を表示することを含む、請求項１に記載の方法。
【請求項９】
グラフの可視描画像を単純化するための装置であって、該装置はコンピュータ・プロセッサと、前記コンピュータ・プロセッサに接続されたコンピュータ・メモリとを含み、前記コンピュータ・メモリは内部にコンピュータ・プログラム命令を配置され、前記コンピュータ・プログラム命令は、
前記グラフの可視描画像から除去するためのノードで、少なくとも１つの残りのノードとの少なくとも２つの結合関係を有する前記ノードを識別する動作と、
除去のために識別されたノードを除去する動作と、
除去されたノードの、前記少なくとも１つの残りのノードとの結合関係に従って、前記少なくとも１つの残りのノードに対して仮想結合関係を形成する動作と、
前記仮想結合関係を表示する動作と、
を前記コンピュータ・プロセッサに実行させることができる、前記装置。
【請求項１０】
グラフの可視描画像を単純化するためのコンピュータ・プログラムであって、コンピュータに、
前記グラフの可視描画像から除去するためのノードで、少なくとも１つの残りのノードとの少なくとも２つの結合関係を有する前記ノードを識別するステップと、
除去のために識別されたノードを除去するステップと、
除去されたノードの、前記少なくとも１つの残りのノードとの結合関係に従って、前記少なくとも１つの残りのノードに対して仮想結合関係を形成するステップと、
前記仮想結合関係を表示するステップと、
を実行させる、前記コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ処理に関し、特に、グラフの可視描画像を単純化するための方法、装置、およびコンピュータ・プログラムに関するものである。
【背景技術】
【０００２】
設計者は、多くの場合、コンピュータ・ネットワーク、製造プロセス、コンピュータ・ソフトウェア、企業階級制、スポーツ・リーグ、電子回路、エンティティ等を表すシステムの構成要素をモデル化するためにコンピュータを使用している。一般に、システムの構成要素および構成要素相互間の結合関係は、ノードおよびそれらノード相互間の結合関係から成るグラフを使用してモデル化される。ノードはシステムの構成要素を表し、一方、ノード相互間の結合関係は構成要素相互間の結合関係を表す。
【０００３】
多くのノードおよび結合関係を有するグラフでは、一般にそのグラフの複雑さが増し、多くの場合、そのグラフのサイズが極めて大きくなる。そのような大きな且つ複雑なグラフは理解し難いのみならず、表示装置の有限なスクリーン領域に表示し難いかまたは表示することができない。大型の複雑なグラフをもっと分かり易くし且つ表示装置上に大型の複雑なグラフを表示する機能を提供するための現在の解決方法は、そのグラフの幾つかのノードをフィルタにかけることである。グラフからノードをフィルタにかけることは、グラフの可視描画像からそのノードを除去する。しかし、グラフのノードをフィルタにかけることは、多くの場合、例えば、フィルタにかけられたノード相互間の結合関係のような、必要以上に多くのそのグラフ表示されたシステムに関する情報を除去する。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の目的は、グラフの可視描画像を単純化するための方法、装置、およびコンピュータ・プログラムを提供することにある。
【課題を解決するための手段】
【０００５】
上記の単純化は、グラフの可視描画像から除去するためのノードであって、少なくとも１つの残りのノードとの少なくとも２つの結合関係を有するノードを識別すること、除去のための識別されたノードを除去すること、およびその除去されたノードの、少なくとも１つの残りのノードとの結合関係に従って、少なくとも１つの残りのノードに対する仮想結合関係を形成することによって行われる。
【０００６】
本発明の上記およびその他の目的、特徴、および利点は、添付図面に示されるような本発明の実施例の下記の詳細な説明から明らかであろう。添付図面では、本発明の実施例に関して、一般に、同じ番号は同じ部分を表す。
【発明を実施するための最良の形態】
【０００７】
本発明の実施例に従ってグラフの可視描画像を単純化するための例示的方法、装置、およびコンピュータ・プログラムを、図１で始まる添付図面を参照して説明する。本発明によるグラフの可視的表示の単純化は、一般に、コンピュータ、即ち、自動コンピューティング・マシンでもって具現化され得る。従って、図１は、本発明の実施例に従ってグラフの可視描画像を単純化する場合に有用な例示的コンピュータ１５２を含む自動コンピューティング・マシンのブロック図を示す。
【０００８】
グラフはノードのセットおよびそれらのノード相互間の結合関係のセットである。多くの場合、ノード相互間の結合関係は「エッジ」と呼ばれる。グラフのノードは、例えば、システム、構成要素、ロケーション、プロセス、ステップ等のような対象物を表す。グラフの各ノードは、例えば、ノードのラベル、タイプ、色、形状等のようなそのノードの特性を定義する、そのノードと関連した属性を有してもよい。１つのグラフにおけるノードの数はそのグラフの階位（order）を指定する。例えば、３つのノードを有するグラフは「３」の階位を有する。
【０００９】
ノード相互間の各結合関係は、グラフのノードのセットにおける２つの「エンドポイント」を有する。結合関係のエンドポイントは、ノードのセットにおける２つの異なるノードであってもよく、或いはノードのセットにおける同じノードであってもよい。結合関係のエンドポイントがノードのセットにおける同じノードであるとき、その結合関係は「ループ」と呼ばれる。グラフの各結合関係は、例えば、その結合関係のラベル、タイプ、色、形状等のような結合関係の特性を定義する、その結合関係と関連した属性を有してもよい。１つのグラフにおける結合関係の数はグラフのサイズを指定する。例えば、２つの結合関係を有するグラフは「２」のサイズを有する。
【００１０】
図１のシステムでは、コンピュータ１５２は、コンピュータ・プロセッサ、即ち、ＣＰＵ１５６、並びに、システム・バス１６０を介してプロセッサ１５６およびそのコンピュータの他のコンポーネントに接続されたランダム・アクセス・メモリ、即ち、ＲＡＭ１６８を含む。ＲＡＭ１６８には、グラフ・アプリケーション１００が記憶されている。グラフ・アプリケーション１００は、本発明の実施例に従ってグラフの可視描画像を単純化するための改良されたコンピュータ・プログラム命令のセットである。一般に、グラフ・アプリケーション１００は、本発明の実施例に従ってグラフの可視描画像から除去するためのノードであって少なくとも１つの残りのノードとの少なくとも２つの結合関係を有するノードを識別すること、除去のために識別されたノードを除去すること、およびその除去されたノードの、その少なくとも１つの残りのノードとの、結合関係に従ってその少なくとも１つの残りのノードに対して仮想結合関係を形成することによって、グラフの可視描画像を単純化するように動作する。本発明の実施例に従ってグラフの可視描画像を単純化するための改良可能なグラフ・アプリケーションの例が、AT&T Information Visualization Research Group による Graphviz、AbsIntAngewandte Informatik GmbH による aiSee 2.2.11、および BRAINSYS Informatiksysteme GmbHによる Graphlet 5.0.1 を含み得る。
【００１１】
図１のシステムでは、ＲＡＭ１６８にグラフ・データ１０２も記憶される。グラフ・データ１０２は、ノード、それらのノードの結合関係および属性、並びにグラフの結合関係を表す。グラフ・データ１０２は、グラフ記述言語を使ってグラフを表すことが可能である。本発明の実施例に従ってグラフの可視描画像を単純化するための改良可能なグラフ記述言語の例は、グラフ記述言語（Graph Description Language - ＧＤＬ）またはグラフ・モデル化言語（Graph ModelingLanguage - ＧＭＬ）を含む。ＧＤＬは、ノード、エッジ、または属性によってそのグラフを記述するＡＳＣＩＩテキストを使用してグラフを表す。属性は、グラフのノードおよびエッジを記述する。「２」の階位および「１」のサイズを有する例示的グラフはＧＤＬを使って次のように表される。
graph:{
node: {title:“node1”}
node: {title:“node2”}
edge: {source:“node1”target:“node2”}
}
【００１２】
上記の例は、「title」属性に対して「node1」の値を有するノードおよび「title」属性に対して「node2」の値を有する別のノードを含むグラフを説明している。そのグラフは「エッジ（edge）」と呼ばれる結合関係も含んでいる。エッジは、「source」属性に対して「node1」の値および「target」属性に対して「node2」の値を有する。即ち、エッジは、ノードの「title」属性に対して「node1」および「node2」の値によって識別されるノード相互間の結合関係を記述する。その結合関係の「source」属性および「target」属性はその結合関係のエンドポイントをＧＤＬで表す。
【００１３】
ＧＭＬもＡＳＣＩＩテキストを使用してグラフを表す。ＧＭＬは、ノード、エッジ、および属性によってグラフを記述するためのキー値の対から成る。「２」の階位および「１」のサイズを有する例示のグラフがＧＭＬを使って次のように表される。
graph[
node[id 1]
node[id 2]
edge[source1
target2]
]
【００１４】
上記の例は、「id」属性に対して「1」の値を有するノードおよび「id」属性に対して「2」の値を有する別のノードを含むグラフを説明している。そのグラフは「エッジ」と呼ばれる結合関係も含んでいる。エッジは、「source」属性に対して「1」の値および「ターゲット」属性に対して「2」の値を有する。即ち、エッジは、ノードの「id」属性に対して「1」および「2」の値によって識別されるノード相互間の結合関係を記述する。ＧＤＬにおけるように、ＧＭＬも「source」属性および「target」属性を使って結合関係のエンドポイントを表す。
【００１５】
ＲＡＭ１６８には、更に、オペレーティング・システム１５４も記憶される。本発明の実施例によるコンピュータにおける有用なオペレーティング・システムは、ＵＮＩＸ（登録商標）、Linux（商標）、Microsoft ＸＰ（商標）、ＡＩＸ（商標）、ＩＢＭ社のi5/OS（商標）および当業者が想起し得るその他のものを含む。図１の例では、オペレーティング・システム１５４、グラフ・アプリケーション１００、およびグラフ・データ１０２がＲＡＭ１６８内に示されるが、一般に、そのようなソフトウェアの多くのコンポーネントが不揮発性メモリ１６６にも記憶される。
【００１６】
図１のコンピュータ１５２は、システム・バス１６０を介してプロセッサ１５６およびそのコンピュータ１５２の他のコンポーネントに接続された不揮発性コンピュータ・メモリ１６６を含む。不揮発性コンピュータ・メモリ１６６は、ハードディスク・ドライブ１７０、光ディスク・ドライブ１７２、電気的消去可能なプログラマブル・リード・オンリ・メモリ空間（いわゆる、「ＥＥＰＲＯＭ」または「フラッシュ」メモリ）１７４、ＲＡＭドライブ（図示されてない）として、および当業者が想起し得るような任意の別種類のコンピュータ・メモリとして具現化され得る。
【００１７】
図１の例示のコンピュータは、１つまたは複数の入出力インターフェース・アダプタ１７８を含む。コンピュータにおける入出力インターフェース・アダプタは、例えば、コンピュータ・ディスプレイ・スクリーンのようなディスプレイ装置１８０への出力、およびキーボードおよびマウスのような入力装置１８１からのユーザ入力を制御するためのソフトウェア・ドライバおよびコンピュータ・ハードウェアを介してユーザ指向の入出力を実装する。図１の例示のコンピュータでは、ディスプレイ装置１８０はグラフの可視描画像を表示する。
【００１８】
図１の例示のコンピュータ１５２は、他のコンピュータ１８２とのデータ通信１８４を実施するための通信アダプタ１６７を含む。そのようなデータ通信は、ＲＳ−２３２接続を介して、ユニバーサル・シリアル・バス（ＵＳＢ）のような外部バスを介して、インターネット・プロトコル（ＩＰ）ネットワークのようなデータ通信ネットワークを介して、および当業者が想起し得るような他の方法で、逐次に実行することが可能である。通信アダプタは、１つのコンピュータが他のコンピュータに直接にまたはネットワークを介してデータを送るデータ通信のハードウェア・レベルを具現化する。本発明の実施例によるグラフの可視描画像を単純化するために有用な通信アダプタの例は、有線のダイヤルアップ通信のためのモデム、有線ネットワーク通信のためのイーサネット（登録商標）（ＩＥＥＥ８０２.３）アダプタ、および無線ネットワーク通信のための８０２.１１ｂアダプタを含む。
【００１９】
更なる説明のために、図２は、本発明の実施例に従ってグラフの可視描画像を単純化するための例示的方法を図解するフローチャートを示す。この方法は、グラフの可視描画像から除去するためのノードであって、少なくとも１つの残りのノードとの少なくとも２つの結合関係を有するノード、を識別するステップ２２０を含む。図２の方法によるその識別するステップ２２０は、例えば、グラフＧＵＩ（Graphing ＧＵＩ）２００のようなグラフィカル・ユーザ・インターフェース（ＧＵＩ）からユーザ標識を受け取ること、または図３および図４に関連して後述されるように所定の選択基準に従って除去するためのノードを選択すること、によって実行することが可能である。図２の例では、除去するために識別されたノードは、少なくとも１つの他のノードと従属結合関係にある従属ノードとして、および、図５および図６に関連して後述されるような少なくとも１つの他のノードとの少なくとも１つの他の結合関係を有する従属ノードとして具現化され得る。除去するために識別されたノードは、図７に関連して後述される包含ノードとの包含結合関係にある被包含ノードとして具現化することも可能である。
【００２０】
図２の方法は、除去のために識別されたノードを除去するステップ２２４も含む。除去のために識別されたノードを除去するステップ２２４は、従属ノードを除去することによって、または図５、図６、および図７に関連して後述されるように除去のために識別されたノードを消滅させて包含ノードにすることによって実行される。
【００２１】
図２の方法は、更に、除去されたノードの、少なくとも１つの残りのノードとの結合関係に従って、その少なくとも１つの残りのノードに対して仮想結合関係を形成するステップ２２６も含む。仮想結合関係２３０は、除去されたノードの少なくとも２つの結合関係を置換する少なくとも１つの残りのノードに対する新たな結合関係であり、その置換結合関係に関する情報および、多くの場合、除去されたノードに関する情報を維持する。
【００２２】
除去されたノードの、少なくとも１つの残りのノードとの結合関係に従って、少なくとも１つの残りのノードに対して仮想結合関係を形成するステップ２２６は、図５および図６に関連して後述されるように、除去されたノードの少なくとも１つの残りのノードとの結合関係に従って、従属結合関係の少なくとも１つの先行（antecedent）ノードと少なくとも１つの他の残りのノードとの間に仮想結合関係を形成することによって実行される。除去されたノードの、少なくとも１つの残りのノードとの結合関係に従って、従属結合関係の少なくとも１つの上位ノードと少なくとも１つの他の残りのノードとの間に仮想結合関係を形成する操作は、従属結合関係にあるノードを含むグラフの可視描画像を単純化するために有利に作用する。
【００２３】
除去されたノードの少なくとも１つの残りのノードとの結合関係に従って少なくとも１つの残りのノードに対して仮想結合関係を形成するステップ２２６は、図７に関連して後述されるように除去されたノードの少なくとも１つの残りのノードとの結合関係に従って、包含ノードと少なくとも１つの他の残りのノードとの間に仮想結合関係を形成することによっても実行され得る。除去されたノードの少なくとも１つの残りのノードとの結合関係に従って、包含ノードと少なくとも１つの他の残りのノードとの間に仮想結合関係を形成する操作は、包含結合関係にあるノードを含むグラフの可視描画像を単純化するために有利に作用する。
【００２４】
図２の方法は仮想結合関係を表示するステップ２３４も含む。図２の方法に従って仮想結合関係を表示するステップ２３４は、例えば、グラフＧＵＩ２４０のようなＧＵＩを使って仮想結合関係を表示することにより実行され得る。
【００２５】
図２に関連して上述したように、グラフの可視描画像から除去するためのノードを識別する操作はＧＵＩからのユーザ指示を受けることによって実行される。従って、更なる説明のために、図３は、本発明の実施例に従ってグラフの可視描画像を単純化するための更なる例示的方法を図解するフローチャートを示す。その方法は、グラフの可視描画像３０９から除去するためのノードを識別するステップ２２０を含み、そのステップは、例えば、グラフＧＵＩ３００のようなＧＵＩからユーザ指示を受けるステップ３２０によって実行される。
【００２６】
図３の例では、グラフＧＵＩ３００は、例えば、カーソルがノード３０４上にあるときにマウスの右ボタンをクリックするというような入力装置をユーザが動作することに応答してポップアップ・メニュー３０６を表示する。ポップアップ・メニュー３０６は、ノードの特性を変更するためにユーザ指示を受けるための「特性（Properties）」とラベル付けられたメニュー項目３０８、ノードのフォーマットを変更するためにユーザ指示を受けるための「フォーマット（Format）」とラベル付けられたメニュー項目３１０、およびグラフの可視描画像のために除去するためのノードを識別するユーザ指示を受けるための「除去（Remove）」とラベル付けられたメニュー項目３１２を含む。図３の例では、ユーザ指示３０７は、グラフＧＵＩ３００に表示されたグラフの可視描画像３０９から除去するためのノード３０４を識別する。除去されるべきノード３０４は、グラフの可視描画像がノード３０４を除去することによって単純化された後、１つの残りのノード３０２との２つの結合関係３０１、３０３を有する。
【００２７】
図３の例では、グラフＧＵＩ３００は、２つのノード３０２、３０４を有し且つ２つのノード３０２、３０４の間に２つの結合関係３０１、３０３を有するグラフの可視描画像３０９も表示する。グラフのノードおよび結合関係が、本発明の実施例に従ってグラフの可視描画像を単純化するためのＧＤＬまたはＧＭＬの改良バージョンに従ってグラフを記述するＡＳＣＩＩテキストのようなデータで表示され得る。本発明の実施例に従ってグラフの可視描画像を単純化するための改良されたＧＤＬのバージョンを使って可視描画像３０９としてグラフＧＵＩ３００に表示されたグラフの例示的記述は次のような記述を含む。
graph:{
node:{title:“node302”display:“TRUE”}
node:{title:“node304”display:“TRUE”}
edge:{source:“node302”target:“node304”
label:“edge303”display:“TRUE”}
edge:{source:“node304”target:“node302”
label:“edge301”display:“TRUE”}
}
【００２８】
上記の例では、「title」属性に対する「node302」の値によって識別されるノードがノード３０２を記述する。「title」属性に対する「node304」の値によって識別されるノードがノード３０４を記述する。「label」属性に対する「edge303」の値によって識別されるノードが結合関係３０３を記述する。「label」属性に対する「edge301」の値によって識別されるノードが結合関係３０１を記述する。「display」属性に対する「TRUE」の値は、各ノード３０２、３０４および各結合関係３０１、３０３が上記のグラフの可視描画像３０９に表示されることを表す。
【００２９】
ＧＵＩからのユーザ指示を受けるステップ３２０の後、図３の方法に従ってグラフの可視描画像３０９から除去するためのノードを識別するステップ２２０が、ノード識別子２２２における除去のための識別されたノードを識別する値を記憶することによって実行される。ノード識別子２２２は、グラフの可視描画像３０９から除去のために識別されたノードを表す。グラフの可視描画像３０９から除去のために識別されたノードが、例えば、本発明の実施例に従ってグラフの可視描画像を単純化するためのＧＤＬの改良バージョンを使って記述されるとき、除去のために識別されたノードを識別するノード識別子２２２に記憶された値は除去のために識別されたノードのＧＤＬ記述における「title」属性の値である。グラフの可視描画像３０９から除去のために識別されたノードが、例えば、本発明の実施例に従ってグラフの可視描画像を単純化するためのＧＭＬの改良バージョンを使って記述されるとき、除去のために識別されたノードを識別するノード識別子２２２に記憶された値は除去のために識別されたノードのＧＭＬ記述における「id」属性の値である。可視描画像３０９としてグラフＧＵＩ３００に表示されたグラフの上記例示記述を使用して、ノード識別子２２２における除去のために識別されたノードを識別する値を記憶する操作が、ノード識別子２２２に「node304」の値を記憶することによって実行され得る。
【００３０】
図３の方法は、除去のために識別されたノードを除去するステップ２２４も含む。除去のために識別されたノードを除去するステップ２２４は、ノード識別子２２２による除去のために識別されたノードの属性に、そのノードがそのノードのグラフの可視描画像に表示されないことを表す値を記憶することによって実行され得る。可視描画像３０９としてグラフＧＵＩに表示されたグラフに関する上記の例を続けると、ノードがそのノードのグラフの可視描画像に表示されないことを表す値を、ノード識別子２２２による除去のために識別されたノードの属性に記憶する操作は、「title」属性における「node304」の値によって識別されたノード３０４の「display」属性に「FALSE」の値を記憶することによって実行され得る。
【００３１】
除去のために識別されたノードを除去する操作は、せいぜい唯１つのエンドポイントと共に描画されたエンドポイントとしてそのノードを有する結合関係を残す。従って、図３の方法に従って除去のために識別されたノードを除去するステップ２２４は、エンドポイントとしてノード識別子２２２によって識別されたノードを有する結合関係の属性に、その結合関係がその結合関係のグラフの可視描画像に表示されないことを表す値を記憶することによっても実行することが可能である。例えば、グラフが可視描画像としてグラフＧＵＩ３００に表示されるという上記の例示的記述を再び考察すると、エンドポイントとしてノード識別子２２２によって識別されたノードを有する結合関係の属性に、その結合関係がその結合関係のグラフの可視描画像に表示されないことを表す値を記憶する操作は、「source」属性または「target」属性に「node304」の値を有する結合関係３０１、３０３の「display」属性に「FALSE」の値を記憶することによって実行され得る。
【００３２】
除去のために識別されたノードを除去するステップ２２４が、そのノード、またはそのノードをグラフのエンドポイントとして有する結合関係を、削除しないということに留意されたい。図３の例に従って除去のために識別されたノードを除去するステップ２２４は、グラフ自体ではなく、グラフの可視描画像からそのノードを除去する。
【００３３】
図３の方法に従って除去するために識別されたノードを除去するステップ２２４の後、本発明の実施例に従ってグラフの可視描画像を単純化するための改良されたＧＤＬのバージョンを使って除去のために識別されたノードを有するグラフの記述は次のような記述を含み得る。
graph:{
node:{title:“node302”display:“TRUE”
node:{title:“node304”display:“FALSE”
edge:{source:“node302”target:“node304”
label:“edge303”display:“FALSE”}
edge:{source:“node304”target:“node302”
label:“edge301”display:“FALSE”}
}
【００３４】
上記の例では、「title」属性における「node302」の値によって識別されたノードの「display」属性に対する「TRUE」の値は、ノード３０２が上記のグラフの可視描画像において表示されたままであることを表す。しかし、「title」属性における「node304」の値によって識別されたノードの「display」属性に対する「FALSE」の値、「label」属性における「edge303」の値によって識別された結合関係の「display」属性に対する「FALSE」の値、および「label」属性における「edge301」の値によって識別された結合関係の「display」属性に対する「FALSE」の値は、除去のために識別されたノードが除去されたことによって、ノード３０４および結合関係３０１、３０３が上記のグラフの可視描画像に表示されないということを表す。
【００３５】
図３の方法は、除去されたノード３０４の、残りのノード３０２と結合関係に従って、残りのノード３０２に対する仮想結合関係２３０を形成するステップ２２６も含む。仮想結合関係２３０は、例えば、本発明の実施例に従ってグラフの可視描画像を単純化するための改良されたＧＤＬのバージョンを使って記述され得る。除去されたノード３０４の、残りのノード３０２との結合関係に従って、残りのノード３０２に対して形成された仮想結合関係２３０の例示的記述は次のような記述を含み得る。
edge:{source:“node302”target:“node302”
label:“virtualedge340”removednode:“node304”
virtual:“TRUE”display:“TRUE”}
【００３６】
上記の例では、「virtual」属性に対する「TRUE」の値は、上記の結合関係が仮想結合関係であるということを表す。仮想結合関係は「label」属性に対する「virtualedge340」によって識別される。その記述は、値「node302」によって識別されたノードが、「label」属性に対する「virtualedge340」の値によって識別された結合関係に対する両エンドポイントとして作用するということを表す。「removednode」属性に対する「node304」の値は、結合関係がノード３０４およびノード３０２の間の結合関係に依存することを表す。結合関係の「display」属性に対する「TRUE」の値は、その結合関係が、その結合関係を含むグラフの可視描画像に表示されるということを表す。図３の方法では、除去されたノード３０４の、残りのノード３０２との結合関係に従ってその残りのノード３０２に対して仮想結合関係２３０を形成するステップ２２６は、本発明の実施例に従ってグラフの可視描画像を単純化するための改良されたＧＤＬのバージョンを使って記述されたグラフの記述内に、その仮想結合関係２３０により表された記述を挿入することによって実行され得る。
【００３７】
図３の方法は、除去されたノード３０４の、他のノード３０２との結合関係に従って可視属性３３２を仮想結合関係２３０に割り当てるステップ３２８も含む。可視属性３３２は、結合関係の可視描画像の特性、または除去されたノードに関する情報もしくはその除去されたノードに対する結合関係を提供するノードを表す。可視属性３３２は、例えば、仮想結合関係の描画像におけるラインのスタイルを使用してその仮想結合関係によって置換される結合関係のタイプを表す操作を含み得る。可視属性３３２は、例えば、残りのノードが有するその除去されたノードとの結合関係を表すために、その残りのノードの描画像における補助的マーク、特徴、または文字も含み得る。当業者が想起し得るように、本発明の実施例に従ってグラフの可視描画像を単純化する場合、可視属性３３２の別の例が有用となり得る。
【００３８】
図３の方法に従って、除去されたノード３０４の、他のノード３０２との結合関係に従って可視属性３３２を仮想結合関係２３０に割り当てるステップ３２８は、ノード識別子２２２によってエンドポイントとして識別されたノードを有する結合関係の属性に、可視属性３３２を表す値を記憶することによって実行され得る。例えば、仮想結合関係２３０の上記の例示記述を再び考察されたい。ノード識別子２２２によってエンドポイントとして識別されたノードを有する結合関係の属性に、その結合関係の可視描画像の特性を表す値を記憶する操作は、仮想結合関係２３０の例示的記述の「linestyle」属性に「dashed」の値を記憶することによって実行され得る。「linestyle」属性を含む仮想結合関係２３０の例示記述は次のような記述を含み得る。
edge:{source:“node302”target:“node302”label:“virtualedge340”
linestyle:“dashed”removednode:“node304”
virtual:“TRUE”display:“TRUE”}
【００３９】
上記の例示記述は、「label」属性に対する「virtualedge340」の値によって識別された仮想結合関係を記述している。「linestyle」属性に対する「dashed」の値は、「label」属性に対する「virtualedge340」の値によって識別された仮想結合関係が、その仮想結合関係を含むグラフの可視描画像を表示するＧＵＩにおいて破線でもって表示されるということを表す。
【００４０】
図３の方法は仮想結合関係２３０を表示するステップ２３４も含む。図３の方法に従って仮想結合関係２３０を表示するステップ２３４は、例えば、グラフＧＵＩ３４２のようなＧＵＩを使って仮想結合関係２３０を表示することによって実行され得る。図３の例では、グラフＧＵＩ３４２は、本発明の実施例に従ってグラフの可視描画像を単純化するための改良されたＧＤＬのバージョンを使って記述され得るグラフの可視描画像３４１を表示する。グラフＧＵＩ３４２に表示されるグラフの可視描画像３４１の例示記述は次のような記述を含み得る。
graph:{
node:{title:“node302”display:“TRUE”}
node:{title:“node304”display:“FALSE”}
edge:{source:“node302”target:“node304”
label:“edge303”display:“FALSE”}
edge:{source:“node304”target:“node302”
label:“edge301”display:“FALSE”}
edge:{source:“node302”target:“node302”
label:“virtualedge340”removednode:“node304”
linestyle:“dashed”display:“TRUE”}
}
【００４１】
グラフＧＵＩ３４２に表示されたグラフの可視描画像３４１の例示記述は、「title」属性に対する「node302」の値によってノード３０２として識別されたノードおよび「label」属性に対する「virtualedge340」の値によって仮想結合関係３４０として識別された結合関係が上記のグラフの可視描画像３４１に表示されるということを表す。グラフＧＵＩ３４２に表示されたグラフの可視描画像３４１の例示記述は、「title」属性に対する「node304」の値によってノード３０４として識別されたノード、「label」属性に対する「edge303」の値によって結合関係３０３として識別された結合関係、および「label」属性に対する「edge301」の値によって結合関係３０１として識別された結合関係が上記のグラフの可視描画像３４１に表示されないということを表す。グラフＧＵＩ３４２に表示されたグラフの可視描画像３４１の仮想結合関係３４０は、ノード３０２が１つの除去されたノードと結合関係を有することを表す。
【００４２】
図３の例では、除去するためのノードを識別する操作は、例えば、グラフィカル・ユーザ・インターフェースを介してユーザが選択したノードを受け取る操作を含む。そのような場合は、除去するためのノード、多くの場合、一時に１つのノードをユーザが選択することを必要とする。グラフの可視描画像から除去するためのノードを識別する操作は、所定の選択基準に従って除去するためのノードを選択することによっても実行され得る。所定の選択基準は、グラフの可視描画像から除去するためのノードを識別するために使用される所定の条件であり、それは、有利なことに、ユーザによる個々のノード選択を必要としない。所定の選択基準は、例えば、特定の対象物を表すノード、特定の値の属性を有するノード、ＧＵＩにおける特定のロケーションに表示されるノード等を含み得る。
【００４３】
更なる説明のために、図４は、本発明の実施例に従ってグラフの可視描画像を単純化するための更なる例示的方法を図解するフローチャートを示す。図４の方法に従ってグラフの可視描画像を単純化する操作が、グラフの可視描画像４０１から除去するためのノードを識別するステップ２２０、除去のために識別されたノードを除去するステップ２２４、グラフの可視描画像４０１から除去するためのノードを識別するステップ２２４、その除去されたノードの、少なくとも１つ残りのノードとの結合関係に従って、その少なくとも１つの残りのノードに対する仮想結合関係を形成するステップ２２６、および仮想結合関係２３０を表示するステップ２３４を含むという点で、図４の方法は図３の方法と同じである。図４の方法は、グラフの可視描画像から除去するためのノードを識別するステップ２２０が所定の選択基準に従って除去するためのノードを選択するステップ４２０を含むという点で図３の方法とは異なる。上述のように、所定の選択基準は、グラフの可視描画像から除去するためのノードを識別するために使用される所定の条件である。所定の選択基準は、例えば、特定の対象物を表すノード、特定の値の属性を有するノード、ＧＵＩにおける特定のロケーションに表示されたノード等を含み得る。
【００４４】
図４の方法によれば所定の選択基準に従って除去するためのノードを選択するステップ４２０は、コンピュータ・メモリに記憶された所定の選択基準を読取ることによって実行され得る。ソフトウェア設計者は、ＧＵＩを生成するグラフ・アプリケーションがプログラムされるとき、またはユーザが、例えば、グラフＧＵＩ４００のようなＧＵＩを使って所定の選択基準を実行時に入力し得るとき、コンピュータ・メモリに所定の選択基準を記憶し得る。図４の例では、グラフＧＵＩ４００は、そのグラフＧＵＩ４００の表示特性を変更するためにユーザ指示を受けるための「特性（Properties）」とラベル付けされたメニュー項目４０８、グラフＧＵＩ４００の表示フォーマットを変更するためにユーザ指示を受けるための「フォーマット（Format）」とラベル付けされたメニュー項目４１０、および所定の選択基準を入力するためにユーザ指示を受けるための「基準（Criteria）」とラベル付けされたメニュー項目４１２を含む「表示（Display）」とラベル付けされたメニュー４０３を表示する。
【００４５】
所定の選択基準に従って除去するためのノードを選択するステップ４２０の後、図４の方法に従ってグラフの可視描画像４０１から除去するためのノードを識別するステップ２２０を、図３に関連して上述したように除去のために識別されたノードを識別する値をノード識別子２２２に記憶することによって実行することも可能である。図４の例では、グラフＧＵＩ４００に表示された、グラフの可視描画像４０１から除去するためのノード４０４を所定の選択基準が識別する。ノード４０４は残りのノード４０２、４０６との２つの結合関係４０５、４０７を有する。
【００４６】
図４の例では、グラフＧＵＩ４００は３個のノード４０２、４０４、４０６を有するグラフの可視描画像４０１を表示する。そのグラフは、ノード４０２および４０４の間の結合関係、並びにノード４０４および４０６の間の結合関係も含む。グラフＧＵＩ４００に表示されたグラフの可視描画像４０１は、上述のように、本発明の実施例に従ってグラフの可視描画像を単純化するための改良されたＧＤＬのバージョンを使用して記述され得る。
【００４７】
所定の選択基準が、グラフＧＵＩに表示されたグラフの可視描画像４０１から除去するためのノード４０４を識別するということに留意されたい。図４の方法に従って、グラフＧＵＩ４００に表示されたグラフの可視描画像４０１を単純化する操作が、グラフＧＵＩ４３２に表示されたグラフの単純化された可視描画像４３４を生成する。グラフの可視描画像４３４は２つのノード４０２、４０６を含む。ノード４０４および結合関係４０５、４０７はグラフの可視描画像４３４から除去され、ノード４０２、４０６の間の仮想結合関係４３０と置換される。グラフ４３２に表示されたグラフの可視描画像４３４の仮想結合関係４３０は、ノード４０２およびノード４０６が除去されたノードとの結合関係を有するということを表す。
【００４８】
除去するための識別されたノードを除去する操作は、従属ノードを除去することによって実行され得るということに留意されたい。従属ノードは、システムのコンポーネントであってそのシステムの他のコンポーネントによる影響を受けるコンポーネントを表す。システムの影響を与えるコンポーネントは「先行（antecedent）ノード」と呼ばれるノードによって表される。先行ノードと従属ノードとの間に、「従属結合関係」と呼ばれる結合関係が存在する。従属結合関係は、従属ノードから先行ノードへの方向性のある結合関係である。従属結合関係の例は、１つのステップの遂行が次のステップの遂行に影響を与えるという製造プロセスにおけるステップ間の結合関係、または１つのソフトウェア・モジュールからの出力が他のソフトウェア・モジュールに対する入力として作用するというソフトウェア・モジュール間の結合関係を含み得る。本発明の実施例に従ってグラフの可視描画像を単純化するためのＧＤＬの改良バージョンを使用すると、１つの結合関係の「source」属性および「target」属性を使って従属結合関係が表される。「source」属性は従属結合関係の従属ノードを表し、「target」属性は従属結合関係の先行ノードを表す。
【００４９】
従って、更なる説明のために、図５は、従属ノードを除去するステップ５２０を含む本発明の実施例に従ってグラフの可視描画像を単純化するための更なる例示方法を説明するフローチャートを示す。図５の方法は、図５の方法によりグラフの可視描画像を単純化する操作が、グラフの可視描画像５０１から除去するためのノードを識別するステップ２２０、除去のために識別されたノードを除去するステップ２２４、除去されたノードの、少なくとも１つの残りのノードとの結合関係に従ってその少なくとも１つの残りのノードに対する仮想結合関係２３０を形成するステップ２２６、および仮想結合関係２３０を表示するステップ２３４を含むという点で図３の方法と同じである。図５の方法は、除去のために識別されたノード５０６がノード５０８との従属結合関係５１４における従属ノードとして具現化されるという点で図３の方法とは異なる。従属ノード５０６は、ノード５０４、５０２との２つの他の従属結合関係５１０、５１２も有する。
【００５０】
図５の方法では、除去のために識別されたノードを除去するステップ２２４が、従属ノード５０６を除去するステップ５２０を含む。従属ノード５０６を除去するステップ５２０は、ノード識別子２２２によって除去のために識別されたノードの属性に、そのノードがそのノードのグラフの可視描画像に表示されないことを表す値を記憶すること、およびノード識別子２２２によってエンドポイントとして識別されたノードを有する結合関係の属性に、図３に関連して上述したように、その結合関係がその結合関係のグラフの可視描画像に表示されないことを表す値を記憶することによって、実行され得る。
【００５１】
図５の方法では、除去されたノード５０６の、少なくとも１つの残りのノード５０２、５０４、５０８との結合関係に従ってその少なくとも１つの残りのノード５０２、５０４、５０８に対して仮想結合関係２３０を形成するステップ２２６は、除去されたノード５０６の、その少なくとも１つの残りのノード５０２、５０４、５０８との結合関係に従って従属結合関係５１４の少なくとも１つの先行ノード５０８と少なくとも１つの残りのノード５０２、５０４との間に仮想結合関係を形成するステップ５２２を含む。そのステップ５２２は、本発明の実施例に従って、仮想結合関係２３０によって表された記述を、グラフの可視描画像を単純化するために改良されたＧＤＬのバージョンを使って記述されたグラフの記述に、挿入することによって実行され得る。除去されたノード５０６の、少なくとも１つの残りのノード５０２、５０４、５０８との結合関係に従って、従属結合関係５１４の少なくとも１つの先行ノード５０８と少なくとも１つの他の残りのノード５０２、５０４との間に形成された仮想結合関係２３０の例示記述は次のような記述を含む。
edge:{source:“node502”target:“node508”label:“virtualedge532”
type:“DEPENDENCY”removednode“node506”
virtual:“TRUE”display:“TRUE”}
【００５２】
上記の例示記述では、「仮想（virtual）」属性に対する“TRUE”の値および「タイプ（type）」属性に対する「DEPENDENCY」の値は、記述された結合関係が仮想従属結合関係であるということを表す。その仮想結合関係は、「ラベル（label）」属性に対する「virtualedge532」の値によって識別される。その記述は、「ソース（source）」属性に対する「node502」の値によって識別されたノード５０２が仮想従属結合関係の従属ノードとして作用するということを表す。その記述は、「ターゲット（target）」属性に対する「node508」の値によって識別されたノード５０８が仮想従属結合関係の先行ノードとして作用するということを表す。「除去されたノード（removednode）」属性に対する「node506」の値は、その結合関係がノード５０６とノード５０２との間の結合関係およびノード５０６とノード５０８との間の結合関係に依存するということを表す。結合関係の「表示（display）」属性に対する「TRUE」の値は、その結合関係がその結合関係を含むグラフの可視描画像に表示されるということを表す。
【００５３】
図５の方法は、除去されたノード５０６の、少なくとも１つの残りのノード５０８との結合関係に従って少なくとも１つの残りのノード５０８に可視属性３３２を割り当てるステップ５２４も含む。そのステップ５２４は、残りのノード５０８の可視描画像の特性を表す値をその残りのノード５０８の属性に記憶することによって実行され得る。本発明の実施例に従って、グラフの可視描画像を単純化するためのＧＤＬの改良バージョンを使って、ノード５０８の次のような記述で「Ｄ」の値を「depictionmarks」属性に記憶する操作を考察することにする。
node:{title:“node508”depictionmarks:“D”display:“TRUE”}
【００５４】
上記の例示記述は、「title」属性に対する「node508」の値によって識別されたノードをノード５０８として記述する。「depictionmarks」属性に対する「Ｄ」の値は、ノード５０８が、そのノードを含むグラフの可視描画像を表示するＧＵＩにおいて「Ｄ」と共に表示されるということを表す。図５の例では、その「Ｄ」マークは、除去されたノードが「Ｄ」マークと共に描画されたノードとの従属結合関係における従属ノードであるということを表す。
【００５５】
図５の例では、グラフＧＵＩ５００は、４つのノード（５０２、５０４、５０６、５０８）を有するグラフの可視描画像５０１を表示する。そのグラフは、ノード５０２からノード５０４への従属結合関係５１６、ノード５０４からノード５０６への従属結合関係５１０、ノード５０２からノード５０６への従属結合関係５１２、ノード５０６からノード５０８への従属結合関係５１４も含む。グラフＧＵＩ５００に表示されたグラフの可視描画像５０１は、上記のように、本発明の実施例に従ってグラフの可視描画像を単純化するための改良されたＧＤＬのバージョンを使って記述され得る。
【００５６】
図５の例では、ユーザは、グラフＧＵＩ５００に表示されたグラフの可視描画像５０１から除去するためのノード５０６を、そのノード上でのマウス・クリックおよびそのノード５０６におけるマウス・クリックに関連したポップアップ・メニューによって識別した。ノード５０６は、残りのノード５０２、５０４、５０８との３つの結合関係５１０、５１２、５１４を有する。図５の方法に従ってグラフＧＵＩ５００に表示されたグラフ５０１の可視描画像を単純化する操作は、グラフＧＵＩ５３６に示されたグラフの単純化された可視描画像５３８を生成する。グラフの可視描画像５３８は３つのノード（５０２、５０４、５０８）を含む。ノード５０６およびそのノード５０６に対する結合関係５１０、５１２、５１４は可視描画像５３８から除去され、仮想結合関係５３０、５３２、および可視属性５３４と置換される。グラフの可視描画像５３８における仮想結合関係５３０は、ノード５０４およびノード５０８が１つの除去されたノードとの結合関係を有するということを表す。仮想結合関係５３２は、ノード５０２およびノード５０８が１つの除去されたノードとの結合関係を有することを表す。可視属性５３４は、ノード５０８がその除去されたノードとの従属結合関係における先行ノードであるということを表す。
【００５７】
図５の例における除去されたノードは唯一の先行ノードとの従属結合関係における従属ノードであるということを留意されたい。除去されたノードは、複数の先行ノードとの従属結合関係における従属ノードでもあり得る。従って、更なる説明のために、図６は、本発明の実施例に従ってグラフの可視描画像を単純化するための更なる例示方法を表すフローチャートを示す。この実施例は、２つの先行ノード６０６、６０８との従属結合関係６０５、６０７における除去されるノード６０４を含む。
【００５８】
図６の方法は、図５の方法と同様に機能する。図６の方法は、グラフの可視描画像６０１から除去するためのノードを識別するステップ２２０、除去のために識別されたノードを除去するステップ２２４、その除去されたノードの、少なくとも１つの残りのノードとの結合関係に従って少なくとも１つの残りのノードに対する仮想結合関係２３０を形成するステップ２２６、および仮想結合関係２３０を表示するステップ２３４を含む。
【００５９】
図６の例では、グラフＧＵＩ６００が、４つのノード６０２、６０４、６０６、６０８を有するグラフの可視描画像６０１を表示する。そのグラフは、ノード６０２からノード６０４への従属結合関係６０３、ノード６０４からノード６０２への従属結合関係６０９、ノード６０４からノード６０６への従属結合関係６０５、およびノード６０４からノード６０８への従属結合関係６０７も含む。グラフＧＵＩ６００に表示されたグラフの可視描画像６０１は、上述のように、本発明の実施例に従ってグラフの可視描画像を単純化するための改良されたＧＤＬのバージョンを使って記述される。
【００６０】
図６の例では、ユーザが、ノードにおけるマウス・クリックおよびマウス・クリックと関連したポップアップ・メニューを通してグラフＧＵＩ６００に表示されたグラフの可視描画像６０１から除去するためのノード６０４を識別した。ノード６０４は、残りのノード６０２、６０６、６０８との４つの結合関係６０３、６０５、６０７、６０９を有する。除去のために識別されたノード６０４は、３つの他のノード６０２、６０６、６０８との３つ従属結合関係６０５、６０７、６０９において従属ノードとして具現化される。ノード６０４は、そのノード６０４が先行ノードとして作用するノード６０２との１つの別の結合関係６０３も有する。図６の方法に従ってグラフＧＵＩ６００に表示されたグラフの可視描画像６０１を単純化するする操作は、グラフＧＵＩ６３４に表示された単純化された可視描画像６３６を生成する。可視描画像６３６は３つのノード６０２、６０６、６０８を含む。
【００６１】
ノード６０４およびそのノード６０４に対する結合関係６０３、６０５、６０７、６０９が可視描画像６３６から除去され、仮想従属結合関係６３０、６３２、６３８および可視属性６４０、６４２と置換される。仮想従属結合関係６３０は、ノード６０２およびノード６０６が、除去されたノードとの結合関係を有することを表す。仮想従属結合関係６３２は、ノード６０２およびノード６０８が、除去されたノードとの結合関係を有することを表す。仮想従属結合関係６３８は、ノード６０２が、除去されたノードとの結合関係を有することを表す。可視属性６４０は、ノード６０６が，除去されたノードとの従属結合関係における先行ノードであることを表す。可視属性６４２は、ノード６０８が，除去されたノードとの従属結合関係における先行ノードであることを表す。
【００６２】
除去のために識別されたノードを除去する操作は、除去のために識別されたノードを消滅させて包含ノードにすることによって実行され得るということが想起されるであろう。被包含ノードは、システムの他のコンポーネントの一部であるそのシステムのコンポーネントを表すノードである。そのコンポーネントを一部とする他のコンポーネントは「包含コンポーネント」と呼ばれるノードによって表される。包含ノードと被包含ノードとの間には「包含結合関係」と呼ばれる結合関係が存在する。包含結合関係は、包含ノードから被包含ノードへの方向性結合関係である。包含結合関係の例は、コンピュータ・プロセッサとそのコンピュータ・プロセッサを含むコンピュータ・マシンとの間の結合関係、またはコンピュータ・ソフトウェア・サブルーチンとそのコンピュータ・ソフトウェア・サブルーチンを含むコンピュータ・ソフトウェア・アプリケーションとの結合関係を含み得る。本発明の実施例に従ってグラフの可視描画像を単純化するためのＧＤＬの改良バージョンを使って、結合関係の「source」属性および「target」属性を使って包含結合関係が表される。「source」属性は包含結合関係の包含ノードを表し、「target」属性はその包含結合関係の被包含ノードを表す。
【００６３】
更なる説明のために、図７は、本発明の実施例に従ってグラフの可視描画像を単純化するための更なる例示方法を図解したフローチャートを示し、その方法は、除去のために識別されたノードを消滅させて包含ノードにするステップ７２０を含む。図７の方法は、図５の方法によるグラフの可視描画像を単純化する操作が、グラフの可視描画像５０１から除去するためのノードを識別するステップ２２０、除去のための識別されたノードを除去するステップ２２４、その除去されたノードの、少なくとも１つの残りのノードとの結合関係に従って、その少なくとも１つの残りのノードに対する仮想結合関係を形成するステップ２２６、および仮想結合関係２３０を表示するステップ２３４を含むという点で図３の方法と同じである。図５の方法は、除去のために識別されたノード７０６が包含ノード７０２との包含結合関係７１２における被包含ノードとして具現化されるという点で図７の方法とは異なる。
【００６４】
図７の方法では、除去のために識別されたノードを除去するステップ２２４は、その除去のために識別されたノード７０６を消滅させて包含ノード７０２にするステップ７２０を含む。その除去のために識別されたノード７０６を消滅させて包含ノード７０２にするステップ７２０は、ノード識別子２２２により除去のために識別されたノード７０６の属性に、そのノード７０６がそのノードのグラフの可視描画像に表示されないことを表す値を記憶することによって、および図３に関連して説明したように、ノード識別子２２２により除去のために識別されたノード７０６を有する結合関係７１０、７１２、７１４の属性に、その結合関係７１０、７１２、７１４がその結合関係７１０、７１２、７１４のグラフの可視描画像に表示されないということを表す値をエンドポイントとして記憶することによって、実行され得る。
【００６５】
図７の方法では、除去されたノード７０６の、残りのノード７０２、７０４、７０８との結合関係に従って、その残りのノード７０２、７０４、７０８に対する可視結合関係２３０を形成するステップ２２６は、除去されたノード７０６の、その残りのノード７０２、７０４、７０８との結合関係に従って、包含ノード７０２と少なくとも１つの他の残りのノード７０４、７０８との間に仮想結合関係２３０を形成するステップ７２２を含む。仮想結合関係２３０を形成するステップ７２２は、本発明の実施例に従ってグラフの可視描画像を単純化するための改良されたＧＤＬのバージョンを使用して記述されたグラフの記述に、その仮想結合関係２３０によって表された記述を挿入することによって実行され得る。
【００６６】
図７の例では、グラフＧＵＩ７００は、４つのノード７０２、７０４、７０６、７０８を有するグラフの可視描画像７０１を表示する。そのグラフは、ノード７０２からノード７０６への包含結合関係７１２、ノード７０２からノード７０４への従属結合関係７０３、ノード７０４からノード７０６への従属結合関係７１０、およびノード７０６からノード７０８への従属結合関係７１４も含む。グラフＧＵＩ７００に表示されたグラフの可視描画像７０１は、上述のように、本発明の実施例に従ってグラフの可視描画像を単純化するために改良されたＧＤＬのバージョンを使って記述され得る。
【００６７】
図７の例では、ユーザが、グラフＧＵＩ７００に表示されたグラフの可視描画像７０１から除去するためのノード７０６を、そのノード上でのマウス・クリックおよびマウス・クリックと関連したポップアップ・メニューを通して識別した。ノード７０６は、残りのノード７０２、７０４、７０８との３つの結合関係７１０、７１２、７１４を有する。グラフＧＵＩ７００に表示されたグラフの可視描画像７０１を図７の方法によって単純化する操作は、グラフＧＵＩ７３４に表示されたその単純化された可視描画像７３６を生成する。グラフの可視描画像７３６は、３つのノード７０２、７０４、７０８を含む。ノード７０６およびそのノード７０６に対する結合関係７１０、７１２、７１４は可視描画像７３６から除去され、仮想結合関係７３０、７３２および可視属性７３４と置換される。仮想結合関係７３０は、ノード７０４および７０２が、除去されたノードとの結合関係を有するということを表す。仮想結合関係７３２は、ノード７０２およびノード７０８が、除去されたノードとの結合関係を有するということを表す。可視属性７３４は、ノード７０２が、除去されたノードとの包含結合関係にある包含ノードであるということを表す。
【００６８】
可視描画像７３６に関連して、図７の方法に従って形成された仮想結合関係７３０、７３２が仮想従属結合関係であるということ留意されたい。その形成された仮想結合関係のタイプは、その除去されたノード７０６と残りのノード７０４、７０８との間の、その除去されたノード７０６が消滅しないときの結合関係と同じタイプである。即ち、除去されたノード７０６と残りのノード７０４、７０８との間の結合関係７１０、７１４が従属結合関係であるため、その形成された仮想結合関係は仮想従属結合関係である。しかし、仮想従属結合関係の形成は説明のためであって、限定のためではない。実際には、除去されたノードの、残りのノードとの結合関係に従って、残りのノードに対する仮想結合関係２３０を形成するステップ２２６は、例えば、裏結合関係（back relationship）、準結合関係（near relationship）、または当業者が思い付き得る任意の他のタイプの結合関係のような他のタイプの仮想結合関係を形成し得る。
【００６９】
図５の例におけるグラフＧＵＩ５００に表示されたグラフの可視描画像５０１が図７の例におけるグラフＧＵＩ７００に表示されたグラフの可視描画像７０１と同じであることに留意されたい。図５の例では、除去のために識別されたノード５０６に対する結合関係５１２が従属結合関係であり、一方、図７の例では、除去のために識別されたノード７０６に対する結合関係７１２が包含結合関係である。図５および図７における除去のために識別されたノードに対する結合関係の異なるタイプがグラフの単純化された可視描画像５３８、７３６におけるわずかに異なる仮想結合関係５３０、７３０を生成するということに留意されたい。図５の例では、ノード５０２からノード５０６への従属結合関係の結果、ノード５０４からノード５０８への仮想従属結合関係５３０が生じる。図７の例では、ノード７０２からノード７０６への包含結合関係の結果、ノード７０４からノード７０２への仮想従属結合関係７３０が生じる。
【００７０】
グラフの可視描画像を単純化するための十分に機能的なコンピュータ・システムに関連して本発明の実施例を十分に説明した。しかし、任意の適当なデータ処理システムによる使用のために信号保持媒体に記憶されたコンピュータ・プログラムとして本発明を具現化することも可能であるということは当業者には明らかであろう。そのような信号保持媒体は磁気的媒体、光学的媒体、または他の適当な媒体を含む機械読取り可能な情報のための伝送媒体または記録可能媒体であってもよい。記録可能媒体の例は、ハード・ドライブまたはディスケットにおける磁気ディスク、光学的ドライブのためのコンパクト・ディスク、および当業者が思い付くような他の媒体を含む。伝送媒体の例は、音声通信のための電話網、並びに、例えば、Ethernets（登録商標）のようなデジタル・データ通信ネットワークやインターネット・プロトコルおよびワールド・ワイド・ウェブと通信を行うネットワークを含む。適当なプログラミング手段を有する任意のコンピュータ・システムが本発明の方法のステップをコンピュータ・プログラムとして具現化することで実行し得るということも当業者には明らかであろう。本明細書に記載された実施例の或るものはコンピュータ・ハードウェア上にインストールされて実行されるソフトウェアに向いているが、ファームウェアまたはハードウェアとして具現化される別の実施例も本発明の範囲内にあることも当業者には明らかであろう。
【００７１】
以上の説明から、本発明の主旨から逸脱することなく、本発明の種々の実施例における修正および変更を行い得ることも当然である。本明細書における記述は単に説明を目的とするものであり、限定の意味に解されるべきではない。本発明の範囲は「特許請求の範囲」における記載によってのみ限定される。
【図面の簡単な説明】
【００７２】
【図１】本発明の実施例に従ってグラフの可視描画像を単純化する場合に有用な例示的コンピュータを含む自動コンピューティング・マシンのブロック図を示す。
【図２】本発明の実施例に従ってグラフの可視描画像を単純化するための例示的方法を図解したフローチャートを示す。
【図３】本発明の実施例に従ってグラフの可視描画像を単純化するための更なる例示的方法を図解したフローチャートを示す。
【図４】本発明の実施例に従ってグラフの可視描画像を単純化するための更なる例示的方法を図解したフローチャートを示す。
【図５】本発明の実施例に従ってグラフの可視描画像を単純化するための更なる例示的方法を図解したフローチャートを示す。
【図６】本発明の実施例に従ってグラフの可視描画像を単純化するための更なる例示的方法を図解したフローチャートを示す。
【図７】本発明の実施例に従ってグラフの可視描画像を単純化するための更なる例示的方法を図解したフローチャートを示す。
【図１】
2007305134.tif 000003
【図２】
2007305134.tif 000004
【図３】
2007305134.tif 000005
【図４】
2007305134.tif 000006
【図５】
2007305134.tif 000007
【図６】
2007305134.tif 000008
【図７】
2007305134.tif 000009