JP4867929B2 - グラフ編集装置 - Google Patents

Description

本発明は、グラフ編集装置にかかり、特に、ノードとエッジとを有するグラフを編集するグラフ編集装置に関する。

ノードとエッジを用いたグラフは、回路図やＵＭＬクラス図など様々な場面で用いられ、その作成や編集をコンピュータを用いて容易に行うことが望まれている。そして、コンピュータなどでノードとエッジを用いたグラフを作成したり、編集する場合には、ノードの位置決定に主眼が置かれており、エッジに関しては従属的に扱われていた。

例えば、ＬＳＩ配線等において、自動配線アルゴリズムが各種知られているが、それらは、所与の条件においてレイアウト全体を決定するものであり、編集中にノードの大きさが変化した場合に適用すると、わずかな変更で接続状態が大きく変化することがあった。そして、人間が操作中に、突然レイアウトが大きく変化してしまうと、情報を見失ってしまう恐れがある。特に、グラフがソフトウェアの設計情報を表現している場合は、新しいレイアウトでは十分に設計情報を示しきれないため、元のように配置しなおす必要が生じる場合もあった。

また、グラフの自動レイアウトシステムの一例が、特許文献１に記載されている。この特許文献１では、接続する２つのノードの中心座標をそれぞれ求め、それらの中心点間を結ぶ線分と、各ノードの外縁との交点を算出することによって、それら交点をエッジの始点及び終点として設定している。

特開平９−２７０４０号公報

しかしながら、上記技術では、ノードの移動に応じてノード間の接続関係を維持しているだけであって、エッジがノードの背後に位置する場合には、その接続関係を見失う場合が生じうる。すると、設計者はグラフの変更を迅速かつ容易に認識することができず、意図するグラフを迅速かつ正確に作成することが困難であった。

このため、本発明の目的は、上述した課題である、グラフの編集を認識しやすく表示して、編集者にとって利便性の高いグラフ編集装置を提供することをその目的とする。

そこで、本発明の一形態であるグラフ編集装置は、
ノード及び当該ノード間を接続するエッジからなるグラフを編集するグラフ編集装置であって、
ノードの位置及び形状を特定するノード情報を記憶するノード情報記憶手段と、
少なくともエッジの当該エッジが接続されたノードに対する位置、折れ曲がり位置を特定するエッジ情報を記憶するエッジ情報記憶手段と、
ノード情報及びエッジ情報に基づいて、ノード及びエッジを表示装置に表示出力する表示出力手段と、を備え、
ノードの位置及び／又は形状の変更操作の入力に応じて、当該変更操作されたノードのノード情報記憶手段に記憶されたノード情報を変更記憶すると共に、当該変更記憶されたノード情報に基づいて、当該ノード情報に対応するノードに接続されたエッジのエッジ情報記憶手段に記憶されたエッジ情報を、変更記憶されたノードとの接続状態を維持しつつ、かつ、当該ノードと重ならないよう、エッジの位置、折れ曲がり位置を移動して変更記憶する編集手段を備えた、
という構成を採る。

また、本発明の他の形態であるプログラムは、
ノード及び当該ノード間を接続するエッジからなるグラフを編集するためのコンピュータに、
予め記憶された、ノードの位置及び形状を特定するノード情報と、少なくともエッジの当該エッジが接続されたノードに対する位置、折れ曲がり位置を特定するエッジ情報と、に基づいて、ノード及びエッジを表示装置に表示出力する表示出力手段と、
ノードの位置及び／又は形状の変更操作の入力に応じて、当該変更操作されたノードのノード情報を変更記憶すると共に、当該変更記憶されたノード情報に基づいて、当該ノード情報に対応するノードに接続されたエッジのエッジ情報を、変更記憶されたノードとの接続状態を維持しつつ、かつ、当該ノードと重ならないよう、エッジの位置、折れ曲がり位置を移動して変更記憶する編集手段と、
を実現させる、という構成を採る。

さらに、本発明の他の形態であるグラフ編集方法は、ノード及び当該ノード間を接続するエッジからなるグラフを編集するグラフ編集方法であって、
予め所定の記憶装置に記憶された、ノードの位置及び形状を特定するノード情報と、少なくともエッジの当該エッジが接続されたノードに対する位置、折れ曲がり位置を特定するエッジ情報と、に基づいて、ノード及びエッジを表示装置に表示出力する表示出力工程と、
ノードの位置及び／又は形状の変更操作の入力に応じて、当該変更操作されたノードのノード情報を変更記憶すると共に、当該変更記憶されたノード情報に基づいて、当該ノード情報に対応するノードに接続されたエッジのエッジ情報を、変更記憶されたノードとの接続状態を維持しつつ、かつ、当該ノードと重ならないよう、エッジの位置、折れ曲がり位置を移動して変更記憶する編集工程と、
編集工程にて変更記憶されたノード情報及び／又はエッジ情報に基づいて、ノード及び／又はエッジを表示装置に再表示出力する再表示出力工程と、
を有する、という構成を採る。

本発明は、以上のように構成されるため、編集者がグラフを編集した際に、かかる編集後のグラフが認識しやすく表示され、編集者にとって利便性の向上を図ることができる、という優れた効果を有する。

本発明は、コンピュータにてＵＭＬ（Unified Modeling Language）や電子回路などで用いられる、ノードとエッジを用いたグラフを作成・編集する装置において、変更点の認識が容易になるよう再表示を行う点に特徴を有する。特に、２次元有向グラフ（例：ＵＭＬクラス図、ユースケース図等）の編集中に、ノードの位置や大きさを変化させた場合（例：リサイズ、非表示情報の表示）でも、エッジの接続点や折れ曲がり点、向きを保持しつつ全体のレイアウトを調整することにより、編集者の意図を損なわずに編集をつづけることができる。

