Decision-to-decision path explained

A decision-to-decision path, or DD-path, is a path of execution (usually through a flow graph representing a program, such as a flow chart) between two decisions. More recent versions of the concept also include the decisions themselves in their own DD-paths.

Definition

In Huang's 1975 paper,^[1] a decision-to-decision path is defined as path in a program's flowchart such that all the following hold (quoting from the paper):

• its first constituent edge emanates either from an entry node or a decision box;
• its last constituent edge terminates either at a decision box or at an exit node; and
• there are no decision boxes on the path except those at both ends

Jorgensen's more recent textbooks restate it in terms of a program's flow graph (called a "program graph" in that textbook). First define some preliminary notions: chain and a maximal chain. A chain is defined as a path in which:

• initial and terminal nodes are distinct, and
• all interior nodes have in-degree = 1 and out-degree = 1.

A maximal chain is a chain that is not part of a bigger chain.

A DD-path is a set of nodes in a program graph such that one of the following holds (quoting and keeping Jorgensen's numbering, with comments added in parentheses):

1. It consists of a single node with in-degree = 0 (initial node)
2. It consists of a single node with out-degree = 0 (terminal node)
3. It consists of a single node with in-degree ≥ 2 or out-degree ≥ 2 (decision/merge points)
4. It consists of a single node with in-degree = 1 and out-degree = 1
5. It is a maximal chain of length ≥ 1.

According to Jorgensen (2013), in Great Britain and ISTQB literature, the same notion is called linear code sequence and jump (LCSAJ).

Properties

From the latter definition (of Jorgensen) we can conclude the following:

• Every node on a flow graph of a program belongs to one DD-path.
• If the first node on a DD-path is traversed, then all other nodes on that path will also be traversed.
• The DD path graph is used to find independent path for testing.
• Every statement in the program has been executed at least once.

DD-path testing

According to Jorgensen's 2013 textbook, DD-path testing is the best known code-based testing method, incorporated in numerous commercial tools.^[2]

DD-path testing is also called C2 testing or branch coverage.^{[3] [4]}

See also

• Basic block
• Basis path testing and its ancillary articles
  • Cyclomatic complexity
  • Essential complexity
• Code coverage
• White-box testing

External links

• http://www.eecs.yorku.ca/course_archive/2011-12/W/4313/slides/11-Paths.pdf

Notes and References

1. Huang. J.C.. An Approach to Program Testing. Computing Surveys. September 1975. 7. 3. 118–119. 10.1145/356651.356652. The definition given there is citing: "Fortran automated verification system Level 1 — user's guide, Program Validation Project, General Research Corp., October 1974."
2. Book: Paul C. Jorgensen. Software Testing: A Craftsman’s Approach, Fourth Edition. 2013. CRC Press. 978-1-4665-6068-0. 136–137.
3. Book: Judith A. Clapp. Saul F. Stanten. W.W. Peng . D.R. Wallace . Deborah A. Cerino . Roger J. Dziegiel Jr. . Software Quality Control, Error, Analysis. 1995. William Andrew. 978-1-4377-4484-2. 347–348.
4. Book: J. C. Huang. Software Error Detection through Testing and Analysis. limited. 2009. John Wiley & Sons. 978-0-470-46405-2. 164–165.