Dominator Tree
2017/01/04追記
非連結だとバグります☆
はじめに
はい、というわけで今日はね、今流行りのDominator Treeについてね、書いていきたいと思います。
Competitive Programming （その2） Advent Calendar 2015 - Adventarの12/25の記事の予定です。
参考論文は "A Fast Algorithm for Finding Dominators in a Flowgraph"です.Thomas LengauerとTarjan先生によって書かれたものです.この記事はこれを理解し和訳したものだと思っていいけどミスってても知りません.ごめんなさい.
めっちゃtexで書きたいんだけどパソコン変えてtexを入れてなかった(そして入れたけど日本語化に失敗した)ので頑張ってはてな記法で書いてる
はじめ元論文の流れのまま証明を書き連ねていたんですけど、見通しが悪いしまあ競プロer向けなので,証明やLemmaは別記事にして,各種定義とアルゴリズムに必要な系と定理だけ紹介することにしました.
Dominator Treeのアルゴリズムを理解するのに必要なのは,
・Dominator Tree,idom,sdomの定義とそのwell-definedness
・Cor1とTh4の主張
だけです.
Dominator Treeの定義,すぐわかる性質
当たり前だけどここが一番重要です.
Flowgraph:
G=(V,E,r)がflowgraph ⇔ (V,E)が有向グラフで,rから任意の頂点に到達可能
dominate:
v,w∈V,w≠rに対し, v dominates w (v is a dominator of w) ⇔ v≠w ∧ 任意のrからwへのpathがvを通る.(v≠wを定義に入れないこともあるっぽい)
immediately dominate:
vがw(≠r)のimmideate dominator(v=idom(w)とかく) ⇔ v dominates w ∧ wのdominatorでありvとは異なる任意のxに対し,x dominates v
dominateする中で一番近いやつ,みたいな感じ
ここでちゃんとw≠rならidom(w)がuniqueに存在することが示せる.:
(
wをdominateする頂点集合をD(w)とかく.D(w)は空ではない(∵定義より明らかにr∈D(w))
D(w)の元を,y<x:"r,x,y,wの順に通るpathがある"で順序付けることができる.なぜなら,
全順序でないとすると(すなわちあるx,y∈D(w)があってx<yでもy<xでもないとすると)xとyを両方通るrからwへのpathがないことになってしまう.これはx,y∈D(w)に矛盾.
ちゃんと順序が成り立つことも言わねばならない.推移律はすぐわかる.
a<b∧b<aとならないことは,r->a->b->wとr->b->a->w (この矢印はpathを表している)をあわせてr->b->wみたいな経路が得られるのでa∈D(w)に反することからわかる(これはちょっと正確ではなくて,ほんとはr->aの間にbがあるケースとかを考えなきゃいけないんだけど,ちゃんと考えるとa<bかb<aのどちらかは成り立たないと矛盾することがわかる)
従ってidom(w)は一意に存在.(D(w)の中でもっとも小さいやつ)
)
Dominator Tree:
v=idom(w)であるときにのみvからwへ(directed) edgeを張るようなグラフを考えると,これはrを根とする根付き木になる.これをDominator Treeと呼ぶ.
(前半部分の証明:w≠rに対して一意に親が決まることと,ループが起こりえない(これも割と明らか)ことからわかる.)
重要な性質:
v,w ∈Vについて,v dominates w ⇔ Dominator Treeにおいてvからwへのpathがある (0)
⇒)はidomの定義からD(w)の元を少しずつ下がっていく感じ
⇐)はdominate関係が推移的であることから明らか.
このくらいです.最後の性質から,dominator treeがわかれば実質dominate関係がすべてわかることになります.dominate関係だけを持つと最悪O(N^2)の辺が生えますが,こうすることで省メモリにもなるしすごい重要です.ていうかこれすごくない? そもそもidomの存在とかも結構非自明だと思う.
ここからDominator Treeを求める方法について書いていきます.
アルゴリズムに必要なひとたち
実際に紹介するアルゴリズムがうまくいくことを保証する定理4があるんですけど,そこまで行きます.がんばるぞい。正直lemmaの証明は読まなくてもそこまで問題ではない(頑張れば示せる くらいに思っといて問題無いです)し,定理4をfactとして認めるならばThem4のstatementとアルゴリズム以外は読まなくてもいいです.あ,定義だけは読んで.
ばんばん飛ばします.
まずflowgraph Gに対して,根rからdfs木を作ります.これを以降Tと書きます(木になるのはflowgraphの定義からわかる)これ以降頂点に対して特に注意せずにv<wとかv≦wとかいう時は,このdfsで訪れた順がはやいかどうかで比較しています.
ついでによく使う記法を2つ定義します.x,y∈Gに対して,
x→* y ⇔ Tにおいて,xからyへのpathがある(つまりxはyの祖先)
x→+ y ⇔ x→* y ∧ x≠y
重要なのはT,つまり根付き木の方で考えていることです.
0回以上繰り返しを意味する*と1回以上を表す+です,元論文では矢印の上に書いてありましたが面倒なのでこれで.
まずsemidominatorと呼ばれるものを定義します.(すごい重要)
Def:
w≠rに対し,semidominator of w ( sdom(w)とかく) =
定義できるのはTでのwの親が(1)のvの条件を満たしてるからです.
なんやこれ,って感じですけど最後までそんな感じです.なぜかこれを使うとうまくいってしまうっぽい.謎.この条件がなんかめっちゃうまく後々効きます.
重要なのはpathの端っこ以外はwより大きいところをとおるpathであること.それとその中でminをとっていることです.
Cor1:
w≠rとする.uを,「sdom(w)→+ u→* wをみたす」もののうち,sdom(u)が最小のもの(のうち任意のひとつ)とする.この時,
Them4:
w≠rとする.
これもうわかんねえな.
この定理4が重要です.sdom(w)を直接求められる式が出ています.
右辺はめっちゃやばそうですが,重要なのは,minの中の集合が,
・左側はwが与えられれば簡単に求まる
・右側は,u>wの条件がある
ことから,sdom(w)をwが大きい順に計算できる ということです.
あと,u →* vかつ(v,w) ∈E という冗長にも見える書き方は,→*がTの辺しか使えないところから来ていて,つまりこの条件を書き下すと,「dfs木でuの子孫(or自分)であり,そっからある辺(後退辺でも良い)1本でwに行ける」です.
アルゴリズム
お ま た せ
O(ElogV)を解説します.
このアルゴリズムは4つのパートからなります.
1:dfs木つくる
2:Them4に従いsdomを計算する
3:2をやってる途中でCor1のuを各wに対して計算する
4:idomをちゃんと計算する.おわり
1から順番に見ていきます.
1:dfs木ツクール
やるだけです.もともとの頂点についてるラベルのことを頂点の名前,dfsによってついた番号をidと書いたりするかも.
2:sdomを計算する
Them4に従って頂点idが大きい方から計算します.今wを処理してるとします.
そのためにもう少しThem4をちゃんと見てみると,「u>w かつ, u→* v かつ(v,w)∈Eなるvがとれる」uのうちsdom(u)の最小 という部分があります.これをもう少しちゃんと考えてみましょう.
wの方は先に固定されてるので,(v,w)∈Eになるようなvは全探索しても良さそうです(全体でO(E)だし).
しかし,uはvの先祖ならなんでもいいのでO(N)くらいあり,全探索するわけには行きません.
そこで,「u>wのうちでu→*vをみたすuに関するsdom(u)のmin」が速く求められればOKです.
これは皆さん当然できますよね????
はい、何も決まってないです。(path上の最大重みを求めるの一般的なテク) - sigma425のブログで紹介したテクですね.
ちゃんと説明すると,まず頂点idが大きい順なので,T上でちゃんと下の頂点から埋まっていくことに注意してください.
降順で頂点を見ていくごとに使っていい頂点vが増えるのでこれを「vとその子たちとの接続クエリ」だと思えて,答えるのはこの記事のまんま,path上にある頂点に値(sdom)がついていて,それの最小を求める となってます.(今言ったpathは,vの属する木の根からvへのpathのこと(これでいいのは上の注意よりわかる))
今回の場合具体的には,
EVAL(v)=「呼ばれた時点の森において,vが属する森の根からvまでのpath上の頂点でsdomが最も小さいもの(のうちのひとつ)」です.
sdomの値ではなくそれを実現する頂点を返してることに注意してください.
3:各wに対してCor1にあるuを求める
2を行えばすべてのsdomを求めることができます.しかし目的はidomを求めることで,それにはCor1を使います.
そこには,idom(v)を求めるときに,「sdom(v)→+ u →* v」なるuの中でsdomが最小なもの(のうちのひとつ)が必要である と書いてあります.
これをsdomが全部計算し終わったあとに求めてもいいんですけど,それよりもっといい方法があって,
sdom(v)がちょうどvが属する森の根になった瞬間にEVAL(v)を呼ぶです.これは図を見るとわかりやすいと思います
最後までsdom求めきっちゃった後だとTの辺は全部追加済みになっちゃって,EVAL(v)を呼んでも上の方の変な部分が入ってしまいます.
赤の線を繋ぐ直前に呼べば,緑の星のところがuの候補になってることがわかります.これが求めたいものです(sdom(v)自体はuにならないことに注意).かしこい.
で具体的にアルゴリズムはどうなるかというと,図に書いてあるwを処理してwとparent[w]を繋ぐ直前に,「parent[w]をsdomとして持つような頂点の集合」
の要素vに対し,EVAL(v)を呼んでCor1で必要なuを手に入れる.というものです.「」部分は割と簡単に持って更新していけるので計算量にも問題ありません.
元論文だとuを求めたあとちょっと変なことをしてるんですけど,それは必要なくてこのstepではuを求めるだけでいいです.
4:idomを求める!
ここまでくると簡単で,sdomは全て求まっているため,Cor1からすぐに求まります.
u≦wがわかる(u→*wより)ので,ここは頂点idの小さい方からループを回せば良いことがわかります.
実際に書いた
じゃあ実際のC++のコードを紹介します.PCK2013の「アカ・ベコ捕獲作戦」でverifyしました.
多分このコードのコメントを読むのが一番速く理解できると思う.
//verified by AOJ294 #include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; const int MAX_V=100000; int par[MAX_V]; //unionfind用 縮約した森の親を持つ int m[MAX_V]; //unionfind用 縮約森を辿った時に正しい答えになるようにする くわしくは前のblogを見て //今回は最小値そのものではなく,semiが最小になるような頂点を持っている(あんまり変わらない) int I; //dfsのときにidつける用 int parent[MAX_V]; //parent[v] = dfs木Tでのvの親 int vertex[MAX_V]; //vertex[i] = dfs順がi番目の頂点 int semi[MAX_V]; //semi[v] = v if vに対しstep2が行われる前 // sdom(v)のnumber otherwise int U[MAX_V]; //U[w] = wに対する,step3で求めるCor1のu int idom[MAX_V]; //idom[v] = idom(v) ほしいもの vector<int> bucket[MAX_V]; //bucket[v] = 現時点での「sdom(x)=v」なるxの集合(のうちstep3が終わってないもの) vector<int> G[MAX_V],rG[MAX_V]; //もとのグラフと,それの辺を逆にしたもの //unionfindここから void init(int N){ rep(i,N) par[i]=i,m[i]=i; } int find(int v){ if(par[v]==v) return v; int r=find(par[v]); if(semi[m[v]]>semi[m[par[v]]]) m[v]=m[par[v]]; return par[v]=r; } int EVAL(int v){ //sdom最小 になる頂点を返す.sdomを返すわけではない! find(v); return m[v]; } void LINK(int x,int y){ par[y]=x; } //unionfindここまで void dfs(int v){ //dfs木 semi[v]=I; vertex[I++]=v; for(int u:G[v]) if(semi[u]<0){ parent[u]=v; dfs(u); } } void makedomtree(int N,int r){ init(N); rep(i,N) semi[i]=-1; dfs(r); //step1 for(int i=N-1;i>0;i--){ //step2 int w=vertex[i]; for(int v:rG[w]){ int u=EVAL(v); chmin(semi[w],semi[u]); } bucket[vertex[semi[w]]].pb(w); //bucketの更新 //ここからstep3 for(int v:bucket[parent[w]]) U[v]=EVAL(v); bucket[parent[w]].clear(); //step3が終わったらbucketから消す LINK(parent[w],w); //辺の追加 } //step4 for(int i=1;i<N;i++){ int w=vertex[i]; int u=U[w]; if(semi[w]==semi[u]) idom[w]=semi[w]; else idom[w]=idom[u]; } for(int i=1;i<N;i++){ //idom[w]の中身をvertex idから名前に変える int w=vertex[i]; idom[w]=vertex[idom[w]]; } idom[r]=-1; } int main(){ int N,M,r; cin>>N>>M>>r; rep(i,M){ int a,b; cin>>a>>b; G[a].pb(b); rG[b].pb(a); } makedomtree(N,r); }
頂点の名前とid,どちらでアクセスしてるか,返すのはどっちでなのか に気をつけてください.
semi[]の役割が一番わかりにくいかと思うんですが,はじめはdfsのために-1で初期化してます.これはどうでもいい.step1終了時は頂点idを指しています.これなにが嬉しいかというと,Them4を見ると,二つの集合の合併の要素のminをとってるんですけど,ここのコードをまとめられます.以下説明します.
今step2,3のループ内で頂点wを処理してるとします.この時,(v,w)∈Eなるvに対して,
- vの処理が既に終わっている時(右の集合に対応)
この時はsemi[v]はsdom(v)のidを指しているため普通にEVAL(v)が目的のものです.
- まだ終わってない時(左の集合に対応)
まだ未処理であることから,vは今作ってる森において次数0の孤立点であることがわかります.
さらにまた未処理なのでsemi[v]=vとなっています.
従って,この時EVAL(v)を呼べばvが帰ってきます.
これに対してsemi[]をかけてもvのままであり,結局目的のものが得られていることがわかります.
結局どっちの場合もうまく目的のものが得られています.
おわりに
以上です.おかしなところや変なところや間違ったところや残念なところやわからないところがあったらtwitterとかで僕に聞いてください.
あと一応verifyしてるとはいえ間違っててなにかで残念なことになっても僕は責任を負いません(逃げの姿勢).
こうちゃんと論文を読んでブログにする,みたいなの初めてだったのでめちゃくちゃ疲れたんですけど,わかってくるとテンションが上がって面白かったです.結局sdomの直感的な理解ができてないんですが(論文にも書いてないんですが)誰かわかったら教えて下さい.
ここまで読んだ皆さん、お疲れ様でした!
