JPH09161084A - グラフ自動描画装置及びグラフ自動描画法 - Google Patents

Abstract

(57)【要約】 【課題】本発明はグラフ自動描画装置及びグラフ自動描
画法に関し、階層関係、隣接関係、及び順序関係からな
る３種類の関係情報をそれぞれ異なる表現形式で明確に
区別して表現できるようにし、１つの図で大規模化、複
雑化した情報を３種類の関係情報を区別しながら視覚的
に明確に表現できるようにする。 【解決手段】順序付木情報取得部１４と位置サイズ決定
部１５と隣接情報取得部１６と隣接エッジ決定部１７を
備え、前記各部により、順序付木の木構造を領域の包含
関係で表現し、ノード間の順序を配置の順序で表現し、
隣接エッジを直線或いは曲線からなる線分で表現して、
順序付木に隣接エッジが混在したグラフの各ノードの位
置及び隣接エッジの経路を決定することで、グラフの自
動描画を可能にした。また、隣接エッジを円弧或いは楕
円弧で表現したり、隣接エッジの向きを円弧或いは楕円
弧の向きで表現する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、与えられたグラフ
情報からグラフ自動描画のための各種処理を行い、その
結果の情報を基にグラフ自動描画を可能にしたグラフ自
動描画装置及びグラフ自動描画法に関する。

【０００２】なお、ここで言う「グラフ」とは、ノード
の集合とそれらの間の関係を表すエッジの集合から構成
されるものである。本発明はグラフの１つのクラスであ
る「木」を基本として、ノードが順序を持ち、更に別の
関係を表現するエッジが混在したグラフを対象とするも
のである。

【０００３】

【従来の技術】以下、従来例を説明する。 §１：グラフ自動描画法の説明 ノードの集合とそれらの間の関係を表すエッジの集合か
ら構成されるグラフは、情報科学や工学をはじめ様々な
分野で多様な構造（ネットワーク、処理フロー、組織構
造など）を表現するために利用されている。グラフは数
学的には（グラフ理論では）、ノードとエッジからなる
トポロジカルな構造であり、図とは独立の概念である
が、図による表現はその構造の理解を助けるのに非常に
有効である。

【０００４】しかしながら、その構造を分かりやすく図
に描くことは人間にとって面倒な作業であるため、計算
機に自動的に描かせたいという要求がある。グラフの
内、広く利用されているものに「木」と呼ばれるクラス
がある。例えば、組織構造や、文章構造（章立て）など
は木で表現することができる。また、ＵＮＩＸのファイ
ル・システムなどは、木の構造を利用してファイル管理
を行っている。

【０００５】このように、木が多用されるのは、組織構
造や文章構造が持つ階層的な関係（階層構造）を表現す
るのに木が適しているからと言える。しかしながら、実
世界の構造の多くは木によって表現される階層構造のよ
うに単純ではなく、複数の関係が複合していることが多
い。そのような関係とは、例えば、「隣接関係」や「順
序関係」と呼ばれるようなものである。先の例では次の
ようになる。

【０００６】：企業における組織構造は基本的には、
部の下に課があり、課の下に係があるというように階層
構造であり、各部署間には職制上の順序が存在し、更に
「兼任」という形で同一人物が複数の部署に所属してい
る。

【０００７】：文章構造（章立て）は基本的には、章
の下に節があり、節の下に項があるというように階層構
造であるが、章、節、項はそれぞれ番号付けられた順序
を持ち、文章間には或る単位で「参照関係」が存在す
る。

【０００８】：ＵＮＩＸのファイル・システムは基本
的には、ディレクトリの下にサブディレクトリがあると
いうように木構造として管理されているが、ファイル名
やディレクトリ名は、例えば、アルファベットの順の辞
書式順序を持ち、「リンク」とう形態で、同一ファイル
が複数の場所で共有されている。これらの関係の複合の
仕方を整理すると次の表のようになる。

【０００９】 ところで、従来のグラフ自動描画法の大部分は、全ての
エッジを同一の表現形式、すなわち、線分（直線または
曲線）で表現するものである。この方法では、エッジの
種類や色や線種などの属性で区別しなければならず、エ
ッジの種類によって表現したい意味を本質的に区別して
表現することはできない。それに対して、例えば、次の
ようなグラフ自動描画法に関する文献が知られている。

【００１０】文献１：三末和男、杉山公造、「図的思考
支援を目的とした複合グラフの階層的描画法につい
て」、情報処理学会論文誌、Ｖｏｌ．３０，Ｎｏ．１
０，ＰＰ．１３２４〜１３３４、１９８９． 文献２：Kozo Sugiyama and Kazuo Misue. 「Visualizat
ion of structural information: Automatic drawing o
f compound digraphs. IEEE Trans.SMC,Vol.21,No.4,p
p.876-892,1991. 前記文献１、２に示されたグラフ自動描画法は、階層関
係と隣接関係の２種類の関係（関係情報）を「折れ線」
と「領域の包含関係」という全く異なる方法で表現する
ため、それらの意味の違いを明確に区別することはでき
る。しかしなから、このグラフ自動描画法は、エッジを
表す折れ線の交差数が少なくなるようノードの順序を決
定するものである。つまり、この方法は、折れ線で表さ
れたエッジによって各領域内におけるノードの順序や位
置を決定するものである。

【００１１】

【発明が解決しようとする課題】前記のような従来のも
のにおいては、次のような課題があった。 (1) ：従来のグラフ自動描画法の大部分は、全てのエッ
ジを同一の表現形式、すなわち、線分（直線または曲
線）で表現するものである。この方法では、エッジの種
類や色や線種などの属性で区別しなければならず、エッ
ジの種類によって表現したい意味を本質的に区別して表
現することができなかった。

【００１２】(2) ：前記文献１、文献２に開示されたグ
ラフ自動描画法では、階層関係と隣接関係の２種類の関
係（関係情報）を「折れ線」と「領域の包含関係」とい
う全く異なる方法で表現するため、それらの意味の違い
を明確に区別することはできる。

【００１３】しかしなから、この方法は、エッジを表す
折れ線の交差数が少なくなるようノードの順序を決定す
るものである。つまり、この方法は、折れ線で表された
エッジによって各領域内におけるノードの順序や位置を
決定するため、例えば、文書などのように順序が重要で
ある場合には不向きである。すなわち、前記の方法で
は、グラフが本来持っている順序を表現できないため、
文章などのように順序が重要である場合には利用できな
い。

【００１４】本発明は、このような従来の課題を解決
し、階層関係、隣接関係、及び順序関係からなる３種類
の関係情報をそれぞれ異なる表現形式で明確に区別して
表現できるようにすると共に、ノードの位置やエッジの
経路などを自動決定することにより、１つの図において
大規模化、複雑化した情報を前記３種類の関係情報を区
別しながら視覚的に明確に表現できるようにすることを
目的とする。

【００１５】

【課題を解決するための手段】図１は本発明の原理説明
図である。 §１：本発明の基本的な説明 本発明では、グラフを自動描画する場合、次の２つの条
件を満たすようにして描画する。すなわち、：条件１
は、「階層エッジ」と「隣接エッジ」を別の表現形式で
表現することである。：条件２は、「ノードの順序関
係」を「配置」で表現することである。

【００１６】つまり、本発明のグラフ自動描画処理で必
要とされるグラフは「階層関係」、「隣接関係」、「順
序関係」の３種類の関係を表現できるものである。この
場合、階層関係を表現する木を基本とし、ノードに順序
関係があり、更に階層関係とは別の隣接関係が存在する
複合的なグラフと言える。以後、この種のグラフを「順
序付複合木」と記す。また、木を構成するエッジ、すな
わち、階層関係を表すエッジを「階層エッジ」、隣接関
係を表すエッジを「隣接エッジ」と呼び分けて説明す
る。

