概要
LIbrary Checker のジャッジをお借りして、次の 3 種類の強連結成分分解アルゴリズムそれぞれの、いくつかのバージョンの速度を比較します。
- Kosaraju's algorithm
- Tarjan's algorithm
- Gabow's algorithm
その結果、Vec<Vec<usize>> を構築して行う Kosaraju's algorithm は、この記事の最速実装に比べて $3$ 倍程度遅いことがわかりました。
今回の計測では最速の座は Gabow's が手にしましたが、Kosaraju's の高速な実装もそれとほぼ変わりませんでした。従って実装の短さを考えると Kosaraju's の高速な実装を採用するのが、私には良い選択肢であると感じました。
結果
Strongly Connected Components - Library Checker ($N, Q \le 5 \cdot 10 ^ 5$）に提出して実行時間を見ます。
※ 複数回提出して平均を取るような丁寧な計測はしておりません
| アルゴリズム | 実行時間 |
|---|---|
| nop | 88 ms |
| nop（出力の CSR 表現） | 68 ms |
| Kosaraju's | 339 ms |
| Tarjan's | 215 ms |
| Gabow's | 197 ms |
| Kosaraju's （グラフの CSR 表現） | 141 ms |
| Tarjan's （グラフの CSR 表現） | 154 ms |
| Gabow's（グラフの CSR 表現） | 154 ms |
| Kosaraju's （グラフと出力の CSR 表現） | 125 ms |
| Tarjan's （グラフと出力の CSR 表現） | 144 ms |
| Gabow's （グラフと出力の CSR 表現） | 119 ms |
結果の見方
- nop は比較対象として用意した、入力を受け取り $N$ 以外すべて無視して、離散グラフに対応する答えを出力するアルゴリズムです。
- 括弧書きなしの 3 種類のアルゴリズムは、グラフの隣接リスト（Kosaraju's は 2 つ、Tarjan's、Gabow's は 1 つ、ちなみに nop は 0 個）と出力をすべて 2 次元
Vecを用いて表しています。括弧書きしているものは、このうち一方または両方を CSR（compressed sparse row）表現に置き換えたバージョンを表します。
結果の表を、見やすいように書き換えてみました。
| アルゴリズム | 無印 | グラフの CSR 表現 | グラフと出力の CSR 表現 |
|---|---|---|---|
| nop | 88 ms | - | 68 ms |
| Kosaraju's | 339 ms | 141 ms | 125 ms |
| Tarjan's | 215 ms | 154 ms | 144 ms |
| Gabow's | 197 ms | 154 ms | 119 ms |
結果の観察
アルゴリズム自体の速さの違いはあまりありません。私の実装では入出力が律速なので、こだわっても仕方がないくらいの差だと思います。（入出力ガチ勢ではなくて申し訳なしです。）一方、2 次元 Vec の使用をやめることは非常に効果的なようです。
計測方法・アルゴリズムの概略説明
nop
入力を受け取り $N$ 以外すべて無視して、離散グラフに対応する答えを出力します。
各アルゴリズムでは、このコード中の nop を置き換えて実装します。
提出：88 ms
use std::io; use std::io::BufRead; use std::io::BufReader; use std::io::BufWriter; use std::io::Write; fn main() { let (n, _m, edges) = input(); let groups = nop(n, &edges); output(&groups); } fn nop(n: usize, _edges: &[(usize, usize)]) -> Vec<Vec<usize>> { let mut groups = vec![]; for i in 0..n { groups.push(vec![i]); } groups } fn input() -> (usize, usize, Vec<(usize, usize)>) { let stdin = io::stdin(); let mut stdin = BufReader::new(stdin.lock()).lines().map(Result::unwrap); let (n, m) = { let s = stdin.next().unwrap(); let mut s = s.split_whitespace(); ( s.next().unwrap().parse::<usize>().unwrap(), s.next().unwrap().parse::<usize>().unwrap(), ) }; let edges = (0..m) .map(|_| { let s = stdin.next().unwrap(); let mut s = s.split_whitespace(); ( s.next().unwrap().parse::<usize>().unwrap(), s.next().unwrap().parse::<usize>().unwrap(), ) }) .collect::<Vec<_>>(); (n, m, edges) } fn output(groups: &[Vec<usize>]) { let stdout = io::stdout(); let mut stdout = BufWriter::new(stdout.lock()); let k = groups.len(); writeln!(stdout, "{}", k).unwrap(); for group in groups { write!(stdout, "{}", group.len()).unwrap(); for &v in group { write!(stdout, " {}", v).unwrap(); } writeln!(stdout).unwrap(); } stdout.flush().unwrap(); }
1. Kosaraju's alrogirhm
蟻本に載っているアルゴリズムです。2 回 DFS をします。1 回目の DFS で $G$ の post-orderを計算し、その逆順始点で逆グラフ $G ^ {\mathrm{op}}$ を DFS するアルゴリズムですね。
提出: 339 ms
fn kosaraju(n: usize, edges: &[(usize, usize)]) -> Vec<Vec<usize>> { let mut g = vec![vec![]; n]; let mut rg = vec![vec![]; n]; for &(u, v) in edges { g[u].push(v); rg[v].push(u); } let mut sorted = vec![]; let mut used = vec![false; n]; for i in 0..n { if !used[i] { dfs1(i, &g, &mut used, &mut sorted); } } let mut groups = vec![]; used.fill(false); for &u in sorted.iter().rev() { if !used[u] { let mut group = vec![]; dfs2(u, &rg, &mut used, &mut group); groups.push(group); } } groups } fn dfs1(i: usize, g: &[Vec<usize>], used: &mut [bool], sorted: &mut Vec<usize>) { used[i] = true; for &v in &g[i] { if !used[v] { dfs1(v, g, used, sorted); } } sorted.push(i); } fn dfs2(u: usize, rg: &[Vec<usize>], used: &mut [bool], group: &mut Vec<usize>) { used[u] = true; group.push(u); for &v in &rg[u] { if !used[v] { dfs2(v, rg, used, group); } } }
2. Tarjan's algorithm
訪問した節点をスタックに詰みつつ lowpoint（lowlink?）を計算しながら DFS をして、帰りがけに strong component の根を検出してはその strong component をスタックからまとめて pop していくアルゴリズムです。これもかなり有名ですね。
関数 dfs の引数の数がすごいことになっていますが、気にしないことにします。
提出: 215 ms
fn tarjan(n: usize, edges: &[(usize, usize)]) -> Vec<Vec<usize>> { let mut g = vec![vec![]; n]; for &(u, v) in edges { g[u].push(v); } let mut index = vec![usize::MAX; n]; let mut lowlink = vec![usize::MAX; n]; let mut on_stack = vec![false; n]; let mut stack = vec![]; let mut groups = vec![]; let mut time = 0; for i in 0..n { if index[i] == usize::MAX { dfs( i, &mut time, &mut g, &mut index, &mut lowlink, &mut on_stack, &mut stack, &mut groups, ); } } groups.reverse(); groups } fn dfs( x: usize, time: &mut usize, g: &Vec<Vec<usize>>, index: &mut Vec<usize>, lowlink: &mut Vec<usize>, on_stack: &mut Vec<bool>, stack: &mut Vec<usize>, groups: &mut Vec<Vec<usize>>, ) { index[x] = *time; lowlink[x] = *time; *time += 1; stack.push(x); on_stack[x] = true; for &v in &g[x] { if index[v] == usize::MAX { dfs(v, time, g, index, lowlink, on_stack, stack, groups); lowlink[x] = lowlink[x].min(lowlink[v]); } else if on_stack[v] { lowlink[x] = lowlink[x].min(index[v]); } } if index[x] == lowlink[x] { let mut group = vec![]; while { let y = stack.pop().unwrap(); on_stack[y] = false; group.push(y); y != x } {} groups.push(group); } }
3. Gabow's algorithm
出典：Gabow, Harold N. "Path-based depth-first search for strong and biconnected components; CU-CS-890-99." (1999).
訪問済みの節点をスタック点は Tarjan's algorithm に似ていますが、加えてこのスタックの中身を今までに見た辺のみで強連結成分分解（これはパスグラフになっています）して分割したおき、これを逐次更新する方針のアルゴリズムです。
提出: 197 ms
fn gabow(n: usize, edges: &[(usize, usize)]) -> Vec<Vec<usize>> { let mut g = vec![vec![]; n]; for &(u, v) in edges { g[u].push(v); } let mut stack = vec![]; let mut boundary = vec![]; let mut index = vec![usize::MAX; n]; let mut groups = vec![]; for x in 0..n { if index[x] == usize::MAX { dfs(x, &g, &mut stack, &mut boundary, &mut index, &mut groups); } } groups.reverse(); groups } fn dfs( x: usize, g: &[Vec<usize>], stack: &mut Vec<usize>, boundary: &mut Vec<usize>, index: &mut [usize], groups: &mut Vec<Vec<usize>>, ) { index[x] = stack.len(); stack.push(x); boundary.push(index[x] as usize); for &y in &g[x] { if index[y] == usize::MAX { dfs(y, g, stack, boundary, index, groups); } else { while (index[y] as isize) < (*boundary.last().unwrap() as isize) { boundary.pop(); } } } if index[x] == *boundary.last().unwrap() { let mut group = vec![]; let k = g.len() + groups.len(); while let Some(y) = stack.pop() { group.push(y); index[y] = k; if y == x { break; } } boundary.pop().unwrap(); groups.push(group); } }
CSR（Compressed Sparse Row）format による高速化
グラフの CSR 表現化
実は二次元 Vec を使うのをやめるだけでかなり速くなります。CSR format（Compressed sparse row (CSR, CRS or Yale format))）というのは疎行列を管理する効率的な方法なのですが、これはグラフの隣接リストにも応用できます。
次のような命名センスのない関数（命名ゆる募です。素直に csr_graph とかがよいのでしょうかね。）で構築します。
fn flat_graph(n: usize, edges: &[(usize, usize)]) -> (Vec<usize>, Vec<usize>) { let mut start = vec![0; n + 1]; for &(u, _) in edges { start[u] += 1; } for i in 1..=n { start[i] += start[i - 1]; } let mut next = vec![0; edges.len()]; for &(u, v) in edges { start[u] -= 1; next[start[u]] = v; } (start, next) }
Kosaraju's に対しては $G ^ {\mathrm{op}}$ も CSR 化したいので、次のように同時に計算します。
fn flat_graph( n: usize, edges: &[(usize, usize)], ) -> (Vec<usize>, Vec<usize>, Vec<usize>, Vec<usize>) { let mut start = vec![0; n + 1]; let mut rev_start = vec![0; n + 1]; for &(u, v) in edges { start[u] += 1; rev_start[v] += 1; } for i in 1..=n { start[i] += start[i - 1]; rev_start[i] += rev_start[i - 1]; } let mut next = vec![0; edges.len()]; let mut rev_next = vec![0; edges.len()]; for &(u, v) in edges { start[u] -= 1; next[start[u]] = v; rev_start[v] -= 1; rev_next[rev_start[v]] = u; } (start, next, rev_start, rev_next) }
使い方は簡単で、&g[x] の代わりに &next[start[x]..start[x + 1]] するだけです。
出力の CSR 表現化
次のような感じで、CSR 表現を出力するように変更すると、さらに高速化できます。
fn main() { let (n, _m, mut edges) = input(); let (group_next, group_start) = kosaraju(n, &mut edges); output(&group_next, &group_start); } fn output(group_next: &[usize], group_start: &[usize]) { let stdout = io::stdout(); let mut stdout = BufWriter::new(stdout.lock()); let k = group_start.len() - 1; writeln!(stdout, "{}", k).unwrap(); for i in 0..k { let g = &group_next[group_start[i]..group_start[i + 1]]; write!(stdout, "{}", g.len()).unwrap(); for &v in g { write!(stdout, " {}", v).unwrap(); } writeln!(stdout).unwrap(); } stdout.flush().unwrap(); }
Kosaraju's は、実はもともと計算していた
sortedの逆順が今回欲しいgroup_nextに一致します。そこでこれを使いまわすことにし、dfs2ではgroup_startだけを全力で計算すればよく、これによりさらに高速化できます。Tarjan's, Gabow's はトポロジカルソートの逆を返してしまうので、いままで
groups.reverse()していた代わりに次のように反転します。
group_next.reverse(); group_start.reverse(); group_start.iter_mut().for_each(|x| *x = n - *x);
- nop も出力で 2 次元
Vecを使っていたことを考えると、同様に試す必要があります。実装はこうです。
fn nop(n: usize, _edges: &[(usize, usize)]) -> (Vec<usize>, Vec<usize>) { ((0..n).collect(), (0..=n).collect()) }