このため、本発明の一形態であるノード及び当該ノード間を接続するエッジからなるグラフを編集するグラフ編集装置は、
ノードの位置及び形状を特定するノード情報を記憶するノード情報記憶手段と、
少なくともエッジの当該エッジが接続されたノードに対する位置、折れ曲がり位置を特定するエッジ情報を記憶するエッジ情報記憶手段と、
ノード情報及びエッジ情報に基づいて、ノード及びエッジを表示装置に表示出力する表示出力手段と、を備え、
ノードの位置及び／又は形状の変更操作の入力に応じて、当該変更操作されたノードのノード情報記憶手段に記憶されたノード情報を変更記憶すると共に、当該変更記憶されたノード情報に基づいて、当該ノード情報に対応するノードに接続されたエッジのエッジ情報記憶手段に記憶されたエッジ情報を、変更記憶されたノードとの接続状態を維持しつつ、かつ、当該ノードと重ならないよう、エッジの位置、折れ曲がり位置を移動して変更記憶する編集手段を備えた、
という構成を採る。

上記発明によると、まず、グラフ編集装置は、ノードの位置及び形状を特定するノード情報と、ノード間を接続するエッジのノードに対する位置と折れ曲がり位置を特定するエッジ情報とを記憶し、これに基づいてノードとエッジを表示出力する。そして、グラフ編集装置は、所定のノードの位置や形状の変更の入力を受け付けると、この変更入力内容に応じて、ノードのノード情報を変更記憶する。これに伴い、このノードに接続されたエッジのエッジ情報も変更記憶する。具体的には、エッジがノードとの接続状態を維持しつつ、かつ、エッジがノードと重ならないよう、エッジの位置と折れ曲がり位置を移動して、変更記憶する。そして、グラフ編集装置は、変更記憶されたノード情報とエッジ情報とに基づいて、変更後のノードとエッジとを表示出力する。

これにより、ノードの変形や移動に応じて、当該ノードに対するエッジの位置関係を維持し、また、エッジがノードの背後に隠れないようエッジの位置を変形して出力する。従って、編集者がグラフの編集を認識しやすく表示されるため、編集者にとって利便性の向上を図ることができる。

そして、上記編集手段は、ノードの位置及び／又は形状の変更に応じて当該ノードがエッジの折れ曲がり位置上に位置する場合に、当該ノードに重ならないよう折れ曲がり位置を移動する、という構成を採る。具体的に、上記編集手段は、ノードの位置及び／又は形状の変更に応じて当該ノードがエッジの折れ曲がり位置上に位置する場合に、当該ノードの位置及び／又は形状を変更した方向に、折れ曲がり位置をノードに重ならないよう移動する。また、上記編集手段は、ノードの位置及び／又は形状の変更に応じて当該ノードの特定の辺に対するエッジの接続状態を維持するよう当該エッジの位置を移動する、という構成を採る。

このように、変更されたノードの特定の辺との接続を維持するようエッジの位置を変更したり、エッジに折れ曲がり位置がある場合には、その折れ曲がり位置がノードに重ならないよう移動することで、より編集者がグラフの編集を認識しやすく表示されることとなる。

また、上記編集手段は、ノードの位置及び／又は形状の変更に応じて当該ノードが他のノードの位置上に位置する場合に、当該他のノードを変更したノードと重ならないよう移動して、当該他のノードのノード情報記憶手段に記憶されたノード情報を変更記憶する、という構成を採る。また、上記編集手段は、他のノードの移動に応じて、当該他のノードに接続されたエッジのエッジ情報記憶手段に記憶されたエッジ情報を、当該他のノードとの接続状態を維持しつつ、かつ、当該他のノードと重ならないよう、その位置、折れ曲がり位置を移動して変更記憶する、という構成を採る。

これにより、変更したノードと重なる他のノードが存在する場合に、この他のノードを移動し、さらに、移動した他のノードに接続するエッジの位置や折れ曲がり点も変更する。従って、さらに編集者がグラフの編集を認識しやすく表示されることとなる。

また、本発明の他の形態である、ノード及び当該ノード間を接続するエッジからなるグラフを編集するグラフ編集方法は、
予め所定の記憶装置に記憶された、ノードの位置及び形状を特定するノード情報と、少なくともエッジの当該エッジが接続されたノードに対する位置、折れ曲がり位置を特定するエッジ情報と、に基づいて、ノード及びエッジを表示装置に表示出力する表示出力工程と、
ノードの位置及び／又は形状の変更操作の入力に応じて、当該変更操作されたノードのノード情報を変更記憶すると共に、当該変更記憶されたノード情報に基づいて、当該ノード情報に対応するノードに接続されたエッジのエッジ情報を、変更記憶されたノードとの接続状態を維持しつつ、かつ、当該ノードと重ならないよう、エッジの位置、折れ曲がり位置を移動して変更記憶する編集工程と、
編集工程にて変更記憶されたノード情報及び／又はエッジ情報に基づいて、ノード及び／又はエッジを表示装置に再表示出力する再表示出力工程と、
を有する、という構成を採る。

そして、上記再表示出力工程は、上記編集工程中に作動し、ノード情報が変更記憶されたとときに当該ノード情報に基づいてノードを表示装置に再表示出力し、エッジ情報が変更記憶されたときに当該エッジ情報に基づいてエッジを表示装置に再表示出力する、という構成を採る。

以下、本発明の具体的な構成及び動作を、実施形態にて説明する。

＜実施形態１＞
本発明の第１の実施形態を、図１乃至図９を参照して説明する。図１は、グラフ編集装置として機能するコンピュータの構成を示す機能ブロック図である。図２乃至図３は、グラフの一例を示す図であり、図４乃至図８は、グラフの編集例を示す図である。図９は、グラフ編集装置の動作を示すフローチャートである。

