自分で作れるなら、Graphvizは必要ない？

209日前原文(spidermonkey.dev)

概要

SpiderMonkeyのIonコンパイラ用に 新しい可視化ツール を開発
インタラクティブなグラフ で最適化プロセスを詳細に観察可能
Graphviz等の従来ツールの 課題を解消
独自のレイアウトアルゴリズムを 1000行未満で実装
本記事では アルゴリズムの設計思想と全体像 を解説

SpiderMonkey Ionコンパイラの可視化ツール刷新

SpiderMonkeyの最適化コンパイラ Ion の処理を インタラクティブなグラフ で可視化
JavaScriptのテストコードを記述し、 即座にグラフ生成・操作 が可能
グラフ上で クリック＆ドラッグで移動、Ctrl+スクロールでズーム 操作
スライダーで最適化過程を段階的に表示、ブロックや命令の追跡も容易
グラフレイアウトの安定性 を重視、ブロックサイズや構造変化にも強い設計

従来ツールの課題と独自アプローチ

以前は iongraph（Python+Graphviz） でPDF出力、視認性や操作性に問題
Graphvizは ノード配置が直感的でなく、安定性に欠ける
- 例：return文がループ本体より上に表示されるなど、 ソース構造と乖離
- 小さな変更で グラフ全体が大きく変化、比較や追跡が困難
制御フローグラフ（CFG） 特有の制約（ループ構造、単一エントリ等）を活用可能
静的PDFでは探索が困難、インタラクティブな操作性が求められる
GraphvizやMermaidの代替として 独自レイアウトアルゴリズムを開発

レイアウトアルゴリズム設計思想

Sugiyamaレイアウトアルゴリズム（階層的グラフ描画）を SpiderMonkey用に最適化
CFGの特性を活かし、 以下の簡略化・工夫を導入
- ループのバックエッジは明示的に扱い、 サイクル処理を単純化
- レイヤー分けで ループ後のブロックを下方に配置、可読性向上
- エッジ交差最小化よりも安定性を優先、分岐順序の一貫性を保持
- ループ構造は ツリー状に整理、ネスト関係を明確化
1000行未満のJavaScript実装、効率的かつ高品質な出力を実現

iongraphレイアウトアルゴリズムの流れ

ステップ1：レイヤー分け
- 各基本ブロックを 「レイヤー（水平トラック）」 に分類
- ループの高さ（レイヤー数）を追跡、 ループ内外の位置関係を調整
- ループ外へのエッジは ループ内容処理後にレイヤー付与
- 実装例（擬似コード）：
  - layerBlock(block, layer = 0)で再帰的にレイヤー割当
  - ループヘッダや親ループの高さも同時に更新
  - ループ外エッジは一時保留、ループ処理後に再帰
ステップ2：ダミーノード生成
- エッジが複数レイヤーを跨ぐ場合、 ダミーノードを挿入
- 下向きダミーは左、上向きダミーは右に配置し、 一貫した流れ を実現
- 同一宛先へのエッジは ダミーノードを統合 し、視覚的ノイズを低減
ステップ3：エッジの直線化
- ノード配置を調整し、 エッジをできるだけ直線的に配置
- ループヘッダ右側へのインデント、親子間の整列を複数パスで実施
- 重複ノード発生時は右方向にずらすなど、 重なりを自動回避
- ダミーノードも 直線化処理に完全参加、複雑なループも整理
- 上下方向の「コーミング」処理で 揺れの少ないグラフ を実現

まとめと今後

独自アルゴリズムにより、 安定・高品質なグラフ可視化 を実現
インタラクティブな操作性 で、最適化過程の理解・デバッグが容易
SpiderMonkey固有の制御フロー特性 を最大限に活用した設計
今後も デモや実装詳細 の公開を予定、さらなる改善を継続

Hackerたちの意見

これは、一般的なアルゴリズムを特定のサブスペースに特化させることで、はるかに良い結果が得られるという素晴らしい例だね。私の経験上、こういうことはよくあるんだけど、問題空間特有の特性を活用することをあまり気にせず、便利だからって一般的なアルゴリズムをそのまま使っちゃうことが多いんだよね（それでも十分なことが多いし）。

これは、Microdiagram（microdiagram.com）のプロトタイプで取り組んでいるコンセプトなんだ。つまり、汎用の図やグラフのレイアウトを作るのはめちゃくちゃ難しいけど、ほとんどの図やチャートはもっとシンプルなルールに従っているから、1種類の図に対してN言語を持つ方が、N種類の図に対して1言語を持つよりもずっと簡単なんだよね。

└

面白そうだね！今までにデザインしたチャートとその言語の例は何かある？

