Arunkumar Khannur's Software Testing Knowledge Center
   
 

8.3 A Path Reduction Procedure


A path reduction procedure or simply reduction procedure is a step by step procedure to derive an ugly path expression from a given flow graph. By using a path reduction procedure, we can systematically proceed from a given flow graph and then follow the steps that include removing node by node, followed by combining parallel links in the simplified flow graph, and finally removing all self-loops in order to arrive at an ugly path expression. In summary, by using a path reduction procedure, we can convert a flow graph with labeled links into an ugly path expression that denotes the set of all entry / exit paths (referred as complete graph in that flow graph). Following are the steps in entire process:

Step 1, 2, and 3 are useful
Step 1: Combine all serial links by multiplying their path expressions.
Step 2: Combine all parallel links by adding their path expressions.
Step 3: Remove all self – loops by replacing them with a link of the form X*, where X represents the path expressions of the link in the loop.
Step 4: Perform the following steps
     Step 4 a: Select any node for removal other than start node and end node. Replace it with set
     of equivalent links whose path 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 path expressions.
     Step 4c: Combine all parallel links by adding their path expressions
     Step 4d: Remove all self loops by replacing them with a link of the form X*, where X represents the
     path 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.

Using an illustration, we shall learn how the path reduction procedure works on a flow graph. Let us consider the following flow graph:

Now, by applying node removal step repeatedly, we can remove several nodes systematically as follows:
Node-by-node Removal
By applying step 4a and then 4b, we remove node 10 as follows:

By proceeding in similar manner, by applying Step 4a and 4b, we remove nodes 9, 8, 7.


As result of node removal exercise, we arrive at:

Combining Parallel Links
The above flow graph has many parallel links. Now by applying Step 4c: Combine all parallel links by adding their path expressions step, we first remove the parallel path between node 3 and 4. By doing this we arrive at following flow graph.
By applying Step 4a and 4b, we remove node 3 as shown below:
Again by applying Step 4c, we arrive at following flow graph.

 
 
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
STEP-AUTO Forum
 Contact Khannur
ISQT Process & Consulting Services Pvt. Ltd.
#732, 1st Floor, 12th Main,
3rd Block, Rajajinagar,
Bangalore - 560010, INDIA
Phone: +91 80 23012511
URL: www.isqtinternational.com
Email: khannur@isqtinternational.com
Skype: arun.isqt