查看“支配”的源代码

{{copyedit|time=2014-02-15T04:50:33+00:00}}
{{Expert|time=2014-02-15}}
{| style="float:right" class=wikitable
|-
! 1 
| dom &nbsp; &nbsp; || {{color|#c0c0c0|1}} || {{color|#800000|2}} || 3 || 4 || 5 || 6
|-
! 2 
| dom ||   || {{color|#c0c0c0|2}} || {{color|#800000|3}} || {{color|#800000|4}} || 5 || {{color|#800000|6}}
|-
! 3 
| dom ||   ||   || {{color|#c0c0c0|3}} ||   ||   ||  
|-
! 4 
| dom ||   ||   ||   || {{color|#c0c0c0|4}} ||   ||  
|-
! 5 
| dom ||   ||   ||   ||   || {{color|#c0c0c0|5}} ||  
|-
! 6 
| dom ||   ||   ||   ||   ||   || {{color|#c0c0c0|6}}
|-
| colspan=8 | 控制关系图
|-
| colspan=8 | {{color|#c0c0c0|灰色节点}} 表示非严格控制
|-
| colspan=8 | {{color|#800000|红色节点}} 表示最近必经
|}
{| style="float:right"
| [[File:Domrel.png|thumb|200px|以1作为开始节点的控制流图实例]]
|}

在[[计算机科学]]中，[[控制流图]]的一个[[节点]] '''d''' '''支配'''节点 '''n'''，当且仅当从开始节点（可以理解为源）到节点 '''n'''的每一条路径均要经过节点'''d'''，写作'''d''' dom '''n''' (一写作'''d''' <math>\gg</math> '''n''')。根据上述定义，容易得到每个节点均控制其自身。

一些相關概念：

* 我们说一个节点 '''d''' 严格控制节点'''n'''，当且仅当 '''d'''控制 '''n''' 而不等于 '''n'''。
* 节点 '''n''' 的最近必经点（immediate dominator），简称 '''idom''' 是一个独特的节点，它严格支配节点 '''n'''，却不支配任何严格支配节点'''n'''的其他节点。不是所有的节点均有最近必经点，如开始节点就没有。
* 一个节点 '''d''' 的可支配边界是一个点集，其中任意节点n均满足， '''d''' 能严格支配所有节点u（(u,v)是图中的一条[[有向边]]），却不能严格支配 '''n'''。就是 '''d''' 支配能力的极限。
* 一个[[支配树]]是一棵[[树 (图论)|树]]，它的所有节点儿子是被其最近支配的所有节点。由于最近必经点是唯一的，故其为一棵树，开始节点即为树根。
*求解支配树一般使用 Tarjan 算法

== 求解支配树的一般方法 ==
一般而言，我们会使用 Tarjan 算法在 <math>O(|V|+|E|)</math>的时间内将其求出

=== 大概步骤 ===
首先来介绍一些这个算法的大概步骤

# 对图进行DFS（深度优先遍历）并求出搜索树和DFS序。这里我们用 <math>dfn[x]</math>表示点 <math>x</math>在dfs序中的位置。
# 根据半必经点定理计算出所有的半必经点作为计算必经点的根据
# 根据必经点定理修正我们的半必经点，求出支配点。

=== 半必经点 ===
我们用 idom[x] 表示点 <math>x</math>的最近支配点，用 semi[x] 表示点 <math>x</math>的半必经点。 

那什么是半必经点呢？
 对于一个节点 <math>Y</math>，存在某个点 <math>X</math>能够通过一系列点 <math>p_i</math>（不包含 <math>X</math>和 <math>Y</math>）到达点 <math>Y</math>且 <math>\forall i \ dfn[i]>dfn[Y]</math>，我们就称 <math>X</math>是 <math>Y</math>的半必经点，记做 semi[Y]=X
当然一个点的“半必经点” <math>X</math>会有多个，而且这些半必经点一定是搜索树中点 <math>X</math>的祖先。 

对于每个点，我们只需要保存其半必经点中最小的一个，下文中用表示点的半必经点中值最小的点的编号。 

我们可以更书面一点的描述这个定理：

* 对于一个节点 <math>Y</math>考虑所有能够到达它的节点，设其中一个为 <math>X</math>
* 若 <math>dfn[X]<dfn[Y]</math>，则 <math>X</math>是 <math>Y</math>的一个半必经点

* 若 <math>dfn[X]>dfn[Y]</math>，那么对于 <math>X</math>在搜索树中的祖先 <math>Z</math>(包括 <math>X</math>)，如果满足 <math>dfn[Z]>dfn[Y]</math>那么 semi[Z] 也是 <math>Y</math>的半必经点

== 历史 ==
[[计算机科学]]中支配的概念第一次被提出是在Reese T. Prosser在1959年一篇关于流网络的论文中提出的<ref>{{cite paper 
|last=Prosser 
|first=Reese T. 
|title=Applications of Boolean matrices to the analysis of flow diagrams 
|url=http://portal.acm.org/ft_gateway.cfm?id=1460314&type=pdf&coll=GUIDE&dl=GUIDE&CFID=79528182&CFTOKEN=33765747 
|journal=AFIPS Joint Computer Conferences: Papers presented at the December 1–3, 1959, eastern joint IRE-AIEE-ACM computer conference 
|publisher=ACM 
|location=Boston, MA
|pages=133–138 
|year=1959 }}</ref> 而在此论文中，Prosser并未提出一种有效算法以计算支配关系,解决这一问题的有效算法直到十年后才被 Edward S. Lowry and C. W. Medlock<ref>{{cite paper 
|title=Object code optimization 
|url=http://portal.acm.org/ft_gateway.cfm?id=362838&type=pdf&coll=GUIDE&dl=GUIDE&CFID=79528182&CFTOKEN=33765747 
|journal=Communications of the ACM 
|volume=12 
|issue=1 
|pages=13–22 
|first=Edward S. 
|last=Lowry 
|coauthors=and Medlock, Cleburne W. |date=January 1969}}</ref> 提出。Ron Cytron等人在1989年将其应用于高效计算应用于[[静态单赋值形式]]的φ 函数时对其重新燃起了兴趣。<ref>{{cite paper 
|first=Ron 
|last=Cytron 
|coauthors=Hind, Michael; and Hsieh, Wilson 
|id = {{citeseerx|10.1.1.50.9287}} 
|title=Automatic Generation of DAG Parallelism 
|journal=Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation 
|year=1989 
|pages=54–68 }}</ref>
==参考==
<references />4.https://blog.csdn.net/a710128/article/details/49913553
[[Category:图论]]