いい仕事だね！例のやつ、Graphvizの出力よりも見栄えがいいよ。特定の狭いユースケースに特化することで、長年開発された一般的なツールを常に上回ることができる良い例だね。

この分野で作業している人は誰でも+1だね！私はしばらくの間、ダイアグラムツールのコードに苦労してきたけど、[mermaidやgraphviz]、可読性と美しさが必要なときはいつもfigjamに戻っちゃう。graph-vizは巨大で、バイナリなんだよね。mermaidはブラウザのSVGレンダリングシステムが必要だし。説明から簡単にダイアグラムを作れるものが欲しいな…。

└

https://basisrobotics.tech/2024/11/24/basis-robot-02-softwar... でmermaidを使ったけど（自動生成）、結構うまくいったよ。ただ、ループを扱おうとはしてなかったけどね。mermaidからpngにレンダリングするツールもあるはずだし。それに、svg/html出力は大きな利点だと思ってる。スタイルを変えられるし、コピーもできるからね。

└

D2もチェックしてみるといいよ。最近HNのフロントページに載ってたから。https://news.ycombinator.com/item?id=45707539

└

これらのツールの問題は、ノードの数が一定以上になると、どんな図も読めなくなっちゃうことだよね。だから、こういうシナリオに内在する妥協に対して、もっとコントロールが必要なんだ。著者が取ったアプローチは、その方向に向けたとても良いステップだと思うし、他の人たちも続いてくれるといいな。

└

ELKを使ってTerraformの図を生成するのはうまくいったよ。いくつかのサンプルはここで見られるよ。

これがもっと汎用的な制御フローチャートビューワーに進化するのを見てみたいな。ほぼどんな言語の実装でも、素晴らしいデバッグツールになると思う。もうほとんどそこまで来てるんじゃないかな。

└

このツールは「汎用」アルゴリズムを特化させることで動いてるんだけど、それで汎用性は下がったけど、シンプルで効率的になったんだよね… で、今はもっと汎用的にしてほしいってリクエストが出てる。（これはジョークだよ！そのジョークは、実は二つの異なる汎用性があるってことなんだけどね。）

これは素晴らしい記事だね。D2のTALAレイアウトエンジンの魔法のソースに、これらのテクニックが使われているのか気になるな。あれは独自のレベルにあると思う。

もっと正確に言うと、比較対象はGraphvizじゃなくてdot(1)なんだ。Graphvizは可視化フレームワークで、いろんなレイアウトエンジンがあって、異なるアルゴリズムを実装してるんだよね：dot、neato、fdp、sfdp、circo、twopi、… この新しいカスタムアルゴリズムがGraphvizに貢献されるといいな。

└

ちょっと混乱するね。どうやら、dotはGraphvizの構文の言語名でもあり、レイアウトエンジンの一つでもあるみたい。大文字小文字の違いがあるかもしれないけど。

└

そうだね、それはいいね。IongraphはMPLで、graphvizはEPLだけど、Iongraphは結局JavaScriptだから、Cに翻訳するにはClaudeを使わなきゃね。

これは素晴らしい記事で、著者に感謝！ただ、graphvizのdotは純粋に杉山方式ではないってことを一言。実際の実装について詳しく書かれた論文がサイトにあるよ。それに、最後の二つの画像（同じ大きなグラフのdotとiongraphの比較）を見ても、dotは面積を最小化するように最適化されてるのが明らかで、iongraphはそうじゃないんだ。これがトレードオフだね。著者は一方が他方よりもナビゲートしやすいと言ってるけど、それは議論の余地があると思う。結局、大きなグラフを可視化するのは実際にはあまり役に立たないことが多いと思った。確かに、いくつかの明確なグラフは見た目が良いけど、実際には明確なグラフを見かけることは少なかったな。人それぞれだけど、同意する人もいるかもね？

└

大きなグラフを見てもあまり得るものがないっていうのには同意する。たいてい、興味のある問題は小さいものに還元できるし。でも、Graphvizは小さなグラフでもすごく見栄えが悪いんだよね。ここがiongraphの良さが光るところ。はっきり言うと、後者のグラフが読みやすい理由は、配線が追いやすいからだと思う。主観的な意見だけど、自分の経験に基づいてるよ。長期的には、こういう場合に役立つインタラクティブな機能をもっと追加できると思う。例えば、検索機能や関係ない配線を薄くする機能とかね。

レイアウトって、人間がすごく簡単に直感的にやることなのに、簡単なアルゴリズムを書くのは難しいよね。ジェネAIを使って人間のような結果を得る可能性があるのかな。こういうアプローチの実現可能性や複雑さについて、誰か意見ある？

いいね、でもその一般的な見出しは好きじゃないな。Graphvizは俺を含めて多くの人に長年役立ってきたし、これからもそうだと思うよ。

ハクソク