memo/20080228

グラフモデルを表示するアプレット

blog での頻出キーワードをグラフモデルで表示するアプレットがあります。

最新版はFlashで書き直したようですが、
見た瞬間に「JDKのサンプルコードが元ネタだな」とわかります。
私も過去に同じ元ネタを使って

人間模様グラフ (人間関係グラフ)

とかやってました。
他にも派生バージョンっていうか、ページナビゲーションのアプレットも過去に作りましたよ。

やってみるとわかるのですが、この「力学モデルによる漸次的な配置計算」は、割とアホなんですよね。

その点、AT&T 謹製の graphviz についてる dot コマンドは、とっても賢いし高速です。どうやってるんでしょうね。

リンク	備考
www.graphviz.org	doxygenの推奨ツールでもあります

と、そんな風に考えていた時期が俺にもありましたが、ふとこんな記事を発見。

リンク	備考
力学モデルを用いたグラフデータの視覚化手法の改良

いわく、この配置戦略は

• 対話的といえるほど高速ではない。
• 配置結果が初期配置に大きく依存する。
• ノードとアークの交差（条件3参照）を高速に回避する手法が無い。

とのこと。そうなんですよね。

それで、記事では改良手法にも言及されてますが

• 改良１ すべてのノードを初期段階から配置するのではなく、１個ずつインクリメンタルに配置するアルゴリズム。

これはすぐできそうですが

• 改良２ アークの曲線化によって、ノードとアークの重なりを避けるアルゴリズム。

これは一気に難しくなりますなぁ。そういや dot も曲線だ。

ともあれ、グラフモデルを視覚化することを考えるのは結構、脳をシゲキします。
MSがWindowsエクスプローラでアイコン同士を線で結べるようにするのは、いつのことでしょうね。

ところで

某ソフトに絡んで、ネットワーク管理のアプリを開発してはいけない身なのですが、はて、いつまでだっけ？
離れてから７年間禁止だったと記憶してますが...確認しておこう。