一种基于程序DD图的无约束边生成算法

Algorithm for the Generation of Unconstrained Edges Based on the Decision-to-Decision Graph

基于相似路径集进行软件故障定位是众多有效故障定位方法中的一种,该方法利用测试技术、程序切片和削片技术给出具体的软件故障定位报告。在实现上述方法时,求出程序DD图(Decision-to-Decision Graph)的无约束边就是关键步骤。目前,针对这一关键步骤的研究中,虽然取得了一定进展,但如何基于程序DD图生成无约束边,尚需要进一步研究。首先选用十字链表结构存储程序的DD图,进而计算出该程序DD图中各边对应的主宰树和蕴含树,

Using similar paths to localize the program faults is a method among many effective ones. Based on the techniques such as testing, program slicing and dicing, this paper presented a detailed report of the location of the faults in a program. When implementing the method, the generation of the unconstrained edges in a decision-to-decision graph is very important. At present,mang researches have been done,however, how to generate the unconstrained edges based on a decision-to-decision graph still needs further research. In our research, we chose orthogonal linked list as the data structure to store the decision-to-decision graph, then calculated the dominator tree and the implication tree of the graph. On this basis, we generated the unconstrained edges in a decision-to-decision graph, The experimental result shows that the proposed method is effective in the generation of the unconstrained edges.