%0 Journal Article
%T Decision Graphs and Their Application to Software Testing
%A Robert Gold
%J ISRN Software Engineering
%D 2013
%R 10.1155/2013/432021
%X Control flow graphs are a well-known graphical representation of programs that capture the control flow but abstract from program details. In this paper, we derive decision graphs that reduce control flow graphs but preserve the branching structure of programs. As an application to software engineering, we use decision graphs to compare and clarify different definitions of branch covering in software testing. 1. Introduction Graphs that represent the control flow of programs have been studied since many years and are known under the names of control flow graphs or program graphs. There are mainly two types of such graphs: one that associates one node with each statement in programs, see, for example, [1], where control flow graphs are applied to optimization or [2] for the application in software engineering; and the other that replaces maximal sets of consecutive nodes with a single entry and a single exit called blocks or segments, by single nodes, for example, [3, 4]. Blocks can be derived from the control flow graphs of the first type or constructed directly from the programs. Both types capture the control flow by abstraction from the program details. Since the control flow through programs is determined by the decisions, for example, the if-then-else-constructs, based on the data and the conditions in such constructs, it is promising to keep in graphical representations of programs only the decisions and the control flow between them and thus defining a reduction of control flow graphs that preserves the branching structure. In this paper, we will study control flow graphs (of the first type) and derive decision graphs [5, 6] that represent the branching structure of programs based on the definition of program graphs reduced to DD-paths by Paige [7]. Statement coverage and branch coverage are widely used in software testing. The first property can be checked with control flow graphs since each node represents a statement (or block of statements). When regarding branch coverage, analogously, the question arises, in which in graph type, each edge represents a branch. More general, decision graphs can be derived not only from control flow graphs but also from arbitrary directed graphs and thus represent the branching structure of the graphs. We show that the branches in a graph correspond to the edges in the derived decision graph. As an application, we compare different definitions of branch covering in software testing that already existed but were specified in different ways in order to find where they differ from each other and thus get new
%U http://www.hindawi.com/journals/isrn.software.engineering/2013/432021/