AlgoViz にビジュアライザを27個追加しました
Brainfuck だけだった AlgoViz に、グラフ・木・配列・データ構造・オートマトンのビジュアライザを27個追加しました。設計方針と、作りながら考えたことをまとめます。
AlgoViz にビジュアライザを27個追加しました
こんにちは、なすです。
2月に Brainfuck ビジュアライザを公開した AlgoViz に、ビジュアライザを27個追加しました。
追加したビジュアライザ
1ページ1アルゴリズムで、Brainfuck と合わせて28ページになりました。
グラフ
- 幅優先探索 (BFS) / 深さ優先探索 (DFS) / ダイクストラ法 / プリム法 / クラスカル法
木
- 二分探索木 / AVL 木 / B木 / ヒープ の構築
- ヒープソート
- trie (接頭辞木) / ハフマン木 の構築
配列
- ソート：バブル / 選択 / 挿入 / シェーカー / クイック / マージ / バケット / 基数
- 探索：線形探索 / 二分探索
データ構造
- スタック / キュー / デック / Union-Find
オートマトン
- 決定性有限オートマトン (DFA)
ほかに、ダークモードへの対応や、スマホでのピンチ操作による拡大・縮小もできるようになっています。
更新の経緯
時系列にするとこうなります。
| 時期 | やったこと |
|---|---|
| 2月下旬 | グラフを描く仕組みを作る。未完成だったので公開ページからは隠していた |
| 4月 | ダークモードに対応 |
| 5月 | Brainfuck のセルの値を mod 128 / 256 で切り替えられるようにし、EOF を 0 から -1 に変更 |
| 8月末 | テストの仕組みを整え、BFS / DFS / ダイクストラ法を公開 |
| 9月 | 木・配列・データ構造・DFA を追加 |
設計方針
AlgoViz が保証するのは「1手ずつ見せること」だけ
ビジュアライザが増えるにつれ、どこまでを AlgoViz でやるかの線引きが必要になりました。結論として、AlgoViz が保証するのは「アルゴリズムが動く様子を1手ずつ見せること」だけにしています。
アルゴリズムの解説、用語の定義、計算量の解説、実装のバリエーションの比較は、技術ブログや教科書、Wikipedia がすでに担っています。そこまで持ち込むと実装が膨らんで、本来見るべき点を見落とします。
なので、ページに置くのは次の2つだけです。
- そのページの操作方法と、画面に出ている色や数字が何を指すか（ヘルプと凡例）
- そのアルゴリズム固有の、動きを見ないと分からないこと（「取り出した瞬間に確定する」「隣接を見終わると外れる＝バックトラック」のようなもの）
メニューにあった「始点から近い順に広がる」のような説明文も消しました。何を選ぶかは名前で分かるし、意味は外部の資料が説明しているからです。
この線引きは文章だけでなく、UI の要素、設定項目、表示のどれにも当てています。迷ったときは「これは AlgoViz が保証すべき体験の範囲内か、外部が担う領域か」を先に問うようにしています。
1ページ1アルゴリズム
ダイクストラ法を足したタイミングで、グラフ探索のページを1ページ1アルゴリズムに分けました。「このページは DFS を見せるためだけのもの」と決まっている方が、作る側も見る側も迷いません。モードを切り替えるプルダウンは置いていません。
論理は C++、見た目は JS
アルゴリズムの論理はすべて C++ で書き、WebAssembly にコンパイルしています。JavaScript 側は「画面のどこに何色の丸を描き、どう線を繋ぐか」という視覚データだけを受け取って、PixiJS で描くことに専念します。JS 側は、それが BFS なのかオートマトンなのかを知りません。
どちらに置くか迷ったときは、「別の描画方法に差し替えても必要か」で決めます。必要なら C++ 側です。
C++ 側は、prepare() と step() の役割分担が要になっています。
prepare()… 配置の収束計算。描画ループが毎フレーム呼ぶstep()… アルゴリズムの1手。再生コントロールが呼ぶ
配置のアルゴリズムは ILayout として差し替えられるようにしていて、今は3種類あります。
- 一般のグラフ： 古典的 MDS で初期位置を決め、Stress Majorization で整え、連結成分ごとの凸包でパッキングする
- 木： Reingold-Tilford で上から下へ描く
- 配列： 番号順に左から一列に並べる（段にも分けられる）
変更の詳細
ソートから速さの工夫を外した
バブルソートやシェーカーソートには、入れ替えが起きなくなった時点で走査を打ち切る工夫がよくあります。速くはなるのですが、これを入れると「隣どうしを何度も比べて少しずつ運ぶ」という仕組みそのものが見えにくくなります。
AlgoViz は速さを競う場所ではないので、外しました。既に並んでいる入力でも最後まで走査するので、手数が入力によらないことも見えるようになります。選択ソートでも、最小の値が既に先頭にあるときに入れ替えを飛ばすのをやめました。そこだけ飛ばすと、1周の形が揃わないからです。
一方で Union-Find は、経路圧縮と union by size をチェックボックスで外せるようにして、工夫がある場合と無い場合を見比べられるようにしています。
円形配置の判定を密度に変えた
完全グラフに近い密なグラフは、力学モデルで配置すると塊になって読めないので、円形に並べています。どのグラフを円形にするかは、最初は平均次数で判定していました。ところがこれだと、頂点数が増えるほど疎なグラフまで円形に落ちてしまいます。
実際に見比べたところ、力学モデルが円形に負けるのは完全に近いときだけでした。
| グラフ | 密度 | 配置 |
|---|---|---|
| 星 / 木 / 格子 / 車輪 | 0.06〜0.20 | 力学（格子は交差ゼロで描ける） |
| かたまりが3つ | 0.31 | 力学（3つの塊を分けて描く） |
| ランダム（平均次数8） | 0.35 | 力学 |
| 完全に近い / 完全グラフ | 0.85〜1.0 | 円形（多角形として読める） |
そこで、密度そのもので判定するようにしました。
Brainfuck の「一気に実行」の修正
既存の Brainfuck ビジュアライザにも手を入れています。
「一気に実行」は、+[] のような停止しないプログラムを渡すと永久に返ってこず、WASM がメインスレッドを占有してタブごと復帰できなくなっていました。EOF を -1 にしたので、,[.,] のような入力をそのまま出力するプログラムも止まらなくなります。
今は5000万ステップで打ち切り、打ち切ったことをバナーで知らせるようにしています。
あわせて、step() と runToEnd() に重複していた70行ほどの実行ロジックを1つにまとめ、一気に実行したあとのステップバックで見た目が変わらなかったバグも直しました。
やっていないこと
ハフマン木（文字を数える）、trie（1文字ずつ降りる）、DFA（遷移記号）の3つは char 単位で処理しているので、UTF-8 で複数バイトになる文字（日本語など）は正しく扱えません。マルチバイト文字にはそのうち対応する予定です。
おわりに
「VisuAlgo の完全日本語版＋α」という目標に向けて、これからもビジュアライザを追加していく予定です。
最後まで読んでくださりありがとうございました。