有誤理詰（アルゴ＝リヅム）
有誤理詰「アルゴリズムのことなら有誤理詰先生に聞いとくれや」
ワイ「バグがありそうな名前や」
有誤理詰「有誤先生と呼ぶんや」
Google の模擬面接
ワイは新型ウイルスの緊急事態発令を受ける中、高校生がコーディング面接の問題で Kosaraju アルゴリズムを解答するGoogle Coding Interview With A High School Studentを視聴した。
ワイ「どんな問題や！！！」
有誤理詰「空港のリストと航路のリストが与えられたとき、起点の空港からどの空港にも移動できるようにする追加航路の最小数を求めるんや」
ワイ「小皿樹？」
ワイは生まれて以来はじめて聞いたアルゴリズムに首を傾げながら有誤理詰に怪訝な眼差しを向けた。
有誤理詰「Kosaraju アルゴリズムは有向グラフの強連結成分を求めるアルゴリズムのことや」
ワイ「今日の連結成分？」
有誤理詰「連結したのは昨日ちゃうんや。強連結成分(Strongly Connected Component)はこれや」
ワイ「アームストロング砲や」
有誤理詰「ストロングしか合ってへんがな」
有誤理詰「強連結成分内の空港は強連結成分内のどの空港にも移動できる。ほな、強連結成分を 1 つの空港に圧縮するとこれや」
有誤理詰「強連結成分のない有向グラフから入次数 (in-degree)が 0 個の空港の数を探すんや」
ワイ「乳児吸う？」
有誤理詰「遠くのほうで 4 歳娘が逃げたんや。入次数とは頂点に入ってくる辺の数のことや」
Kosaraju アルゴリズム
ワイは新型ウイルスの第 2 波に怯える中、Kosaraju アルゴリズムを解説するStrongly Connected Components Kosaraju's Algorithm Graph Algorithmを視聴した。
ワイ「Tushar さんの解説は分かりやすいんや」
有誤理詰「深さ優先探索 (depth-first search)で宛先の頂点のなくなった頂点からスタックに入れていくとこれや」
A ＜ C ＜ F ＜ E ＜ D ＜ B ＜ K ＜ H ＜ G ＜ J ＜ I
ワイ「ワイの不可さを優先して」
有誤理詰「グラフの向きを逆にするとこれや」
有誤理詰「I から順にスタックから出して逆向きのグラフで探索すると強連結成分や。有名な CLRS 本に数学的証明が載っているんや」
ワイ「置いてけ堀や」
有誤理詰「ABC 内の 1 つの頂点は DEF より後でスタックに入ることが保証されるんや。それを B としたら B が先に ABC を探索して DEF が残るんや」
ワイ「お堀の深さを優先したい（遠い目）」
プログラム
class Kosaraju {
visited: Set<VertexAlphabet> = new Set();
stack: VertexAlphabet[] = [];
stack_scc: VertexAlphabet[] = [];
stack_scc_result: VertexAlphabet[][] = [];
graph = new Graph();
graph_reverse = new Graph();
edges_alphabet: EdgeAlphabet[];
initialize(): void {
this.edges_alphabet.forEach(([v1a, v2a]) => {
this.graph.add([v1a, v2a]);
this.graph_reverse.add([v2a, v1a]);
});
}
find_scc(): void {
this.first_path();
this.visited.clear();
this.second_path();
}
first_path(): void {
["B", "I", ...this.graph.vertexes_alphabet].forEach(va => {
if (!this.graph.vertexes_alphabet.includes(va)) return;
this.visit(va);
});
}
second_path(): void {
while (this.stack.length) {
var vertex = this.stack.pop()!;
this.visit2(vertex);
if (this.stack_scc.length) {
this.stack_scc_result.push(this.stack_scc);
this.stack_scc = [];
}
}
}
visit(vertex: VertexAlphabet): void {
if (this.visited.has(vertex)) return;
this.visited.add(vertex);
this.graph.get_adjacent_vertexes_from_vertex(vertex).forEach(vertex2 => {
this.visit(vertex2);
});
this.stack.push(vertex);
}
visit2(vertex: VertexAlphabet): void {
if (this.visited.has(vertex)) return;
this.visited.add(vertex);
this.stack_scc.push(vertex);
this.graph_reverse.get_adjacent_vertexes_from_vertex(vertex).forEach(vertex2 => {
this.visit2(vertex2);
});
}
}
Tarjan アルゴリズム
ワイ「検索結果数が 10 倍もあって目についたんや」
有誤理詰「Tarjan アルゴリズムも有向グラフの強連結成分を求めるアルゴリズムのことや」
ワイ「田じゃん？」
有誤理詰「未訪問の頂点をスタックに入れて Index 値をふっていくんや。宛先の頂点がスタックにあったら現在の頂点の Lowlink 値を小さいほうの値で更新するんや。グラフ探索の戻りで Lowlink 値を伝播させていくんや。グラフ探索の戻りで現在の頂点の Lowlink 値と Index 値が同じだったらスタックから出して強連結成分や」
ワイ「明日、連結したい（遠い目）」
プログラム
ワイ「YouTube 視聴でコーディングするのは無理や！！！」
有誤理詰「Tarjan アルゴリズムを説明するのは難しいんや」
ワイ「田じゃん？」
有誤理詰「Tushar さんの解説は分かりやすいんや。出力は長くなるんやが、アルゴリズムの要所 で Lowlink 値などの変更を console.log してすべて出力するのが分かりやすいんや」
console.log（クリックで開く）
"B".onStack = true
A(), B(0, 0, S), C(), D(), E(), F(), G(), H(), I(), J(), K()
"C".onStack = true
A(), B(0, 0, S), C(1, 1, S), D(), E(), F(), G(), H(), I(), J(), K()
"A".onStack = true
A(2, 2, S), B(0, 0, S), C(1, 1, S), D(), E(), F(), G(), H(), I(), J(), K()
w("B").onStack at v("A")
A(2, 0, S), B(0, 0, S), C(1, 1, S), D(), E(), F(), G(), H(), I(), J(), K()
w("A").index === void 0 at v("C")
A(2, 0, S), B(0, 0, S), C(1, 0, S), D(), E(), F(), G(), H(), I(), J(), K()
w("C").index === void 0 at v("B")
A(2, 0, S), B(0, 0, S), C(1, 0, S), D(), E(), F(), G(), H(), I(), J(), K()
"D".onStack = true
A(2, 0, S), B(0, 0, S), C(1, 0, S), D(3, 3, S), E(), F(), G(), H(), I(), J(), K()
"E".onStack = true
A(2, 0, S), B(0, 0, S), C(1, 0, S), D(3, 3, S), E(4, 4, S), F(), G(), H(), I(), J(), K()
"F".onStack = true
A(2, 0, S), B(0, 0, S), C(1, 0, S), D(3, 3, S), E(4, 4, S), F(5, 5, S), G(), H(), I(), J(), K()
w("D").onStack at v("F")
A(2, 0, S), B(0, 0, S), C(1, 0, S), D(3, 3, S), E(4, 4, S), F(5, 3, S), G(), H(), I(), J(), K()
w("F").index === void 0 at v("E")
A(2, 0, S), B(0, 0, S), C(1, 0, S), D(3, 3, S), E(4, 3, S), F(5, 3, S), G(), H(), I(), J(), K()
w("E").index === void 0 at v("D")
A(2, 0, S), B(0, 0, S), C(1, 0, S), D(3, 3, S), E(4, 3, S), F(5, 3, S), G(), H(), I(), J(), K()
"F".onStack = false
"E".onStack = false
"D".onStack = false
scc: [ 'F', 'E', 'D' ]
w("D").index === void 0 at v("B")
A(2, 0, S), B(0, 0, S), C(1, 0, S), D(3, 3), E(4, 3), F(5, 3), G(), H(), I(), J(), K()
"A".onStack = false
"C".onStack = false
"B".onStack = false
scc: [ 'A', 'C', 'B' ]
"I".onStack = true
A(2, 0), B(0, 0), C(1, 0), D(3, 3), E(4, 3), F(5, 3), G(), H(), I(6, 6, S), J(), K()
"J".onStack = true
A(2, 0), B(0, 0), C(1, 0), D(3, 3), E(4, 3), F(5, 3), G(), H(), I(6, 6, S), J(7, 7, S), K()
"K".onStack = true
A(2, 0), B(0, 0), C(1, 0), D(3, 3), E(4, 3), F(5, 3), G(), H(), I(6, 6, S), J(7, 7, S), K(8, 8, S)
"K".onStack = false
scc: [ 'K' ]
w("K").index === void 0 at v("J")
A(2, 0), B(0, 0), C(1, 0), D(3, 3), E(4, 3), F(5, 3), G(), H(), I(6, 6, S), J(7, 7, S), K(8, 8)
"G".onStack = true
A(2, 0), B(0, 0), C(1, 0), D(3, 3), E(4, 3), F(5, 3), G(9, 9, S), H(), I(6, 6, S), J(7, 7, S), K(8, 8)
"H".onStack = true
A(2, 0), B(0, 0), C(1, 0), D(3, 3), E(4, 3), F(5, 3), G(9, 9, S), H(10, 10, S), I(6, 6, S), J(7, 7, S), K(8, 8)
w("I").onStack at v("H")
A(2, 0), B(0, 0), C(1, 0), D(3, 3), E(4, 3), F(5, 3), G(9, 9, S), H(10, 6, S), I(6, 6, S), J(7, 7, S), K(8, 8)
w("H").index === void 0 at v("G")
A(2, 0), B(0, 0), C(1, 0), D(3, 3), E(4, 3), F(5, 3), G(9, 6, S), H(10, 6, S), I(6, 6, S), J(7, 7, S), K(8, 8)
w("G").index === void 0 at v("J")
A(2, 0), B(0, 0), C(1, 0), D(3, 3), E(4, 3), F(5, 3), G(9, 6, S), H(10, 6, S), I(6, 6, S), J(7, 6, S), K(8, 8)
w("J").index === void 0 at v("I")
A(2, 0), B(0, 0), C(1, 0), D(3, 3), E(4, 3), F(5, 3), G(9, 6, S), H(10, 6, S), I(6, 6, S), J(7, 6, S), K(8, 8)
"H".onStack = false
"G".onStack = false
"J".onStack = false
"I".onStack = false
scc: [ 'H', 'G', 'J', 'I' ]
A(2, 0), B(0, 0), C(1, 0), D(3, 3), E(4, 3), F(5, 3), G(9, 6), H(10, 6), I(6, 6), J(7, 6), K(8, 8)
ワイ「対数を慰めたい（遠い目）」
有誤理詰「ほな、Tarjan's strongly connected components algorithmの擬似コードを TypeScript1 にするんや」
class Tarjan {
edges_alphabet: EdgeAlphabet[];
graph = new Graph();
index = 0;
stack: VertexAlphabet[] = [];
scc_results: VertexAlphabet[][] = [];
initialize(): void {
this.edges_alphabet.forEach(edge => {
this.graph.add(edge);
});
}
find_scc(): void {
["B", "I", ...this.graph.vertexes_alphabet].forEach(va => {
var v = this.graph.vertexes.get(va)!;
if (!v) return;
if (v.index === void 0) this.strongconnect(va);
});
}
strongconnect(va: VertexAlphabet): void {
var v: Vertex = this.graph.vertexes.get(va)!;
v.index = this.index;
v.lowlink = this.index;
this.index++;
this.stack.push(va);
v.onStack = true;
this.graph.get_adjacent_vertexes_from_vertex(va).forEach(wa => {
var w = this.graph.vertexes.get(wa)!;
if (w.index === void 0) {
this.strongconnect(wa);
v.lowlink = Math.min(v.lowlink!, w.lowlink!);
} else if (w.onStack) v.lowlink = Math.min(v.lowlink!, w.index);
});
var wa: VertexAlphabet;
var w: Vertex;
var scc: VertexAlphabet[] = [];
if (v.lowlink === v.index)
do {
wa = this.stack.pop()!;
w = this.graph.vertexes.get(wa)!;
w.onStack = false;
scc.push(wa);
} while (wa !== va);
if (scc.length) this.scc_results.push(scc);
}
}
全米が震えた
高校生が Kosaraju アルゴリズムを解答したことで全米が震えた。その余波でワイは Kosaraju アルゴリズムと Tarjan アルゴリズムを学習してしまった。
ワイ「小皿樹アルゴリズムのほうが 分かりやすいんやが、田じゃんアルゴリズムのほうが実用的や」
有誤理詰「学習できて良かったんや。でも最後まで先生と呼ばれなかったんや・・・」