［構成］
図１に示すように、グラフ編集装置を構成するコンピュータ１は、ディスプレイといった表示部３と、キーボードやマウスといった操作部４と、演算装置であるＣＰＵ（図示せず）と、記憶装置であるフラッシュメモリやハードディスク（図示せず）と、を備えた一般的なコンピュータである。そして、コンピュータ１は、演算装置に所定のプログラムが組み込まれることによって構築された、表示処理部１１と、編集処理部１２と、レイアウト修正処理部１３と、を備えている。また、コンピュータ１は、記憶装置に、ノード格納部２１と、エッジ格納部２２と、ノード変更コマンド格納部２３と、エッジ変更コマンド格納部２４と、を備えている。以下、各構成について詳述する。

上記ノード格納部２１（ノード情報記憶手段）は、ノード自体を特定する情報と、ノードの位置及び形状を特定する情報と、からなるノード情報を記憶する。例えば、ノードの形状及び位置は、図４に示すように定義されている。この例では、２つのノード１００，２００を図示している。そして、ノード１００は、点ａ，ｂ，ｃ，ｄを４頂点とする四角形形状であり、当該各頂点座標にて形状及び位置が特定されている。また、ノード２００の形状及び位置も同様に、各頂点ｅ，ｆ，ｇ，ｈの座標にて特定されている。ここでは、座標系は、頂点ａが原点（０，０）となっており、右方向にＸ方向、下方向にＹ方向を取る。

また、上記エッジ格納部２２（エッジ情報記憶手段）は、上述した各ノード間を接続するエッジ自体を特定する情報と、エッジの位置、形状を特定する情報と、からなるエッジ情報を記憶している。具体的に、エッジ情報は、エッジの位置及び形状を特定する情報として、エッジが接続されているノードとの接続位置（接続点）、当該接続位置からエッジが延びる方向、エッジ自体の折れ曲がり位置、がある。例えば、エッジは、図４に示すように定義されている。この例では、ノード１００に接続された２つのエッジ３００，４００を示している。

そして、エッジ３００は、ノード１００のｂｃ辺に接続しており、上記座標系上における、ノード１００との接続位置Ｒ（１０，４）、この接続位置Ｒからエッジが延びる方向Ｄ＝０度、エッジの２箇所の折れ曲がり位置Ｂ１（１５，４），Ｂ２（１５，１０）、によって特定されており、これら各座標Ｒ，Ｂ１，Ｂ２と方向Ｄが、エッジ情報として格納されている。なお、エッジ３００の一端側である接続位置Ｒとは反対側の他端は、ノード２００との接続位置にて特定される。また、エッジが延びる方向は、図の右方向であるＸ軸方向を０度とし、図の下方向であるＹ軸方向が９０度となるよう、時計回りに角度が増加するよう定義している。

そして、上記編集処理部１２は、上記ノード格納部２１とエッジ格納部２２とに記憶された各ノード情報及び各エッジ情報に基づいて、ノードの位置及び形状と、これらノードを接続するエッジの位置及び形状を特定し、表示処理部１１を介して表示部３（表示装置）に表示出力する。これにより、図２（ａ）に示すように、「クラス」を表す複数のノードと、各ノード間を接続するエッジと、からなるグラフが表示出力され、グラフの編集者は、グラフの全体形状を視認することができる。このように、編集処理部１２と表示処理部１１とは、グラフを表示出力する表示出力手段として機能する。

また、上記編集処理部１２は、操作部４から編集者によって入力された、グラフを変更する操作内容を表す変更操作情報を受け付ける。例えば、編集者によって入力される変更操作情報は、マウスの操作によって入力される、ノードの特定の辺を移動することによるノードの拡大や縮小を表す情報であったり、あるいは、ノード自体の移動を表す情報である。

なお、ノードの位置の移動は、該当するノードの特定の辺の拡大と縮小との組み合わせによって表すことができるため、編集処理部１２では、移動の変更操作が入力されると、ノードの辺の拡大と縮小の変更操作情報として受け付ける。例えば、ノードが上方向に移動した場合、上辺を上方に拡大、下辺を上方に縮小、とみなしてかかる入力を受け付け、以下に説明するノードの変更処理を行う。そして、編集処理部１２は、ノードの変更操作情報を受け付けると、かかる変更操作情報をレイアウト修正処理部１３に通知する。

上記レイアウト修正処理部１３は、上述したように、ノードの拡大、縮小（あるいは拡大、縮小の組み合わせからなる移動）の変更操作情報を受けると、これに対応してノードやエッジの形状、位置などを変更する処理を行う。まずはじめに、変更対象となっているノードのノード情報をノード格納部２１から読み出し、そのノード情報の各頂点の座標を、変更操作情報に応じて変更して、ノードの拡大、縮小の編集処理を実行する。例えば、図２（ｂ）及び図３（ａ）の網掛けにて示すノードのように、右方向に拡大したり、図３（ｂ）の網掛けにて示すノードのように、上方向に拡大するよう、ノードの各頂点の座標を変更する。そして、変更したノードを特定する情報と、当該ノードの変更後の座標が設定されたノード変更コマンドを生成して、ノード変更コマンド格納部２３に蓄積する。

また、このノードの拡大、縮小により、他のノードやエッジの位置等を変更する必要が生じうる。従って、レイアウト修正処理部１３は、他のノードやエッジの変更が必要であるか否かを判別する処理を行う。この判別を行うためのルールは、予めレイアウト修正処理部１３に組み込まれて設定されている。そして、他のノードやエッジの変更が必要である場合には、当該ノードやエッジの変更後の位置、形状等を算出し、変更処理を指示するノード変更コマンド及びエッジ変更コマンドを生成して、それぞれノード変更コマンド格納部２３とエッジ変更コマンド格納部２４に格納しておく。このとき、ノード変更コマンドやエッジ変更コマンドは、上述同様に、変更するノードやエッジを特定する情報と、当該ノードやエッジの変更後の座標が設定される。