【００１７】一般にグラフをレイアウトする際に重要な
のは図としての質であり、つまり、良い図は見るものの
理解を助けるが、良くない図は誤解を与えたり混乱を招
いたりする可能性がある。グラフ自動描画装置によって
描きたいのは当然質の良い図である。ここでは、順序付
複合木を良い図として描くための条件として前記２つの
条件を必要とする。前記２つの条件は経験的に取り決め
た条件であるが、広く受け入れられる条件である。

【００１８】前記２つの条件を満たすための順序付複合
木の表現方法として次のような表現方法を採用する。
「ノード」は長方形などの「領域」で表現する。「階層
エッジ」はノードの表す領域の包含関係で表現する。
「隣接エッジ」は線（直線、折れ線、曲線など）で表現
する。「ノードの順序」はノードの並び順（上から下、
右から左など）で表現する。また、順序付複合木ＴをＴ
＝（Ｖ，Ｅ，Ａ，Ｏ）のように形式的に表現する。

【００１９】ここで、Ｖはノードの集合、Ｅは階層エッ
ジの集合、Ａは隣接エッジの集合、ＯはノードＶ上の順
序関係である。エッジは始点ノードと終点ノードの組に
よって（ｖ_h ，ｖ_t ）のように表される。階層エッジは
必ず向きを持たなくても良いとする。

【００２０】§２：本発明の構成の説明 本発明の構成は次の通りである。 (1) ：与えられたグラフ情報から、ノード、ノードの階
層関係のエッジを表す階層エッジ、及びノードの順序か
らなる順序付木に各ノード間の隣接関係のエッジを表す
隣接エッジが混在したグラフの各ノードの位置と隣接エ
ッジの経路を決定することで、グラフの自動描画を可能
にしたグラフ自動描画装置において、装置本体２と、入
力装置２０と、出力装置２１を備え、前記装置本体２に
は、主制御部１１と、メモリ１２と、順序付木情報取得
部１４と、位置サイズ決定部１５と、隣接情報取得部１
６と、隣接エッジ決定部１７を備えた。

【００２１】(2) ：グラフ自動描画装置において、与え
られたグラフ情報からノードＶ、ノードの階層関係のエ
ッジを表す階層エッジＥ、及びノードの順序Ｏからなる
順序付木Ｔ′＝（Ｖ，Ｅ，Ｏ）の構成情報を取得する順
序付木情報取得部１４と、順序付木情報取得部１４が取
得した順序付木の構成情報からノードの位置及びサイズ
を決定する位置サイズ決定部１５と、与えられたグラフ
情報からノードＶ及び各ノード間の隣接関係のエッジを
表す隣接エッジＡからなる隣接グラフＧ＝（Ｖ，Ａ）の
構成情報を取得する隣接情報取得部１６と、隣接情報取
得部１６が取得した隣接グラフの構成情報及び位置サイ
ズ決定部１５が決定したノードの位置及びサイズを基に
隣接エッジの経路を決定する隣接エッジ決定部１７を備
え、前記各部により、順序付木の木構造を領域の包含関
係で表現し、ノード間の順序を配置の順序で表現し、隣
接エッジを直線或いは曲線からなる線分で表現して、順
序付木Ｔ′＝（Ｖ，Ｅ，Ｏ）に隣接エッジＡが混在した
グラフＴ＝（Ｖ，Ｅ，Ａ，Ｏ）の各ノードの位置及び隣
接エッジの経路を決定することで、グラフの自動描画を
可能にした。

【００２２】(3) ：前記(2) のグラフ自動描画装置にお
いて、前記隣接エッジを、円弧或いは楕円弧で表現する
ようにした。 (4) ：前記(2) のグラフ自動描画装置において、前記隣
接エッジの向きを、円弧或いは楕円弧の向きで表現する
ようにした。

【００２３】(5) ：前記(2) 〜(4) のグラフ自動描画装
置において、前記ノードの間の順序を表現する配置の並
びを、順序付木の木構造における深さの偶奇によって縦
方向と横方向とに交互に変えるようにした。

【００２４】(6) ：グラフ自動描画装置により、ノー
ド、ノードの階層関係のエッジを表す階層エッジ、及び
ノードの順序からなる順序付木に各ノード間の隣接関係
のエッジを表す隣接エッジが混在したグラフの各ノード
の位置と隣接エッジの経路を決定することで、グラフの
自動描画を可能にしたグラフ自動描画法であって、前記
順序付木の木構造を領域の包含関係で表現し、ノード間
の順序を配置の順序で表現し、前記隣接エッジを直線或
いは曲線からなる線分で表現するようにした。

【００２５】（作用）前記構成に基づく本発明の作用を
図１に基づいて説明する。入力装置２０からグラフ情報
が入力されると、主制御部１１はそのグラフ情報をメモ
リ１２に格納する。その後主制御部１１の指示により、
順序付木情報取得部１４、位置サイズ決定部１５、隣接
情報取得部１６、隣接エッジ決定部１７がグラフ自動描
画のための処理（前処理）を開始すると、前記メモリ１
２に格納してあるグラフ情報を使用して処理を行い、処
理後の情報（データ）をメモリ１２に格納する。

【００２６】その後、グラフを自動描画する場合は、メ
モリ１２の情報を使用して処理を行い、出力装置２１へ
グラフの描画情報を出力する。このようにして描画した
グラフ描画例は図１のＢ図のようになる。この場合、グ
ラフ自動描画のための処理（前処理）は次のようにして
行う。すなわち、グラフ情報として順序付複合木Ｔ＝
（Ｖ，Ｅ，Ａ，Ｏ）の情報が与えられた場合、自動描画
のための処理は次のようにして行う。

【００２７】：先ず、順序付木情報取得部１４は、与
えられたグラフ情報（メモリ１２の情報）からノード
Ｖ、ノードの階層関係のエッジを表す階層エッジＥ、ノ
ードの順序Ｏからなる順序付木Ｔ′＝（Ｖ，Ｅ，Ｏ）の
構成情報を取得する（必要な情報を取り出す）。

【００２８】：位置サイズ決定部１５は、前記順序付
木情報取得部１４が取得した順序付木の構成情報からノ
ードの位置及びサイズを決定し、メモリ１２に格納して
おく。

【００２９】：隣接情報取得部１６は、与えられたグ
ラフ情報（メモリ１２の情報）からノードＶ及び各ノー
ド間の隣接関係のエッジを表す隣接エッジＡからなる隣
接グラフＧ＝（Ｖ，Ａ）の構成情報を取得する（必要な
情報を取り出す）。

【００３０】：隣接エッジ決定部１７は、前記隣接情
報取得部１６が取得した隣接グラフの構成情報及び前記
位置サイズ決定部１５が決定したノードの位置及びサイ
ズ（メモリ１２の情報）を基に隣接エッジの経路を決定
する。そして、決定した情報はメモリ１２に格納してお
く。

【００３１】以上のようにして、階層関係、隣接関係、
及び順序関係からなる３種類の関係情報をそれぞれ異な
る表現形式で明確に区別して表現することができる。ま
た、ノードの位置やエッジの経路などを自動決定するこ
とにより、１つの図において大規模化、複雑化した情報
を前記３種類の関係情報を区別しながら視覚的に明確に
表現することができる。

【００３２】

【発明の実施の形態】以下、発明の実施の形態を図面に
基づいて詳細に説明する。 （各実施の形態に共通の説明） §１：グラフ自動描画装置の構成の説明・・・図２参照 図２はグラフ自動描画装置のブロック図である。以下に
説明する各実施の形態におけるグラフ自動描画装置は図
２に示した通りである。このグラフ自動描画装置は、パ
ーソナルコンピュータ、ワークステーションなど各種の
コンピュータにより実現する。

【００３３】図示のように、グラフ自動描画装置は、装
置本体２と、ハードディスクドライブ（以下「ＨＤＤ」
と記す）３と、プリンタ４と、ディスプレイ装置５とキ
ーボード６等で構成されている。そして、前記装置本体
２には、主制御部１１と、メモリ１２と、入出力制御部
（以下「Ｉ／Ｏ制御部」と記す）１３と、順序付木情報
取得部１４と、位置サイズ決定部１５と、隣接情報取得
部１６と、隣接エッジ決定部１７等を設ける。前記各部
の機能等は次の通りである。

