支配 (圖論)
![]() |
1 | dom | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
2 | dom | 2 | 3 | 4 | 5 | 6 | |
3 | dom | 3 | |||||
4 | dom | 4 | |||||
5 | dom | 5 | |||||
6 | dom | 6 | |||||
支配關係圖 | |||||||
灰色節點 表示非嚴格支配 | |||||||
紅色節點 表示直接支配 |
![]() |
在計算機科學中,控制流圖的一個節點(基本塊) d 支配節點 n,若且唯若從開始節點(可以理解為源)到節點 n的每一條路徑均要經過節點d,寫作d dom n (一寫作d n)。根據上述定義,容易得到每個節點均支配其自身。
一些相關概念:
- 說一個節點 d 嚴格支配節點n,若且唯若 d支配 n 而不等於 n。
- 節點 n 的直接支配節點(immediate dominator),簡稱 idom 是一個獨特的節點,它嚴格支配節點 n,卻不嚴格支配任何嚴格支配節點n的其他節點。不是所有的節點均有直接支配節點,如開始節點就沒有。
- 一個節點 d 的可支配邊界是一個點集,其中任意節點n均滿足, d 能支配 n 的前驅結點,卻不能嚴格支配 n。就是 d 支配能力的極限。
- 一個支配樹是一棵樹,它的所有節點兒子是被其直接支配的所有節點。由於直接支配節點是唯一的,故其為一棵樹,開始節點即為樹根。
- 求解支配樹一般使用 Tarjan 算法
求解支配樹的一般方法
一般而言,會使用 Tarjan 算法在 的時間內將其求出
大概步驟
首先來介紹一些這個算法的大概步驟
- 對圖進行DFS(深度優先遍歷)並求出搜索樹和DFS序。這裡用 表示點 在dfs序中的位置。
- 根據半必經點定理計算出所有的半必經點作為計算必經點的根據
- 根據必經點定理修正半必經點,求出支配點。
半必經點
用 idom[x] 表示點 的直接支配節點,用 semi[x] 表示點 的半必經點。
那什麼是半必經點呢?
對於一個節點 ,存在某個點 能夠通過一系列點 (不包含 和 )到達點 且 ,就稱 是 的半必經點,記做 semi[Y]=X
當然一個點的「半必經點」 會有多個,而且這些半必經點一定是搜索樹中點 的祖先。
對於每個點,只需要保存其半必經點中最小的一個,下文中用表示點的半必經點中值最小的點的編號。
可以更書面一點的描述這個定理:
- 對於一個節點 考慮所有能夠到達它的節點,設其中一個為
- 若 ,則 是 的一個半必經點
- 若 ,那麼對於 在搜索樹中的祖先 (包括 ),如果滿足 那麼 semi[Z] 也是 的半必經點
歷史
計算機科學中支配的概念第一次被提出是在Reese T. Prosser在1959年一篇關於流網絡的論文中提出的[1] 而在此論文中,Prosser並未提出一種有效算法以計算支配關係,解決這一問題的有效算法直到十年後才被 Edward S. Lowry and C. W. Medlock[2] 提出。Ron Cytron等人在1989年將其應用於高效計算應用於靜態單賦值形式的φ 函數時對其重新燃起了興趣。[3]
參考
- ^ Prosser, Reese T. Applications of Boolean matrices to the analysis of flow diagrams. AFIPS Joint Computer Conferences: Papers presented at the December 1–3, 1959, eastern joint IRE-AIEE-ACM computer conference (Boston, MA: ACM). 1959: 133–138.
- ^ Lowry, Edward S.; and Medlock, Cleburne W. Object code optimization. Communications of the ACM. January 1969, 12 (1): 13–22.
- ^ Cytron, Ron; Hind, Michael; and Hsieh, Wilson. Automatic Generation of DAG Parallelism. Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation. 1989: 54–68. CiteSeerX: 10.1.1.50.9287
.