Unconstrained edges and their application to branch analysis and testing of programs

Structural testing is based on the control flow of programs. In particular, branch testing requires that every branch in a program be exercised at least once; accordingly, a test path set must be selected from the potentially infinite executions paths. In this article, program structure is analyzed using a reduced graph representation, called ddgraph, which has been developed ad hoc. Two relationships (dominance and implication) between the edges of a ddgraph are introduced; these relationships make it possible to identify an edge subset, called unconstrained, with the property that, when the unconstrained edges are exercised, the traversal of all the other edges is guaranteed. Applying this property to program testing, we can state that a test path set that covers all unconstrained program branches will satisfy the branch coverage criterion. © 1993.