- Donald Knuthは2024年のStanfordクリスマス講演で有向グラフの strong components と weak components を扱い、Tarjanの strong components アルゴリズムを最も愛するアルゴリズムとして挙げた
- strong componentを1つの頂点に縮約すると サイクルのないDAG となり、アルゴリズムは sink strong component を見つけて取り除く流れで動作する
- ここでいう weak component は向きを無視した連結成分ではなく、strong components を再びまとめて linear order になるようにする、より一般的な partition である
- TarjanアルゴリズムはDFS中に tree arc、back arc、loop、forward arc、cross arc を区別し、strong components とその トポロジカルソート を同時に得る
- Knuthが強調した魅力は手順そのものだけでなく、必要な判定情報が正確な瞬間にアクセス可能になるよう配置された 深いデータ構造 にある
講演の出発点とKnuthの新刊
- 講演冒頭の近況は新刊 Constraint Satisfaction に合わせた内容だった
- 前日に内部原稿を出版社へ送り、予約注文も可能になった
- クリスマス前の印刷は難しいかもしれず、正式な刊行日は2月3日の見込み
- 本の中では1月印刷と記されており、この5年間にわたるKnuthの主要プロジェクトだった
- 今回のテーマである Strong Components and Weak Components のより詳しい内容は pre-fascicle 12A にある
- 現在の本は volume 4 Fascicle 7 で、先行する fascicle は volume 4A と 4B としてハードカバー出版されている
- この内容は将来 volume 4C の最初の3分の1になる予定
- 講演の副題は「Which algorithm do you love the most?」に近い
- Knuthはふだん「いちばん好きなアルゴリズム」を選べという質問を嫌うが、この場合は Tarjanの strong components アルゴリズム が明確な答えだという
- 1973年にこの手続きを学んだとき、データ構造も定理やアルゴリズムと同じように「深くなりうる」と初めて理解した
Strong component と weak component の違い
- 有向グラフは頂点と向きのある矢印で構成される
- 2つの頂点 u, v が相互に到達可能なら、同じ strong component に属する
- サイクル上の頂点はすべて同じ strong component に含まれる
- 複数の場所から入ってくる経路があっても外へ出られない頂点は、単独で1つの strong component になりうる
- Knuthが使う weak component は、向きを無視した undirected component とは異なる
- 向きを無視してつながる成分は「undirected component」と呼ぶべきだという立場
- weak component は strong components を縮約して得られるDAGをさらに partition し、全体が直線的な順序になるようにする概念である
- strong components をそれぞれ1つの「super vertex」に縮約すると、サイクルのないグラフになる
- これは半順序 (partial order) と見なせる
- weak components まで縮約すると total order または linear order になる
- トポロジカルソートとも直接つながっている
- ある x がすべての topological sorting で常に y より前に来るなら、両者は異なる weak component にある
- ある並べ方では x が y より前で、別の並べ方では y が x より前になりうるなら、両者は同じ weak component にある
- Knuthはこれを mutual incomparability と結び付けている
概念とアルゴリズムの歴史
- weak component の概念は、Knuth、Ron Graham、Mazkin と表記された教授が別の問題について書簡を交わす過程で生まれた
- 1970年2月28日に Mazkin が Graham に送った手紙に、partition によって total order を得る内容があった
- 1970年12月、Knuthは Graham に対し、3人がそれぞれ異なるアプローチでより一般的な結果を証明したと書いた
- Knuthは Mazkin を共著者に含めることにしたが、その直後に Mazkin が心臓発作で急死したとの知らせを受けた
- 関連論文は1972年の Discrete Mathematics volume 2 number 1 に掲載された
- 当時の Discrete Mathematics は創刊間もないジャーナルで、その後どれほど多くの優れた論文が載るかは誰も予想していなかった
- Tarjan の strong components アルゴリズムは1972年の SIAM Journal on Computing volume 1 number 2 に掲載された
- Tarjan は当時大学院生で、その論文は彼の publication list で6本目だった
- Knuthは1973年1月にこの論文を読み、このアルゴリズムを気に入った
- Aho、Hopcroft、Ullman のアルゴリズム教科書にも Tarjan アルゴリズムがよく整理されている
- Hopcroft は Stanford でのサバティカル中に Tarjan と研究室を共有し、いくつものアルゴリズムを考案した
- Hopcroft は無向グラフの biconnected components アルゴリズムのアイデアを持っており、Tarjan は類似のアイデアを有向グラフの strong components に適用した
- Shimon Even の本は Tarjan アルゴリズムの low point を扱っている
- component を見つけるには low point が必要で、low point を計算するには component を知る必要があるように見える循環的状況を Tarjan が解決した
DFSで strong components を見つける方法
- Knuth はグラフ探索を洞窟探検になぞらえる
- 各 room が vertex で、各 room から行ける別の room の一覧が outgoing arc である
- コンピュータは図を見ず、vertex の一覧と arc の一覧だけを見て探索する
- 基本の探索方法は depth-first search である
- まだ見ていない outgoing arc をたどって深く進む
- もう進める場所がなければ前の位置に戻る
- すでに訪問済みの vertex に出会ったら、その arc の種類を判定する
- DFSでは arc は5種類に分かれる
- tree arc: 新しい vertex を初めて発見して作られる DFS tree の arc
- back arc: ancestor に戻る arc
- loop: 自分自身へ向かう arc で、strong components には影響しない
- forward arc: descendant へ向かう arc
- cross arc: ancestor でも descendant でもない vertex へ向かう arc
- アルゴリズムは strong component を発見するたび、まだ残っているグラフの sink component を見つける
- 有限DAGには必ず sink がある
- sink strong component を取り除き、残りのグラフでもう一度探す形で進む
- この過程で strong components を見つけるのと同時に、その topological sort も得られる
- 性能は非常に高速とされる
- M 本の arc と N 個の vertex に対し、最悪時の memory access は 5M + 17N 程度
- arc 一覧の終端確認や pointer 更新のような処理まで含めた数値である
Weak components、改良版、実装
- weak components アルゴリズムも strong components を見つける過程と並行して進められる
- strong components が右から左へ、つまり sink から発見されることを利用する
- 新しい strong component が左側に入ってきたとき、既存の weak components とどう結合するかを判断する
- weak component の判定では、各 component 内の source と sink が重要になる
- ある weak component のすべての sink が、次の weak component のすべての source へ arc を持たなければならない
- この条件が weak components を持つための必要十分条件である
- プログラミング上は source だけ追跡しても更新可能
- Tarjan は1974年の Information Processing Letters volume 3 number 1 に、weak components を見つける3ページのアルゴリズム論文を出した
- Knuth はこの内容を自身の pre-fascicle 12A にまとめている
- worst-case linear time を保証するのに十分な data structure を維持するのは単純ではない
- Dijkstra も strong components 問題を扱っている
- Dijkstra の本の第25章は「Finding the maximal strong components in a directed graph」を扱う
- Dijkstra は sink strong component を取り除いていく構造を使ったが、Tarjan の low point の単純化には到達しなかった
- Dijkstra の解法は構造追跡のために4つの新しい array を導入した
- Knuth と Tarjan は最近、既存アルゴリズムを見直してよりよい定義と改良版を作った
- Kurki-Suonio の1970年代のアイデアを基に修正したが、元の論文には fallacy があった
- 従来方式で arc ごとに7回程度だったアクセスを5回程度に減らした
- いくつかの field を統合して、より複雑だがより高速な形にし、これを「premature optimization」ではなく「post-mature optimization」だと冗談めかしている
- 実装は CWEBプログラム として提供される
- プログラム名として Tarjan strong and weak、Tarjan strong に言及している
- 入力は Stanford GraphBase format の graph
- Knuth は自身のウェブサイト上のプログラム群をもっと見つけやすく整理し、2022年以降更新されていない状態を直すと述べた
- Stanford GraphBase には、Roget の thesaurus category およそ1,000個を vertex とし、synonym または antonym 関係を arc とする directed graph の例がある
1件のコメント
Hacker News のコメント
2022年にサンフランシスコを訪れたとき、スタンフォード大学のキャンパスを見て回っていて、静かな誰もいない夏の校舎の廊下を通って外へ出ようとした瞬間、偶然 Knuth のオフィスを見かけた
名声のわりに驚くほど小さくて二度見したが、むしろ彼の質素な人柄によく合う空間のように感じた
https://janvandenberg.blog/wp-content/img_1813-scaled.jpg
報奨金の小切手も1枚ではなく2枚持っている。小さな誤植だったが、この2つの文書を持っているというのは本当にすてきだ
誰も悪用はしないだろうが、自分のオフィスの写真が知らないうちに公開されていると知ったら、かなりぞっとすると思う
余暇に TAOCP 4A と 4B を読んでいるが、本当に素晴らしいので強くおすすめする。
大多数のプログラマーにとって実用的ではないかもしれないが、Knuth がアルゴリズムを設計し説明する方法は驚くべきもので、唯一無二だ。
とくに 4B の Dancing Links（踊るリンク） の実装は、有名な論文以降に大きく更新されており、精巧で美しいデータ構造でありながら速度も非常に速い。80代になってもなお見事だ。
私たちの規模で必要な費用を計算すると数千万ドルになったが、Route 53 のインフラ予算全体は数万ドル程度だった。エッジでは、ハードディスクが故障した CloudFront サーバーをネームサーバーとして再利用し、API サーバーも質素なもので、チームは6人ほどだった。AWS 流の「がむしゃらにやる」とは、ほとんどお金を使わず、下振れリスクを減らし、素早くやり遂げることだった。
だからパケットスクラバーに数千万ドルを要求することはできなかったし、届くまでにも時間がかかり、特定ベンダーに依存しすぎる可能性もあった。
初期には Route 53 のネームサーバーを専用 IP レンジで運用して、ある程度分離することにした。専用のネットワークリンクにより、Amazon の他のインフラに影響が及ばないようにすることはできた。しかし Route 53 の顧客同士が運命を共有する問題は解決できず、実際の計画は「問題が起きたら既存のネットワークとシステムツールで非常にうまくフィルタリングしよう」という程度だった。
その年の初夏、Knuth の 4A 関連の最新分冊を読みながら 組合せアルゴリズム に夢中になっていたのだが、ある夜、多数の仮想ネームサーバーを作れば、各顧客に4つの仮想ネームサーバーの組合せを一意に割り当てられる、という考えが「ピンと」来た。重なり具合も制御でき、およそ2,000個のネームサーバーがあれば、どの2顧客も2個を超えて共有しないことを保証できるとすぐに計算できた。実験上、ドメインはネームサーバー2個に到達できなくても問題なく解決できるが、それ以上になると問題になるため、この数が重要だった。
IP を割り当てる再帰探索アルゴリズムは 4A のアルゴリズムから直接着想を得たもので、顧客ドメインに対して独立した分離の次元をさらに2つ提供した。顧客は4つの独立した「ストライプ」から4つのネームサーバーを受け取る。これはネームサーバー名に使う異なるトップレベルドメイン（co.uk、com、net、org）に対応する。したがって、そのうち1つのトップレベルドメインで DNSSEC のミスのような問題が起きても、影響を受けるネームサーバーは1つだけで済む。
さらに4つの独立した「ブレイド」から出るようにし、どの2つのネームサーバーも特定のネットワーク経路や物理ハードウェアを共有しないことを保証できた。統計学と暗号学のバックグラウンドから組合せ論は知っていたが、4A を読んでいなければこのような設計はできなかっただろう。
この解決策ほど興奮したことはなかった。実質的に追加のインフラコストなしで、顧客ドメイン間に証明可能なネットワーク IP レベルの分離を提供できたからだ。数学だった。完全に無料ではなく、anycast IP アドレスを2,000個使う必要があり、多くのトップレベルドメインがネームサーバー登録と glue レコードを要求する仕組みだったため、ドメインも512個登録しなければならなかった。レジストラとのやり取りはかなり面白かったが、最終的にはやり遂げた。
この方式を Shuffle Sharding と名付けたが、発明というより発見に近い。ランダム配置を使う多くのマルチテナントシステムは一種の shuffle sharding を得ることになり、Stochastic Fair Blue のようなネットワークフィルタリング手法も時間ベースのハッシングで似た効果を生む。しかし、私たちが適用できたほどの制御力を持つまったく同じ方式は見たことがなく、呼び出し元だけでなく、「代わりに呼び出す」パターンにおける呼び出し元の呼び出し元まで、さらに多くのレベルに分離する再帰的な入れ子の shuffle sharding にまで拡張できた。
数年後、感謝の気持ちから Knuth のクリスマス講演を直接見に行き、最前列に座った。何が着想を与えてくれるか分からないので、今でも Knuth が出す資料はすべて読んでいる。オルガン曲まで含めてだ。
だから Knuth の本は、プログラマーにとって驚くほど実用的だと思う。思考を広げ、理解を深めてくれる。それ以上に何を望むというのか。
元の Dancing Links 論文 は、私の最も好きな論文の1つだ。「この過程は、グローバルなデータ構造内のポインタ変数たちに精巧に振り付けられた踊りを踊らせる」といった文を見ると、Knuth のアルゴリズムへの愛がそのまま表れている。
私はこれをクロスワード生成に使っていて、横・縦の単語がグリッドの exact cover（厳密被覆） を構成するようにしている。
更新されたアルゴリズムがメモリ使用量を減らしているのか気になる。
この大きな問題には解がおよそ1億個ほどあると推定していて、秒間100個見つけても終わるまで10日ほどかかる。
取り組んでいる問題は「Fancy Tetris Houten Puzzel」で、同じ色のピース同士が少なくとも1辺を接してすべて連結している場合の数を数えることだ。
この exact cover 問題を解くために、メモリにあまり敏感でない別のアルゴリズムも検討している。
コンピューターサイエンス関連の文献を最近読み始めたばかりの立場から聞いている。
数年前に San Francisco に行ったとき、Donald Knuth がまだ存命であるだけでなく、Stanford で毎年講演を続けていると知って驚いた。
キャンパスで建物を探し、ほとんどついていくのが難しいテーマについて彼が話すのを直接見た夜は、長く記憶に残るだろう。Donald Knuth は本当に 伝説 だ。
チームメンバーが先月 Seminumerical Algorithms で誤りを見つけ、1 hexadecimal dollar の報奨小切手を受け取った。元のメールの印刷物に手書きの注釈が付いて一緒に届いた。
Donald Knuth から最も刺激を受ける部分は、何十年にもわたる 献身と規律 だ。
プロジェクト、言語、ディストリビューションを次々に乗り換えている身として、彼から学ぶことは本当に多い。
服がとても鮮やかで生き生きとしていて、昔の村で着られていた世界各地の民族衣装のように見えるのだけれど、イラン風なのかスラブ風なのか、その中間のどこかなのかよく分からない。
もっと見当をつけられる人はいる？
記憶はおぼろげで、奥さんも関係していたかもしれない。2010年代半ば以降の講演ではよく着ているようで、どこかに説明があるはず。
2012年、マンチェスター市庁舎前の広場にオリンピック聖火がやって来るのを見ようとして、窓枠によじ登ろうとしていた Knuth のそばにいたことがある。声をかけたし、窓の外に落ちるのではと一瞬手を伸ばしたが、大丈夫だった。彼は好奇心が強く、質問と知性が輝いていて、年齢より若く見える人だと感じた。
どちらも Alan Turing 生誕100周年記念イベントに参加していて、同じ部屋に Knuth、Gary Kasparov、Fred Brooks、Vint Cerf などコンピュータ科学の巨人たちがいることに驚いた。昼食時に外の広場へオリンピック聖火が入ってきて、彼は我慢できずに見に行った。それに興奮しているのは彼だけのように見えた。
その日の夜の晩餐会で講演し、その後 4B が出たばかりの頃にマンチェスターで再会して本へのサインをお願いしたら、前のイベントで見かけた私のことをぼんやり覚えていた。
この話をするのは、彼のシャツがずっと折衷的で好奇心旺盛な心を示していると思うからだ。他の場面でも、そうした証拠を確かに見た。
だから伝統的な Sami の衣装への愛着はそこから来ているのかもしれない。
[0]: https://youtu.be/jB0aeePskBg
https://www.youtube.com/playlist?list=PLoROMvodv4rOAvKVR_dyC...
確認してみたら87歳だった。Donald Knuth は1938年1月10日生まれ。
わあ。
Knuth は今でも驚異的だ。
ただ、Stanford でこのレベルの資料にふさわしい音声録音を誰もきちんと面倒見られなかったというのは、とても意外だし残念。誰かがポケットの中の録音機で録ったように聞こえる。
Knuth の老年の声のことを言っているのではなく、彼が止まって聴衆の質問を受けるときの音質がどれほど悪いかを聞けば分かる。
こういう動画は、そもそも自分がなぜコンピュータを好きになったのかを思い出させてくれる。
いまだに鋭いというのはかなり驚きだ。残念ながら、私が20年ほど前に学部生だった頃には、すでにもう講義はしていなかった。
質問の扱い方がいい: https://youtu.be/Hi8r_63LGyg?t=827
何を尋ねているのか理解するのに時間をかけ、とても明確に答えている。