ここで、ノードやエッジの変更処理の一例を、図５乃至図８を参照して説明する。まず、図５（ａ）においては、ノード１００の右辺ｂｃが右側に拡大する変更操作入力を受けたときの様子を示す。この場合に、ノード１００の右辺ｂｃの拡大位置は、符号１０１〜１０４に示すように、様々な位置が考えられるが、例えば、図５（ｂ）の辺ｂ’ｃ’に示すように、エッジ３００の折曲がり点Ｂ１，Ｂ２を越えるところまで拡大したとする。すると、まず、レイアウト修正処理部１３は、上述したように、ノード１００の拡大を指示するノード変更コマンドを生成して格納する。

続いて、レイアウト修正処理部１３は、上記ノード１００の拡大により、他のノードやエッジの変更が必要か否かを判別する。この判別は、例えば、拡大されたノード１００の右辺ｂｃに接続されているエッジの接続位置Ｒと、折り曲がり位置Ｂ１，Ｂ２が、ノード１００自体と重なるか否かを判別することで行う。つまり、図５（ｂ）に示すノードを右側に拡大する場合には、当該拡大方向である右方向のノードの座標（ｂ’，ｃ’のＸ座標）が、エッジの接続位置ＲのＸ座標よりも大きくなれば当該接続位置の変更が必要であると判別する。また、拡大方向のノードの座標（ｂ’，ｃ’のＸ座標）が、折り曲がり位置Ｂ１，Ｂ２のＸ座標以上となるか場合に、変更が必要であると判別する。なお、変更が必要であると判別する基準は、必ずしも上記基準に限定されず、例えば、拡大したノードの座標と、エッジの折れ曲がり位置の座標とが、予め設定された範囲内である場合に、エッジの変更が必要であると判別してもよい。

そして、エッジの変更が必要であると判別した場合には、当該エッジの接続位置Ｒ、折れ曲がり位置Ｂ１，Ｂ２を、ノードを拡大した方向つまりＸ方向にさらに移動するよう、各座標を変更する。このとき、エッジの接続位置Ｒは、ノード１００の右辺ｂ’ｃ’との接続が維持されるよう、つまり、ｂ’，ｃ’のＸ座標と同じになるよう移動する。また、エッジの折れ曲がり位置Ｂ１，Ｂ２は、ノード１００と重ならないよう、つまり、Ｂ１，Ｂ２のＸ座標をＸ方向に移動して、ノード１００のｂ’ｃ’辺のＸ座標よりも大きい座標上に位置するよう、Ｂ１’，Ｂ２’のように移動する。そして、このような移動を実行するために、当該エッジ３００と特定する情報と、変更後の接続位置や折れ曲がり位置の座標を設定したエッジ変更コマンドを生成して、エッジ変更コマンド格納部２４に格納しておく。

なお、上述したように、ノード１００の右辺ｂｃのみを拡大する場合には、上辺ａｂ、下辺ｃｄ、左辺ｄａに接続しているエッジは影響を受けないため、かかるエッジの変更の必要は無い。また、ノードの他の辺が拡大する場合にも、当該拡大した辺の方向に位置するノードやエッジに対して、上述同様の判別基準を適用し、ノードやエッジの変更が必要であるか否かを判別可能である。なお、変更が必要か否かの判別基準は、拡大方向の座標の取り方に対応して適用される。

次に、図６（ａ）に、ノード１００の右辺ｂｃを左方向に縮小させる変更操作入力を受けたときの様子を示す。この場合に、ノード１００の右辺ｂｃの縮小位置は、符号１１１〜１１３に示すように、様々な位置が考えられるが、例えば、図６（ｂ）の辺ｂ’ｃ’に示すように、下辺ｃｄに接続しているエッジ４００の接続位置Ｒ３を越えるところまで縮小したとする。すると、まず、レイアウト修正処理部１３は、上述したように、ノード１００の縮小を指示するノード変更コマンドを生成して格納する。

続いて、レイアウト修正処理部１３は、上記ノード１００の縮小により、他のノードやエッジの変更が必要か否かを判別する。この判別は、例えば、縮小されたノード１００の右辺ｂｃに接続されているエッジ３００の接続位置Ｒ、及び、下辺ｃｄに接続されているエッジ４００の接続位置Ｒ３が、変更後のノード１００のいずれかの辺の上に位置しているか否かを座標から判別する。つまり、この場合には、接続している各エッジ３００，４００の接続位置Ｒ，Ｒ３が、ノードから離れてしまうため、各エッジ３００，４００の接続位置Ｒ、Ｒ３の変更が必要であると判別する。

また、エッジ４００の折り曲がり位置Ｂ３，Ｂ４の縮小方向の座標（Ｘ座標）が、縮小された辺ｂ’，ｃ’のＸ座標以下となるか否かにより、変更が必要であるかを判別する。つまり、この場合には、エッジ４００の折れ曲がり位置Ｂ３のＸ座標が、縮小された辺ｂ’，ｃ’のＸ座標以下となるため、当該折れ曲がり位置Ｂ３の変更が必要であると判別する。なお、変更が必要であると判別する基準は、必ずしも上記基準に限定されず、例えば、縮小したノードの座標と、エッジの折れ曲がり位置の座標とが、予め設定された範囲内である場合に、エッジの変更が必要であると判別してもよい。

