
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 selfloops 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.
Matrixreduction 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 MatrixReduction Method

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


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

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 MatrixReduction Method.

11.9.2 Node Reduction Algorithm using MatrixReduction Method

Node Reduction Algorithm using MatrixReduction 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 selfloops
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 outlinks of every node that had a selfloop 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 MatrixReduction Method

Consider the following graph and its corresponding matrix so as to illustrate node reduction algorithm using matrixreduction method in a stepbystep 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 selfloop. 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: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 