【００３４】(1) ：ＨＤＤ３は、内部にハードディスク
（ディスク記憶媒体）を備え、前記ハードディスクに対
して各種データ（情報）の書き込み、及び読み出しを行
うものである。なお、このハードディスクには、予めグ
ラフ描画処理に必要なグラフ情報、その他各種データを
格納しておく。

【００３５】(2) ：プリンタ４は、装置本体２で処理し
た結果のデータを印刷して出力するものである。 (3) ：ディスプレイ装置５は、装置本体２で処理中のデ
ータや処理結果のデータ等を画面に表示するものであ
る。

【００３６】(4) ：キーボード６は、オペレータにより
操作され、各種データや制御情報等を入力するものであ
る。 (5) ：主制御部１１は、装置本体２の各種制御を行うも
の（例えば、ＣＰＵ）である。

【００３７】(6) ：メモリ１２は、装置本体２の内部に
設けた半導体メモリであり、装置本体２で使用するデー
タ等を記憶するものである。 (7) ：Ｉ／Ｏ制御部１３は、ＨＤＤ３、プリンタ４、デ
ィスプレイ装置５、キーボード６等の入出力装置に対す
る入出力制御を行うものである。

【００３８】(8) ：順序付木情報取得部１４は、与えら
れたグラフ情報からノードＶ、ノードの階層関係のエッ
ジを表す階層エッジＥ、及びノードの順序Ｏからなる順
序付木Ｔ′＝（Ｖ，Ｅ，Ｏ）の構成情報を取得するもの
である。

【００３９】(9) ：位置サイズ決定部１５は、順序付木
情報取得部１４が取得した順序付木の構成情報からノー
ドの位置及びサイズを決定するものである。 (10)：隣接情報取得部１６は、与えられたグラフ情報か
らノードＶ及び各ノード間の隣接関係のエッジを表す隣
接エッジＡからなる隣接グラフＧ＝（Ｖ，Ａ）の構成情
報を取得するものである。

【００４０】(11)：隣接エッジ決定部１７は、隣接情報
取得部１６が取得した隣接グラフの構成情報及び位置サ
イズ決定部１５が決定したノードの位置及びサイズを基
に隣接エッジの経路を決定するものである。

【００４１】§２：パラメータ等の準備処理の説明・・
・図３参照 図３はパラメータの説明図である。以下の説明では、図
３に示したｘ−ｙ座標を設定し、原点Ｏに対し図示矢印
方向をｘ軸の＋方向、及びｙ軸の＋方向として説明す
る。本実施の形態ではノードは全て長方形で描くことに
する。ノードｖの位置は左下の頂点を基準（ｘ−ｙ座標
の原点０の位置）としてｘ（ｖ）とｙ（ｖ）で表すこと
にする。サイズ、すなわち、ノードの高さと幅をそれぞ
れｈ（ｖ）とｗ（ｖ）で表すことにする。

【００４２】また、ｖ_h ，ｖ_t ∈Ｖに対して、（ｖ_h ，
ｖ_t ）∈Ｅの時、すなわち、ノードの集合Ｖに含まれる
ノードｖ_h ，ｖ_t に対し、（ｖ_h ，ｖ_t ）が階層エッジ
の集合Ｅの要素である時、ノードｖ_h をノードｖ_t の
「親」、逆にノードｖ_t をノードｖ_h の「子」と呼ぶ。

【００４３】ノードｖの全ての子の集合をＣｈ（ｖ）で
表す。階層エッジの集合Ｅは木を構成するので唯一のノ
ード以外は必ず一つ親を持つ。親を持たないノードをル
ートと呼びＲで表す。また、子を持たないノードを「リ
ーフノード」、または単に「リーフ」と呼ぶ。

【００４４】グラフの描画を行うに当たり、リーフノー
ドのサイズは既に決まっているとする。これは通常、ノ
ードの中身として描かれるラベルなどによって決められ
るものであり、全て同じサイズでも、それぞれ異なって
いても構わない。また、親の領域内での配置のためのパ
ラメータも予め決められているとする。

【００４５】図３のＡ図において、ｘ_L とｘ_R はそれぞ
れ左右のスペース、ｘ_S はノード間のｘ軸方向のスペー
スを表す。また、図３のＢ図において、ｙ_T とｙ_B はそ
れぞれ上下のスペース、ｙ_S はノード間のｙ軸方向のス
ペースを表す。

【００４６】なお、前記各パラメータ等のデータは、予
めＨＤＤ３のハードディスク（記憶媒体）に格納してお
き、グラフ自動描画処理時にＨＤＤ３から読み出し、メ
モリ１２に格納して使用するものとする。

【００４７】§３：基本処理の説明 順序付複合木Ｔ＝（Ｖ，Ｅ，Ａ，Ｏ）の情報が与えられ
た場合、自動レイアウトの手順、すなわち、自動描画手
順は次のようになる。この場合、ＨＤＤ３のハードディ
スクには、順序付複合木Ｔ＝（Ｖ，Ｅ，Ａ，Ｏ）の情報
（グラフ情報）が予め格納されているものとする。

【００４８】グラフ自動描画装置の電源が投入され装置
の立ち上げ処理が行われると、主制御部１１の制御によ
り、ＨＤＤ３のハードディスクに格納されている順序付
複合木Ｔ＝（Ｖ，Ｅ，Ａ，Ｏ）の情報（グラフ情報）が
読み出され、メモリ１２に格納される。

【００４９】その後、主制御部１１の指示により、順序
付木情報取得部１４、位置サイズ決定部１５、隣接情報
取得部１６、隣接エッジ決定部１７がグラフ自動描画の
ための処理（前処理）を開始すると、前記メモリ１２に
格納してあるグラフ情報を使用して前記処理を行い、処
理後の情報（データ）を再びメモリ１２に格納してお
く。

【００５０】その後、グラフを描画する場合は、主制御
部１１の制御によりメモリ１２の情報を使用してグラフ
描画処理を行い、プリンタ４、ディスプレイ装置５、或
いはＨＤＤ３へグラフの描画情報を出力する。この場
合、前記グラフ自動描画のための処理は次のようにして
行う。すなわち、グラフ情報として順序付複合木Ｔ＝
（Ｖ，Ｅ，Ａ，Ｏ）の情報が与えられた場合、自動描画
のための処理は次のようにして行う。

【００５１】：先ず、順序付木情報取得部１４は、与
えられたグラフ情報（メモリ１２の情報）からノード
Ｖ、ノードの階層関係のエッジを表す階層エッジＥ、ノ
ードの順序Ｏからなる順序付木Ｔ′＝（Ｖ，Ｅ，Ｏ）の
構成情報を取得する（必要な情報を取り出す）。

【００５２】：位置サイズ決定部１５は、前記順序付
木情報取得部１４が取得した順序付木の構成情報からノ
ードの位置及びサイズを決定し、メモリ１２に格納す
る。 ：隣接情報取得部１６は、与えられたグラフ情報（メ
モリ１２の情報）からノードＶ及び各ノード間の隣接関
係のエッジを表す隣接エッジＡからなる隣接グラフＧ＝
（Ｖ，Ａ）の構成情報を取得する（必要な情報を取り出
す）。

【００５３】：隣接エッジ決定部１７は、前記隣接情
報取得部１６が取得した隣接グラフの構成情報及び前記
位置サイズ決定部１５が決定したノードの位置及びサイ
ズ（メモリ１２の情報）を基に隣接エッジの経路を決定
する。そして、決定した情報はメモリ１２に格納する。