そして、エッジの変更が必要であると判別した場合には、当該エッジの接続位置Ｒ，Ｒ３、折れ曲がり位置Ｂ３を、ノードを縮小した方向つまりＸ方向にさらに移動するよう、各座標を変更する。このとき、エッジの接続位置Ｒ，Ｒ３は、ノード１００の右辺ｂ’ｃ’と下辺ｃ’ｄとの接続がそれぞれ維持されるよう移動する。また、エッジの折れ曲がり位置Ｂ３は、当該エッジ４００の接続位置からの方向がＤ＝９０度で変化しないよう、そのＸ座標をＸ方向に移動する。そして、このような移動を実行するために、当該エッジ３００，４００をそれぞれ特定する情報と、変更後の接続位置や折れ曲がり位置の座標を設定したエッジ変更コマンドを生成して、エッジ変更コマンド格納部２４に格納しておく。

なお、上述したように、ノード１００の右辺ｂｃのみを縮小する場合には、左辺ｄａに接続しているエッジは影響を受けないため、かかるエッジの変更の必要は無い。また、ノードの他の辺が縮小する場合にも、当該縮小した辺と、当該辺を挟む他の辺に接続されたエッジに対して、上述同様の判別基準を適用し、エッジの変更が必要であるか否かを判別可能である。なお、変更が必要か否かの判別基準は、縮小方向の座標の取り方に対応して適用される。

次に、図７（ａ）は、ノード１００の右辺ｂｃが右側に拡大する変更操作入力を受けたときの様子を示す。この場合に、ノード１００の右辺ｂｃの拡大位置は、符号１２１，１２２に示すように、様々な位置が考えられるが、例えば、図７（ｂ）の辺ｂ’ｃ’に示すように、他のノード２００と重なるまで拡大したとする。すると、まず、レイアウト修正処理部１３は、上述したように、ノード１００の拡大を指示するノード変更コマンドを生成して格納する。

続いて、レイアウト修正処理部１３は、上記ノード１００の拡大により、他のノードと重なっていて、当該ノードの変更が必要か否かを判別する。この判別は、例えば、拡大されたノード１００の右辺ｂｃの少なくとも一部が、他のノード２００の領域内に位置するか否かを、各ノード１００，２００の座標に基づいて判別する。つまり、図７（ｂ）に示すノードを右側に拡大する場合には、当該拡大方向である右方向のノードの座標（ｂ’，ｃ’のＸ座標）が、その拡大方向に位置する他のノード２００の４頂点座標ｅｆｇｈ内に位置する場合には、当該他のノード２００の位置の変更が必要であると判別する。

そして、他のノード２００の変更が必要であると判別した場合には、当該ノードの各頂点の座標ｅｆｇｈを、ノードの拡大した方向つまりＸ方向にさらに移動し、拡大したノードと重ならないよう各頂点ｅ’ｆ’ｇ’ｈ’の座標を変更する。具体的には、移動するノードの各頂点ｅ’ｆ’ｇ’ｈ’のＸ座標を、拡大されたノード１００の右辺ｂ’ｃ’のＸ座標よりも大きい値に変更する。このとき、各ノード１００，２００間に所定の隙間が空くよう座標を変更する。そして、このような移動を実行するために、他のノード２００と特定する情報と、変更後の各頂点の座標を設定したノード変更コマンドを生成して、ノード変更コマンド格納部２３に格納しておく。なお、他のノードの変更が必要であると判別する基準は、必ずしも上記基準に限定されず、例えば、拡大したノードの座標と、拡大方向に位置する他のノードの座標とが、予め設定された範囲内である場合に、当該他のノードの変更が必要であると判別してもよい。

また、上記ノード１００の拡大により、当該ノード１００に接続されたエッジ３００に変更が必要か否かを、上述したように判別する。さらに、上述したように移動した他のノード２００に接続されたエッジがある場合には、当該他のノード２００の移動によってこれに接続されたエッジの変更が必要であるか、ということも上述同様に判別する。そして、エッジの変更が必要であれば、エッジの接続位置や折れ曲がり位置とを変更して、当該エッジと特定する情報と、変更後の接続位置や折れ曲がり位置の座標を設定したエッジ変更コマンドを生成して、エッジ変更コマンド格納部２４に格納しておく。図７（ｂ）の場合には、ノード３００の両端である接続位置、及び、２箇所の折れ曲がり位置Ｂ１，Ｂ２の座標をそれぞれ変更する。

次に、図８（ａ）に、ノード１００を移動する変更操作入力を受けたときの様子を示す。これは、上述したように、ノード１００の右辺ｂｃを右方向に拡大し、左辺ｄａを右方向に縮小したものとして扱うことができる。従って、上述同様に、拡大方向に位置する他のノードやエッジに変更が必要であるか否かを判別し、変更が必要であると判別されたノード及びエッジの位置、形状を変更する。

例えば、図８（ｂ）の辺ｂ’ｃ’に示すように、ノード１００の右辺が他のノード２００と重なるまで移動（拡大）したとすると、上述同様に、移動したノード１００の各頂点が、移動（拡大）方向に位置する他のノード２００の範囲内に位置しないよう、つまり、ノード１００とノード２００とが重ならないよう、かつ、所定の隙間を空けて、他のノード２００の各頂点の座標ｅ’ｆ’ｇ’ｈ’を変更する。そして、この他のノード２００の移動を実行するためのノード変更コマンドを生成して、格納しておく。

そして、さらに、拡大したノード１００の右辺及び移動した他のノード２００の左辺には、それぞれエッジが接続されているため、これら各エッジ３００，５００の接続位置Ｒ１，Ｒ２、及び、折れ曲がり位置Ｂ５，Ｂ６を、上述同様に変更する（Ｒ１’，Ｒ２’，Ｂ５’，Ｂ６）。そして、このような移動を実行するためのエッジ変更コマンドを生成して、格納しておく。

