
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 selfloops 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 incominglinks 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:

Nodebynode 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:9788131758366; Pages:341 + xxii) 
Follow Khannur 

Khannur's Company 

ISQT Process & Consulting Services Pvt. Ltd., Bangalore, INDIA

Khannur's Software Testing Forum 

STEPAUTO 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 