【００５４】（実施の形態１の説明） §１：順序付木の描画法１の説明 実施の形態１では、順序付木の描画法１により次のよう
にしてグラフ自動描画のための処理を行う。順序付木の
描画法１は、順序付木Ｔ′＝（Ｖ，Ｅ，Ｏ）の情報を取
得してノードの位置とサイズを決定し、順序に従ってノ
ードを横方向（水平方向）に並べる方法である。

【００５５】今、ノードｖの子がｖ₁ ，ｖ₂ ，ｖ₃ ・・
・ｖ_n であるとする。つまり、ノードの全ての子の集合
Ｃｈ（ｖ）を、Ｃｈ（ｖ）＝｛ｖ₁ ，ｖ₂ ，ｖ₃ ・・・
ｖ_n｝とする。また、子の番号付けは順序関係Ｏに従っ
ているとする。この時、次のように定義される関数Ｘ_H
とＹ_H （式１、式２参照）で、ｉ番目のノードｖ_i （１
≦ｉ≦ｎ）の位置を与える。

【００５６】

【数１】

【００５７】更に、次のように定義される関数Ｗ_H とＨ
_H （式３、式４）でノードｖのサイズ（幅と高さ）を与
える。

【００５８】

【数２】

【００５９】ノードｖの子の位置とノードｖのサイズを
計算するには、全ての子のサイズが既に決まっていなけ
ればならないので、順序付木のリーフ側から再帰的に計
算処理を進める必要がある。

【００６０】§２：フローチャートによる順序付木の描
画法１の処理説明・・・図４参照 図４は描画法１の処理フローチャートである。以下、図
４に基づいて順序付木の描画法１の処理（ノードｖの子
の位置とノードｖのサイズを計算する処理）を説明す
る。なお、この処理は、主制御部１１の指示により位置
サイズ決定部１５が行う処理であり、Ｓ１〜Ｓ１０は各
処理ステップを示す。

【００６１】順序付木情報取得部１４がメモリ１２から
順序付木の構成情報を取得した後、位置サイズ決定部１
５が「ｌａｙｏｕｔ_H （ｖ）」の処理を開始すると（Ｓ
１）、位置サイズ決定部１５は、Ｃｈ（ｖ）の要素を順
序関係Ｏに従ってｖ₁ ，ｖ₂，ｖ₃ ・・・ｖ_n と番号付
けする（Ｓ２）。なお、「ｌａｙｏｕｔ_H （ｖ）」はノ
ードｖを横方向（水平方向）に並べる（レイアウトす
る）ことを表す。

【００６２】次に、位置サイズ決定部１５は、変数ｊを
ｊ＝１に設定し（Ｓ３）、ｊがｊ≦ｎ（ｎ：ノードｖの
子の数）か否かを判定し（Ｓ４）、ｊ≦ｎであれば、Ｃ
ｈ（ｖ_j ）がＣｈ（ｖ_j ）＝φ（φ：空集合）か否か
（注目しているノードｖ_j の子があるか否か）を判定す
る（Ｓ５）。その結果、Ｃｈ（ｖ_j ）＝φでなければ
（注目しているノードｖ_j の子がいる場合）、「ｌａｙ
ｏｕｔ_H （ｖ_j ）」の処理（再帰的計算処理）を行う
（Ｓ６）。

【００６３】なお、前記「ｌａｙｏｕｔ_H （ｖ_j ）」の
再帰的計算処理は、注目しているノードｖ_j に子がある
場合、描画法１の「ｌａｙｏｕｔ_H （ｖ）」の処理を
「ｌａｙｏｕｔ_H （ｖ_j ）」の処理に代えて新規にＳ１
からＳ１０の処理を行うことを表す。すなわち、注目し
ているノードｖ_j に子がある場合、ノードｖをｖ_j に代
えて描画法１の処理を繰り返して行うことにより、ノー
ドｖ_j の子の位置とサイズを計算するものである。

【００６４】そして、前記Ｓ６の処理終了後、ノードｖ
の子であるｖ_j のｘ軸上の位置ｘ（ｖ_j ）＝Ｘ
_H （ｖ_j ）、及びｙ軸上の位置ｙ（ｖ_j ）＝Ｙ
_H （ｖ_j ）を決定する（Ｓ７）。また、前記Ｓ５の処理
でＣｈ（ｖ_j ）＝φと判定された場合は、前記Ｓ６の処
理をせずにＳ７の処理を行う。なお、前記決定したｘ軸
上の位置ｘ（ｖ _j ）＝Ｘ_H （ｖ_j ）、及びｙ軸上の位置
ｙ（ｖ_j ）＝Ｙ_H （ｖ_j ）は、メモリ１２へ格納してお
くその後、位置サイズ決定部１５は、ｊをｊ＝ｊ＋１と
して（Ｓ８）、前記Ｓ４の処理から繰り返す。前記のよ
うにして処理を繰り返し、ｊがｊ＞ｎになるとノードｖ
の子のサイズ（幅と高さ）を決定する（Ｓ９）。なお、
ノードｖの子の幅ｗ（ｖ）は、ｗ（ｖ）＝Ｗ_H （ｖ₁ ，
ｖ₂ ，・・・ｖ_n ）であり（式３参照）、高さｈ（ｖ）
は、ｈ（ｖ）＝Ｈ_H （ｖ₁ ，ｖ₂ ，・・・ｖ_n ）である
（式４参照）。

【００６５】前記Ｓ９の処理が終了したら、位置サイズ
決定部１５は、決定したノードｖの子のサイズ（幅と高
さ）を、メモリ１２に格納しておく。そして「ｌａｙｏ
ｕｔ _H （ｖ）」の処理を終了する（Ｓ１０）。その後グ
ラフを描画するにはメモリ１２のデータを基に、例え
ば、ディスプレイ装置５の画面上で描画する。

【００６６】§３：描画法１による順序付木の描画例の
説明・・・図５参照 図５は描画法１による順序付木の描画例である。前記図
４に示したフローチャートの処理は、「ｌａｙｏｕｔ_H
（Ｒ）」のようにルートＲから始めることで、ルートＲ
を除く全てのノードの位置と、リーフを除く全てのノー
ドのサイズを計算することができる。前記処理では、ル
ートＲの位置は決まらないが、ルートは図の外枠に対応
するので任意の位置におけば良い。このような処理で計
算したデータ（メモリ１２のデータ）を基に描いた順序
付木の描画例は図５に示した通りである。

【００６７】この描画例では、ノードＡ（ルートＲ）の
中にノードＡＡとＡＢが横方向に並べて描画され、ノー
ドＡＡの中に、ノードＡＡＡとＡＡＢとＡＡＣ（リーフ
ノード）が横方向に並べて描画され、ノードＡＢの中に
ノードＡＢＡとＡＢＢ（リーフノード）が横方向に並べ
て描画されている。

【００６８】（実施の形態２の説明） §１：順序付木の描画法２の説明 実施の形態２では順序付木の描画法２により、グラフ自
動描画のための処理を次のようにして行う。順序付木の
描画法２は、順序付木Ｔ′＝（Ｖ，Ｅ，Ｏ）の情報を取
得してノードの位置とサイズを決定し、順序に従ってノ
ードを縦方向（垂直方向）に並べる方法である。基本的
には前記描画法１と同じであるが、ノードｖの子ｖ₁ ，
ｖ₂ ，ｖ₃ ・・・ｖ_n に対して、次のように定義される
関数ＸｖとＹｖでｉ番目のノードｖ_i （１≦ｉ≦ｎ）の
位置を与える（式５、式６参照）。

【００６９】

【数３】

【００７０】また、次のように定義される関数ＷｖとＨ
ｖでノードｖのサイズを与える（式７、式８参照）。

【００７１】

【数４】

【００７２】§２：フローチャートによる順序付木の描
画法２の処理説明・・・図６参照 図６は描画法２の処理フローチャートである。以下、図
６に基づいて順序付木の描画法２の処理（ノードｖの子
の位置とノードｖのサイズを計算する処理）を説明す
る。なお、この処理は、主制御部１１の指示により位置
サイズ決定部１５が行う処理であり、Ｓ２１〜Ｓ３０は
各処理ステップを示す。