以上のようにして、レイアウト修正処理部１３は、ノード、エッジの位置、形状等の変更処理を行い、各変更コマンドを格納する。そして、レイアウトの修正が終了すると、その旨を編集処理部１２に通知する。

そして、編集処理部１２は、レイアウト修正処理部１３からレイアウト修正の終了通知を受けると、レイアウト修正処理部１３にて格納されたノード変更コマンド格納部２３内のノード変更コマンド、及び、エッジ変更コマンド格納部２４に格納されたエッジ変更コマンドを実行する。そして、上記各コマンドにて設定されたノードやエッジの位置、形状を、変更後の位置、形状を表す情報を、該当するノード格納部２１のノード情報及びエッジ格納部２２内のエッジ情報に変更記憶する。

以上のように、編集処理部１２とレイアウト修正処理部１３とは、ノードの変更操作の入力に応じて、ノードやエッジのレイアウトの変更処理を行い、変更後のノード及びエッジの情報を変更して記憶する編集手段として機能する。

その後、上述同様に、表示処理部１１が、変更後のノード情報及びエッジ情報に基づいて、ノードとエッジを表示部３に表示出力する。これにより、編集者は、変更後のノードとエッジからなるグラフを視認することができる。

［動作］
次に、上述したグラフ編集装置の動作を、図９のフローチャートを参照して説明する。まず、ノード格納部２１とエッジ格納部２２に格納されているノード情報及びエッジ情報に基づいて、ノードとエッジとからなるグラフを、表示部３に表示出力する（表示出力工程）。

その後、編集者にて、マウスの操作等による、ノードの形状や位置を変更する入力があると（ステップＳ１）、この変更操作にかかる変更後のノードの形状を求める（ステップＳ２）。続いて、このノードの変更が縦横それぞれに対し、拡大であるか縮小であるか、を判定する（ステップＳ３）。なお、ノードを移動した場合は、拡大と縮小の組み合わせと考える。たとえば、上に移動した場合、上辺は拡大、下辺は縮小とみなして両方の処理を実施する。

そして、縮小である場合には（ステップＳ４で［縮小］）、当該縮小にかかるノードの変更のみを行い、エッジの処理へ移行する（ステップＳ１０に進む）。一方、ノードの拡大の場合には（ステップＳ４で［拡大］）、まず、ノードの拡大処理を行い、その後、拡大された向きに存在する他のノードを１つ取得する（ステップＳ５）。そして、変更後のノードの形状と、他のノードが重なっているかどうかを判定する（ステップＳ６）。

上記判定によりノード同士が重なっている場合には（ステップＳ６で［重なっている］）、他のノードを重ならない位置に移動させるコマンドを生成して、ノード変更コマンド格納部２３に格納する（ステップＳ７）。

そして、上記処理を、ノードが拡大された向きに存在する全ノードに対し実施する（ステップＳ９で［未処理ノードが存在］）。その後、全てのノードに対し実施した後（ステップＳ９で［全ノード処理］）、エッジの処理に移行する（ステップＳ１０へ進む）。

次に、拡大または縮小された向きに存在するエッジを１つ取得する（ステップＳ１０）。そして、変更後のノードとエッジが干渉するか、つまり、エッジに変更か必要かどうかを判定する（ステップＳ１１）。ここでは、上述したように、ノードとの接続位置を確保できない場合、他の辺に移動してしまう場合、ノードが折れ曲がり位置に重なる場合などの場合を、変更が必要であるとして判定する。

そして、エッジに変更が必要であると判定した場合には（ステップＳ１２で［干渉あり］）、エッジの変形だけでなく、ノードの移動も必要かどうかを判定する（ステップＳ１３）。ノードの移動が必要な場合とは、例えば、エッジを最小の大きさにした場合でも、接続の両端のいずれか一方もしくは両方との干渉を解消できない状態を言う。そのような移動が必要な状態の場合は（ステップＳ１４で［移動必要］）、上述同様に、まずノード同士を重ならない位置に移動させるよう、ノード変更コマンドを生成してノード変更コマンド格納部２３に格納する（ステップＳ１５）。また、ノードの移動が必要でない場合でも（ステップＳ１４で［移動不要］）、エッジのノードに対する干渉を解消するためのエッジ変形コマンドを生成して、エッジ変更コマンド格納部２４に格納する（ステップＳ１６）。

そして、上記処理を、全エッジに対し実施する（ステップＳ１７で［未処理エッジが存在］）。全てのエッジに対し実施した後（ステップＳ１７で［全エッジ処理］）、ノード変更コマンド格納部２３から１つノード変更コマンドを選択し、ノードの変形や移動を実施する。そして、全てのノードの変形や移動を実施する。同様に、エッジ変更コマンド格納部２４から１つエッジ変更コマンドを選択し、エッジの変形を実施する。そして、全てのエッジの変形を実施する。以上のようにして変形や移動したノード、エッジの情報を、ノード格納部２１及びエッジ格納部２２に格納する（ステップＳ１８、編集処理工程）。そして、かかる情報に基づいて、変更後のノードとエッジを表示出力する（ステップＳ１９、再表示出力工程）。

なお、上記では、全てのノードとエッジの移動、変更処理が完了した後に、表示部３にノードとエッジを表示出力しているが、各ノードやエッジの移動、変更処理を実施、つまり、各変更コマンドを生成する毎に、ノードやエッジを表示出力してもよい（再表示出力工程）。

以上のように、本実施形態におけるグラフ編集装置によると、所定のノードの位置や形状の変更の入力を受け付けたときに、ノード同士が重ならず、また、エッジがノードとの接続状態を維持しつつ、かつ、エッジがノードと重ならないよう、ノード及びエッジの位置、形状を変更して、変更後のノード及びエッジを表示出力する。これにより、ノードの変形や移動に応じて、当該ノードに対するエッジの位置関係を維持し、また、エッジがノードの背後に隠れないようエッジの位置が変形されて出力される。従って、編集者がグラフの編集を認識しやすく表示されるため、編集者にとって利便性の向上を図ることができる。

