The Wayback Machine - https://web.archive.org/web/20221025131320/https://baike.sogou.com/kexue/d11021.htm

图论算法

编辑
入口节点为1的控制流图示例

计算机科学中，在控制流程图里，如果从起始节点到n的每条路径均经过节点d，那么节点d支配节点n 。使用符号，可以这样表达： d dom n (或有时 d >> n)。根据定义，每个节点支配它自己。

有几个相关的概念:

  • 节点 d 严格支配 节点 n 如果 d 支配n 但同时不等于 n。
  • 节点n的直接支配者 （或称idom）是唯一严格支配n的节点， 并且不严格支配其他任何支配n的节点。除了起始节点，每个节点都只有一个直接的支配者。
  • 节点d 的支配边界是一组满足下列条件的节点n，其中d支配n的一个直接支配者，但是d并不严格支配n。这组节点，代表了d的支配关系在此终结。
  • 支配树 是这样一颗树，其中每一个节点的子节点都是它所直接支配的节点。因为直接支配者是唯一的，所以它是一棵树。起始节点就是树的根。

1 历史编辑

支配是里斯·普罗瑟（Reese T. Prosser）在1959年一篇关于流程图分析的论文中首次提出的。[1] 普罗瑟没有提出一种计算支配的算法，这种算法又等了10年才由爱德华·劳里 (Edward S. Lowry)和西·梅德洛克 (C. W. Medlock)完成。[2] 罗恩(Ron Cytron)等人 在1989年将支配应用在高效计算放置φ函数(用于静态单赋值形式[3])的位置问题上，这时又重新点燃了对支配的兴趣，

2 应用程序编辑

支配者，尤其是支配边界，在编译器中被用于计算静态单赋值形式。很多编译器的优化方法也受益于支配者。这种案例下的流程图由一些基本块构成。

自动并行化得益于后支配边界。这是一种计算控制依赖性的有效方法，对分析至关重要。

内存使用情况分析可以从支配树中获的帮助，从而轻松发现漏洞并识别高内存占用情况。[4]

在硬件系统中，支配器用于计算为测试而生成的信号的概率，估计功率的变换行为和做噪声分析，以及在等效性检查中选择分割点。[5] 在软件系统中，它们用于减少结构测试技术（例如语句和分支覆盖率[6]）中测试集的大小。

3 算法编辑

节点n的支配者由以下数据流方程的最大解给出:

Dom(n0) = {n0}

Dom(n) = {n} .....

  

  

其中 n0 是起始节点。

起始节点的支配者就是起始节点本身。任何其他节点n的支配集是n的所有前驱节点p的支配集的交集。节点n也在n的支配集中

一种直接求解的算法如下:

 //开始节点的支配者是开始本身
 Dom(n0)= {n0}
 //对于所有其他节点，将所有节点设置为支配者
  for each n in N - {n0}
     Dom(n)= N；
 //迭代地s删除不是支配者的节点
 while changes in any Dom(n)
     for each n in N - {n0}:
          对于pred(n)中的所有p，Dom(p)的相交部分与Dom(n) = {n}做并集操作

直接求解法复杂度是节点数的平方，即0(n2)。 Lengauer 和Tarjan 开发了一种几乎是线性的算法，[7] 在实际应用中，除了一些人造的图外，该算法和其简化版本在所有大小的图上可做到和其他任何已知算法一样快甚至更快，并且它的优势随着图大小的增加而变得更突出。[7]

莱斯大学的基思·库珀(Keith D. Cooper)、蒂莫西·哈维(Timothy J. Harvey)和肯·肯尼迪 (Ken Kennedy)还描述了一种算法，该算法根本上解出了上述数据流方程，但使用了精心设计的数据结构以提高性能。[8]

4 后支配地位编辑

与前面"支配"的定义相似，如果一个节点n到图结束节点的所有路径皆经过某节点z,那么 z 就后支配节点n 。同样地，节点n的直接后支配者 是n的后支配者节点，并满足不严格后支配任何其他n的严格后支配者节点的条件。

参考文献

  • [1]

    ^Prosser, Reese T. (1959). "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. IRE-AIEE-ACM '59 (Eastern): 133–138. doi:10.1145/1460299.1460314..

  • [2]

    ^Lowry, Edward S.; Medlock, Cleburne W. (January 1969). "Object code optimization". Communications of the ACM. 12 (1): 13–22. doi:10.1145/362835.362838..

  • [3]

    ^Cytron, Ron; Hind, Michael; Hsieh, Wilson (1989). "Automatic Generation of DAG Parallelism". Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation: 54–68. CiteSeerX 10.1.1.50.9287..

  • [4]

    ^"Dominator Tree". eclipse.org. SAP AG and IBM Corporation. 2012 [2008]. Retrieved 21 June 2013..

  • [5]

    ^Teslenko, Maxim; Dubrova, Elena (2005). An Efficient Algorithm for Finding Double-Vertex Dominators in Circuit Graphs. Proceedings of Design and Test in Europe Conference. Date '05. pp. 406–411. CiteSeerX 10.1.1.598.3053. doi:10.1109/DATE.2005.53. ISBN 9780769522883..

  • [6]

    ^Dubrova, Elena (2005). Structural Testing Based on Minimum Kernels. Proceedings of Design and Test in Europe Conference. Date '05. pp. 1168–1173. CiteSeerX 10.1.1.583.5547. doi:10.1109/DATE.2005.284. ISBN 9780769522883..

  • [7]

    ^Lengauer, Thomas; and Tarjan; Robert Endre (July 1979). "A fast algorithm for finding dominators in a flowgraph". ACM Transactions on Programming Languages and Systems. 1 (1): 121–141. CiteSeerX 10.1.1.117.8843. doi:10.1145/357062.357071..

  • [8]

    ^Cooper, Keith D.; Harvey, Timothy J; Kennedy, Ken (2001). "A Simple, Fast Dominance Algorithm" (PDF)..

阅读 71
版本记录

  • 暂无