Arunkumar Khannur's Software Testing Knowledge Center

8.4 Applications

Path expressions represent the entire program in the most generalized graphical representation form. With the help of node-removal procedure you can convert the graph into most abstract algebraic expressions. However many times such algebraic expressions could be ugly.

8.4.1 Counting Paths in an Entire Program

By using algebraic expressions representing the path, from the tester’s point of view we try to find answer for the following questions:

  1. What is the maximum number of different possible paths exist between entrance to exit of a single entry / single exit routine?
  2. What is the fewest number of different possible path exist between entrance to exit of a single entry / single exit routine?
  3. How many different path are really there between entrance to exit of a single entry / single exit routine?
  4. What is the average number of path that exist between entrance to exit of a single entry / single exit routine?

The answers for these questions are not straight forward and also statistics and static analysis are of no use. However heuristic approach is of great help.

If an expression has an unachievable path(s), the task of determining the actual number of different paths from entry to exit is very difficult. On the other hand, if an expression has independent and uncorrelated predicates, then the flowgraph has no loops and also, the number of minimum and maximum paths are the same.

8.4.2 Counting Maximum Number of Paths in the Program

A program in its most generalized form can be represented in the form of a path expression. Moving from program to final path expression form is a very systematic transformation involving steps that include – representing a program as a flow graph with nodes and labeled links, and then using a reduction procedure arrive at a path expression equivalent of that flow graph.

Each path in a flowgraph consists of many path expressions and each such path expression is a set of paths. Total number of paths in a particular path expression is referred to as its weight.

In order to count maximum paths in the program, following table with cases like parallel, sequential, and loop for path expressions and weight expressions is of great help. In the table A and B are path expressions and WA and WB are respective weights of A and B.

With the help of this table, we can count maximum paths in a program using the following steps:
Step 1: Arrive at control flow graph corresponding to a given program.
Step 2: Convert control flow graph into graph with nodes and labeled links
Step 3: Convert control flow graph with labeled links into weighted graph representation. To do this, consider each single link and give a weight of “1”. Also, consider each loop and from its initial and final value of loop index variable, indicate the total number of times that loop gets executed.
Step 4: Apply a path reduction procedure as follows:
    Step 4 a: Select any node for removal other than start node and end node. Replace it with set of equivalent links whose weight expressions correspond to all the ways you can form a product of the set of incoming-links with the set of outgoing- links of that node.
    Step 4 b: Combine any remaining serial links by multiplying their weight expressions.
    Step 4c: Combine all parallel links by adding their weight expressions
    Step 4d: Remove all self loops by replacing them with a link of the form Σ WAj , where WA represents the weight expression of the link in the loop.
    Step 4e: Check whether the graph consists of a single link between the entry node and exit node. If NO, go back to step 4a else Exit.

Khannur's Book
Arunkumar Khannur, Software Testing - Techniques and Applications, Published by Pearson Publications, 2011 (ISBN:978-81-317-5836-6; Pages:341 + xxii)
Follow Khannur
Khannur's Company
ISQT Process & Consulting Services Pvt. Ltd., Bangalore, INDIA
Khannur's Software Testing Forum
 Contact Khannur
ISQT Process & Consulting Services Pvt. Ltd.
#732, 1st Floor, 12th Main,
3rd Block, Rajajinagar,
Bangalore - 560010, INDIA
Phone: +91 80 23012511
Skype: arun.isqt