本発明は、ＵＭＬや電子回路などで用いられるノードとエッジを用いたグラフを作成・編集するために使用するコンピュータに適用可能であり、産業上の利用可能性を有する。

コンピュータの構成を示す機能ブロック図である。 ノードとエッジとを有するグラフの一例を示す図である。 ノードとエッジとを有するグラフの一例を示す図である。 ノードとエッジの位置、形状を特定する座標の一例を示す図である。 ノードとエッジとを変形するときの様子を説明する図である。 ノードとエッジとを変形するときの様子を説明する図である。 ノードとエッジとを変形するときの様子を説明する図である。 ノードとエッジとを変形するときの様子を説明する図である。 コンピュータの動作を示すフローチャートである。

符号の説明

１ コンピュータ
３ 表示部
４ 操作部
１１ 表示処理部
１２ 編集処理部
１３ レイアウト修正処理部
２１ ノード格納部
２２ エッジ格納部
２３ ノード変更コマンド格納部
２４ エッジ変更コマンド格納部
１００，２００ ノード
３００，４００，５００ エッジ

Claims (8)

1. ノード及び当該ノード間を接続するエッジからなるグラフを編集するグラフ編集装置であって、
   前記ノードの位置及び形状を特定するノード情報を記憶するノード情報記憶手段と、
   少なくとも前記エッジの当該エッジが接続された前記ノードに対する位置、折れ曲がり位置を特定するエッジ情報を記憶するエッジ情報記憶手段と、
   前記ノード情報及び前記エッジ情報に基づいて、前記ノード及び前記エッジを表示装置に表示出力する表示出力手段と、を備え、
   前記ノードの位置及び／又は形状の変更操作の入力に応じて、当該変更操作された前記ノードの前記ノード情報記憶手段に記憶された前記ノード情報を変更記憶すると共に、当該変更記憶された前記ノード情報に基づいて、当該ノード情報に対応する前記ノードに接続された前記エッジの前記エッジ情報記憶手段に記憶された前記エッジ情報を、前記変更記憶されたノードとの接続状態を維持しつつ、かつ、当該ノードと重ならないよう、前記エッジの位置、折れ曲がり位置を移動して変更記憶する編集手段を備え、
   前記編集手段は、前記ノードの位置及び／又は形状の変更に応じて当該ノードが前記エッジの折れ曲がり位置上に位置する場合に、当該ノードの位置及び／又は形状を変更した方向に、前記エッジの折れ曲がり位置を前記ノードに重ならないよう移動する、
   ことを特徴とするグラフ編集装置。
2. 前記編集手段は、前記ノードの位置及び／又は形状の変更に応じて当該ノードの特定の辺に対する前記エッジの接続状態を維持するよう当該エッジの位置を移動する、
   ことを特徴とする請求項１記載のグラフ編集装置。
3. ノード及び当該ノード間を接続するエッジからなるグラフを編集するグラフ編集装置であって、
   前記ノードの位置及び形状を特定するノード情報を記憶するノード情報記憶手段と、
   少なくとも前記エッジの当該エッジが接続された前記ノードに対する位置、折れ曲がり位置を特定するエッジ情報を記憶するエッジ情報記憶手段と、
   前記ノード情報及び前記エッジ情報に基づいて、前記ノード及び前記エッジを表示装置に表示出力する表示出力手段と、を備え、
   前記ノードの位置及び／又は形状の変更操作の入力に応じて、当該変更操作された前記ノードの前記ノード情報記憶手段に記憶された前記ノード情報を変更記憶すると共に、当該変更記憶された前記ノード情報に基づいて、当該ノード情報に対応する前記ノードに接続された前記エッジの前記エッジ情報記憶手段に記憶された前記エッジ情報を、前記変更記憶されたノードとの接続状態を維持しつつ、かつ、当該ノードと重ならないよう、前記エッジの位置、折れ曲がり位置を移動して変更記憶する編集手段を備え、
   前記編集手段は、前記ノードの位置及び／又は形状の変更に応じて当該ノードが他のノードの位置上に位置する場合に、前記ノードの位置及び／又は形状を変更した方向に、前記他のノードを変更したノードと重ならないよう移動して、当該他のノードの前記ノード情報記憶手段に記憶された前記ノード情報を変更記憶すると共に、前記他のノードの移動に応じて、当該他のノードに接続された前記エッジの前記エッジ情報記憶手段に記憶されたエッジ情報を、当該他のノードとの接続状態を維持しつつ、かつ、当該他のノードと重ならないよう、当該他のノードの移動方向に、前記エッジの位置、折れ曲がり位置を移動して変更記憶する、
   ことを特徴とするグラフ編集装置。
4. ノード及び当該ノード間を接続するエッジからなるグラフを編集するためのコンピュータに、
   予め記憶された、前記ノードの位置及び形状を特定するノード情報と、少なくとも前記エッジの当該エッジが接続された前記ノードに対する位置、折れ曲がり位置を特定するエッジ情報と、に基づいて、前記ノード及び前記エッジを表示装置に表示出力する表示出力手段と、
   前記ノードの位置及び／又は形状の変更操作の入力に応じて、当該変更操作された前記ノードの前記ノード情報を変更記憶すると共に、当該変更記憶された前記ノード情報に基づいて、当該ノード情報に対応する前記ノードに接続された前記エッジの前記エッジ情報を、前記変更記憶されたノードとの接続状態を維持しつつ、かつ、当該ノードと重ならないよう、前記エッジの位置、折れ曲がり位置を移動して変更記憶する編集手段と、
   を実現させると共に、
   前記編集手段は、前記ノードの位置及び／又は形状の変更に応じて当該ノードが前記エッジの折れ曲がり位置上に位置する場合に、当該ノードの位置及び／又は形状を変更した方向に、前記エッジの折れ曲がり位置を前記ノードに重ならないよう移動する、
   ことを実現させるためのプログラム。