【００７３】順序付木情報取得部１４がメモリ１２から
順序付木の構成情報を取得した後、位置サイズ決定部１
５が「ｌａｙｏｕｔ_V （ｖ）」の処理を開始すると（Ｓ
２１）、位置サイズ決定部１５は、Ｃｈ（ｖ）の要素を
順序関係Ｏに従って、ｖ₁ ，ｖ₂ ，ｖ₃ ・・・ｖ_n と番
号付けする（Ｓ２２）。なお、「ｌａｙｏｕｔ
_V （ｖ）」はノードｖを縦方向（垂直方向）に並べるこ
とを表す。

【００７４】次に、位置サイズ決定部１５は、変数ｊを
ｊ＝１に設定し（Ｓ２３）、ｊがｊ≦ｎ（ｎ：ノードｖ
の子の数）か否かを判定し（Ｓ２４）、ｊ≦ｎであれ
ば、Ｃｈ（ｖ_j ）がＣｈ（ｖ_j ）＝φ（φ：空集合）か
否か（注目しているノードｖ_jの子があるか否か）を判
定する（Ｓ２５）。その結果、Ｃｈ（ｖ_j ）＝φでなけ
れば（注目しているノードｖ_j の子がいる場合）、「ｌ
ａｙｏｕｔ_V （ｖ_j ）」の処理（再帰的計算処理）を行
う（Ｓ２６）。

【００７５】なお、前記「ｌａｙｏｕｔ_V （ｖ_j ）」の
再帰的計算処理は、注目しているノードｖ_j に子がある
場合、描画法２の「ｌａｙｏｕｔ_V （ｖ）」の処理を
「ｌａｙｏｕｔ_V （ｖ_j ）」の処理に代えて新規にＳ２
１からＳ３０の処理を行うことを表す。すなわち、注目
しているノードｖ_j に子がある場合、ノードｖをｖ_j に
代えて描画法２の処理を繰り返して行うことにより、ノ
ードｖ_j の子の位置とサイズを計算するものである。

【００７６】そして、前記Ｓ２６の処理終了後、位置サ
イズ決定部１５は、ノードｖの子であるｖ_j のｘ軸上の
位置ｘ（ｖ_j ）＝Ｘ_V （ｖ_j ）、及びｙ軸上の位置ｙ
（ｖ_j）＝Ｙ_V （ｖ_j ）を決定する（Ｓ２７）。また、
前記Ｓ２５の処理でＣｈ（ｖ_j）＝φと判定された場合
は、前記Ｓ２６の処理をせずにＳ２７の処理を行う。な
お、前記決定したｘ軸上の位置ｘ（ｖ_j ）＝Ｘ
_V （ｖ_j ）、及びｙ軸上の位置ｙ（ｖ_j ）＝Ｙ
_V （ｖ_j ）は、メモリ１２に格納しておく。

【００７７】その後、位置サイズ決定部１５は、ｊをｊ
＝ｊ＋１として（Ｓ２８）、前記Ｓ２４の処理から繰り
返す。前記のようにして処理を繰り返し、ｊがｊ＞ｎに
なるとノードｖの子のサイズ（幅と高さ）を決定する
（Ｓ２９）。なお、ノードｖの子の幅ｗ（ｖ）は、ｗ
（ｖ）＝Ｗ_V （ｖ₁ ，ｖ₂ ，・・・ｖ_n ）であり（式７
参照）、高さｈ（ｖ）は、ｈ（ｖ）＝Ｈ_V （ｖ₁ ，
ｖ₂ ，・・・ｖ_n ）である（式８参照）。

【００７８】前記Ｓ２９の処理が終了したら、位置サイ
ズ決定部１５は、決定したノードｖの子のサイズ（幅と
高さ）を、メモリ１２へ格納しておく。そして「ｌａｙ
ｏｕｔ_V （ｖ）」の処理を終了する（Ｓ３０）。

【００７９】§３：描画法２による順序付木の描画例の
説明・・・図７参照 図７は描画法２による順序付木の描画例である。前記図
６に示したフローチャートの処理は、「ｌａｙｏｕｔ_H
（Ｒ）」のようにルートＲから始めることで、描画法１
と同様にルートＲを除く全てのノードの位置と、リーフ
を除く全てのノードのサイズを計算することができる。
このような処理で計算したデータを基に描いた順序付木
の描画例は図７に示した通りである。

【００８０】この描画例では、ノードＡ（ルートＲ）の
中にノードＡＡとＡＢが縦方向に並べて描画され、ノー
ドＡＡの中に、ノードＡＡＡとＡＡＢとＡＡＣ（リーフ
ノード）が縦方向に並べて描画され、ノードＡＢの中に
ノードＡＢＡとＡＢＢ（リーフノード）が縦方向に並べ
て描画されている。

【００８１】（実施の形態３の説明） §１：順序付木の描画法３の説明 実施の形態３では順序付木の描画法３により、グラフ自
動描画のための処理を次のようにして行う。順序付木の
描画法３は、前記描画法１、描画法２と同様に順序付木
Ｔ′＝（Ｖ，Ｅ，Ｏ）の情報を取得してノードの位置と
サイズを決定し、順序に従ってノードを並べる方法であ
る。

【００８２】この場合、描画法１では図が横長になり、
描画法２では図が縦長になる傾向がある。そこで描画法
３では、ノードの深さが偶数である場合と奇数である場
合に、それぞれ子の並び方を縦方向と横方向に変えるこ
とで図の縦横のバランスを良くするようにした。

【００８３】§２：フローチャートによる順序付木の描
画法３の処理説明・・・図８、図９参照 図８は描画法３の処理フローチャート（その１）、図９
は描画法３の処理フローチャート（その２）である。以
下、図８、図９に基づいて順序付木の描画法３の処理
（ノードｖの子の位置とノードｖのサイズを計算する処
理）を説明する。なお、図８に示した処理は、ノードｖ
の直ぐ下の子を縦方向（垂直方向）に並べる処理であ
り、図９に示した処理は、ノードｖの直ぐ下の子を横方
向（水平方向）に並べる処理である。また、Ｓ４１〜Ｓ
５０は各処理ステップを示す。

【００８４】(1) ：描画法３の処理フローチャート（そ
の１）の説明・・・図８参照 順序付木情報取得部１４がメモリ１２から順序付木の構
成情報を取得した後、位置サイズ決定部１５が「ｌａｙ
ｏｕｔ_VH（ｖ）」の処理を開始すると（Ｓ４１）、位置
サイズ決定部１５は、Ｃｈ（ｖ）の要素を順序関係Ｏに
従って、ｖ₁ ，ｖ₂ ，ｖ₃ ・・・ｖ_n と番号付けする
（Ｓ４２）。なお、「ｌａｙｏｕｔ_VH（ｖ）」はノード
ｖの直ぐ下の子を縦方向（垂直方向）に並べる（レイア
ウトする）ことを表す。

【００８５】次に、位置サイズ決定部１５は、変数ｊを
ｊ＝１に設定し（Ｓ４３）、ｊがｊ≦ｎ（ｎ：ノードｖ
の子の数）か否かを判定し（Ｓ４４）、ｊ≦ｎであれ
ば、Ｃｈ（ｖ_j ）がＣｈ（ｖ_j ）＝φ（φ：空集合）か
否か（注目しているノードｖ_jの子があるか否か）を判
定する（Ｓ４５）。その結果、Ｃｈ（ｖ_j ）＝φでなけ
れば（注目しているノードｖ_j の子がいる場合）、位置
サイズ決定部１５は「ｌａｙｏｕｔ_HV（ｖ_j ）」の処理
（再帰的計算処理）を行う（Ｓ４６）。

