Tulip――巨大なノード数に対応したグラフ作成ツール

  Tulip は巨大なグラフを作成し、様々な視覚効果や操作を加えた上で、その結果をエクスポートすることを想定して作られたフレームワークである。TulipはGraphvizパッケージで作成されたグラフをインポートできると同時に、各種のビットマップ画像およびSVGやEPSフォーマットにてエクスポートすることも可能であり、PDFファイルでの使用も視野に入れた作業で利用することができる。

 Tulipパッケージの入手先としては、Ubuntu HardyおよびopenSUSE用の1-Click Installが利用可能である。Fedoraの標準リポジトリにTulipをパッケージ化したものは用意されていないが、TulipのダウンロードページにアクセスすればバイナリRPMが取得できる。本稿で使用したものの場合は、バージョン3.0.0をソースコードからFedora 8の64ビットマシンにインストールしている。

 ソースからのビルドを行う場合は、OpenGL Extension Wrangler Libraryの開発パッケージをインストールしておかなくてはならない。その他にも私の環境では、下記の実行例のように64ビットQt4ライブラリのパスを明示的に指定しておく必要があった。

$ sudo yum install glew-devel
$ ./configure --with-qt-libraries=/usr/lib64
$ make
$ sudo make install

 TulipはOpenGLを使用する関係上、仮想マシン上にて仮想的なX Windowセッション内部での実行を試みると、そのパフォーマンスは大幅に低下してしまう。それとは対照的にNvidia GeForce 7900グラフィックスカードおよびIntel Q6600クアドコアCPUを搭載したFedora 8マシンで直接実行させた場合のパフォーマンスは非常に良好であった。

 私が最初に仮想化テクノロジを用いずにTulipを実行させた際に遭遇したのが、グラフの再描画によってウィンドウが白一色で塗りつぶされて、描画したはずのグラフが見えなくなるという不具合である。ただしこの問題についてはメニューからView → Redraw Viewを選択するか、Control-Shift-Rのショートカットをキーボードから実行することで、グラフは再び見えるようになる。そしてNvidia製のクローズソース系ドライバを使用する環境でTulipを実行する場合は__GL_FSAA_MODE変数を設定してはいけない。当初私はこの値を2としていたのだが、この設定を解除したところTulipの再描画は正常に行われるようになってくれた。

tulip_thumb.png
Tulip

 メニューの下に表示されるツールバーの右側には、マウス操作でグラフを描画するためのアイコン群が配置されている。そのうち赤い立方体のアイコンが新規グラフノードの作成用、その右隣がグラフノードの連結用ボタンである。同じくこれらの左側に配置されているのはノードの削除、ズーム、選択、移動を行うためのボタンである。またノードの移動だけでなくサイズ変更や回転も行いたい場合は、このツールバーにある移動モードオプションを選択しておけばいい。これら2つの操作に関しては、選択ノードのバウンディングボックスに表示される特殊なハンドルを介して行うようになっている。

 画面左上側にはグラフの全体像が確認できる縮小表示用の領域が設けられており、また現在のグラフビューウィンドウに描かれているのがグラフ全体におけるどの位置に当たるのかを示すボックスも表示されるようになっている。こうしたグラフビューの拡大と縮小は、マウスホイールにて操作することができる。なお拡大/縮小の操作は画面の中心ではなく、グラフ上のマウスポインタの現在位置を基準にして実行される。こうした説明を聞かされると、自分が注目するノードを中心とした拡大/縮小を連続的に実行するにはホイールの回転と同時にマウスポインタの位置を合わせ続ける必要があると考えるかもしれないが、よほど極端に拡大させない限りそうした補正はインタフェース側が自動で行ってくれるので、このようなマウスの同時操作をユーザが強要されることはない。

 Tulipというプログラムで最も注目すべき機能はAlgorithmメニューであろう。このAlgorithmsメニューに置かれたアイテムは、Selection、Color、Measure、Layout、Size、Generalという分類がされている。特にLayoutサブメニューは、グラフ理論にそれほど詳しくない人間が重宝するはずだ。私の場合は、特定タイプのグラフについては有効に機能しないと事前に知らされていたレイアウトアルゴリズムを実地に試して、何が原因でそのアルゴリズムは適さないのかを再確認したことがある。

 Algorithmsメニューに用意されている機能の中には、グラフ理論に関する知識を有していないと使いこなせないものも含まれている。例えばStrahler水流次数という理論を知らない人間がMeasure → Graph → Strahlerというコマンドを使用しても基本的に意味をなさないであろう。ちなみに100ページに渡ってTulipの操作法を解説したユーザマニュアルには、これらのアルゴリズムについて解説した資料に関する参照情報も各種掲載されている。

 今回私はTulipによる巨大グラフのインポート機能を検証する目的で、300万個のノードで構成された平面グラフを読み込ませてみた。その結果、読み込み処理が完了するまでには1分以上を要し、Tulipプロセスだけで591MBもの常駐メモリを消費する状態になったのである。このように巨大なグラフを扱う場合は、ユーザによる誤操作が重大な影響をもたらす危険性に注意しなければならない。例えば300万ノードのグラフに対してPlanar/Mixed Modelグラフレイアウトを実行させてみたところ、割り当てられていた最大3.3GBの仮想メモリをプロセスが使い尽くした果てに、途中で処理が止まってしまったことがある。なおこの試験を行ったのは、プロセスの誤判断による過剰なメモリ割り当てを防止する目的で私自身が明示的に「ulimit -S -v 3300000」による仮想メモリサイズの上限指定を施した環境であった。

 私が試した限りにおいて“Import graph from Website”機能によるインポート結果は、シングルノードグラフに変換されるか、std::out_of_range例外の発生によりプログラムが中断されるかのいずれかであった。私としてはTulipの具体的な用途としてサイトの構造マップの生成を想定していただけに、この結果にははなはだ失望させられた次第である。

 Tulipのホームページはポップアップ形式の広告が表示されるようになっているが、こうした広告の存在は、これからTulipを使用しようとする潜在的ユーザの一部の意欲をそぐ結果になっているかもしれない。オープンソース系プロジェクトにとってこうした広告掲載による収入は魅力的なのかもしれないが、Tulipのホームページで採用されているタイプのポップアップ広告をどの程度受け入れるべきかのバランスは、さじ加減の難しい問題である。

 グラフのレイアウトを整えた上でビットマップないしベクタフォーマットへの変換処理を必要としている人間にとって、Tulipは最適なツールとして機能してくれるはずだ。Tulipを利用すればこうした変換用のコードを自力で記述する必要がないだけではなく、どうすれば自分のグラフを最も理解しやすい形態に整えられるかについても、事前に用意された各種のレイアウトを必要なだけ試すことができるのだ。またTulipへのグラフ読み込みに関しては、GraphvizのドットファイルおよびGMLフォーマットに対応したインポート機能が有用なオプションとなる場合があるだろう。いずれにせよ巨大なグラフを操作できるTulipの存在を知っておいて損はないはずだ。

Ben Martinは10年以上にわたってファイルシステムに取り組んでおり、博士課程の修了後、現在はlibferris、ファイルシステム、検索ソリューションを中心としたコンサルティング業に従事している。

Linux.com 原文