Arunkumar Khannur's Software Testing Knowledge Center
   
 

11.9 Node Reduction Algorithm- Matrix Reduction Method

In Chapter 8 Paths, Path Products, and Regular Expressions, we discussed on graphical method based path reduction procedure or simply reduction procedure. Using graphical method we showed how we can derive an ugly path expression from a given flow graph that involved 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 converted 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). In this section, we discuss another way of implementing node reduction algorithm by using the concept of matrix.
Matrix-reduction method is more methodical and less tedious compared to that of node reduction using graphical method.

11.9.1 Some Matrix Properties and Node Reduction Algorithm using Matrix-Reduction Method


Following properties of graph and its equivalent representation in the form of matrix are very important in using Node Reduction Algorithm.

  1. Node Numbering is Arbitrary and Does Not Affect Anything: For a graph, we can give numbers to nodes arbitrarily. Even if this would result in different numbering, the behaviour of the graph and its corresponding program remain intact. Thus, node numbering does not affect anything
  2. Interchanging Node Names in the Matrix: Whenever we wish to interchange node names in the matrix, we must interchange both the corresponding rows and the corresponding columns. Following example provides clarity on this.

Consider the matrix:
Now if we wish to interchange names of nodes 4 and 5 in the graph, we need to first interchange row 4 and 5; once this is done, we shall proceed to interchange columns 4 and 5. This is illustrated as follows:
Step 1: Interchange rows 4 and 5 of the original matrix. By doing this, we arrive at the following:

Step2: Interchange columns 4 and 5 of the abovel matrix. By doing this, we arrive at the following:

These properties play a very important role in Node Reduction Algorithm using Matrix-Reduction Method.

11.9.2 Node Reduction Algorithm using Matrix-Reduction Method

Node Reduction Algorithm using Matrix-Reduction Method involves following steps:
Step 1: Represent a Given Flow Graph in the Form of a Matrix
Step 2: Node Removal and Replacement with Equivalent Links
This step is carried out as follows:
Step 2a: remove all self-loops
Step 2b: Identify parallel links and add them. Replace intersection of start node and end node of this parallel links by equivalent value obtained after addition.
Step 2c: In this step, we select one node for removal at a time and identify equivalent links that bypass that node. Then, we replace the node by equivalent links.
Step 2d: Simplify the path expression so obtained.
Step 2e: Observe loop terms. Adjust the out-links of every node that had a self-loop to account for the effect of the loop.
Step 2f: This would result in a matrix whose size has been reduced by 1.
Step 3: Continue Step 2c to Step 2f until only two nodes of interest are left with.

11.9.3 Illustration Node Reduction Algorithm using Matrix-Reduction Method

Consider the following graph and its corresponding matrix so as to illustrate node reduction algorithm using matrix-reduction method in a step-by-step way:

Step 1: Represent a Given Flow Graph in the Form of a Matrix The corresponding relationship matrix of the given flow graph is:

Steps 2 to 3: Node Removal and Replacement with Equivalent Links
In this step, we select one node for removal at a time and identify equivalent links that bypass that node. Then, we replace the intersection of the node by equivalent links.

Here, first of all we shall remove the node with self-loop. In the given matrix, node 7 has self loop in the form link e. We remove this link by identifying equivalent link ef that bypass that node and connects node 8. By doing this, we arrive at following matrix:
 
 
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