【００８６】なお、前記「ｌａｙｏｕｔ_HV（ｖ_j ）」の
再帰的計算処理は、注目しているノードｖ_j に子がある
場合、図９に示した「ｌａｙｏｕｔ_HV（ｖ）」の処理を
「ｌａｙｏｕｔ_HV（ｖ_j ）」の処理に代えてＳ５１から
Ｓ６０の処理を行うことを表す。すなわち、注目してい
るノードｖ_j に子がある場合、ノードｖをｖ_j に代えて
「ｌａｙｏｕｔ_HV（ｖ_j ）」の処理を行うことにより、
ノードｖ_j の子の位置とサイズを計算するものである。

【００８７】そして、前記Ｓ４６の処理終了後、位置サ
イズ決定部１５は、ノードｖの子であるｖ_j のｘ軸上の
位置ｘ（ｖ_j ）＝Ｘ_V （ｖ_j ）、及びｙ軸上の位置ｙ
（ｖ_j）＝Ｙ_V （ｖ_j ）を決定する（Ｓ４７）。また、
前記Ｓ４５の処理でＣｈ（ｖ_j）＝φと判定された場合
は、前記Ｓ４６の処理をせずにＳ４７の処理を行う。な
お、前記決定したｘ軸上の位置ｘ（ｖ_j ）＝Ｘ
_V （ｖ_j ）、及びｙ軸上の位置ｙ（ｖ_j ）＝Ｙ
_V （ｖ_j ）は、メモリ１２に格納しておく。

【００８８】その後、位置サイズ決定部１５は、ｊをｊ
＝ｊ＋１として（Ｓ４８）、前記Ｓ４４の処理から繰り
返す。前記のようにして処理を繰り返し、ｊがｊ＞ｎに
なると位置サイズ決定部１５は、ノードｖの子のサイズ
（幅と高さ）を決定する（Ｓ４９）。なお、ノードｖの
子の幅ｗ（ｖ）は、ｗ（ｖ）＝Ｗ_V （ｖ₁ ，ｖ₂ ，・・
・ｖ_n ）であり（式７参照）、高さｈ（ｖ）は、ｈ
（ｖ）＝Ｈ_V （ｖ₁ ，ｖ₂，・・・ｖ_n ）である（式８
参照）。

【００８９】前記Ｓ４９の処理が終了したら、位置サイ
ズ決定部１５は、決定したノードｖの子のサイズ（幅と
高さ）をメモリ１２へ格納しておく。そして「ｌａｙｏ
ｕｔ _V （ｖ）」の処理を終了する（Ｓ５０）。

【００９０】(2) ：描画法３の処理フローチャート（そ
の２）の説明・・・図９参照 順序付木情報取得部１４がメモリ１２から順序付木の構
成情報を取得した後、位置サイズ決定部１５が「ｌａｙ
ｏｕｔ_HV（ｖ）」の処理を開始すると（Ｓ５１）、位置
サイズ決定部１５は、Ｃｈ（ｖ）の要素を順序関係Ｏに
従って、ｖ₁ ，ｖ₂ ，ｖ₃ ・・・ｖ_n と番号付けする
（Ｓ５２）。なお、「ｌａｙｏｕｔ_HV（ｖ）」はノード
ｖの直ぐ下の子を横方向（水平方向）に並べる（レイア
ウトする）ことを表す。

【００９１】次に、位置サイズ決定部１５は、変数ｊを
ｊ＝１に設定し（Ｓ５３）、ｊがｊ≦ｎ（ｎ：ノードｖ
の子の数）か否かを判定し（Ｓ５４）、ｊ≦ｎであれ
ば、Ｃｈ（ｖ_j ）がＣｈ（ｖ_j ）＝φ（φ：空集合）か
否か（注目しているノードｖ_jの子があるか否か）を判
定する（Ｓ５５）。その結果、Ｃｈ（ｖ_j ）＝φでなけ
れば（注目しているノードｖ_j の子がいる場合）、「ｌ
ａｙｏｕｔ_VH（ｖ_j ）」の処理（再帰的計算処理）を行
う（Ｓ５６）。

【００９２】なお、前記「ｌａｙｏｕｔ_VH（ｖ_j ）」の
再帰的計算処理は、注目しているノードｖ_j に子がある
場合、図８に示した「ｌａｙｏｕｔ_VH（ｖ）」の処理を
「ｌａｙｏｕｔ_VH（ｖ_j ）」の処理に代えてＳ４１から
Ｓ５０の処理を行うことを表す。すなわち、注目してい
るノードｖ_j に子がある場合、ノードｖをｖ_j に代えて
「ｌａｙｏｕｔ_VH（ｖ_j ）」の処理を行うことにより、
ノードｖ_j の子の位置とサイズを計算する。

【００９３】そして、前記Ｓ５６の処理終了後、位置サ
イズ決定部１５は、ノードｖの子であるｖ_j のｘ軸上の
位置ｘ（ｖ_j ）＝Ｘ_H （ｖ_j ）、及びｙ軸上の位置ｙ
（ｖ_j）＝Ｙ_H （ｖ_j ）を決定する（Ｓ５７）。また、
前記Ｓ５５の処理でＣｈ（ｖ_j）＝φと判定された場合
は、前記Ｓ５６の処理をせずにＳ５７の処理を行う。な
お、前記決定したｘ軸上の位置ｘ（ｖ_j ）＝Ｘ
_H （ｖ_j ）、及びｙ軸上の位置ｙ（ｖ_j ）＝Ｙ
_H （ｖ_j ）はメモリ１２に格納しておく。

【００９４】その後、位置サイズ決定部１５は、ｊをｊ
＝ｊ＋１として（Ｓ５８）、前記Ｓ５４の処理から繰り
返す。前記のようにして処理を繰り返し、ｊがｊ＞ｎに
なると位置サイズ決定部１５は、ノードｖの子のサイズ
（幅と高さ）を決定する（Ｓ５９）。なお、ノードｖの
子の幅ｗ（ｖ）は、ｗ（ｖ）＝Ｗ_H （ｖ₁ ，ｖ₂ ，・・
・ｖ_n ）であり（式３参照）、高さｈ（ｖ）は、ｈ
（ｖ）＝Ｈ_H （ｖ₁ ，ｖ₂，・・・ｖ_n ）である（式４
参照）。

【００９５】前記Ｓ５９の処理が終了したら、位置サイ
ズ決定部１５は、決定したノードｖの子のサイズ（幅と
高さ）をメモリ１２に格納しておく。そして「ｌａｙｏ
ｕｔ _HV（ｖ）」の処理を終了する（Ｓ６０）。

【００９６】§３：描画法３による順序付木の描画例の
説明・・・図１０のＡ図参照 図１０のＡ図は描画法３による順序付木の描画例であ
る。前記図８、図９に示したフローチャートの処理は、
「ｌａｙｏｕｔ_HV（Ｒ）」、または「ｌａｙｏｕｔ
_VH（Ｒ）」のようにルートＲから始めることで、ルート
Ｒを除く全てのノードの位置と、リーフを除く全てのノ
ードのサイズを計算することができる。このような処理
で計算したデータを基に描いた順序付木の描画例は図１
０のＡ図に示した通りである。

【００９７】この描画例では、ノードＡ（ルートＲ）の
中にノードＡＡとＡＢが縦方向に並べて描画され、ノー
ドＡＡの中に、ノードＡＡＡとＡＡＢとＡＡＣ（リーフ
ノード）が横方向に並べて描画され、ノードＡＢの中に
ノードＡＢＡとＡＢＢ（リーフノード）が横方向に並べ
て描画されている。このように、ノードの深さが偶数で
ある場合と奇数である場合に、それぞれ子の並び方を縦
方向と横方向に変えることで図の縦横のバランスを良く
することができる。

【００９８】（実施の形態４の説明） §１：順序付木の描画法４の説明 実施の形態４では、順序付木の描画法４によりグラフ自
動描画のための処理を行う。順序付木の描画法４は、位
置サイズ決定部１５によりノードの位置とサイズを決定
した後、前記ノードの位置とサイズの情報、及び隣接情
報取得部１６が取得した隣接グラフＧ＝（Ｖ，Ａ）の情
報を基に、隣接エッジ決定部１７が隣接エッジの経路を
決定する方法である。