5. ノード及び当該ノード間を接続するエッジからなるグラフを編集するためのコンピュータに、
   予め記憶された、前記ノードの位置及び形状を特定するノード情報と、少なくとも前記エッジの当該エッジが接続された前記ノードに対する位置、折れ曲がり位置を特定するエッジ情報と、に基づいて、前記ノード及び前記エッジを表示装置に表示出力する表示出力手段と、
   前記ノードの位置及び／又は形状の変更操作の入力に応じて、当該変更操作された前記ノードの前記ノード情報を変更記憶すると共に、当該変更記憶された前記ノード情報に基づいて、当該ノード情報に対応する前記ノードに接続された前記エッジの前記エッジ情報を、前記変更記憶されたノードとの接続状態を維持しつつ、かつ、当該ノードと重ならないよう、前記エッジの位置、折れ曲がり位置を移動して変更記憶する編集手段と、
   を実現させると共に、
   前記編集手段は、前記ノードの位置及び／又は形状の変更に応じて当該ノードが他のノードの位置上に位置する場合に、前記ノードの位置及び／又は形状を変更した方向に、前記他のノードを変更したノードと重ならないよう移動して、当該他のノードの前記ノード情報記憶手段に記憶された前記ノード情報を変更記憶すると共に、前記他のノードの移動に応じて、当該他のノードに接続された前記エッジの前記エッジ情報記憶手段に記憶されたエッジ情報を、当該他のノードとの接続状態を維持しつつ、かつ、当該他のノードと重ならないよう、当該他のノードの移動方向に、前記エッジの位置、折れ曲がり位置を移動して変更記憶する、
   ことを実現させるためのプログラム。
6. ノード及び当該ノード間を接続するエッジからなるグラフを編集するグラフ編集方法であって、
   予め所定の記憶装置に記憶された、前記ノードの位置及び形状を特定するノード情報と、少なくとも前記エッジの当該エッジが接続された前記ノードに対する位置、折れ曲がり位置を特定するエッジ情報と、に基づいて、前記ノード及び前記エッジを表示装置に表示出力する表示出力工程と、
   前記ノードの位置及び／又は形状の変更操作の入力に応じて、当該変更操作された前記ノードの前記ノード情報を変更記憶すると共に、当該変更記憶された前記ノード情報に基づいて、当該ノード情報に対応する前記ノードに接続された前記エッジの前記エッジ情報を、前記変更記憶されたノードとの接続状態を維持しつつ、かつ、当該ノードと重ならないよう、前記エッジの位置、折れ曲がり位置を移動して変更記憶する編集工程と、
   前記編集工程にて変更記憶された前記ノード情報及び／又は前記エッジ情報に基づいて、前記ノード及び／又は前記エッジを表示装置に再表示出力する再表示出力工程と、
   を有し、
   前記編集工程は、前記ノードの位置及び／又は形状の変更に応じて当該ノードが前記エッジの折れ曲がり位置上に位置する場合に、当該ノードの位置及び／又は形状を変更した方向に、前記エッジの折れ曲がり位置を前記ノードに重ならないよう移動する、
   ことを特徴とするグラフ編集方法。
7. ノード及び当該ノード間を接続するエッジからなるグラフを編集するグラフ編集方法であって、
   予め所定の記憶装置に記憶された、前記ノードの位置及び形状を特定するノード情報と、少なくとも前記エッジの当該エッジが接続された前記ノードに対する位置、折れ曲がり位置を特定するエッジ情報と、に基づいて、前記ノード及び前記エッジを表示装置に表示出力する表示出力工程と、
   前記ノードの位置及び／又は形状の変更操作の入力に応じて、当該変更操作された前記ノードの前記ノード情報を変更記憶すると共に、当該変更記憶された前記ノード情報に基づいて、当該ノード情報に対応する前記ノードに接続された前記エッジの前記エッジ情報を、前記変更記憶されたノードとの接続状態を維持しつつ、かつ、当該ノードと重ならないよう、前記エッジの位置、折れ曲がり位置を移動して変更記憶する編集工程と、
   前記編集工程にて変更記憶された前記ノード情報及び／又は前記エッジ情報に基づいて、前記ノード及び／又は前記エッジを表示装置に再表示出力する再表示出力工程と、
   を有し、
   前記編集工程は、前記ノードの位置及び／又は形状の変更に応じて当該ノードが他のノードの位置上に位置する場合に、前記ノードの位置及び／又は形状を変更した方向に、前記他のノードを変更したノードと重ならないよう移動して、当該他のノードの前記ノード情報記憶手段に記憶された前記ノード情報を変更記憶すると共に、前記他のノードの移動に応じて、当該他のノードに接続された前記エッジの前記エッジ情報記憶手段に記憶されたエッジ情報を、当該他のノードとの接続状態を維持しつつ、かつ、当該他のノードと重ならないよう、当該他のノードの移動方向に、前記エッジの位置、折れ曲がり位置を移動して変更記憶する、
   ことを特徴とするグラフ編集方法。
8. 前記再表示出力工程は、前記編集工程中に作動し、前記ノード情報が変更記憶されたとときに当該ノード情報に基づいて前記ノードを表示装置に再表示出力し、前記エッジ情報が変更記憶されたときに当該エッジ情報に基づいて前記エッジを表示装置に再表示出力する、
   ことを特徴とする請求項６又は７記載のグラフ編集方法。
   

Images