ツリー表示調整装置
【課題】ツリー構造を望ましいレイアウトに調整させて表示させることが可能な技術を提供する。
【解決手段】ツリー表示提供装置は第１の決定手段と、第２の決定手段と、回転移動手段とを有している。第１の決定手段は、ユーザの入力に応じて決定される値である第１の値及び第２の値を決定する。第２の決定手段は、対象となる部分木における親子ノード間の距離である半径方向距離が第１の値となるようにするとともに、兄弟ノード間の回転方向距離が所定の値以上になるように各ノードの位置決定を行う。回転移動手段は、前記第２の値に応じて前記対象となる部分木を回転移動させる。
【解決手段】ツリー表示提供装置は第１の決定手段と、第２の決定手段と、回転移動手段とを有している。第１の決定手段は、ユーザの入力に応じて決定される値である第１の値及び第２の値を決定する。第２の決定手段は、対象となる部分木における親子ノード間の距離である半径方向距離が第１の値となるようにするとともに、兄弟ノード間の回転方向距離が所定の値以上になるように各ノードの位置決定を行う。回転移動手段は、前記第２の値に応じて前記対象となる部分木を回転移動させる。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書に記載の実施の形態は、ツリー表示調整装置に関する。
【背景技術】
【０００２】
ツリー構造は、ある階層に属する一つのデータから、下位階層に位置する複数のデータが枝分かれした状態で配置されている構造であり、様々な局面で使用されている。開発者などがツリー構造をコンピュータ上で図示させて、検証、改良等の作業を行うことが一般的に行われている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００６−０４８５３１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、ツリー構造が大きくなってノードの数が多数になり、あるいはツリー構造が複雑化するに従い、ツリー構造の内容を一目して把握することが困難になり、ツリー構造を整列させる必要が生ずる。しかし、ツリー構造におけるノードを、手動にて目的の配置に整列させることは負担が大きく、またどのような配置が見やすく理解しやすい配置となるかを直感的に見出すことも困難である。
【０００５】
本発明は、ツリー構造を望ましいレイアウトに調整させて表示させることが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
一の実施の形態によれば、ツリー表示調整装置が提供される。ツリー表示提供装置は第１の決定手段と、第２の決定手段と、回転移動手段とを有している。
【０００７】
第１の決定手段は、ユーザの入力に応じて決定される値である第１の値及び第２の値を決定する。第２の決定手段は、対象となる部分木における親子ノード間の距離である半径方向距離が第１の値となるようにするとともに、兄弟ノード間の回転方向距離が所定の値以上になるように各ノードの位置決定を行う。回転移動手段は、前記第２の値に応じて前記対象となる部分木を回転移動させる。
【図面の簡単な説明】
【０００８】
【図１】ツリー表示調整装置の構成例を示す機能ブロック図
【図２】ツリー表示調整処理の内容を示したフローチャート
【図３】ノード位置決定処理の一例を示すフローチャート
【図４】図４は、兄弟ノード処理順決定処理の一例を示したフローチャート
【図５】兄弟ノードの処理順決定処理の例を示すためのツリーを示した図
【図６】兄弟ノードの処理順決定処理の例を示すためのツリーを示した別の図
【図７】葉ノード位置決定処理の一例を示したフローチャート
【図８】図８は、親ノード位置決定処理の一例を示したフローチャート
【図９】ユーザによって選択された対象部分木の例を示す図
【図１０】ノードの位置を決定するための極座標系を示す図
【図１１】ノードｂが当該座標の位置に配置された状態を示す図
【図１２】ノードｃが葉ノード位置決定処理により決定された座標の位置に配置された状態を示す図
【図１３】ノードｄが極座標に配置された状態を示す図
【図１４】ノードｅが上記極座標の位置に配置された状態を示す図
【図１５】ノードｅ以下の部分木ツリー全体を原点を中心とした回転移動させた状態を示す図
【図１６】ノードｆ、ノードｇ、ノードｈが極座標系に配置された状態を示す図
【図１７】ノードｉが極座標に配置された状態を示す図
【図１８】ツリー方向θ’とツリー整列方向θを示した図
【図１９】ツリー方向θ’をツリー整列方向下θに一致するように対象部分木全体を回転移動させた状態を示す図
【図２０】ツリー表示調整装置の画面表示例を示す図
【図２１】図２０に続く、ツリー表示調整装置の画面表示例を示す図
【図２２】図２１に続く、ツリー表示調整装置の画面表示例を示す図
【発明を実施するための形態】
【０００９】
添付の図面を参照しながら、本発明の一実施の形態の説明をする。
[用語の定義]
本明細書中で使用する用語の定義を述べる。
【００１０】
（１） ツリー
「ツリー」とは、木構造のデータの表示形式をいう。ツリーは、一般的にノードとノード間を結ぶエッジで表される。
【００１１】
（２）ノード
「ノード」とは、ツリー内の枝の分かれる部分である。各ノードは0個以上の子ノードを持つ。子ノードを持つノードは、子ノードの親ノードと呼ばれる。
【００１２】
（３）兄弟ノード
「兄弟ノード」とは、同じ親ノードを持つノード同士をいう。
【００１３】
（４）ルートノード
「ルートノード」とは、木構造の頂点にある最上位ノードをいう。根ノードとも呼ばれる。
【００１４】
（５）リーフノード
「リーフノード」とは、子ノードを有さないノードをいう。葉ノードとも呼ばれる。
【００１５】
（６）ツリーの方向
「ツリーの方向」とは、ルートノードの子ノードのうち両端に位置する子ノードの偏角の平均値をいう。「ツリーの方向」は、ルートノードからリーフノードへ広がっていく木のおよそ中心を通る軸の方向である。
【００１６】
（７）半径方向間隔
「半径方向間隔」とは、親ノードとその子ノードの距離をいう。また、「基準半径方向間隔」は、ツリー構造の整列に用いる半径方向間隔の値で、記号「ｒ」で表す。
【００１７】
（８）回転方向間隔
「回転方向間隔」とは、隣り合う同世代ノード間の弧の長さをいう。「基準回転方向間隔」は、ツリー構造の整列に用いる回転方向間隔の値で、記号「ｌ」（英小文字の「エル」）で表す。
【００１８】
（９）深さ
「深さ」とは、ルートノードからのエッジ数をいう。ルートノードの子ノードは深さが「１」である。同じ親ノードから同一の深さの子ノードは同世代のノードである。
【００１９】
[ツリー表示調整装置の概要]
本実施の形態にかかるツリー表示調整装置の概要を述べる。
ツリー表示調整装置は、ユーザの操作に応じて、ユーザの選択したノード（「選択ノード」と呼ぶ）以下の部分木に含まれる各ノードを、選択ノードからの位置が適切になるように配置して、適切なレイアウトでツリー構造の表示を行う装置である。
【００２０】
ツリー表示調整装置は、選択ノードを中心として見たときに隣り合う同世代ノード間の弧の長さが一定以上になるように選択ノード以下の各ノードを配置する。ツリー表示調整装置によって整列させられると、選択ノードの周りに選択ノードの子ノード及びそれ以降の世代のノードが放射状に並べられる。また、ツリー表示調整装置は、選択ノード以下の親子間の距離（半径方向間隔）をユーザの入力に応じて変化させ、その結果ツリーの広がり具合を変化させることが可能である。
【００２１】
ツリー表示調整装置は、ポインティングデバイスによって入力された位置をインタラクティブにツリー構造の整列に反映させる。
ツリー表示調整装置は、画面上に表示された選択ノードとポインティングデバイスによって指定されたポイントとの距離から、基準半径方向距離を計算し、その基準半径方向距離を選択ノード以下の全エッジ(ブランチ）に適用する。
【００２２】
ツリー表示調整装置は、選択ノードからポインティングデバイスにより指定されたポイントへの方向と、ツリー方向とを一致させるようにツリー全体を、ルートノードを中心として回転移動させる。
【００２３】
なお、視覚化されたツリー構造は、設計に使うツールであるため、中心から広がっていく放射状の配置が適しており、ツリー表示調整装置は、このような放射状の配置を実現するものである。
【００２４】
また、初めから最適な配置は分からず、試しながら配置するので、ユーザの操作に応じてインタラクティブに結果を視認できる本ツリー表示調整装置は有用である。
【００２５】
また、本ツリー表示調整装置はトップのルートノードだけではなく、ツリーの一部分である部分木に対しても適用可能な配置技術である。そのため、本ツリー表示調整装置は部分的にバランスの悪いツリーを綺麗に並べる場合にも適している。
【００２６】
[ツリー表示調整装置の構成例]
本実施の形態にかかるツリー表示調整装置の構成例について説明する。
ツリー表示調整装置は、例えばコンピュータ、ワークステーションなどの情報処理装置によって実現される装置である。この情報処理装置は、演算処理装置（ＣＰＵ）、主メモリ（ＲＡＭ）、読出し専用メモリ（ＲＯＭ）、入出力装置（Ｉ／Ｏ）、及び必要な場合にはハードディスク装置等の外部記憶装置を具備している装置である。
【００２７】
図１は、ツリー表示調整装置の構成例を示す機能ブロック図である。なお、図１に示した各構成要素は、ツリー表示調整装置を機能ごとのまとまりとしてとらえた要素であって、実際のツリー表示調整装置が各構成要素に相当するハードウエア（回路、モジュール、ユニットなど）を備えていることを意味するものではない。なお、以下に構成要素が「接続する」、「接続されている」と記しているが、必ずしも物理的に配線等により接続されていることを指すものではなく、構成要素間でデータや信号を送受信できること意味しており、例えばプログラムモジュールなどの間でのデータの受け渡しの実行も「接続」されていると呼んでいる。
【００２８】
ツリー表示調整装置１は、入力部１０と、入力部１０に接続されたノード位置決定部３０と、ノード位置決定部３０に接続するツリー構造データ記憶部４０、静的パラメータ値記憶部５０と、ノード位置決定部３０に接続された出力部２０とを有している。
【００２９】
ノード位置決定部３０は、動的パラメータ値決定部３１、兄弟ノード処理順決定部３２、葉ノード位置決定部３０、親ノード位置決定部３０、ツリー方向変更部３５、決定位置記憶部３６とを有している。動的パラメータ値決定部３１は本実施の形態の第１の決定手段に相当し、葉ノード位置決定部３０及び親ノード位置決定部３０は、本実施の形態の第２の決定手段に相当し、ツリー方向変更部３５は本実施の形態の回転移動手段に相当する。
【００３０】
入力部１０は、ノードの位置を決定するためのユーザの操作内容を出力する手段であって、例えばポインティングデバイス、タッチパネルなどである。
ノード位置決定部３０は、入力部１０から入力に基づいて、動的パラメータ値である基準半径方向距離ｒ、ツリー整列方向θを決定し、これらに基づいてツリー中の選択されたノード群(後述する処理対象部分木）中の各ノードの位置を決定し、決定した位置に基づいてツリーを表示させる機能を有する。基準半径方向距離ｒは本実施の形態の第１の値に相当し、ツリー整列方向θは本実施の形態の第２の値に相当する。
【００３１】
ツリー構造データ記憶部４０は、ツリー構造データを記憶する機能を有する。
静的パラメータ値記憶部５０は、静的パラメータである基準回転方向距離ｌを記憶する機能を有する。基準回転方向距離ｌは本実施の形態の所定の値に相当する。
【００３２】
出力部２０は、ノード位置決定部３０によって決定されたノードの位置に基づいてツリーを表示する機能を有し、例えば液晶ディスプレイ装置である。
動的パラメータ値決定部３１は入力部の操作に応じて動的に変化する値である動的パラメータの値を決定する機能を有する。
【００３３】
兄弟ノード処理順決定部３２は、兄弟ノードが複数存在する場合、ノードの位置決定処理を実行する順番を決定する機能を有し、後述する兄弟ノード処理順決定処理を実行する。
【００３４】
葉ノード位置決定部３０は、位置決定をしようとするノードが葉ノードである場合に、当該葉ノードの位置決定を行う機能を有し、後述する葉ノード位置決定処理を実行する。
【００３５】
親ノード位置決定部３０は、位置決定をしようとするノードが親ノードである場合に、当該親ノードの位置決定を行う機能を有し、後述する親ノード位置決定処理を実行する。
【００３６】
ツリー方向変更部は、処理対象部分木のツリー方向をツリー整列方向に一致させるように処理対象部分木を回転移動させる機能を有し、後述するツリー方向変更処理を実行する。
【００３７】
決定位置記憶部３６は、ツリー方向変更部３５によって、回転移動させられた後の各ノードの位置情報を記憶する機能を有する。記憶された各ノードの位置情報に基づいて、出力部２０にレイアウトの調整されたツリーが表示される。
【００３８】
[ツリー表示調整]
以下に、ツリー表示調整装置による処理の概要について説明する。
[用いられるパラメータ]
【００３９】
ツリー表示調整装置は、ツリー表示調整処理を実行するために3つのパラメータを使用する。３つのパラメータとは基準半径方向間隔ｒ、基準回転方向間隔ｌ、ツリー整列方向θである。
【００４０】
基準半径方向間隔ｒは、ユーザの入力操作により定まる動的パラメータであって、例えばツリー表示調整装置は、ポインティングデバイスによるドラッグ＆ドロップ操作により決定する、ポインタの移動開始点とポインタの移動終了点との距離を半径方向間隔ｒとして記憶し、計算に使用する。
【００４１】
ツリー整列方向θは、ユーザによる入力操作により定まるパラメータであって、例えばツリー表示調整装置は、ポインティングデバイスによるドラッグ＆ドロップ操作により決定する、選択ノードの座標とポインタの移動終了点とを結ぶ線分により決定される方向(角度)である。
【００４２】
基準回転方向間隔ｌは、あらかじめ設定された値を有する静的パラメータである。基準回転方向間隔ｌは、上記基準半径方向間隔ｒ及びツリー整列方向θとは異なり、別途ユーザ等により指定される値である。
[ツリー表示調整装置の動作（ツリー表示調整処理）]
【００４３】
次に、ツリー表示調整装置１の動作について説明する。図２は、ツリー表示調整装置１の主たる動作である、ツリー表示調整処理の内容を示したフローチャートである。
【００４４】
まず、ユーザが表示されているツリー構造のうち、整列させたい部分（対象部分木と呼ぶ）の最も上位のノード（対象部分木ルートノードと呼ぶ）から、所望のエッジの長さの距離分だけポインティングデバイスのポインタをドラッグするツリー表示調整装置１は、このドラッグ＆ドロップにより出力される（ポインティングデバイスのポインタの座標（以下、ポインティングデバイス座標という）を取得する（Ｓ１０）。ポインティングデバイス座標のドラッグ開始位置により、処理対象部分木の部分木ルートノードが特定される、
【００４５】
次に、ツリー表示調整装置１はポインティングデバイス座標のドラッグ開始位置及び終了位置にから基準半径方向距離ｒを算出する（Ｓ２０）。
【００４６】
次に、ツリー表示調整装置１は、ポインティングデバイス座標のドラッグ開始位置及び終了位置にからツリー整列方向を算出する（Ｓ３０）。
【００４７】
次にツリー表示調整装置１はノード位置決定処理を実行する（Ｓ４０）ノード位置決定処理の内容については後述する。
次にツリー表示調整装置１はノード位置決定処理により決定された各ノードの位置(座標)に基づいて、ツリーを描画する（Ｓ５０）。
【００４８】
次に、ツリー表示調整装置１は、ポインティングデバイスのポインタ（又はボタンなど）が離されたか否かを判定する（Ｓ６０）。離されたと判定した場合（Ｓ６０、Ｙｅｓ）、ツリー表示調整装置１は、ツリー表示調整装置１はツリー表示調整処理を終了する。一方、離されていないと判定した場合（Ｓ６０、Ｎｏ）、ツリー表示調整装置１は、ステップＳ１０に戻りツリー表示調整処理を続行する。この場合、その時点のポインティングデバイス座標を新たなドラッグ終了位置として、新たな基準半径方向間隔ｒ及びツリー整列方向θが定まり、これらに基づいてツリー表示調整処理が再実行される。そのため、ユーザはポインティングデバイスのポインタを動かし続けることによって、ツリーの表示をインタラクティブに変化させて視認し続けることが出来、好ましいレイアウトを発見することが容易となる。
【００４９】
以上で、ツリー表示調整装置１の主たる動作である、ツリー表示調整処理の説明を終了する。
【００５０】
[ノード位置決定処理]
次にツリー表示調整処理中のノード位置決定処理(図２、Ｓ４０）の内容を説明する。図３はノード位置決定処理の一例を示すフローチャートである。
【００５１】
ノード位置決定処理に入ると、ツリー表示調整装置１、より詳しくはノード位置決定部３０は、処理対象ノードが葉ノードか否かを判定する（Ｓ１１０）。葉ノードでないと判定した場合（Ｓ１１０、Ｎｏ）、ツリー表示調整装置１、より詳しくはノード位置決定部３０は、ツリー構造データ記憶部４０から処理対象ノードの全子ノードの情報を取得する（Ｓ１２０）。なお、処理対象ノードが決定されてない場合は、対象部分木ルートノードが処理対象ノードとされる。
【００５２】
次にツリー表示調整装置１、より詳しくは兄弟ノード処理順決定部３２はステップＳ１２０において取得した情報に基づいて兄弟ノード処理順決定処理を実行する（Ｓ１３０）。兄弟ノード処理順決定処理は、兄弟ノードのうちどのノードを処理対象として選択するかの順番を定める処理である。兄弟ノード処理順決定処理の詳しい内容は後述する。
【００５３】
次にツリー表示調整装置１は、未処理の兄弟ノードのうち最上位の処理順のノードの情報を読む（Ｓ１４０）。ここで情報を読まれるノードが新たな処理対象ノードとなる。
【００５４】
次にツリー表示調整装置１は、ノード位置決定処理（Ｓ１５０）を行う。これはノード位置決定処理（Ｓ４０）の再帰処理（再帰呼び出し）である。
【００５５】
次にツリー表示調整装置１は、処理対象ノードの兄弟ノードのうち未処理のノードが存在するか否かを判定する（Ｓ１６０）。兄弟ノードのうち未処理のノードが存在すると判定した場合（Ｓ１６０、Ｙｅｓ）、次にツリー表示調整装置１は、ステップＳ１４０に戻る。
【００５６】
一方、兄弟ノードのうち未処理のノードは存在しないと判定した場合（Ｓ１６０、Ｎｏ）、ツリー表示調整装置１、より詳しくは親ノード位置決定部３０は親ノード位置決定処理を実行する（Ｓ１７０）。親ノード位置決定処理は、処理対象ノードの親ノードの位置(座標)を、前述の動的及び静的パラメータ及びその子ノードの位置(座標)に基づいて決定する処理である。親ノード位置決定処理の内容については後述する。なお、ここで決定された親ノードの位置(座標)は最終的に確定されたものではなく、後述するツリー方向変更処理によってさらに変更されることがある。
【００５７】
次に、ツリー表示調整装置１、より詳しくはツリー方向変更部３５は、ツリー方向変更処理を実行する（Ｓ１８０）。ツリー方向変更処理は、処理対象部分木の各ノードの位置決定後、処理対象部分木のツリー方向を決定し、当該ツリー方向をユーザの入力で定まるツリー整列方向に一致させるように、処理対象部分木ツリーを対象部分木ルートノードを中心とした回転移動させる処理である。
【００５８】
ツリー方向変更処理が終了すると、ツリー表示調整装置１はノード位置決定処理を終了する。なお、そのノード位置決定処理が再帰呼び出しされた処理である場合は、再帰呼び出ししたノード位置決定処理に戻り、ノード位置決定処理が続行されることになる。
【００５９】
一方、ステップＳ１１０において処理対象ノードが葉ノードであると判定した場合（Ｓ１１０、Ｙｅｓ）、ツリー表示調整装置１、より詳しくは葉ノード位置決定部３０は、葉ノード位置決定処理を実行する（Ｓ１９０）。葉ノード位置決定処理は、処理対象ノードである葉ノードの位置(座標)を、前述の動的及び静的パラメータに基づいて決定する処理である。葉ノード位置決定処理の内容については後述する。なお、ここで決定された葉ノードの位置(座標)は最終的に確定されたものではなく、後述するツリー方向変更処理によってさらに変更されることもある。葉ノード位置決定処理（Ｓ１９０）終了後、ツリー表示調整装置１はノード位置決定処理を終了する。なお、そのノード位置決定処理が再帰呼び出しされた処理である場合は、再帰呼び出ししたノード位置決定処理に戻り、ノード位置決定処理が続行されることになる。
以上で、ノード位置決定処理の説明を終了する。
【００６０】
[兄弟ノード処理順決定処理]
次に、上述したノード位置決定処理中の一処理である、兄弟ノード処理順決定処理（図３、Ｓ１３０参照）について説明する。図４は、兄弟ノード処理順決定処理の一例を示したフローチャートである。
【００６１】
兄弟ノード処理順決定処理に入ると、ツリー表示調整装置１、より詳しくは兄弟ノード処理順決定部３２は、処理対象ノードの兄弟ノードから、互いに隣接するノードの組み合わせを全て生成する（Ｓ３１０）。
【００６２】
次にツリー表示調整装置１より詳しくは兄弟ノード処理順決定部３２は、それぞれの組み合わせにおける２つのノードのノード間角度を求める（Ｓ３２０）。「ノード間角度」とは、２つのノードの偏角の差の絶対値である。このステップで全ての組み合わせについて２つのノードのノード間角度が算出される。
【００６３】
次にツリー表示調整装置１より詳しくは兄弟ノード処理順決定部３２は、ステップＳ３２０において算出した全組み合わせのノード間角度のうち、最大のノード間角度を有する組み合わせを抽出する（Ｓ３３０）。
【００６４】
次にツリー表示調整装置１より詳しくは兄弟ノード処理順決定部３２は、ステップＳ３３０において抽出した組み合わせの２つのノードのうち、反時計回り方向のノード（極座標において、より大きな偏角を有するノード）を最初の処理順（処理順位第１位）のノードに決定する（Ｓ３４０）。
【００６５】
次にツリー表示調整装置１は、最初の処理順に定められたノードを基準として、反時計回り方向から見て近い順番で、残りの兄弟ノードの処理順（処理順位第２位、第３位、…）を決定する（Ｓ３５０）。その後ツリー表示調整装置１より詳しくは兄弟ノード処理順決定部３２は、兄弟ノード処理順決定処理を終了する。
【００６６】
[兄弟ノード処理順決定処理の具体例]
次に、兄弟ノードの処理順決定処理（図４参照）の具体例を示す。図５、図６は、兄弟ノードの処理順決定処理の例を示すためのツリーを示した図である。
【００６７】
ツリー表示調整装置１は、処理順を決定する対象となる兄弟ノードについて、互いに隣接するノードの組み合わせを生成する（Ｓ３１０）。図５に示したツリーにおいて、ノードａの子ノードであって、互いに兄弟ノードの関係であるノードｂ、ノードｅ、ノードｉについて処理順を決定する場合は、ノードｂ、ノードｅ、ノードｉが図５に示したような位置関係にある場合、ツリー表示調整装置１は、ノードｂとノードｅの組み合わせ、ノードｅとノードｉの組み合わせ、ノードｉとノードｂの組み合わせの３つの組み合わせを生成する。
【００６８】
次に、ツリー表示調整装置１は、それぞれの組み合わせにおける２つのノードのノード間角度を求める（Ｓ３２０）。「図５に示した例では、ノードｂとノードｅの組み合わせについてノードｂとノードｅのノード間角度α、ノードｅとノードｉの組み合わせについてノードｅとノードｉのノード間角度β、ノードｉとノードｂの組み合わせについてノードｉとノードｂのノード間角度γのそれぞれの角度を算出する。
【００６９】
次に、ツリー表示調整装置１、より詳しくは兄弟ノード処理順決定部３２は、ステップＳ３２０で求めた組み合わせのノード間角度のうち最大のノード間角度を有する組み合わせを抽出する（Ｓ３３０）。図５に示した例では、γ＞β＞αの関係になるものとする。この場合には最大のノード間角度はノード間角度γであるので、ツリー表示調整装置１、より詳しくは兄弟ノード処理順決定部３２は、ノードｉノードｂとの組み合わせを抽出する。
【００７０】
次にツリー表示調整装置１、より詳しくは兄弟ノード処理順決定部３２は、抽出した組み合わせの２つのノードのうち、親ノード（ノードａ）を中心として反時計回り方向側（極座標の偏角が大きい方）のノードを最初の処理順のノードに決定する（Ｓ３４０）。図５の例では、ノードｉよりノードｂの偏角が大きいので、ノードｂが最初の処理順ノードに決定される。
【００７１】
次にツリー表示調整装置１は、最初の処理順に定められたノードを基準として、反時計回り方向から見て最初の処理順に定められたノードに近い順番で、残りの兄弟ノードの処理順を決定する（Ｓ３５０）。図５に示した例では、反時計回り方向から見てノードｂに近い順番は、ノードｅ、ノードｉの順となる。
【００７２】
以上で、ノードａを親ノードとする３つの兄弟ノードの処理順はノードｂ、ノードｅ、ノードｉと決定される。
これで第１世代の兄弟ノードについて兄弟ノードの処理順決定処理は終了する。
【００７３】
兄弟ノードの処理順決定処理は、第２世代以降のノードにも同様に適用される。図６は、図５のツリーにおける第２世代のノードに兄弟ノードの処理順決定処理を適用する例を示した図である。この例では、第１世代のノードｉの３つの子ノード、ノードｆ、ノードｇ、ノードｈの処理順を決定する。この例では最大の角度を有する隣接する兄弟ノードの組み合わせはノードｈとノードｆの組み合わせであり、親ノードを中心として反時計回り方向側（座標の偏角が大きい方）のノードはノードｆである。よって、最初の処理順のノードはノードｆに決定され、ノードｆから見て反時計回り方向に近いノードの順は、ノードｇ、ノードｈとなる。よって、ノードｆ、ノードｇ、ノードｈの処理順はノードｆ、ノードｇ、ノードｈと決定される。
【００７４】
[葉ノード位置決定処理]
次に、ノード位置決定処理(図３参照)内の一処理である、葉ノード位置決定処理（図３、Ｓ１９０）の内容を説明する。図７は、葉ノード位置決定処理の一例を示したフローチャートである。
【００７５】
葉ノード位置決定処理に入ると、ツリー表示調整装置１、より詳しくは葉ノード位置決定部３０は、処理対象ノードである葉ノードが当該葉ノードと同世代ノードのうち最初に位置決定されるノードであるか否かを判定する（Ｓ４１０）。同世代ノードのうち最初に位置決定されるノードであると判定した場合（Ｓ４１０，Ｙｅｓ）、ツリー表示調整装置１、より詳しくは葉ノード位置決定部３０は当該葉ノードの位置を当該世代の基準位置に定める。基準位置は、極座標の動径を基準半径方向距離ｒ×当該葉ノードの深さ（世代数）とし、極座標の偏角を０[rad]とする位置(極座標）である。
【００７６】
一方、同世代ノードのうち最初に位置決定されるノードでないと判定した場合（Ｓ４１０，Ｎｏ）、ツリー表示調整装置１は、当該葉ノードの位置を隣の同世代ノードから基準回転方向距離ｌだけ離れた位置に決定する（Ｓ４２０）。より詳しくは当該葉ノードの座標を、極座標の動径を基準半径方向距離ｒ×当該葉ノードの深さ（世代数）とし、極座標の偏角を隣の同世代ノードから基準回転方向距離ｌだけ離れた位置となる角度]とする。
【００７７】
なお、「隣の同世代ノード」とは、同世代ノードのうち、直近に位置決定がなされたノード、若しくは同世代ノードのうち最も大きな角度を有するノードである。
以上でツリー表示調整装置１、より詳しくは葉ノード位置決定部３０は葉ノード位置決定処理を終了する。
【００７８】
[親ノード位置決定処理]
次に、ノード位置決定処理(図３参照)内の一処理である、親ノード位置決定処理（図３、Ｓ１７０）の内容を説明する。図８は、親ノード位置決定処理の一例を示したフローチャートである。
【００７９】
親ノード位置決定処理に入ると、ツリー表示調整装置１、より詳しくは親ノード位置決定部３０は処理対象ノードの親ノードの半径方向の位置（原点からの距離）を基準半径方向距離ｒ×（その親ノードの深さ(世代数)）により決定する（Ｓ５１０）。
【００８０】
次にツリー表示調整装置１、より詳しくは親ノード位置決定部３０は、当該親ノードの偏角を子ノードの角度の最大値と最小値の平均値とする（Ｓ５２０）。
【００８１】
次にツリー表示調整装置１、より詳しくは親ノード位置決定部３０は、当該親ノードと、その親ノードに隣接する同世代ノードとの回転方向距離が基準回転方向距離ｌより小さいか否かを判定する（Ｓ５３０）。当該回転方向距離が基準回転方向距離ｌより小さいと判定した場合（Ｓ５３０、Ｙｅｓ）、ツリー表示調整装置１、より詳しくは親ノード位置決定部３０は、当該親ノードの偏角を、当該親ノードと隣接する同世代ノード距離が基準回転方向距離ｌとなる角度に変更する（Ｓ５４０）。変更された角度を変更後角度と呼ぶ。
【００８２】
次にツリー表示調整装置１、より詳しくは親ノード位置決定部３０は、当該親ノードの変更後角度に合わせて、当該親ノード以下の全ノードを、原点を中心として回転移動させる（Ｓ５５０）。すなわち、ステップＳ５２０において算出された角度と変更後角度との差を、各ノードの座標の偏角に加算して各ノードの新しい座標の偏角とする。
【００８３】
一方、当該回転方向距離が基準回転方向距離ｌより小さくないと判定した場合（Ｓ５３０、Ｎｏ）、ツリー表示調整装置１、より詳しくは親ノード位置決定部３０はそのまま親ノード位置決定処理を終了する。
以上で親ノード位置決定処理の説明を終了する。
【００８４】
[ノード位置決定処理の具体例]
次に、上述したノード位置決定処理(図３参照)の具体例を説明する。
図９にユーザによって選択された対象部分木の例を示す。この対象部分木は、この部対象分木におけるルートノード（「部分木ルートノード」と呼ぶこととする）であるノードａと、ノードａの子ノードであるノードｂ、ノードｅ、ノードｉと、ノードｅの子ノードであるノードｃ、ノードｄと、ノードｉの子ノードであるノードｆ、ノードｇ、ノードｈで構成される。
【００８５】
部分木ルートノードであるノードａは第０世代のノード、ノードｂ、ノードｅ、ノードｉは第１世代のノード、ノードｃ、ノードｄ、並びにノードｆ、ノードｇ、ノードｈは第2世代のノードである。
【００８６】
[第1世代ノードのノード位置決定処理の開始]
対象部分木についてノード位置決定処理を実行するツリー表示調整装置１は、まず、部分木ルートノードａの子ノード、ノードｂ、ノードｅ、ノードｉについて位置決定を行う。これらノードｂ、ノードｅ、ノードｉをどのような順番で位置決定を行うかは、兄弟ノード処理順決定処理（図４参照）により定まる。ここでは、この兄弟ノード処理順決定処理により、ノードｂ、ノードｅ、ノードｉの順に処理順が決定されたものとする。
【００８７】
[ノードｂの位置決定]
本実施の形態では、ツリー表示調整装置１は、図１０に示すような極座標系を用いて各ノードの位置決定を行うものとして説明するが、その他の座標系を用いてもかまわない。
【００８８】
ツリー表示調整装置１は、第1世代ノードの中の処理順が最初と定められたノードであるノードｂの位置決定を行う。ノードｂの位置決定を行うに先立ち、ツリー表示調整装置１はノードｂが葉ノードであるか否かを判定する。ノードｂは葉ノードであるため、ツリー表示調整装置１は葉ノード位置決定処理を実行しノードｂの位置を決定する。ノードｂの位置は、同世代ノードの基準位置である座標、すなわち動径を基準半径方向距離ｒとし、偏角を角度０とする座標に決定される。図１１は、ノードｂが当該座標の位置に配置された状態を示す図である。
【００８９】
[ノードｅ、ノードｃ、ノードｄの位置決定]
次に、ツリー表示調整装置１は、ノードｂと同世代である第1世代ノードの中で、処理順が第2位と定められたノードであるノードｅを処理対象ノードとする。
【００９０】
ノードｅの位置決定を行うに先立ち、ツリー表示調整装置１はノードｅが葉ノードであるか否かを判定する。ノードｅは葉ノードではないので、ツリー表示調整装置１はノードｅの子ノード（第2世代ノード）であるノードｃ、ノードｄの位置決定を行う。ここで、ツリー表示調整装置１は兄弟ノード処理順決定処理により、ノードｃ、ノードｄの順に位置決定を行うものとする。
【００９１】
[ノードｃの位置決定]
ノードｃの位置決定を行うに先立ち、ツリー表示調整装置１はノードｃが葉ノードであるか否かを判定する。ノードｃは葉ノードであるので、ツリー表示調整装置１は、葉ノード位置決定処理によって、ノードｃの座標を第2世代ノードの基準位置である動径を半径方向距離ｒ×深さ（世代数）＝ｒ×２＝２ｒとし、偏角を角度０である座標に決定する。図１２は、ノードｃが葉ノード位置決定処理により決定された座標の位置に配置された状態を示す図である。
【００９２】
[ノードｄの位置決定]
次に、ツリー表示調整装置１は、ノードｃの次の順位であるノードｄを新たな処理対象ノードとする。ノードｄの位置決定を行うに先立ち、ツリー表示調整装置１はノードｄが葉ノードであるか否かを判定する。ノードｄは葉ノードであるので、ツリー表示調整装置１は、葉ノード位置決定処理によって、ノードｄの動径を基準半径方向距離ｒ×世代数＝２ｒとし、偏角をノードｃから回転方向距離ｌだけ離れた位置となる角度とする座標にノードｄを配置する。すなわち、ノードｄの座標（２ｒ、ｌ／２ｒ）となる。図１３は、ノードｄが極座標に配置された状態を示す。
【００９３】
[ノードｅの再配置位置の決定]
ノードｅの全ての子ノードの位置決定が完了すると、ツリー表示調整装置１は親ノード位置決定処理を実行して、ノードｅの位置決定を行う。まず、ツリー表示調整装置１は、ノードｅの座標の動径を基準半径方向距離ｒ×深さ（世代数）＝ｒ×１＝ｒとし、その偏角を子ノードの偏角の最大値と最小値の平均値とする。ここでは、子ノードの偏角の最大値はノードｄの「ｌ／２ｒ」であり、子ノードの角度の最小値はノードｃの「０」である。よって、これらの平均値は（ｌ／2ｒ＋０）／２＝ｌ／４ｒとなる。この処理段階では、ノードｅの位置は（ｒ、ｌ／４ｒ）と算出される。図１４は、ノードｅが上記極座標の位置に配置された状態を示す。
【００９４】
次にツリー表示調整装置１は、ノードeが同世代ノードで隣接するノードと基準回転方向距離ｌより離れているか否かを判定する。基準回転方向距離ｌより離れていると判定した場合、ツリー表示調整装置１は当該ノードの位置をそのままとする。一方、基準回転方向距離ｌより離れていないと判定した場合、同世代ノードで隣接するノードと基準回転方向距離ｌだけ離れるように、処理対象ノード以下のツリーを、原点を中心として回転移動させる。この例では、ノードｅは、同世代ノードで隣接するノードであるノードｂと基準回転方向距離ｌより離れていないので、ノードｅがノードｂから基準回転方向距離ｌだけ離れるように、ノードｅ以下の部分木ツリーを、原点を中心として回転移動させる。図１５に、ノードｅを、隣接する同世代ノードｂから基準回転方向距離ｌだけ離れるように、ノードｅ以下の部分木ツリー全体を、原点を中心とした回転移動させた状態を示す。この回転移動によってノードｅの座標は（ｒ、ｌ／ｒ）となり、ノードｂの座標は（２ｒ、３ｌ／４ｒ）となり、ノードｄの座標は（２ｒ、５ｌ／４ｒ）となる。
【００９５】
[ノードｉ、ノードｆ、ノードｇ，ノードｈの位置決定]
次に、ツリー表示調整装置１は、第1世代ノードの中の処理順が第３位と定められたノードであるノードｉの位置決定を行う。
【００９６】
ノードｉの位置決定を行うに先立ち、ツリー表示調整装置１はノードｉが葉ノードであるか否かを判定する。ノードｉは葉ノードではないため、ツリー表示調整装置１はノードiの子ノード（第2世代ノード）であるノードｆ、ノードｇ、ノードｈの位置決定を行う。ここで、ツリー表示調整装置１は「兄弟ノード処理順決定処理」により、ノードｆ、ノードｇ、ノードｈの順に処理順を決定したものとする。
【００９７】
[ノードｆの位置決定]
次に、ツリー表示調整装置１は、第1の順位であるノードｆの位置決定をする。ノードｆの位置決定を行うに先立ち、ツリー表示調整装置１はノードｆが葉ノードであるか否かを判定する。ノードｆは葉ノードであるため、ツリー表示調整装置１は、葉ノード位置決定処理により、座標の動径を基準半径方向距離ｒ×深さ（世代数）＝ｒ×２＝２ｒとし、座標の偏角を、同世代ノードのうち直近に配置されたノード（ここではノードｄ）から回転方向距離ｌだけ離れた位置となる角度とする座標の位置にノードｆを配置する。すなわち、ノードｆの座標は（２ｒ、７ｌ／４ｒ）となる。
【００９８】
[ノードｇの位置決定]
次に、ツリー表示調整装置１は、兄弟ノード中第２の順位であるノードｇの位置決定をする。ノードｇの位置決定を行うに先立ち、ツリー表示調整装置１はノードｇが葉ノードであるか否かを判定する。ノードｇは葉ノードであるため、ツリー表示調整装置１は、葉ノード位置決定処理により、座標の動径を基準半径方向距離ｒ×深さ（世代数）＝ｒ×２＝２ｒとし、座標の偏角を、同世代ノードのうち直近に配置されたノード（ここではノードｆ）から回転方向距離ｌだけ離れた位置となる角度とする座標の位置にノードｇを配置する。すなわち、ノードｇの座標は（２ｒ、９ｌ／４ｒ）となる。
【００９９】
[ノードｈの位置決定]
次に、ツリー表示調整装置１は、兄弟ノード中第３の順位であるノードｈの位置決定をする。ノードｈの位置決定を行うに先立ち、ツリー表示調整装置１はノードｈが葉ノードであるか否かを判定する。ノードｈは葉ノードであるため、ツリー表示調整装置１は、葉ノード位置決定処理により、座標の動径を基準半径方向距離ｒ×深さ（世代数）＝ｒ×２＝２ｒとし、座標の偏角を、同世代ノードのうち直近に配置されたノード（ここではノードｇ）から回転方向距離ｌだけ離れた位置となる角度とする座標の位置にノードｈを配置する。すなわち、ノードｈの座標は（２ｒ、１１ｌ／４ｒ）となる。
【０１００】
図１６にノードｆ、ノードｇ、ノードｈが極座標系に配置された状態を示す。
【０１０１】
[ノードｉの位置決定]
ノードｉの全ての子ノードの位置決定が完了すると、ツリー表示調整装置１はこれら子ノードの親ノードであるノードｉの位置決定を行う。まず、ツリー表示調整装置１は、ノードｉの座標の動径を基準半径方向距離ｒ×世代数（１）＝ｒとし、その偏角を子ノードの偏角の最大値と最小値の平均値とする。ここでは、子ノードの偏角の最大値はノードｈの「１１ｌ／４ｒ」であり、子ノードの角度の最小値はノードｆの「７ｌ／４ｒ」である。よって、これらの平均値は（１１ｌ／４ｒ＋７ｌ／４ｒ）／２＝９ｌ／４ｒとなる。よって、この処理段階では、ノードｉの座標は（ｒ、９ｌ／４ｒ）と算出される。図１７は、ノードｉが極座標に配置された状態を示す。
【０１０２】
[ノードｉの再配置位置の決定]
次に、ツリー表示調整装置１はノードｉが同世代ノードで隣接するノードと回転方向距離ｌより離れているか否かを判定する。基準回転方向距離ｌより離れていると判定した場合、ツリー表示調整装置１は当該ノードの位置をそのままとする。一方、基準回転方向距離ｌより離れていないと判定した場合、同世代ノードで隣接するノードと基準回転方向距離ｌだけ離れるように、対象ノード以下のツリーを、原点を中心とした回転移動させる。この例では、ノードｅは、同世代ノードで隣接するノードであるノードｅと基準回転方向距離ｌより離れているので、そのままノードｉの座標が決定される。
［ノードａの配置］
次に、ツリー表示調整装置１は原点に部分木ルートノードであるノードａを配置する。なお、部分木ルートノードはいつ行ってもかまわない。後述する回転移動の終了後であってもかまわない。
【０１０３】
[ツリー整列方向への回転移動]
次に、ツリー表示調整装置１は対象部分木のツリー方向を、ツリー整列方向θに一致させるよう対象部分木のツリー方向を回転移動させる。
【０１０４】
まず、ツリー表示調整装置１は対象部分木のツリー方向を算出する。
対象部分木のツリー方向は、全ての第１世代ノードの偏角の最大値と最小値の平均値である。ここでは、第１世代ノードの偏角の最大値はノードｉの「９ｌ／４ｒ」であり、第１世代ノードの角度の最小値はノードｂの「０」である。よって、これらの平均値は（９ｌ／４ｒ＋０）／２＝９ｌ／４ｒとなり、ツリー方向θ’は＝９ｌ／４ｒと算出される。
【０１０５】
次に、ツリー表示調整装置１はそのツリー方向θ’をツリー整列方向θに一致するように、原点を中心として対象部分木ツリー全体を回転移動させる。図１８はツリー方向θ’とツリー整列方向θを示した図、図１９は、ツリー方向θ’をツリー整列方向下θに一致するように対象部分木全体を、原点を中心として回転移動させた状態を示す図である。
【０１０６】
ツリー方向とツリー整列方向が一致するように、対象部分木を回転移動させると、ノード位置決定処理は完了する。
[画面例]
【０１０７】
ツリー表示調整装置１の画面表示例を示す。図２０はユーザがツリー表示を調整したい部分木の部分木ルートノード２００にポインティングデバイスのポインタ２１０を置いた状態の画面例である。
【０１０８】
図２１は、図２０の状態の後に、ポインタ２１０がドラッグされた状態の画面例である。ポインタ２１０の移動に応じて部分木ルートノード２００以下のノードは、親子ノード間の距離である半径方向距離が基準半径方向距離ｒとなり、兄弟ノード間の回転方向距離が基準回転方向距離ｌ以上になり、ツリー方向がツリー整列方向に一致するように回転移動されている。
【０１０９】
図２２は、図２１の状態の後にポインタ２１０がさらに部分木ルートノード２００から離れた位置までドラッグされた状態の画面例である。親子ノード間の距離である半径方向距離がより長くなり、ツリー方向は現在のポインタの位置に従って新たなツリー整列方向に一致するように回転移動されている。
【０１１０】
このように本ツリー表示調整装置によれば、インタラクティブにツリー表示の調整を行うことが可能となる。
【０１１１】
[まとめ]
本実施の形態によれば、ノードを個別に移動させる必要がなくなるため、整列を行うのにかかる時間を短縮することが出来る。
また、本実施の形態によれば、インタラクティブに結果を確認しながらノードの整列が行われるため、ユーザが所望する配置にすることが容易となる。
【０１１２】
エッジの長さ（親子ノード間の距離）が変わると、連動してツリーの広がり具合が変化するため、直感的に整列を行える。
ドラッグアンドドロップにより、個別にノードを移動させることによって、整列の順序を容易に変更できる。
【０１１３】
以上、本発明の実施の形態を説明したが、本発明はこれらに限定されるものではなく、発明の趣旨を逸脱しない範囲内において、種々の変更、追加、組み合わせ等が可能である。
【符号の説明】
【０１１４】
１・・・ツリー表示調整装置； ３０・・・ノード位置決定部； ３１・・・動的パラメータ決定部； ３３・・・葉ノード位置決定部； ３４・・・親ノード位置決定部； ３５・・・ツリー方向変更部
【技術分野】
【０００１】
本明細書に記載の実施の形態は、ツリー表示調整装置に関する。
【背景技術】
【０００２】
ツリー構造は、ある階層に属する一つのデータから、下位階層に位置する複数のデータが枝分かれした状態で配置されている構造であり、様々な局面で使用されている。開発者などがツリー構造をコンピュータ上で図示させて、検証、改良等の作業を行うことが一般的に行われている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００６−０４８５３１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、ツリー構造が大きくなってノードの数が多数になり、あるいはツリー構造が複雑化するに従い、ツリー構造の内容を一目して把握することが困難になり、ツリー構造を整列させる必要が生ずる。しかし、ツリー構造におけるノードを、手動にて目的の配置に整列させることは負担が大きく、またどのような配置が見やすく理解しやすい配置となるかを直感的に見出すことも困難である。
【０００５】
本発明は、ツリー構造を望ましいレイアウトに調整させて表示させることが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
一の実施の形態によれば、ツリー表示調整装置が提供される。ツリー表示提供装置は第１の決定手段と、第２の決定手段と、回転移動手段とを有している。
【０００７】
第１の決定手段は、ユーザの入力に応じて決定される値である第１の値及び第２の値を決定する。第２の決定手段は、対象となる部分木における親子ノード間の距離である半径方向距離が第１の値となるようにするとともに、兄弟ノード間の回転方向距離が所定の値以上になるように各ノードの位置決定を行う。回転移動手段は、前記第２の値に応じて前記対象となる部分木を回転移動させる。
【図面の簡単な説明】
【０００８】
【図１】ツリー表示調整装置の構成例を示す機能ブロック図
【図２】ツリー表示調整処理の内容を示したフローチャート
【図３】ノード位置決定処理の一例を示すフローチャート
【図４】図４は、兄弟ノード処理順決定処理の一例を示したフローチャート
【図５】兄弟ノードの処理順決定処理の例を示すためのツリーを示した図
【図６】兄弟ノードの処理順決定処理の例を示すためのツリーを示した別の図
【図７】葉ノード位置決定処理の一例を示したフローチャート
【図８】図８は、親ノード位置決定処理の一例を示したフローチャート
【図９】ユーザによって選択された対象部分木の例を示す図
【図１０】ノードの位置を決定するための極座標系を示す図
【図１１】ノードｂが当該座標の位置に配置された状態を示す図
【図１２】ノードｃが葉ノード位置決定処理により決定された座標の位置に配置された状態を示す図
【図１３】ノードｄが極座標に配置された状態を示す図
【図１４】ノードｅが上記極座標の位置に配置された状態を示す図
【図１５】ノードｅ以下の部分木ツリー全体を原点を中心とした回転移動させた状態を示す図
【図１６】ノードｆ、ノードｇ、ノードｈが極座標系に配置された状態を示す図
【図１７】ノードｉが極座標に配置された状態を示す図
【図１８】ツリー方向θ’とツリー整列方向θを示した図
【図１９】ツリー方向θ’をツリー整列方向下θに一致するように対象部分木全体を回転移動させた状態を示す図
【図２０】ツリー表示調整装置の画面表示例を示す図
【図２１】図２０に続く、ツリー表示調整装置の画面表示例を示す図
【図２２】図２１に続く、ツリー表示調整装置の画面表示例を示す図
【発明を実施するための形態】
【０００９】
添付の図面を参照しながら、本発明の一実施の形態の説明をする。
[用語の定義]
本明細書中で使用する用語の定義を述べる。
【００１０】
（１） ツリー
「ツリー」とは、木構造のデータの表示形式をいう。ツリーは、一般的にノードとノード間を結ぶエッジで表される。
【００１１】
（２）ノード
「ノード」とは、ツリー内の枝の分かれる部分である。各ノードは0個以上の子ノードを持つ。子ノードを持つノードは、子ノードの親ノードと呼ばれる。
【００１２】
（３）兄弟ノード
「兄弟ノード」とは、同じ親ノードを持つノード同士をいう。
【００１３】
（４）ルートノード
「ルートノード」とは、木構造の頂点にある最上位ノードをいう。根ノードとも呼ばれる。
【００１４】
（５）リーフノード
「リーフノード」とは、子ノードを有さないノードをいう。葉ノードとも呼ばれる。
【００１５】
（６）ツリーの方向
「ツリーの方向」とは、ルートノードの子ノードのうち両端に位置する子ノードの偏角の平均値をいう。「ツリーの方向」は、ルートノードからリーフノードへ広がっていく木のおよそ中心を通る軸の方向である。
【００１６】
（７）半径方向間隔
「半径方向間隔」とは、親ノードとその子ノードの距離をいう。また、「基準半径方向間隔」は、ツリー構造の整列に用いる半径方向間隔の値で、記号「ｒ」で表す。
【００１７】
（８）回転方向間隔
「回転方向間隔」とは、隣り合う同世代ノード間の弧の長さをいう。「基準回転方向間隔」は、ツリー構造の整列に用いる回転方向間隔の値で、記号「ｌ」（英小文字の「エル」）で表す。
【００１８】
（９）深さ
「深さ」とは、ルートノードからのエッジ数をいう。ルートノードの子ノードは深さが「１」である。同じ親ノードから同一の深さの子ノードは同世代のノードである。
【００１９】
[ツリー表示調整装置の概要]
本実施の形態にかかるツリー表示調整装置の概要を述べる。
ツリー表示調整装置は、ユーザの操作に応じて、ユーザの選択したノード（「選択ノード」と呼ぶ）以下の部分木に含まれる各ノードを、選択ノードからの位置が適切になるように配置して、適切なレイアウトでツリー構造の表示を行う装置である。
【００２０】
ツリー表示調整装置は、選択ノードを中心として見たときに隣り合う同世代ノード間の弧の長さが一定以上になるように選択ノード以下の各ノードを配置する。ツリー表示調整装置によって整列させられると、選択ノードの周りに選択ノードの子ノード及びそれ以降の世代のノードが放射状に並べられる。また、ツリー表示調整装置は、選択ノード以下の親子間の距離（半径方向間隔）をユーザの入力に応じて変化させ、その結果ツリーの広がり具合を変化させることが可能である。
【００２１】
ツリー表示調整装置は、ポインティングデバイスによって入力された位置をインタラクティブにツリー構造の整列に反映させる。
ツリー表示調整装置は、画面上に表示された選択ノードとポインティングデバイスによって指定されたポイントとの距離から、基準半径方向距離を計算し、その基準半径方向距離を選択ノード以下の全エッジ(ブランチ）に適用する。
【００２２】
ツリー表示調整装置は、選択ノードからポインティングデバイスにより指定されたポイントへの方向と、ツリー方向とを一致させるようにツリー全体を、ルートノードを中心として回転移動させる。
【００２３】
なお、視覚化されたツリー構造は、設計に使うツールであるため、中心から広がっていく放射状の配置が適しており、ツリー表示調整装置は、このような放射状の配置を実現するものである。
【００２４】
また、初めから最適な配置は分からず、試しながら配置するので、ユーザの操作に応じてインタラクティブに結果を視認できる本ツリー表示調整装置は有用である。
【００２５】
また、本ツリー表示調整装置はトップのルートノードだけではなく、ツリーの一部分である部分木に対しても適用可能な配置技術である。そのため、本ツリー表示調整装置は部分的にバランスの悪いツリーを綺麗に並べる場合にも適している。
【００２６】
[ツリー表示調整装置の構成例]
本実施の形態にかかるツリー表示調整装置の構成例について説明する。
ツリー表示調整装置は、例えばコンピュータ、ワークステーションなどの情報処理装置によって実現される装置である。この情報処理装置は、演算処理装置（ＣＰＵ）、主メモリ（ＲＡＭ）、読出し専用メモリ（ＲＯＭ）、入出力装置（Ｉ／Ｏ）、及び必要な場合にはハードディスク装置等の外部記憶装置を具備している装置である。
【００２７】
図１は、ツリー表示調整装置の構成例を示す機能ブロック図である。なお、図１に示した各構成要素は、ツリー表示調整装置を機能ごとのまとまりとしてとらえた要素であって、実際のツリー表示調整装置が各構成要素に相当するハードウエア（回路、モジュール、ユニットなど）を備えていることを意味するものではない。なお、以下に構成要素が「接続する」、「接続されている」と記しているが、必ずしも物理的に配線等により接続されていることを指すものではなく、構成要素間でデータや信号を送受信できること意味しており、例えばプログラムモジュールなどの間でのデータの受け渡しの実行も「接続」されていると呼んでいる。
【００２８】
ツリー表示調整装置１は、入力部１０と、入力部１０に接続されたノード位置決定部３０と、ノード位置決定部３０に接続するツリー構造データ記憶部４０、静的パラメータ値記憶部５０と、ノード位置決定部３０に接続された出力部２０とを有している。
【００２９】
ノード位置決定部３０は、動的パラメータ値決定部３１、兄弟ノード処理順決定部３２、葉ノード位置決定部３０、親ノード位置決定部３０、ツリー方向変更部３５、決定位置記憶部３６とを有している。動的パラメータ値決定部３１は本実施の形態の第１の決定手段に相当し、葉ノード位置決定部３０及び親ノード位置決定部３０は、本実施の形態の第２の決定手段に相当し、ツリー方向変更部３５は本実施の形態の回転移動手段に相当する。
【００３０】
入力部１０は、ノードの位置を決定するためのユーザの操作内容を出力する手段であって、例えばポインティングデバイス、タッチパネルなどである。
ノード位置決定部３０は、入力部１０から入力に基づいて、動的パラメータ値である基準半径方向距離ｒ、ツリー整列方向θを決定し、これらに基づいてツリー中の選択されたノード群(後述する処理対象部分木）中の各ノードの位置を決定し、決定した位置に基づいてツリーを表示させる機能を有する。基準半径方向距離ｒは本実施の形態の第１の値に相当し、ツリー整列方向θは本実施の形態の第２の値に相当する。
【００３１】
ツリー構造データ記憶部４０は、ツリー構造データを記憶する機能を有する。
静的パラメータ値記憶部５０は、静的パラメータである基準回転方向距離ｌを記憶する機能を有する。基準回転方向距離ｌは本実施の形態の所定の値に相当する。
【００３２】
出力部２０は、ノード位置決定部３０によって決定されたノードの位置に基づいてツリーを表示する機能を有し、例えば液晶ディスプレイ装置である。
動的パラメータ値決定部３１は入力部の操作に応じて動的に変化する値である動的パラメータの値を決定する機能を有する。
【００３３】
兄弟ノード処理順決定部３２は、兄弟ノードが複数存在する場合、ノードの位置決定処理を実行する順番を決定する機能を有し、後述する兄弟ノード処理順決定処理を実行する。
【００３４】
葉ノード位置決定部３０は、位置決定をしようとするノードが葉ノードである場合に、当該葉ノードの位置決定を行う機能を有し、後述する葉ノード位置決定処理を実行する。
【００３５】
親ノード位置決定部３０は、位置決定をしようとするノードが親ノードである場合に、当該親ノードの位置決定を行う機能を有し、後述する親ノード位置決定処理を実行する。
【００３６】
ツリー方向変更部は、処理対象部分木のツリー方向をツリー整列方向に一致させるように処理対象部分木を回転移動させる機能を有し、後述するツリー方向変更処理を実行する。
【００３７】
決定位置記憶部３６は、ツリー方向変更部３５によって、回転移動させられた後の各ノードの位置情報を記憶する機能を有する。記憶された各ノードの位置情報に基づいて、出力部２０にレイアウトの調整されたツリーが表示される。
【００３８】
[ツリー表示調整]
以下に、ツリー表示調整装置による処理の概要について説明する。
[用いられるパラメータ]
【００３９】
ツリー表示調整装置は、ツリー表示調整処理を実行するために3つのパラメータを使用する。３つのパラメータとは基準半径方向間隔ｒ、基準回転方向間隔ｌ、ツリー整列方向θである。
【００４０】
基準半径方向間隔ｒは、ユーザの入力操作により定まる動的パラメータであって、例えばツリー表示調整装置は、ポインティングデバイスによるドラッグ＆ドロップ操作により決定する、ポインタの移動開始点とポインタの移動終了点との距離を半径方向間隔ｒとして記憶し、計算に使用する。
【００４１】
ツリー整列方向θは、ユーザによる入力操作により定まるパラメータであって、例えばツリー表示調整装置は、ポインティングデバイスによるドラッグ＆ドロップ操作により決定する、選択ノードの座標とポインタの移動終了点とを結ぶ線分により決定される方向(角度)である。
【００４２】
基準回転方向間隔ｌは、あらかじめ設定された値を有する静的パラメータである。基準回転方向間隔ｌは、上記基準半径方向間隔ｒ及びツリー整列方向θとは異なり、別途ユーザ等により指定される値である。
[ツリー表示調整装置の動作（ツリー表示調整処理）]
【００４３】
次に、ツリー表示調整装置１の動作について説明する。図２は、ツリー表示調整装置１の主たる動作である、ツリー表示調整処理の内容を示したフローチャートである。
【００４４】
まず、ユーザが表示されているツリー構造のうち、整列させたい部分（対象部分木と呼ぶ）の最も上位のノード（対象部分木ルートノードと呼ぶ）から、所望のエッジの長さの距離分だけポインティングデバイスのポインタをドラッグするツリー表示調整装置１は、このドラッグ＆ドロップにより出力される（ポインティングデバイスのポインタの座標（以下、ポインティングデバイス座標という）を取得する（Ｓ１０）。ポインティングデバイス座標のドラッグ開始位置により、処理対象部分木の部分木ルートノードが特定される、
【００４５】
次に、ツリー表示調整装置１はポインティングデバイス座標のドラッグ開始位置及び終了位置にから基準半径方向距離ｒを算出する（Ｓ２０）。
【００４６】
次に、ツリー表示調整装置１は、ポインティングデバイス座標のドラッグ開始位置及び終了位置にからツリー整列方向を算出する（Ｓ３０）。
【００４７】
次にツリー表示調整装置１はノード位置決定処理を実行する（Ｓ４０）ノード位置決定処理の内容については後述する。
次にツリー表示調整装置１はノード位置決定処理により決定された各ノードの位置(座標)に基づいて、ツリーを描画する（Ｓ５０）。
【００４８】
次に、ツリー表示調整装置１は、ポインティングデバイスのポインタ（又はボタンなど）が離されたか否かを判定する（Ｓ６０）。離されたと判定した場合（Ｓ６０、Ｙｅｓ）、ツリー表示調整装置１は、ツリー表示調整装置１はツリー表示調整処理を終了する。一方、離されていないと判定した場合（Ｓ６０、Ｎｏ）、ツリー表示調整装置１は、ステップＳ１０に戻りツリー表示調整処理を続行する。この場合、その時点のポインティングデバイス座標を新たなドラッグ終了位置として、新たな基準半径方向間隔ｒ及びツリー整列方向θが定まり、これらに基づいてツリー表示調整処理が再実行される。そのため、ユーザはポインティングデバイスのポインタを動かし続けることによって、ツリーの表示をインタラクティブに変化させて視認し続けることが出来、好ましいレイアウトを発見することが容易となる。
【００４９】
以上で、ツリー表示調整装置１の主たる動作である、ツリー表示調整処理の説明を終了する。
【００５０】
[ノード位置決定処理]
次にツリー表示調整処理中のノード位置決定処理(図２、Ｓ４０）の内容を説明する。図３はノード位置決定処理の一例を示すフローチャートである。
【００５１】
ノード位置決定処理に入ると、ツリー表示調整装置１、より詳しくはノード位置決定部３０は、処理対象ノードが葉ノードか否かを判定する（Ｓ１１０）。葉ノードでないと判定した場合（Ｓ１１０、Ｎｏ）、ツリー表示調整装置１、より詳しくはノード位置決定部３０は、ツリー構造データ記憶部４０から処理対象ノードの全子ノードの情報を取得する（Ｓ１２０）。なお、処理対象ノードが決定されてない場合は、対象部分木ルートノードが処理対象ノードとされる。
【００５２】
次にツリー表示調整装置１、より詳しくは兄弟ノード処理順決定部３２はステップＳ１２０において取得した情報に基づいて兄弟ノード処理順決定処理を実行する（Ｓ１３０）。兄弟ノード処理順決定処理は、兄弟ノードのうちどのノードを処理対象として選択するかの順番を定める処理である。兄弟ノード処理順決定処理の詳しい内容は後述する。
【００５３】
次にツリー表示調整装置１は、未処理の兄弟ノードのうち最上位の処理順のノードの情報を読む（Ｓ１４０）。ここで情報を読まれるノードが新たな処理対象ノードとなる。
【００５４】
次にツリー表示調整装置１は、ノード位置決定処理（Ｓ１５０）を行う。これはノード位置決定処理（Ｓ４０）の再帰処理（再帰呼び出し）である。
【００５５】
次にツリー表示調整装置１は、処理対象ノードの兄弟ノードのうち未処理のノードが存在するか否かを判定する（Ｓ１６０）。兄弟ノードのうち未処理のノードが存在すると判定した場合（Ｓ１６０、Ｙｅｓ）、次にツリー表示調整装置１は、ステップＳ１４０に戻る。
【００５６】
一方、兄弟ノードのうち未処理のノードは存在しないと判定した場合（Ｓ１６０、Ｎｏ）、ツリー表示調整装置１、より詳しくは親ノード位置決定部３０は親ノード位置決定処理を実行する（Ｓ１７０）。親ノード位置決定処理は、処理対象ノードの親ノードの位置(座標)を、前述の動的及び静的パラメータ及びその子ノードの位置(座標)に基づいて決定する処理である。親ノード位置決定処理の内容については後述する。なお、ここで決定された親ノードの位置(座標)は最終的に確定されたものではなく、後述するツリー方向変更処理によってさらに変更されることがある。
【００５７】
次に、ツリー表示調整装置１、より詳しくはツリー方向変更部３５は、ツリー方向変更処理を実行する（Ｓ１８０）。ツリー方向変更処理は、処理対象部分木の各ノードの位置決定後、処理対象部分木のツリー方向を決定し、当該ツリー方向をユーザの入力で定まるツリー整列方向に一致させるように、処理対象部分木ツリーを対象部分木ルートノードを中心とした回転移動させる処理である。
【００５８】
ツリー方向変更処理が終了すると、ツリー表示調整装置１はノード位置決定処理を終了する。なお、そのノード位置決定処理が再帰呼び出しされた処理である場合は、再帰呼び出ししたノード位置決定処理に戻り、ノード位置決定処理が続行されることになる。
【００５９】
一方、ステップＳ１１０において処理対象ノードが葉ノードであると判定した場合（Ｓ１１０、Ｙｅｓ）、ツリー表示調整装置１、より詳しくは葉ノード位置決定部３０は、葉ノード位置決定処理を実行する（Ｓ１９０）。葉ノード位置決定処理は、処理対象ノードである葉ノードの位置(座標)を、前述の動的及び静的パラメータに基づいて決定する処理である。葉ノード位置決定処理の内容については後述する。なお、ここで決定された葉ノードの位置(座標)は最終的に確定されたものではなく、後述するツリー方向変更処理によってさらに変更されることもある。葉ノード位置決定処理（Ｓ１９０）終了後、ツリー表示調整装置１はノード位置決定処理を終了する。なお、そのノード位置決定処理が再帰呼び出しされた処理である場合は、再帰呼び出ししたノード位置決定処理に戻り、ノード位置決定処理が続行されることになる。
以上で、ノード位置決定処理の説明を終了する。
【００６０】
[兄弟ノード処理順決定処理]
次に、上述したノード位置決定処理中の一処理である、兄弟ノード処理順決定処理（図３、Ｓ１３０参照）について説明する。図４は、兄弟ノード処理順決定処理の一例を示したフローチャートである。
【００６１】
兄弟ノード処理順決定処理に入ると、ツリー表示調整装置１、より詳しくは兄弟ノード処理順決定部３２は、処理対象ノードの兄弟ノードから、互いに隣接するノードの組み合わせを全て生成する（Ｓ３１０）。
【００６２】
次にツリー表示調整装置１より詳しくは兄弟ノード処理順決定部３２は、それぞれの組み合わせにおける２つのノードのノード間角度を求める（Ｓ３２０）。「ノード間角度」とは、２つのノードの偏角の差の絶対値である。このステップで全ての組み合わせについて２つのノードのノード間角度が算出される。
【００６３】
次にツリー表示調整装置１より詳しくは兄弟ノード処理順決定部３２は、ステップＳ３２０において算出した全組み合わせのノード間角度のうち、最大のノード間角度を有する組み合わせを抽出する（Ｓ３３０）。
【００６４】
次にツリー表示調整装置１より詳しくは兄弟ノード処理順決定部３２は、ステップＳ３３０において抽出した組み合わせの２つのノードのうち、反時計回り方向のノード（極座標において、より大きな偏角を有するノード）を最初の処理順（処理順位第１位）のノードに決定する（Ｓ３４０）。
【００６５】
次にツリー表示調整装置１は、最初の処理順に定められたノードを基準として、反時計回り方向から見て近い順番で、残りの兄弟ノードの処理順（処理順位第２位、第３位、…）を決定する（Ｓ３５０）。その後ツリー表示調整装置１より詳しくは兄弟ノード処理順決定部３２は、兄弟ノード処理順決定処理を終了する。
【００６６】
[兄弟ノード処理順決定処理の具体例]
次に、兄弟ノードの処理順決定処理（図４参照）の具体例を示す。図５、図６は、兄弟ノードの処理順決定処理の例を示すためのツリーを示した図である。
【００６７】
ツリー表示調整装置１は、処理順を決定する対象となる兄弟ノードについて、互いに隣接するノードの組み合わせを生成する（Ｓ３１０）。図５に示したツリーにおいて、ノードａの子ノードであって、互いに兄弟ノードの関係であるノードｂ、ノードｅ、ノードｉについて処理順を決定する場合は、ノードｂ、ノードｅ、ノードｉが図５に示したような位置関係にある場合、ツリー表示調整装置１は、ノードｂとノードｅの組み合わせ、ノードｅとノードｉの組み合わせ、ノードｉとノードｂの組み合わせの３つの組み合わせを生成する。
【００６８】
次に、ツリー表示調整装置１は、それぞれの組み合わせにおける２つのノードのノード間角度を求める（Ｓ３２０）。「図５に示した例では、ノードｂとノードｅの組み合わせについてノードｂとノードｅのノード間角度α、ノードｅとノードｉの組み合わせについてノードｅとノードｉのノード間角度β、ノードｉとノードｂの組み合わせについてノードｉとノードｂのノード間角度γのそれぞれの角度を算出する。
【００６９】
次に、ツリー表示調整装置１、より詳しくは兄弟ノード処理順決定部３２は、ステップＳ３２０で求めた組み合わせのノード間角度のうち最大のノード間角度を有する組み合わせを抽出する（Ｓ３３０）。図５に示した例では、γ＞β＞αの関係になるものとする。この場合には最大のノード間角度はノード間角度γであるので、ツリー表示調整装置１、より詳しくは兄弟ノード処理順決定部３２は、ノードｉノードｂとの組み合わせを抽出する。
【００７０】
次にツリー表示調整装置１、より詳しくは兄弟ノード処理順決定部３２は、抽出した組み合わせの２つのノードのうち、親ノード（ノードａ）を中心として反時計回り方向側（極座標の偏角が大きい方）のノードを最初の処理順のノードに決定する（Ｓ３４０）。図５の例では、ノードｉよりノードｂの偏角が大きいので、ノードｂが最初の処理順ノードに決定される。
【００７１】
次にツリー表示調整装置１は、最初の処理順に定められたノードを基準として、反時計回り方向から見て最初の処理順に定められたノードに近い順番で、残りの兄弟ノードの処理順を決定する（Ｓ３５０）。図５に示した例では、反時計回り方向から見てノードｂに近い順番は、ノードｅ、ノードｉの順となる。
【００７２】
以上で、ノードａを親ノードとする３つの兄弟ノードの処理順はノードｂ、ノードｅ、ノードｉと決定される。
これで第１世代の兄弟ノードについて兄弟ノードの処理順決定処理は終了する。
【００７３】
兄弟ノードの処理順決定処理は、第２世代以降のノードにも同様に適用される。図６は、図５のツリーにおける第２世代のノードに兄弟ノードの処理順決定処理を適用する例を示した図である。この例では、第１世代のノードｉの３つの子ノード、ノードｆ、ノードｇ、ノードｈの処理順を決定する。この例では最大の角度を有する隣接する兄弟ノードの組み合わせはノードｈとノードｆの組み合わせであり、親ノードを中心として反時計回り方向側（座標の偏角が大きい方）のノードはノードｆである。よって、最初の処理順のノードはノードｆに決定され、ノードｆから見て反時計回り方向に近いノードの順は、ノードｇ、ノードｈとなる。よって、ノードｆ、ノードｇ、ノードｈの処理順はノードｆ、ノードｇ、ノードｈと決定される。
【００７４】
[葉ノード位置決定処理]
次に、ノード位置決定処理(図３参照)内の一処理である、葉ノード位置決定処理（図３、Ｓ１９０）の内容を説明する。図７は、葉ノード位置決定処理の一例を示したフローチャートである。
【００７５】
葉ノード位置決定処理に入ると、ツリー表示調整装置１、より詳しくは葉ノード位置決定部３０は、処理対象ノードである葉ノードが当該葉ノードと同世代ノードのうち最初に位置決定されるノードであるか否かを判定する（Ｓ４１０）。同世代ノードのうち最初に位置決定されるノードであると判定した場合（Ｓ４１０，Ｙｅｓ）、ツリー表示調整装置１、より詳しくは葉ノード位置決定部３０は当該葉ノードの位置を当該世代の基準位置に定める。基準位置は、極座標の動径を基準半径方向距離ｒ×当該葉ノードの深さ（世代数）とし、極座標の偏角を０[rad]とする位置(極座標）である。
【００７６】
一方、同世代ノードのうち最初に位置決定されるノードでないと判定した場合（Ｓ４１０，Ｎｏ）、ツリー表示調整装置１は、当該葉ノードの位置を隣の同世代ノードから基準回転方向距離ｌだけ離れた位置に決定する（Ｓ４２０）。より詳しくは当該葉ノードの座標を、極座標の動径を基準半径方向距離ｒ×当該葉ノードの深さ（世代数）とし、極座標の偏角を隣の同世代ノードから基準回転方向距離ｌだけ離れた位置となる角度]とする。
【００７７】
なお、「隣の同世代ノード」とは、同世代ノードのうち、直近に位置決定がなされたノード、若しくは同世代ノードのうち最も大きな角度を有するノードである。
以上でツリー表示調整装置１、より詳しくは葉ノード位置決定部３０は葉ノード位置決定処理を終了する。
【００７８】
[親ノード位置決定処理]
次に、ノード位置決定処理(図３参照)内の一処理である、親ノード位置決定処理（図３、Ｓ１７０）の内容を説明する。図８は、親ノード位置決定処理の一例を示したフローチャートである。
【００７９】
親ノード位置決定処理に入ると、ツリー表示調整装置１、より詳しくは親ノード位置決定部３０は処理対象ノードの親ノードの半径方向の位置（原点からの距離）を基準半径方向距離ｒ×（その親ノードの深さ(世代数)）により決定する（Ｓ５１０）。
【００８０】
次にツリー表示調整装置１、より詳しくは親ノード位置決定部３０は、当該親ノードの偏角を子ノードの角度の最大値と最小値の平均値とする（Ｓ５２０）。
【００８１】
次にツリー表示調整装置１、より詳しくは親ノード位置決定部３０は、当該親ノードと、その親ノードに隣接する同世代ノードとの回転方向距離が基準回転方向距離ｌより小さいか否かを判定する（Ｓ５３０）。当該回転方向距離が基準回転方向距離ｌより小さいと判定した場合（Ｓ５３０、Ｙｅｓ）、ツリー表示調整装置１、より詳しくは親ノード位置決定部３０は、当該親ノードの偏角を、当該親ノードと隣接する同世代ノード距離が基準回転方向距離ｌとなる角度に変更する（Ｓ５４０）。変更された角度を変更後角度と呼ぶ。
【００８２】
次にツリー表示調整装置１、より詳しくは親ノード位置決定部３０は、当該親ノードの変更後角度に合わせて、当該親ノード以下の全ノードを、原点を中心として回転移動させる（Ｓ５５０）。すなわち、ステップＳ５２０において算出された角度と変更後角度との差を、各ノードの座標の偏角に加算して各ノードの新しい座標の偏角とする。
【００８３】
一方、当該回転方向距離が基準回転方向距離ｌより小さくないと判定した場合（Ｓ５３０、Ｎｏ）、ツリー表示調整装置１、より詳しくは親ノード位置決定部３０はそのまま親ノード位置決定処理を終了する。
以上で親ノード位置決定処理の説明を終了する。
【００８４】
[ノード位置決定処理の具体例]
次に、上述したノード位置決定処理(図３参照)の具体例を説明する。
図９にユーザによって選択された対象部分木の例を示す。この対象部分木は、この部対象分木におけるルートノード（「部分木ルートノード」と呼ぶこととする）であるノードａと、ノードａの子ノードであるノードｂ、ノードｅ、ノードｉと、ノードｅの子ノードであるノードｃ、ノードｄと、ノードｉの子ノードであるノードｆ、ノードｇ、ノードｈで構成される。
【００８５】
部分木ルートノードであるノードａは第０世代のノード、ノードｂ、ノードｅ、ノードｉは第１世代のノード、ノードｃ、ノードｄ、並びにノードｆ、ノードｇ、ノードｈは第2世代のノードである。
【００８６】
[第1世代ノードのノード位置決定処理の開始]
対象部分木についてノード位置決定処理を実行するツリー表示調整装置１は、まず、部分木ルートノードａの子ノード、ノードｂ、ノードｅ、ノードｉについて位置決定を行う。これらノードｂ、ノードｅ、ノードｉをどのような順番で位置決定を行うかは、兄弟ノード処理順決定処理（図４参照）により定まる。ここでは、この兄弟ノード処理順決定処理により、ノードｂ、ノードｅ、ノードｉの順に処理順が決定されたものとする。
【００８７】
[ノードｂの位置決定]
本実施の形態では、ツリー表示調整装置１は、図１０に示すような極座標系を用いて各ノードの位置決定を行うものとして説明するが、その他の座標系を用いてもかまわない。
【００８８】
ツリー表示調整装置１は、第1世代ノードの中の処理順が最初と定められたノードであるノードｂの位置決定を行う。ノードｂの位置決定を行うに先立ち、ツリー表示調整装置１はノードｂが葉ノードであるか否かを判定する。ノードｂは葉ノードであるため、ツリー表示調整装置１は葉ノード位置決定処理を実行しノードｂの位置を決定する。ノードｂの位置は、同世代ノードの基準位置である座標、すなわち動径を基準半径方向距離ｒとし、偏角を角度０とする座標に決定される。図１１は、ノードｂが当該座標の位置に配置された状態を示す図である。
【００８９】
[ノードｅ、ノードｃ、ノードｄの位置決定]
次に、ツリー表示調整装置１は、ノードｂと同世代である第1世代ノードの中で、処理順が第2位と定められたノードであるノードｅを処理対象ノードとする。
【００９０】
ノードｅの位置決定を行うに先立ち、ツリー表示調整装置１はノードｅが葉ノードであるか否かを判定する。ノードｅは葉ノードではないので、ツリー表示調整装置１はノードｅの子ノード（第2世代ノード）であるノードｃ、ノードｄの位置決定を行う。ここで、ツリー表示調整装置１は兄弟ノード処理順決定処理により、ノードｃ、ノードｄの順に位置決定を行うものとする。
【００９１】
[ノードｃの位置決定]
ノードｃの位置決定を行うに先立ち、ツリー表示調整装置１はノードｃが葉ノードであるか否かを判定する。ノードｃは葉ノードであるので、ツリー表示調整装置１は、葉ノード位置決定処理によって、ノードｃの座標を第2世代ノードの基準位置である動径を半径方向距離ｒ×深さ（世代数）＝ｒ×２＝２ｒとし、偏角を角度０である座標に決定する。図１２は、ノードｃが葉ノード位置決定処理により決定された座標の位置に配置された状態を示す図である。
【００９２】
[ノードｄの位置決定]
次に、ツリー表示調整装置１は、ノードｃの次の順位であるノードｄを新たな処理対象ノードとする。ノードｄの位置決定を行うに先立ち、ツリー表示調整装置１はノードｄが葉ノードであるか否かを判定する。ノードｄは葉ノードであるので、ツリー表示調整装置１は、葉ノード位置決定処理によって、ノードｄの動径を基準半径方向距離ｒ×世代数＝２ｒとし、偏角をノードｃから回転方向距離ｌだけ離れた位置となる角度とする座標にノードｄを配置する。すなわち、ノードｄの座標（２ｒ、ｌ／２ｒ）となる。図１３は、ノードｄが極座標に配置された状態を示す。
【００９３】
[ノードｅの再配置位置の決定]
ノードｅの全ての子ノードの位置決定が完了すると、ツリー表示調整装置１は親ノード位置決定処理を実行して、ノードｅの位置決定を行う。まず、ツリー表示調整装置１は、ノードｅの座標の動径を基準半径方向距離ｒ×深さ（世代数）＝ｒ×１＝ｒとし、その偏角を子ノードの偏角の最大値と最小値の平均値とする。ここでは、子ノードの偏角の最大値はノードｄの「ｌ／２ｒ」であり、子ノードの角度の最小値はノードｃの「０」である。よって、これらの平均値は（ｌ／2ｒ＋０）／２＝ｌ／４ｒとなる。この処理段階では、ノードｅの位置は（ｒ、ｌ／４ｒ）と算出される。図１４は、ノードｅが上記極座標の位置に配置された状態を示す。
【００９４】
次にツリー表示調整装置１は、ノードeが同世代ノードで隣接するノードと基準回転方向距離ｌより離れているか否かを判定する。基準回転方向距離ｌより離れていると判定した場合、ツリー表示調整装置１は当該ノードの位置をそのままとする。一方、基準回転方向距離ｌより離れていないと判定した場合、同世代ノードで隣接するノードと基準回転方向距離ｌだけ離れるように、処理対象ノード以下のツリーを、原点を中心として回転移動させる。この例では、ノードｅは、同世代ノードで隣接するノードであるノードｂと基準回転方向距離ｌより離れていないので、ノードｅがノードｂから基準回転方向距離ｌだけ離れるように、ノードｅ以下の部分木ツリーを、原点を中心として回転移動させる。図１５に、ノードｅを、隣接する同世代ノードｂから基準回転方向距離ｌだけ離れるように、ノードｅ以下の部分木ツリー全体を、原点を中心とした回転移動させた状態を示す。この回転移動によってノードｅの座標は（ｒ、ｌ／ｒ）となり、ノードｂの座標は（２ｒ、３ｌ／４ｒ）となり、ノードｄの座標は（２ｒ、５ｌ／４ｒ）となる。
【００９５】
[ノードｉ、ノードｆ、ノードｇ，ノードｈの位置決定]
次に、ツリー表示調整装置１は、第1世代ノードの中の処理順が第３位と定められたノードであるノードｉの位置決定を行う。
【００９６】
ノードｉの位置決定を行うに先立ち、ツリー表示調整装置１はノードｉが葉ノードであるか否かを判定する。ノードｉは葉ノードではないため、ツリー表示調整装置１はノードiの子ノード（第2世代ノード）であるノードｆ、ノードｇ、ノードｈの位置決定を行う。ここで、ツリー表示調整装置１は「兄弟ノード処理順決定処理」により、ノードｆ、ノードｇ、ノードｈの順に処理順を決定したものとする。
【００９７】
[ノードｆの位置決定]
次に、ツリー表示調整装置１は、第1の順位であるノードｆの位置決定をする。ノードｆの位置決定を行うに先立ち、ツリー表示調整装置１はノードｆが葉ノードであるか否かを判定する。ノードｆは葉ノードであるため、ツリー表示調整装置１は、葉ノード位置決定処理により、座標の動径を基準半径方向距離ｒ×深さ（世代数）＝ｒ×２＝２ｒとし、座標の偏角を、同世代ノードのうち直近に配置されたノード（ここではノードｄ）から回転方向距離ｌだけ離れた位置となる角度とする座標の位置にノードｆを配置する。すなわち、ノードｆの座標は（２ｒ、７ｌ／４ｒ）となる。
【００９８】
[ノードｇの位置決定]
次に、ツリー表示調整装置１は、兄弟ノード中第２の順位であるノードｇの位置決定をする。ノードｇの位置決定を行うに先立ち、ツリー表示調整装置１はノードｇが葉ノードであるか否かを判定する。ノードｇは葉ノードであるため、ツリー表示調整装置１は、葉ノード位置決定処理により、座標の動径を基準半径方向距離ｒ×深さ（世代数）＝ｒ×２＝２ｒとし、座標の偏角を、同世代ノードのうち直近に配置されたノード（ここではノードｆ）から回転方向距離ｌだけ離れた位置となる角度とする座標の位置にノードｇを配置する。すなわち、ノードｇの座標は（２ｒ、９ｌ／４ｒ）となる。
【００９９】
[ノードｈの位置決定]
次に、ツリー表示調整装置１は、兄弟ノード中第３の順位であるノードｈの位置決定をする。ノードｈの位置決定を行うに先立ち、ツリー表示調整装置１はノードｈが葉ノードであるか否かを判定する。ノードｈは葉ノードであるため、ツリー表示調整装置１は、葉ノード位置決定処理により、座標の動径を基準半径方向距離ｒ×深さ（世代数）＝ｒ×２＝２ｒとし、座標の偏角を、同世代ノードのうち直近に配置されたノード（ここではノードｇ）から回転方向距離ｌだけ離れた位置となる角度とする座標の位置にノードｈを配置する。すなわち、ノードｈの座標は（２ｒ、１１ｌ／４ｒ）となる。
【０１００】
図１６にノードｆ、ノードｇ、ノードｈが極座標系に配置された状態を示す。
【０１０１】
[ノードｉの位置決定]
ノードｉの全ての子ノードの位置決定が完了すると、ツリー表示調整装置１はこれら子ノードの親ノードであるノードｉの位置決定を行う。まず、ツリー表示調整装置１は、ノードｉの座標の動径を基準半径方向距離ｒ×世代数（１）＝ｒとし、その偏角を子ノードの偏角の最大値と最小値の平均値とする。ここでは、子ノードの偏角の最大値はノードｈの「１１ｌ／４ｒ」であり、子ノードの角度の最小値はノードｆの「７ｌ／４ｒ」である。よって、これらの平均値は（１１ｌ／４ｒ＋７ｌ／４ｒ）／２＝９ｌ／４ｒとなる。よって、この処理段階では、ノードｉの座標は（ｒ、９ｌ／４ｒ）と算出される。図１７は、ノードｉが極座標に配置された状態を示す。
【０１０２】
[ノードｉの再配置位置の決定]
次に、ツリー表示調整装置１はノードｉが同世代ノードで隣接するノードと回転方向距離ｌより離れているか否かを判定する。基準回転方向距離ｌより離れていると判定した場合、ツリー表示調整装置１は当該ノードの位置をそのままとする。一方、基準回転方向距離ｌより離れていないと判定した場合、同世代ノードで隣接するノードと基準回転方向距離ｌだけ離れるように、対象ノード以下のツリーを、原点を中心とした回転移動させる。この例では、ノードｅは、同世代ノードで隣接するノードであるノードｅと基準回転方向距離ｌより離れているので、そのままノードｉの座標が決定される。
［ノードａの配置］
次に、ツリー表示調整装置１は原点に部分木ルートノードであるノードａを配置する。なお、部分木ルートノードはいつ行ってもかまわない。後述する回転移動の終了後であってもかまわない。
【０１０３】
[ツリー整列方向への回転移動]
次に、ツリー表示調整装置１は対象部分木のツリー方向を、ツリー整列方向θに一致させるよう対象部分木のツリー方向を回転移動させる。
【０１０４】
まず、ツリー表示調整装置１は対象部分木のツリー方向を算出する。
対象部分木のツリー方向は、全ての第１世代ノードの偏角の最大値と最小値の平均値である。ここでは、第１世代ノードの偏角の最大値はノードｉの「９ｌ／４ｒ」であり、第１世代ノードの角度の最小値はノードｂの「０」である。よって、これらの平均値は（９ｌ／４ｒ＋０）／２＝９ｌ／４ｒとなり、ツリー方向θ’は＝９ｌ／４ｒと算出される。
【０１０５】
次に、ツリー表示調整装置１はそのツリー方向θ’をツリー整列方向θに一致するように、原点を中心として対象部分木ツリー全体を回転移動させる。図１８はツリー方向θ’とツリー整列方向θを示した図、図１９は、ツリー方向θ’をツリー整列方向下θに一致するように対象部分木全体を、原点を中心として回転移動させた状態を示す図である。
【０１０６】
ツリー方向とツリー整列方向が一致するように、対象部分木を回転移動させると、ノード位置決定処理は完了する。
[画面例]
【０１０７】
ツリー表示調整装置１の画面表示例を示す。図２０はユーザがツリー表示を調整したい部分木の部分木ルートノード２００にポインティングデバイスのポインタ２１０を置いた状態の画面例である。
【０１０８】
図２１は、図２０の状態の後に、ポインタ２１０がドラッグされた状態の画面例である。ポインタ２１０の移動に応じて部分木ルートノード２００以下のノードは、親子ノード間の距離である半径方向距離が基準半径方向距離ｒとなり、兄弟ノード間の回転方向距離が基準回転方向距離ｌ以上になり、ツリー方向がツリー整列方向に一致するように回転移動されている。
【０１０９】
図２２は、図２１の状態の後にポインタ２１０がさらに部分木ルートノード２００から離れた位置までドラッグされた状態の画面例である。親子ノード間の距離である半径方向距離がより長くなり、ツリー方向は現在のポインタの位置に従って新たなツリー整列方向に一致するように回転移動されている。
【０１１０】
このように本ツリー表示調整装置によれば、インタラクティブにツリー表示の調整を行うことが可能となる。
【０１１１】
[まとめ]
本実施の形態によれば、ノードを個別に移動させる必要がなくなるため、整列を行うのにかかる時間を短縮することが出来る。
また、本実施の形態によれば、インタラクティブに結果を確認しながらノードの整列が行われるため、ユーザが所望する配置にすることが容易となる。
【０１１２】
エッジの長さ（親子ノード間の距離）が変わると、連動してツリーの広がり具合が変化するため、直感的に整列を行える。
ドラッグアンドドロップにより、個別にノードを移動させることによって、整列の順序を容易に変更できる。
【０１１３】
以上、本発明の実施の形態を説明したが、本発明はこれらに限定されるものではなく、発明の趣旨を逸脱しない範囲内において、種々の変更、追加、組み合わせ等が可能である。
【符号の説明】
【０１１４】
１・・・ツリー表示調整装置； ３０・・・ノード位置決定部； ３１・・・動的パラメータ決定部； ３３・・・葉ノード位置決定部； ３４・・・親ノード位置決定部； ３５・・・ツリー方向変更部
【特許請求の範囲】
【請求項１】
ユーザの入力に応じて決定される値である第１の値及び第２の値を決定する第１の決定手段と、
対象となる部分木における親子ノード間の距離である半径方向距離が第１の値となるようにするとともに、兄弟ノード間の回転方向距離が所定の値以上になるように各ノードの位置決定を行う第２の決定手段と、
前記第２の値に応じて前記対象となる部分木を回転移動させる回転移動手段と
を有するツリー表示調整装置。
【請求項２】
前記第２の決定手段は、第１の値の変化にリアルタイムに応じて各ノードの位置決定を行い、
前記回転移動手段は第２の値の変化にリアルタイムに応じて前記部分木を回転移動させる
ことを特徴とする請求項１に記載のツリー表示調整装置。
【請求項１】
ユーザの入力に応じて決定される値である第１の値及び第２の値を決定する第１の決定手段と、
対象となる部分木における親子ノード間の距離である半径方向距離が第１の値となるようにするとともに、兄弟ノード間の回転方向距離が所定の値以上になるように各ノードの位置決定を行う第２の決定手段と、
前記第２の値に応じて前記対象となる部分木を回転移動させる回転移動手段と
を有するツリー表示調整装置。
【請求項２】
前記第２の決定手段は、第１の値の変化にリアルタイムに応じて各ノードの位置決定を行い、
前記回転移動手段は第２の値の変化にリアルタイムに応じて前記部分木を回転移動させる
ことを特徴とする請求項１に記載のツリー表示調整装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【公開番号】特開２０１３−９７５０８（Ｐ２０１３−９７５０８Ａ）
【公開日】平成２５年５月２０日（２０１３．５．２０）
【国際特許分類】
【出願番号】特願２０１１−２３８５９０（Ｐ２０１１−２３８５９０）
【出願日】平成２３年１０月３１日（２０１１．１０．３１）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２５年５月２０日（２０１３．５．２０）
【国際特許分類】
【出願日】平成２３年１０月３１日（２０１１．１０．３１）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]