【００９９】この描画法では隣接エッジを直線分で表現
する。隣接エッジは直線分であるので、その経路を与え
る情報としては、始点の座標（ｓ_x ，ｓ_y ）と終点の座
標（ｅ_x ，ｅ_y ）が定まれば十分である。隣接エッジａ
∈Ａに対してそれらを次のように与える。

【０１００】 ｓ_x （ａ）＝ｘ（head（ａ））＋ｗ（head（ａ））・・・式９ ｓ_y （ａ）＝ｙ（head（ａ））・・・式１０ ｅ_x （ａ）＝ｘ（tail（ａ））・・・式１１ ｅ_y （ａ）＝ｙ（tail（ａ））＋ｈ（tail（ａ））・・・式１２ ここで、headはエッジの始点ノードを与える関数であ
り、tailはエッジの終点ノードを与える関数である。つ
まり、始点側のノードの右上の頂点から終点側のノード
の左下の頂点へ向かう線分を描くことになる。

【０１０１】§２：描画法４による順序付木の描画例の
説明・・・図１０のＢ図参照 図１０のＢ図は描画法３、４による複合順序付木の描画
例である。図１０のＡ図に示した図に、描画法４で隣接
エッジを描き加えた例を図１０のＢ図に示す。描画法４
は、例として単純な方法を示したが、そのため図１０の
Ｂ図に示したように、ノードと隣接エッジが不必要に重
なってしまっている。

【０１０２】例えば、ノードＡＢＢからＡＢＡへ向かう
隣接エッジはノードへの接続位置を変更することで、ど
ちらのノードとも重ならないようにすることが可能であ
る。しかしなから、隣接エッジを直線分で描くことの本
質的な問題は、ノードＡＡＡからＡＡＣへ向かう隣接エ
ッジが、ノードＡＡＢと重なっていることに見られる。

【０１０３】この重なりは、どのように接続位置を変更
してもなくすことができない。グラフによっては、この
ような隣接エッジが沢山含まれる場合もあるので、この
ような場合には次に説明する描画法５を用いれば解決す
る。しかし、隣接エッジが少なく、重なりが少ない場合
には描画法４でも十分である。

【０１０４】（実施の形態５の説明） §１：順序付木の描画法５の説明 実施の形態５の描画法は、実施の形態４の描画法と同様
に位置サイズ決定部１５によりノードの位置とサイズを
決定した後、前記ノードの位置とサイズの情報、及び隣
接情報取得部１６が取得した隣接グラフＧ＝（Ｖ，Ａ）
の情報を基に、隣接エッジ決定部１７が隣接エッジの経
路を決定する方法である。

【０１０５】この描画法５では、隣接エッジを楕円弧で
表現するものである。これにより、描画法４で見られる
問題、すなわち、直線分で隣接エッジを描く限りノード
ＡＡＡからＡＡＣへ向かう隣接エッジと、ノードＡＡＢ
との重なりが無くせないという問題を解決できる。

【０１０６】隣接エッジは楕円弧なので、その経路を与
える情報としては、楕円の中心座標（ｃ_x ，ｃ_y ）と、
ｘ方向とｙ方向の半径（ｒ_x ，ｒ_y ）、及び弧の始点と
終点の角（ａ_s ，ａ_e ）が求まれば十分である。それら
の求め方を次に説明する。

【０１０７】§２：隣接エッジが接続する頂点の選び方
の説明 図１１は描画法５の説明図（その１）であり、Ａ図は始
点ノードを基準にした四つの領域を示した図、Ｂ図は四
つの領域におけるエッジの接続の仕方を示した図であ
る。また、図１２は描画法５の説明図（その２）であ
り、Ａ図はエッジの接続の仕方を示した図、Ｂ図は領域
におけるエッジの描き方を示した図である。

【０１０８】実施の形態５のグラフ自動描画法では、始
点ノードと終点ノードの同じ頂点を接続する。その組み
合わせは、左上と左上、左下と左下、右下と右
下、右上と右上の４通りである。これらの内の一つの
組み合わせを始点ノードと終点ノードの位置関係によっ
て選ぶ。

【０１０９】前記実施の形態１、２、３で決定されたレ
イアウトに従うと、二つのノードの位置関係はどちらか
一方が他方を完全に包含している場合を除くと、二つは
完全に離れているはずである。よって、始点ノードをｖ
_O で表すと、終点ノードの位置は、図１１のＡ図に示す
４つの領域、、、に分類できる。なお、境界に
重なっている場合には、反時計回り側の領域に含まれて
いるものと見なす。つまり、領域と領域の境界に重
なっている場合には領域に含まているものと見なす。

【０１１０】そして、終了ノードが前記４つの領域
のどれに含まれるかによって、接続する頂点の組み
合わせを次の表のように決める。また、領域への分類
は、厳密にはノードの位置とサイズを利用して次の表の
条件に基づいて行う。

【０１１１】

【表１】

【０１１２】そして、図１１のＢ図に示したように楕円
弧を描く。図では始点ノードをｖ_O、終点ノードをｖ₁
で表している。図から明らかなように、このように接続
する頂点を選ぶことで、楕円弧は始点ノードｖ_O や、終
点ノードｖ₁ と重ならなくできる。また、エッジの向き
を考慮する場合、始点ノードｖ_O から終点ノードｖ₁へ
向かって楕円弧を時計回りに辿ることで、矢印が無くて
も向きを知ることができる。

【０１１３】なお、どちらか一方が他方を完全に包含し
ている場合は、どの組み合わせでも基本的には変わりが
ない。ここでは図１２のＡ図に示したように、始点ノー
ドｖ _O が終点ノードｖ₁ に包含される場合は、右上と右
上、始点ノードｖ_O が終点ノードｖ₁ を包含する場合は
左下と左下を選ぶことにする。以上で、二つのノードが
与えられた時に、楕円弧の始点と終点の座標が求まる。

【０１１４】§３：２点を通る楕円弧の求め方 二つのノードの頂点を通る楕円弧の求め方を前記領域
について説明する。その他の領域についてもｘ軸或いは
ｙ軸に対する鏡像をとることで求めることができる。描
画に利用する楕円の長半径と短半径の比は、１：ｋ（ｋ
≦１）で一定とする。

【０１１５】この時、図１２のＢ図に示したように、前
記領域を更に三つの領域−ａ、−ｂ、−ｃに分
けてそれぞれ描く方を変える。ｘ軸の正の向きを０（０
度）として、反時計回りの向きに角θ（θ度）をとる
と、三つの部分領域は次の表に示した範囲になる。

【０１１６】

【表２】

【０１１７】楕円の代わりに正円を利用する場合には、
ｋ＝１となるため、部分領域−ｂはなくなり、次の表
に示したようになる。

【０１１８】

【表３】

【０１１９】このようにすると、領域−ａと−ｂで
は、始点に楕円の左端が接するように描く。ただし、領
域−ａでは横長の楕円、領域−ｂでは縦長の楕円を
用いる。領域−ｃでは、終点が縦長の楕円の上端に接
するように描く。以下、具体的な楕円の求め方を例に説
明する。なお、上端に接する場合、ｘとｙが入れ替わる
だけで基本的には同じである。

【０１２０】始点の座標を（ｘ₀ ，ｙ₀ ）、終点の座標
を（ｘ₁ ，ｙ₁ ）とする。楕円の左端が（ｘ₀ ，ｙ₀ ）
に接しているので、（ｘ₁ ，ｙ₁ ）を通り、ｘ方向の半
径とｙ方向の半径の比が１：ｋである楕円は一意に定ま
り、楕円のｘ方向とｙ方向の半径（ｒ_X ，ｒ_y ）は次の
表のようになる（式１３、式１４参照）。

【０１２１】

【数５】

【０１２２】従って、楕円の中心座標（ｃ_x ，ｃ_y ）は
次のようになる（式１５、式１６参照）。

