研究上の成果としては、アニメーション表示を前提としたグラフ描画アルゴリ ズムの改良とその評価、ソフトウェアの成果として、klicの実行可視化システ ム「viewPP」が挙げられる。以下、これらについて述べる。
研究上の成果
昨年度と今年度で、「アニメーション表示を前提としたグラフ自動描画アルゴ リズムの改良と評価」について研究を行った。
並列論理型言語を可視化するにあたっては、節やアトムといったものをグラフ の節、論理変数をグラフの辺として表現することができる。つまり、プログラ ムを画面上にグラフとして表すことができることになる。
また、プログラムの実行やユーザによるプログラムおよびデータの変更に伴っ てグラフの形状が動的に変化するため、それに対応できる「グラフ自動描画ア ルゴリズム」が必要になってくる。
グラフ自動描画アルゴリズムには様々な種類が存在するが、節や辺の配置の自 由度などを考慮して、「力指向アルゴリズム」をベースとすることにした。こ れは、各節の間に引力や斥力を定義して、それらによる力の釣り合いを計算す ることによって節や辺の配置を行うアルゴリズムであり、各節を少しずつ動か して目的の位置にもっていくという方式であるためにアニメーション化がしや すい。
力指向グラフ描画アルゴリズムのビジュアルプログラミングシステム向けの改 良としては、他にも中野の改良[2]がある が、これは Kamada-Kawai のアルゴリズム[3]を改良したものであり、計算量の点から不 利である。そこで、本研究では力指向アルゴリズムの中ではシンプルなもので ある「Eadesのアルゴリズム」[4]を基本に することにした。
これは、辺により直接接続された節の間に引力、そうでない節の間に斥力を定 義し、その力のつりあいを求めることによりグラフを再配置するものである。 節同士に働く引力・斥力は, dをノード間の実際の距離、d 0をノード間理想距離(ばね の自然長)としたときの引力をf s、斥力を f r、それぞれのバランスをとるために乗ず る係数をC s , C rと表わすと、
f s(d)＝C s log
f r(d)＝C r
のように定義される。
この式から、直接接続されていない節同士に働く斥力は、その節の間の距離に 反比例するが、これは、再配置のための計算の過程をそのまま見せることによっ てアニメーションさせようとしたときに、「節が密集している部分の動きが不 連続・不自然なものになる」という問題を引き起こす。そのことから、斥力を 計算する関数を変更することによって、よりアニメーションに向いた形に Eades のアルゴリズムを改良することにした。
具体的には、斥力を計算する関数を以下の通りに変更した。
f r(d)＝
この変更により、節同士が密集しているときの不自然な動きを抑えることがで きた[5]。
実際の効果を調べるため、いろいろなグラフについて、初期配置を円周上とし たときの円の半径を変化させたときの各節の移動ピクセル数を調べることにし た。その実験の結果を図-1に示す。
ここで挙げた他のグラフについても、おおむねこのように初期配置の半径が小 さいときの節の移動量が少なくなっており、改良の効果が認められた[6]。
なお、斥力計算関数において、場合分けをしなくても良いように、
f(d)＝ 
のような形の関数を元にした斥力計算関数についても実
験を行ったが、d が大きくなったときの 0 への収束が速すぎ、Eades
のアルゴリズムの改良に組みこむのは困難であった。
本研究についての外部発表論文は以下の通りである。
昨年度は、Tcl/Tk と klic のインタフェースとなるプログラムである「 klitcl」を開発した。本年度は、それを用いて並列論理型言語の実行を視 覚化するシステムである viewPPを開発した。
可視化や操作系は Tcl/Tk を使い、単一化可能性の判断や実行されるべき述語 の選択(ガード部の処理)などにklic を使い、それらの間のインタフェースを klitcl で取るという構成になっている。
Tcl/Tk 側のルーチンから必要に応じて画面上のグラフ構造を解析し、それを klic で書かれたルーチンに送ってそちらで単一化可能性などを調べ、結果を Tcl/Tk 側に戻す。その結果を元に、画面上のグラフ構造を変化させていくこ とにより、実行の過程を可視化する。また、定義節の内容は klic側のルーチ ンに、klicのサブセットのような型の文法を持った言語で与え、実行される節 の選択(ガード部の処理)等に利用する。
viewPPの実行の様子を図-2に示す。 述語は大きな円で、アトムなどは小さな円で表現され、それらを結ぶ線が論理 変数やリスト構造を表現している。
画面上にグラフ構造の形でプログラムを作成し、そのグラフの変形によってプ ログラムの実行が表現される。グラフの変形をスムースなアニメーション的表 示とすることによって、プログラム実行過程のわかりやすさの向上を図った。
辺や節の画面上の配置に、前述の改良版Eadesアルゴリズムを用いている。 Eadesのアルゴリズムをベースとしているため、節や辺の位置についての自由 度が高く、ユーザが好きな位置にプログラムの各要素を配置することができる。
これにより、並列論理型言語の実行をわかりやすい形で見ることができるよう になる。
図形を用いてプログラムを表現する際に必ずと言っていいほど問題となるのが スケーラビリティについてであるが、これについては色々な研究がなされてい るし、我々の研究室でも成果があるので、充分解決可能な問題であると考えて いる。
viewPPのプログラムサイズは、Tcl/Tkパートが約2500ステップ、klic パートが約1000ステップ程度であり、LaTeXで書かれた日本語マニュアルと plane text の簡易マニュアルが添付される。
残された課題
まず「グラフ描画アルゴリズム」に関しては、力指向アルゴリズムでグラフを 配置した際に起こりがちな現象である「ねじれの現象」と、ユーザの想像と全 く違う形(バランスなどは取れているが、論理的な継がりが分りにくくなって しまうような形)に再配置されてしまう現象を解消するように、さらにアルゴ リズムを改良していく必要がある。
「ビジュアルプログラミングシステムの制作」については、今回は特に「実行 の視覚化」部分を重点的に実装したため、今後は入力やデバッグについての実 装に入る。
評価
ビジュアルプログラミングシステムのための要素技術としてのグラフ描画アル ゴリズムの研究を進めると共に、並列論理型言語を可視化するシステムの制作 を行った。
グラフ描画アルゴリズムについては、グラフ構造をユーザに提示するようなあ らゆるシステムについて応用が可能であり、データ構造のわかりやすい表示の ための研究として極めて重要であると考えられる。
ビジュアルプログラミングシステム viewPPの作成については、プロ グラムの実行の可視化については実装が完了した。今後は入力システムやデバッ グシステムの統合などを行っていく必要がある。
