Decision-to-decision path

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.

A flow graph of a program. Each color denotes a different DD-path. Nodes 1,2,5 and 6 are each in their own DD-path containing a single node. Nodes 3 and 4 together form one DD-path (they are a maximal chain).

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).[2] 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 parenthesis):[2]

  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).[2]

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]

gollark: <@593113791252660224> Are you <@738361430763372703>?
gollark: Great, thanks.
gollark: Probably they just reroute specific bits of it when they want to do evilness.
gollark: They almost certainly can't actually inspect all traffic in software.
gollark: The total traffic probably sums to terabits or more and could not possibly go through some servers.

See also

References
  1. Huang, J.C. (September 1975). "An Approach to Program Testing". Computing Surveys. 7 (3): 118–119. doi: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. Paul C. Jorgensen (2013). Software Testing: A Craftsman’s Approach, Fourth Edition. CRC Press. pp. 136–137. ISBN 978-1-4665-6068-0.
  3. Judith A. Clapp; Saul F. Stanten; W.W. Peng; D.R. Wallace; Deborah A. Cerino; Roger J Dziegiel Jr. (1995). Software Quality Control, Error, Analysis. William Andrew. pp. 347–348. ISBN 978-1-4377-4484-2.
  4. J. C. Huang (2009). Software Error Detection through Testing and Analysis. John Wiley & Sons. pp. 164–165. ISBN 978-0-470-46405-2.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.