【０１２３】

【数６】

【０１２４】更に、弧の始点と終点の角（ａ_s ，ａ_e ）
は次のように求まる（式１７、式１８参照）。ただし、
０≦ａ_e ＜π／２であり、弧は始点から終点に向かって
時計回りに描く。

【０１２５】

【数７】

【０１２６】以上で、隣接エッジの経路を求めることが
できる。 §４：描画法５による順序付木の描画例の説明・・・図
１３参照 前記図１０のＡ図に示した図に、描画法５により隣接エ
ッジを描き加えた例を図１３に示す。この例では、隣接
エッジに時計回りの向きがあるとして描いている。従っ
て、矢印を付けなくても向きを読み取ることが可能であ
る。円弧を利用することで、このような付加的な情報を
表現することも可能である。

【０１２７】

【発明の効果】以上説明したように、本発明によれば次
のような効果がある。 (1) ：階層関係、隣接関係、及び順序関係からなる３種
類の関係情報をそれぞれ異なる表現形式で明確に区別し
て表現することができる。

【０１２８】(2) ：ノードの位置やエッジの経路などを
自動決定することにより、１つの図において大規模化、
複雑化した情報を階層関係、隣接関係、及び順序関係か
らなる３種類の関係情報を区別しながら視覚的に明確に
表現することができる。従って、現代の大規模化、複雑
化した情報を人間に視覚的に提示するための技術の向上
が可能である。

【０１２９】(3) ：本発明では、グラフが本来持ってい
る順序を十分明確に表現できるので、例えば、文章など
のように順序が重要である場合にも十分に利用すること
ができる。

【０１３０】前記効果の外、各請求項に対応して次のよ
うな効果がある。 (4) ：請求項１では、順序付木情報取得部と位置サイズ
決定部と隣接情報取得部と隣接エッジ決定部を備え、前
記各部により、順序付木の木構造を領域の包含関係で表
現し、ノード間の順序を配置の順序で表現し、隣接エッ
ジを直線或いは曲線からなる線分で表現して、順序付木
に隣接エッジが混在したグラフの各ノードの位置及び隣
接エッジの経路を決定することで、グラフの自動描画を
可能にしている。

【０１３１】従って、１つの図において階層関係、隣接
関係、及び順序関係からなる３種類の関係情報を区別し
ながら同時に、かつ視覚的に明確に表現することができ
る。また、１つの図で多くの情報を与えることができる
と共に、隣接エッジを線分で表現するので直観的で分か
り易い。

【０１３２】(5) ：請求項２では、隣接エッジを円弧或
いは楕円弧で表現している。隣接エッジを直線で表現し
た場合、ノードと隣接エッジが不必要に重なってしまう
ことがある。しかし、請求項２のように、隣接エッジを
円弧或いは楕円弧で表現すると、前記のようなノードと
隣接エッジの不必要な重なりの問題を解決することがで
きる。その結果、質の良い図を描画することが可能にな
る。

【０１３３】(6) ：請求項３では、隣接エッジの向きを
円弧或いは楕円弧の向きで表現している。従って、エッ
ジの向きを考慮する場合、始点ノードから終点ノードへ
向かって楕円弧を時計回りに辿ることにより、矢印がな
くても向きを容易に知ることができる。

【０１３４】(7) ：請求項４では、ノードの間の順序を
表現する配置の並びを、順序付木の木構造における深さ
の偶奇によって縦方向と横方向とに交互に変えている。
従って、描画した図の縦横のバランスを良くすることが
できる。

【０１３５】(8) ：請求項５では、順序付木に隣接エッ
ジが混在したグラフの各ノードの位置と隣接エッジの経
路を決定することで、グラフの自動描画を可能にしたグ
ラフ自動描画法であって、順序付木の木構造を領域の包
含関係で表現し、ノード間の順序を配置の順序で表現
し、前記隣接エッジを直線或いは曲線からなる線分で表
現するようにしている。

【０１３６】従って、１つの図において階層関係、隣接
関係、及び順序関係からなる３種類の関係情報を区別し
ながら同時に、かつ視覚的に明確に表現することができ
る。また、１つの図で多くの情報を与えることができる
と共に、隣接エッジを線分で表現するので直観的で分か
り易い。

【図面の簡単な説明】

【図１】本発明の原理説明図である。

【図２】実施の形態におけるグラフ自動描画装置のブロ
ック図である。

【図３】実施の形態におけるパラメータの説明図であ
る。

【図４】実施の形態１における描画法１の処理フローチ
ャートである。

【図５】実施の形態１における描画法１による順序付木
の描画例である。

【図６】実施の形態２における描画法２の処理フローチ
ャートである。

【図７】実施の形態２における描画法２による順序付木
の描画例である。

【図８】実施の形態３における描画法３の処理フローチ
ャート（その１）である。

【図９】実施の形態３における描画法３の処理フローチ
ャート（その２）である。

【図１０】実施の形態における描画法３、４による描画
例である。

【図１１】実施の形態５における描画法５の説明図（そ
の１）である。

【図１２】実施の形態５における描画法５の説明図（そ
の２）である。

【図１３】実施の形態５における描画法５による順序付
木の描画例である。

【符号の説明】

２ 装置本体 ３ ＨＤＤ（ハードディスクドライブ） ４ プリンタ ５ ディスプレイ装置 ６ キーボード １１ 主制御部 １２ メモリ １３ Ｉ／Ｏ制御部 １４ 順序付木情報取得部 １５ 位置サイズ決定部 １６ 隣接情報取得部 １７ 隣接エッジ決定部

Claims (5)

【特許請求の範囲】
1. 【請求項１】与えられたグラフ情報からノード、ノード
   の階層関係のエッジを表す階層エッジ、及びノードの順
   序からなる順序付木の構成情報を取得する順序付木情報
   取得部と、前記順序付木情報取得部が取得した順序付木
   の構成情報からノードの位置及びサイズを決定する位置
   サイズ決定部と、与えられたグラフ情報からノード及び
   各ノード間の隣接関係のエッジを表す隣接エッジからな
   る隣接グラフの構成情報を取得する隣接情報取得部と、
   前記隣接情報取得部が取得した隣接グラフの構成情報及
   び前記位置サイズ決定部が決定したノードの位置及びサ
   イズを基に隣接エッジの経路を決定する隣接エッジ決定
   部を備え、 前記各部により、順序付木の木構造を領域の包含関係で
   表現し、ノード間の順序を配置の順序で表現し、隣接エ
   ッジを直線或いは曲線からなる線分で表現して、順序付
   木に隣接エッジが混在したグラフの各ノードの位置及び
   隣接エッジの経路を決定することで、グラフの自動描画
   を可能にしたことを特徴とするグラフ自動描画装置。
2. 【請求項２】前記隣接エッジを、円弧或いは楕円弧で表
   現することを特徴とした請求項１記載のグラフ自動描画
   装置。
3. 【請求項３】前記隣接エッジの向きを、円弧或いは楕円
   弧の向きで表現することを特徴とした請求項２記載のグ
   ラフ自動描画装置。
4. 【請求項４】前記ノードの間の順序を表現する配置の並
   びを、順序付木の木構造における深さの偶奇によって縦
   方向と横方向とに交互に変えることを特徴とした請求項
   １または２または３記載のグラフ自動描画装置。
5. 【請求項５】グラフ自動描画装置により、ノード、ノー
   ドの階層関係のエッジを表す階層エッジ、及びノードの
   順序からなる順序付木に各ノード間の隣接関係のエッジ
   を表す隣接エッジが混在したグラフの各ノードの位置と
   隣接エッジの経路を決定することで、グラフの自動描画
   を可能にしたグラフ自動描画法であって、 前記順序付木の木構造を領域の包含関係で表現し、ノー
   ド間の順序を配置の順序で表現し、前記隣接エッジを直
   線或いは曲線からなる線分で表現することを特徴とした
   グラフ自動描画法。