Software Testing Methodologies Unit V

6. If there are more than a few numbers of states then use hierarchical design to represent
them.
7. If there is large number of states then software tools and programming languages must
be developed.
8. The capability to initialize to an arbitrary state must be inbuilt together with the transition
verification instrumentation.

GRAPH MATRICES AND APPLICATIONS

(1) Motivational Overview:
(1) What are the problems with pictorial graphs?
Problems with pictorial graphs:
1. Tracing a path in a pictorial graph is difficult task.
2. There is every possibility of having an error while tracing i.e. we can miss a link or cover
some links twice.
3. Even yellow marking pen also not be reliable because once the concentration is lost during
marking; we will lose the position to be marked.
4. It is very difficult to generate test cases for a pictorial graph
5. The time is also wasted if pictorial graphs are used.
(2) What are the graph matrices and their applications?
(i) Graph Matrices:
 The matrix in which every node of a graph is represented by one row and one column is
called a graph matrix. or The matrix that represents the structure of a graph is known as
graph matrix.
 In a graph matrix each row and each column intersection represents, the relationship
between the respective row nodes and column nodes.
 A graph is an abstract representation of a software structure.
 A graph can be traced thoroughly to perform a check for covering paths, sensitizing paths,
predicate expressions etc.
 Here we use either pictorial graphs or graph matrices.
 Tracing a path in a pictorial graph is difficult task.
 There is every possibility of having an error while tracing i.e. we can miss a link or cover
some links twice. Even yellow marking pen also not be reliable because once the
concentration is lost during marking; we will lose the position to be marked.
 Graph matrices are introduced to overcome these problems.
 A graph matrix is purely based on matrix methods.
(ii) Applications:
(i) Tool Building:
 Using matrix representation and its methods we construct test tools.
 It is more difficult to generate test cases for a pictorial graph than the graph matrix.
(ii) Doing and understanding testing theory:
 Theoretically speaking, graphs are the simple structures but when used in theorem proving
we use graph matrices because pictorial graphs will omit some important algorithms.
(iii) The Basic Algorithms:
 The basic algorithms represent a basic tool kit. The basic tool kit consists of
1. Matrix multiplication is used to derive the path expression from every node to every other
node.
2. A partitioning algorithm is used for eliminating loops from graphs.
3. A collapsing process is used to get the path expression.
Page 13
Software Testing Methodologies Unit V
(3) Write relative merits and demerits of different Graph Matrix representations?
(i) Merits:
1. Using matrix representation and its methods we construct test tools.
2. Matrix representation gives the best results.
3. Graph matrices are used for developing algorithms and proving theorems of graphs.
4. Linked list representation is used to represent graph matrices.
(ii) Demerits:
1. Graph matrix representation for two dimensional arrays is useful only for small graphs
with simple link weights, however with large graphs; this matrix representation gives
inconvenience.
2. Matrix representation requires a large storage space.
3. An additional weight matrix is also needed.
4. Since many entries of the graph matrices are null, the time taken to process such entries
is a waste of time.
(2) The Matrix of a graph:
(1) Explain about the matrix of a graph?
(i) Basic Principles:
 A graph matrix is array representation of nodes. In a graph matrix each row and each
column intersection represents, the relationship between the respective row nodes and
column nodes.
 Some examples of graphs and their associated matrices are given by.
a a
a
a b a b
1 [0] 1 [a] 1 2 1 2

Figure (a) Figure (b) Figure (c) Figure (d)

3 1 2 3 4
a e c
1 2 3 a b 1 a
b 2 a
1 1 d 2
1 2
2 b+c 3 b
d c
3 c c d 4 d
3 4
Figure (e) Figure (f)
d
1 2 3 4 5
a b c
1 3 4 2 1 a
f 2
e g 3 d b
5 4 c f
h 5 g e h

Figure (f)

Page 14
Software Testing Methodologies Unit V
1 2 3 4 5 6 7 8
1 a i
2
3 b h
h
3 c g 4 j
a b 5 m
m d e f
1 5 6 7 8 2 6 c l d
i l 7 e
j
4 k 8 f k g

Figure (h)
 Now observe the following
1. The size of the matrix is equal to the number of nodes.
2. There is a place to put every link weight between any node and any other node. i.e. The
entry at a row and column intersection is the link weight of the link.
3. A connection from node i to node j does not same that a connection from node j to node
i. For example in figure (h) the (5,6) entry is m but the (6,5) entry is c..
(ii) A simple weight:
 Let ‘1’ means that there is a connection and ‘0’ means that there is no connection.
 The different arithmetic rules are
1+1=1 1+0=1 0+0=0
1x1=1 1x0=0 0x0=0
 A matrix with link weights defined with 1 or 0 is called a connection matrix.
 Consider the following flowgraph and its matrix representation.
1 2 3 4 5 6 7 8
1 1 1 2-1=1
2
3 1 1 2-1=1
1
3 1 1 4 1 1-1=0
1 1 5 1 1-1=0
1 1 e 1
1 5 6 7 8 2 6 1 1 1 3-1=2
1 1 7 1 1-1=0
1
4 1 8 1 1 1 3-1=2

6+1=7
 Each row of a matrix denotes the outlinks corresponding to that node and each column
denotes the inlinks corresponding to that node.
 A branch node is a node with more than one non zero entry in its row. For example rows
1,3,6, and 8 of the above figure have more than one entry, so these nodes are branch
nodes.
 A junction node is a node with more than one non zero entry in its column. For example
columns 5,6 and 7 of the above figure have more than one entry, so these nodes are
junction nodes
 By subtracting 1 from the total number of entries in each row and ignoring rows with no
entries we obtain the number of decisions for each row. Adding these decision values and
then adding 1 to the sum gives the graph’s cyclomatic complexity.
 In the above figure the graph’s cyclomatic complexity is 7.
(iii) Further notation:
 The link weight between node i and node j, is denoted by aij.

Page 15
Software Testing Methodologies Unit V
 A self loop at node i is denoted by a ii The link weight for the link between nodes j and i is
denoted by aji.
 Consider the following figure.
h
3 c g
a b
e
1 5
m 6 d 7 8
f
2
i j l
4 k
 From the above figure
abmd=a13 a35 a56 a67
degef=a67 a78 a87 a78 a82
ahekmlld=a13 a37 a78 a85 a56 a66 a66 a67
 The expression aij ajj ajm denotes that a path from node i to j, with a self loop at j and then a
link from node j to m.
 The transpose of a matrix is the matrix with rows and columns interchanged.
 It is denoted by AT.
 If C=AT then cij=aji
 The intersection of two matrices is denoted by A#B. If C=A # B then cij=aij # bij.
(3) Node Reduction Algorithm:
Write the steps involved in Node Reduction Algorithm. Illustrate with an example?
Node Reduction Algorithm:
Steps:
1. The reduction is done one node at a time by combining the elements in the last column with
the elements in the last row and putting the result into the entry at the corresponding
intersection. This step is called cross-term reduction. After cross term reduction the matrix
size is reduced by one.
2. If there is one entry in one position and we want to enter another entry in that same position
then add that two entries. This step is called parallel reduction.
3. If there is entry in principle diagonal then it represents a self loop. To remove that self loop,
multiply every term in that row by the loop term. This step is called loop reduction.
4. By using the above three steps a 2x2 size matrix is obtained with the path expression. This
path expression is the required path expression from node 1 to node 2.
Example:
 Consider the following flow graph.
d
1 a 3 b 4 c 2

f
e g
5
h
 Specify the above flowgraph in the matrix format.
1 2 3 4 5
1 . a
2 .
3 d . b
4 c . f
5 g e h

Page 16
Software Testing Methodologies Unit V
 Remove the self loop at node 5 by applying the loop reduction step.
1 2 3 4 5
1 . a
2 .
3 d . b
4 c . f
5 h*g h*e .
 Combine the elements in the last column with the elements in the last row by applying
cross-term reduction and parallel reduction steps.
1 2 3 4
1 . a
2 .
3 d . b
4 c+fh*g fh*e .
 Combine the elements in the last column with the elements in the last row by applying
cross-term reduction and parallel reduction steps.
1 2 3
1 . a
2 .
3 d+b(c+fh*g) bfh*e

 Again a self loop occurred at node 3. So Remove the self loop by applying loop reduction
step.
1 2 3
1 . a
2 .
3 (bfh*e)*(d+b(c+fh*g))
 Combine the elements in the last column with the elements in the last row by applying
cross-term reduction.
1 2
.
1 a(bfh*e)*(d+b(c+fh*g))

2 .
Note: Refer other four examples from class notes
(4) Applications:
(1) Illustrate the applications of Node Reduction Algorithm:
(i) Maximum Path Count Arithmetic:
 For theory refer unit-5 material.
 For example refer unit-8 notes.
(ii) Probability of path expressions:
 For theory refer unit-5 material.
 For example refer unit-8 notes.

Page 17
Software Testing Methodologies Unit V

(5) Relations:
(1) What is a Relation? What are the different properties of Relations?
Relation:
 The property by which two nodes are interconnected is called a relation.
 A relation can be represented by a link with connecting nodes.
 A link represented with link weight.
 This link weight can be numerical, logical, illogical, or whatever.
 The graph matrix which consists of unweighted simple links is called a connection matrix
 The graph matrix which consists of weighted simple links is called a relation matrix.
Different properties of relations:
 The different properties of relations are.
(i) Transitive Relations:
 A Relation R is transitive if aRb and bRc then aRc.
 Examples of transitive relations are: is connected to, is greater than or equal to, is less than
or equal to, is a relative of, etc.
 Examples of intransitive relations are: is a friend of, is a neighbor of, etc.

(ii) Reflexive Relations:

 A relation R is reflexive if for every a, aRa. This relation represents a self-loop at every
node.
 Examples of reflexive relations are: equals, is a relative of, etc.
 Examples of irreflexive relations include: not equals, is a friend of, etc.
(iii) Symmetric Relations:
 A relation R is symmetric if aRb then bRa. This relation represents if a link from a to b then
there is also a link from b to a.
 A graph whose relations are symmetric is called an undirected graph and a graph whose
relations are not symmetric is called a directed graph
 Examples of symmetric relations are: a relative of, is brother of, etc.
 Examples of asymmetric relations are: is the boss of, is greater than, etc.
(iv) Antisymmetric Relations:
 A relation R is antisymmetric, if aRb and bRa, then a = b.
 Examples of antisymmetric relations are: is greater than or equal to, is a subset of, etc.
 Examples of nonantisymmetric relations are: is connected to, is a relative of, etc.
(2) What are Equivalence Relations and Partial Ordering Relations?
(i)Equivalence Relations:
 A relation is said to be an equivalence relation if it satisfies transitive, reflexive, and
symmetric properties. If a set of objects satisfy an equivalence relation, then it forms an
equivalence class.
 The idea behind a partition-testing is that we can partition the input space into equivalence
classes.
(ii) Partial Ordering Relations:
 A partial ordering relation satisfies the reflexive, transitive, and antisymmetric properties.
 A graph which shows partial ordering relation between its nodes is said to be partial
ordered graph. Partial ordered graphs have different properties. They are
i. loop free,
ii. There is at least one maximum element.
iii. There is at least one minimum element.

Page 18
Software Testing Methodologies Unit V
iv. If you reverse all the arrows the resultant graph is also partial ordered.
 The maximum element ‘a’ represents the relation xRa. Similarly, the minimum element ‘a’,
represents a relation aRx. Examples are Trees and loop-free graphs.
(6) The Powers of a Matrix:
(i) Explain about Matrix Powers and Products?
Matrix Powers and Products:
 A graph matrix is array representation of nodes. In a graph matrix each row and each
column intersection represents, the relationship between the respective row nodes and
column nodes.
 The square of the matrix represents all path segments with two links long. Similarly the
third power represents all path segments with three links long and so on.
 Let A be a matrix whose entries are aij. The set of all paths between any node i and any
node j is given by
n n n n n n
aij + aik akj + aik akmamj + aikakmaml alj
M

M
M

M
M
M
k=1 k=1 m=1 k=1 m=1 l=1

n n
n n
+... ... aikakmaml . . . aqp apj
M

M
M
M
k=1 m=1 l=1 p=1
 Given a matrix whose entities are aij the square of that matrix is given by
n
aij =
M

aik akj
k=1
 When given two matrices A,B with entries aik and bkj respectively. The product of AB is a
new matrix C whose entries are cij.
n
cij =
M

aik bkj
k=1

a11 a12 a13 a14 b11 b12 b13 b14 c11 c12 c13 c14
a21 a22 a23 c21
a24 x b21 b22 b23 b24 = c22 c23 c24
a31 a32 a33 a34 b31 b32 b33 b34 c31 c32 c33 c34
a41 a42 a43 a44 b41 b42 b43 b44 c41 c42 c43 c44
c11 = a11b11+ a12 b21 + a13 b31 + a14 b41
c12 =a11b12 + a12 b22 + a13 b32 +a14b42
c13 =a11b13+a12 b23 + a13 b33 + a14b43
c32 = a41b12+ a42 b22+a43 b32 + a44 b42
c44 = a41b14 +a42 b24 +a43b34+a44 b44
 The c32 entry is obtained by combining, the entries in the third row of the A matrix, with the
corresponding elements in the second column of the B matrix.
Example:
 Consider the following flowgraph and its graph matrix.
d
1 2 3 4 5
a b c
1 3 4 2 1 a
f 2
e g Let A = 3 d b
5 4 c f
h 5 g e h .
Page 19
Software Testing Methodologies Unit V
A2 = A * A
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
1 a 1 a 1 ad ab
2 2 2
A2 =
3 d b x 3 d b = 3 bc bf
4 c f 4 c f 4 fg fe fh
5 g e h 5 g e h 5 ed+hg he eb h2

A3 = A 2 * A
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
1 ad ab 1 a 1 abc abf
2 2 2
A3 = 3 bc bf x 3 d b = 3 bfg bfe bfh
4 fg fe fh 4 c f 4 fed+fhg fhe feb fh2
5 ed+hg he eb h2 5 g e h 5 hed+ebc+h g h2e heb ebf+h 3
2

(ii) Explain about the set of all paths and the algorithm for finding set of all paths?
(a) The set of all paths:
 The set of all paths is given by the following infinite series of matrix powers.
∞
∑ Ai = A1+A2+A3+…+A∞
i=1
 Let I be an n x n diagonal matrix where n is the number of nodes, then the above
expression becomes
∞
∑ Ai = A(I+A1+A2+A3+…+A∞)
i=1
 We know that (A+A) = A
So (A+I)2 = A2 + 2AI + I2 = A2 + 2A + I2 = A2 + A+A + I2= A2+A+I. (Since A + A = A)

 Similarly
(A+I)n = I+A1+A2+A3+…An
 Now the original expression becomes
∞
∑ Ai = A(I+A1+A2+A3+…+A∞) = A(A+I)∞
i=1
 If the paths of length n-1, where n is the number of nodes, the set of all such paths is

n-1
∑ Ai = A(A+I)n-2
i=1
(b) The algorithm for finding set of all paths:
 The algorithm for finding set of all paths
1. Express n-2 as a binary number.
2. Calculate the successive squares of (A+I) matrix, that is (A+I)2, (A+I)4, (A+I)8, (A+I)16
and so on.
3. Select only the binary powers of (A+I) matrix that correspond to a value 1 in the binary
representation of (n-2).
4. The set of all paths of length less than or equal to (n-1) is obtained from the original
matrix as a result of step 3.
Page 20
Software Testing Methodologies Unit V
 For example the set of all paths for 16 nodes is given by
15
∑ Ai = A(A+I)8(A+I)4(A+I) 2
i=1
 A matrix for which A2=A is said to be idempotent matrix. A matrix whose successive power
gives an idempotent matrix is called idempotent generator. The n th power of a matrix A + I
over a transitive relation is called the transitive closure of the matrix.
(iii) What are the loops? How to convert graphs with loops into loop-free graphs:
 Loops are infinite sum of matrix powers.
 The way to handle loops is similar like handling loops in regular expressions.
 Loop terms are displayed on the principle diagonal of the graph matrix. A loop can be
removed from a graph by using loop reduction step of Node Reduction Algorithm.
Example:
 Consider the following flowgraph and its graph matrix
d
1 2 3 4 5 1 2 3 4 5
a b c
1 3 4 2 1 a 1 1 a
f 2 2 1
e g Let A = 3 d b A+I= 3 d 1 b
5 4 c f 4 c 1 f
h 5 g e h 5 g e h+1

 In (A+I) matrix there is a self loop at node 5. Now we can obtain (A+I)* after removing the
self loop at node 5 by applying loop reduction step.
 i.e. To remove self loop at node 5 multiply loop term h* with all row elements of row 5.
1 2 3 4 5
1 1 a
2 1
(A+I)* = 3 d 1 b
4 c 1 f
5 h*g h*e 1

(A+I)2* = (A+I)* (A+I)*

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
1 1 a 1 1 a 11 ad a ab
2 1 2 1 2 1
= 3 d 1 b x3 d 1 b = 3 d+bc 1 b bf
4 c 1 f 4 c 1 f 4 c+fh*g fh*e 1 f
5 h*g h*e 1 5 h*g h*e 1 5 h*g+h*ed h*e h*eb 1

(A+I)3* = (A+I)2* (A+I)* 1 2 3 4 5

1 2 3 4 5 1 2 3 4 5 1 1 ad+abc a ab abf
1 1 ad a ab 1 1 a 2 1
2 1 2 1 3 d+bc+ 1+ b bf
= 3 d+bc 1 b bf x 3 d 1 b = bfh*g bfh*e
4 c+fh*g fh*e 1 f 4 c 1 f c+fh*g+ 1+
5 h*g+h*ed h*e h*eb 1 h*g h*e
4
fh*ed fh*e fh*eb f
5 1
5 h*g+h*ed 1+
+h*e(d+bc) h*e h*eb h*ebf
 No new loops were found for the second power matrix
Page 21
Software Testing Methodologies Unit V
 But the third power matrix has a loop term bfh*e at node 3. So all other entries in that row
are multiplied by (bfh*e)*. Similarly there is a loop term (fh*eb) at node 4.
 So all other entries in that row are multiplied by (fh*eb)*. Also a loop term (h*ebf)* at
node 5.
 So all other entries in the fifth row is multiplied by (h*ebf)*
(iv) Explain about Partitioning Algorithm in detail?
Partitioning Algorithm:
 It is an algorithm which is used to transform the graphs with loops into loop free graphs.
 There are certain points to remember here. They are
1. A graph is loop free at the top level.
2. Many graphs with loops are easy to analyze, if you know where to break the loops.
3. This algorithm is used to develop a tool which can identify the loops.
 The partition algorithm represents.
(A+I)n # (A+I)nT
Example:
 Consider the following flowgraph and its graph matrix (A + I).
1 1 2 3 4 5 6 7 8
1 1 1
2 7 2 1 1 1
8 3 1 1
3 4 1 1 1
A+I =
5 5 1 1
4 6 1
7 1 1 1
6 8 1 1

 The transitive closure matrix (A+I) n can be obtained by using the following steps.
Step:1: Mark all diagonal entries by 1
Step:2: The flow from node 1 to node 6 is 1-2-7-2-3-4-5-3-4-6
So mark nodes 1,2,3,4,5,6,7 by 1 in the first row
Step:3: The flow from node 2 to node 6 is 2-7-2-3-4-5-3-4-6
So mark nodes 2,3,4,5,6 by 1 in the second row.
Step:4: The flow from node 3 to node 6 is 3-4-5-3-4-6.
So mark nodes 3,4,5,6 by 1 in the third row
Step:5: The flow from node 4 to node 6 is 4-5-3-4-6.
So mark nodes 3,4,5,6 by 1 in the fourth row
. Step:6: The flow from node 5 to node 6 is 5-3-4-6.
So mark nodes 3,4,5,6 by 1 in the fifth row.
Step:7: The flow from node 6 is only 6. So mark node 6 by 1 in the sixth row.
Step:8: The flow from node 7 to node 6 is 7-2-3-4-5-3-4-6
So mark nodes 2,3,4,5,6,7 by 1 in the seventh row
. Step:9: The flow from node 8 to node 6 is 8-3-4-5-3-4-6
So mark nodes 3,4,5,6,8 by 1 in the eighth row

Page 22
Software Testing Methodologies Unit V
 Therefore the transitive closure matrix is.
1 2 3 4 5 6 7 8
1 1 1 1 1 1 1 1
2 1 1 1 1 1 1
3 1 1 1 1
n 4 1 1 1 1
(A+I) =
5 1 1 1 1
6 1
7 1 1 1 1 1 1
8 1 1 1 1 1

 The transpose of (A+I) is. n

1 2 3 4 5 6 7 8
1 1
2 1 1 1
3 1 1 1 1 1 1 1
nT
(A+I) = 4 1 1 1 1 1 1 1
5 1 1 1 1 1 1 1
6 1 1 1 1 1 1 1 1
7 1 1 1
8 1

 The intersection of transitive closure matrix (A+I) n and transpose matrix (A+I)nT is given by,
identifying similar rows and column entries from (A+I)n and (A+I)nT
1 2 3 4 5 6 7 8
1 1
2 1 1
3 1 1 1
4 1 1 1
(A+I) n#(A+I) nT= 5 1 1
1
6 1
7 1 1
8 1
 From the above matrix, by comparing a row/column with other rows/columns, the
equivalent nodes to be grouped.
 After grouping
Let A=[1] B=[2,7] C=[3,4,5] D=[6] E=[8]
 The graph and graph matrix representation to the above values is given by
FlowGraph .
1
A
Graph Matrix

2,7 A B C D E
B A 1 1
8
B 1 1
E
C 1 1
3,4,5
D 1
C
E 1 1

6
D

Page 23
Software Testing Methodologies Unit V
(v) Explain about Breaking Loops And Applications:
 Consider the matrix format of a flowgraph.
 If there are any entries on the principal diagonal, then break the loop for that link.
 Here we use successive powers of the matrix.
 Another way to break the loop is applying the node reduction algorithm.
 Here we break the loop or we remove the self loop at any node is, by multiplying loop term
with all other entries in that corresponding row.
(vi) Explain about Some matrix properties?
 To interchange the node names in the flowgraph, we must interchange both the
corresponding rows and the corresponding columns of the node names in the graph matrix.
 Consider the following flowgraph and its Graph matrix.
d 1 2 3 4 5
a 3 b 4 c
1 2 1 a
f 2
e g 3 d b
5 4 c f
h 5 g e h

 Interchange rows 3 and 4 to the above graph matrix.

1 2 3 4 5
1 a
2
3 c f
4 d b
5 g e h
 Interchange columns 3 and 4 to the above graph matrix.
1 2 3 4 5
1 a
2
3 c f
4 d b
5 g e h
 The flowgraph to the above graph matrix is given by.
d
a b c
1 4 3 2
f
e g
5
h
 By comparing the above flowgraph with the given flowgraph, it is proved that nodes 3,4 are
interchanged

Page 24
Software Testing Methodologies Unit V
(7) Building Tools:
Explain about building tools of graph matrices?
i. Matrix Representation in software:
 A graph is an abstract representation of the software structure.
 Theoretically speaking, graphs are the simple structures but when used in theorem proving
we have to apply graph matrices.
 It consists of
a) Overview:
 We prove theorems and develop graph algorithms by using graph matrices. When we
want to process graphs in a computer we represent them as linked lists.
b) Node degree and graph density:
 Each intermediate node may have any number of inner links and outer links.
 The inner links of a node represents the in degree of the node.
 Similarly the outer links of a node represents the out degree of a node.
 The sum of in degree and out degree of a particular node is the degree of that node.
 The average degree of a node for a graph is between 3 and 4.
 The degree of a simple branch and simple junction is 3.
 The degree of a loop in a graph is 4.
 Any graph with average degree of 5 or 6 is said to be a very busy flowgraph.
c) What is wrong with arrays:
 We can represent the matrix as a two-dimensional array for small graphs with simple
weights, but this is not convenient for larger graphs because
(i) Space:
 Matrix representation requires a large storage space.
 Hence a linked list representation is used which requires less storage space.
(ii) Weights:
 An additional weight matrix is required for complicated link weights.
(iii) Variable-Length Weights:
 The link weights in a flow graphs are represented in a two dimensional string array
(matrix format), in which most of entries are null.
(iv) Processing time:
 Since many entries of the graph matrices are null, the time taken to process such
entries are more.
d) Linked-list Representation:
 Consider following the flowgraph.

d
a b c
1 3 4 2
f
e g
5
h
 The linked list for the above flowgraph is

Page 25
Software Testing Methodologies Unit V
1,3;a
2,exit
3,2;d
3,4;b
4,2;c
4,5;f
5,2;g
5,3;e
5,5;h
 List entries are usually placed in lexicographic (dictionary) order.
 The link weight expressions are stored in a string array to which link names act as
pointers.
 If the link weights are values then, they are stored in an array of fixed length.
List Entry Content
1 node 1,3;a
2 node 2,exit
3 node 3,2;d
,4;b
4 node 4,2;c
,5;f
5 node 5,2;g
,3;e
,5;h
 The node names appear only once, at the first link entry. A node name i.e starting node
is used for the list entry.
 And there are back pointers for the inlinks. So we get
List Entry Content List Entry Content
1 node 1,3;a 4 node 4,2;c
2 node 2,exit ,5;f
3, 3,
4, node 5,2;g
5
5, ,3;e
3 node 3,2;d ,5;h
,4;b
4,
1, 5,
5,
 It is important to keep the lists sorted in lexicographic order with the following priorities:
node names or pointer outlink names, inlink names.
2. Matrix Operations:
a) Parallel Reduction:
 Parallel links after sorting are adjacent entries with the same pair of node names. Ex:
y
node 17,21;x
x z ,44;y
21 17 44
w ,44;z
,44;w
 We have three parallel links from node 17 to 44. So

Page 26
Software Testing Methodologies Unit V
Node 17,21;x
,44;y(where y=y+z+w)
b)Loop Reduction:
 The loop reduction step is used to remove the loop. Here self link represents the loop.
 For removing a loop, the loop term is multiplied with all the outer links of the node at
which the loop presents. Consider the following example.
d
a b c List Entry Content Before Content After
1 3 4 2
5 node 5,2;g node 5,2;h*g
f ,3;e
e g ,3;h*e
,5;h
5 4, 4,
h 5,
c) Cross term reduction:
 Select a node for reduction.
 The cross term reduction represents that we combine every inlink to the node with every
outlink from that node after removing that node.
 The links created by node removal are stored in a separate list which is then sorted and
thereafter merged into the master list.
d) Addition, Multiplication and other operations:
 Here addition of two matrices is simple. Multiplication is more complicated.
 Transposition is done by reversing the pointer directions, resulting in a list that is not
correctly sorted. Sorting that list provides the transpose. All other matrix operations can
be easily implemented by sorting, merging, and combining parallels.
List Entry Content Before Content After
d
2 node 2,exit node 2,exit
1 a 3 b 4 c 2
3, 3,
f 4, 4,
e g 5, 5,
5 3 node 3,2;d node 3,2;d
h ,4;b ,2;bc
,5;bf
1, 1,
5, 5,
4 node 4,2;c
,5;f
3,
5 node 5,2;h*g node 5,2;h*g
,3;h*e ,3;h*e
4,
3. Node Reduction Optimization:
 The optimum order for node reduction is to do lowest-degree nodes first. The idea is to get
the lists as short as possible as quickly as possible. Nodes of degree 3 reduce the total link
count by one link when removed. A degree-4 node keeps the link count the same, and all
higher-degree nodes increase the link count.
 For large graphs with 500 or more nodes and an average degree of 6 or 7, the difference
between not optimizing the node-reduction order and optimizing it was about 50: 1 in
processing time.
Page 27
Software Testing Methodologies Unit IV

UNIT –IV
SOFTWARE TESTING TOOLS
(1) Introduction to Testing-Automated Testing:
 Automated Testing means using an automation tool executing the test case suite. Manual
Testing is performed by a human sitting in front of a computer carefully executing the test steps.
 The automation software can also enter test data into the System. Now compare expected and
actual results and generate detailed test reports. Test Automation demands considerable
investments of money and resources.
 Successive development cycles will require execution of same test suite repeatedly. Using a test
automation tool, it's possible to record this test suite and re-play it as required. Once the test suite
is automated, no human test is required.
 This improve ROI (Return On Investment) of Test Automation. The goal of Automation is to
reduce the number of test cases to be run manually and not to eliminate Manual Testing.
(2) Concepts of Test Automation:
(i) Test Automation
 Automated Software Testing or Test Automation is the process of automating the manual test
cases. This also involves comparing the run time data with the test data provided, and producing
useful Test Results.
(ii) Test Automation tool – What we can expect
 To test a software, a manual testing engineer needs to do the following basic actions:
1. Click a button, link, image
2. Select radio button
3. Check / Uncheck a checkbox
4. Type into an Edit box or controls which resemble edit box
 But also he needs to get the run time data from the application and compare with the test data
provided (i.e. checkpoints). For this actually, we will be extracting the values from an edit box,
button, link, image, table, drop down list, etc.
 All of these basic features are provided by Test Automation tools such as QTP(Quick Test
Professional). There are many test automation tools which allow users to record user actions
and replay them any number of iterations and compare the actual results with the test data and
generate results.
(iii) Why Test Automation?
 Since the very large quantity of software development tools available in the market the
productivity of the developer is dramatically increased over the past years.
 To manage the quality of the product developed it is essential to thoroughly test all the features of
the application.
 If the application is a large software product having lot of features, then it is very much difficult to
test by manually executing the test cases.
 There will be a lot of pressure on testing team to test more and more functionalities in less
time. Hence, the Automation Testing has become an integral part of software development.
(iv) Benefits of Test Automation:
(a) Execution is Less Time Consuming:
 Automated tools execute the test cases (test script) faster than manual test case execution.
 Hence, in less time, more end-to-end test cases can be covered during test execution.
(b) Un-attended mode execution:

Page 1
Software Testing Methodologies Unit IV
 There is no need of human involvement for the execution of entire Test Automation Suite for
regression testing. But, to achieve the unattended mode execution, the automation framework
has to be properly designed.
(c) Repeatable:
 The test suite can be executed multiple times on the application under test.
 For example, if there is a need to test the application on different browsers and environments, we
need to just change the configurations of the test automation suite and execute.
 In case of manual execution, we would need one more resource to execute the same set of test
cases on different environment / browser.
(d) Reusability:
 The test suite can be built in such a way that the functions or methods written are highly reusable
across the framework. Also, the entire test suite built with a proper framework can also be utilized
for different versions of the application under test.
(e) Consistency of Test Execution:
 There is a chance of manual tester making errors during execution of test cases. But, the test
suite being automated we can expect no or zero errors during execution.
 For example, if there is a need to enter a value in an edit box such as 7693178.87651, a manual
tester might make mistakes (as this is a big number with five decimal values) but the automation
tool will not make any mistakes. It will enter the same value even if the test is run for many times.
(f) Better Coverage:
 As the time required executing automated test suite will be less compared to manual test case
execution, more number of test scenarios can be covered during the execution.
 Hence, we can expect better coverage.
(g) Cost Effective:
 Once the test suite is completely ready for regression testing, the resources required will be less
compared to manual test execution. This reduces the cost of testing.
(v) Key factors to be considered in Test Automation:
(a) Test automation is expensive
 It involves testing tools as well as skilled professionals.
(b) Size of the Regression Test Suite:
 Generally, a recommendation is made for test automation if there is a long regression cycle.
(c) Tool compatibility:
 Test Automation tool has to be compatible with the application under test.
 A comprehensive tool evaluation has to be conducted and a best suited tool should be
recommended for automation testing.
(d) No. of Regression Cycles:
 If there is a need to execute the automated test suite against many builds / releases then the test
automation becomes cost effective and beneficial.
(3) Introduction to list of tools like Win runner, Load Runner & JMeter:
(i) Win Runner:
 Win Runner is the most used Automated Software Testing Tool.
 Main Features of Win Runner are
•Developed by Mercury Interactive
•Functionality testing tool
•Supports o/s and web technologies
•To Support .net, xml, SAP, Multimedia etc we can use QTP.
• Winrunner run on Windows only.
•Xrunner run only UNIX and linux.
•Tool developed in C on VC++ environment.

Page 2
Software Testing Methodologies Unit IV
•To automate our manual test win runner used TSL (Test Script language like c)
The main Testing Process in Win Runner is
1) Learning
 Recognization of objects and windows in our application by winrunner is called learning.
2) Recording
 Winrunner records over manual business operation in TSL
3) Edit Script
 Depends on corresponding manual test, test engineer inserts check points in to that record script.
4) Run Script:
 During test script execution, winrunner compare tester given expected values and application
actual values and returns results.
5) Analyze Results
 Tester analyzes the tool given results to concentrate on defect tracking if required.
(ii) Load Runner:
 LoadRunner is a software testing tool from Micro Focus.
 It is used to test applications, measuring system behaviour and performance under load.
 LoadRunner can simulate thousands of users concurrently using application software, recording
and later analyzing the performance of key components of the application.
 The components of LoadRunner are The Virtual User Generator, Controller, and the Agent
process, LoadRunner Analysis and Monitoring, LoadRunner Books Online.
 The Component of LoadRunner would you use to record a Script is the Virtual User Generator
(VuGen) component .
 LoadRunner copy hundreds or thousands of human users with Virtual Users (Vusers) to apply
measurable & repeatable production workloads and stresses an Application end-to-end.
 Vusers copy the actions of human users by performing typical Business Processes.
 For each user action, the tool submits an input request to server and receives the response.
 Increase number of Vusers, to increase the load on the Server.
(iii) Jmeter:
 The Apache JMeter is pure Java open source software, which was first developed by Stefano
Mazzocchi of the Apache Software Foundation, designed to load test functional behavior and
measure performance. You can use JMeter to analyze and measure the performance of web
application or a variety of services.
 Apache JMeter is a testing tool used for analyzing and measuring the performance of different
software services and products. It is a pure Java open source software used for testing Web
Application or FTP application. It is used to execute performance testing, load testing and
functional testing of web applications.
 First JMeter can be integrated into selenium using the plugins, So Selenium you can use as
an automation tool for your testing needs. The Apache JMeter is pure Java open source
software, designed to load test functional behavior and measure performance.
 JMeter is an open source desktop Java application that is designed to load test and measure
performance. It can be used to simulate loads of various scenarios and output performance data
in several ways, including CSV and XML files, and graphs.
 Apache JMeter is one of the most popular open source systems for testing applications, and also
a 100% Java scripted desktop application.
(4) About Win Runner:
 WinRunner is a test automation tool, designed to help customers save testing time and effort by
automating the manual testing process. Automated testing with WinRunner addresses the
problems by manual testing, speeding up the testing process

Page 3
Software Testing Methodologies Unit IV
 WinRunner uses the GUI Map file to recognize objects on the application. When WinRunner runs
a test, it uses the GUI map to locate objects. It reads an object's description in the GUI map and
then looks for an object with the same properties in the application being tested
(5) Using Win runner:
 After installing the WinRunner on your computer, invoke the WinRunner application:
Start -> Programs ->WinRunner ->WinRunner
 The opening screen of the WinRunner application is displayed, prompting you to select one of the
three options:
New Test: To create a new test script
Open Test: To open an existing test script
Quick Preview: To view the quick preview of WinRunner

(6) Recording Test Cases

 To test any application, first you can run the application and understand its operation. Then, you
can invoke WinRunner, again run the application and record the GUI operations.
 During the recording mode, WinRunner will capture all your actions, which button you pressed,
where you clicked the mouse etc. You need to work with the application as usual and perform all
the actions to be tested.
 Once the recording is completed, WinRunner generates a script in TSL (Test Script Language).
You can run this test script generated by WinRunner to view the results. The test results will
show whether the test has passed or failed.
 There are two modes of recording:
(i) Context Sensitive mode:
 This mode of recording is used when the location of the GUI controls (i.e. X and Y coordinates)
or the mouse positions are not necessary.

Page 4
Software Testing Methodologies Unit IV
(ii) Analog mode:
 This mode of recording is used when the mouse positions, the location of the controls in the
application, also play an important role in testing the application. This mode of recording has to
be used to validate bitmaps, testing the signature etc.
 The procedure for recording a test case is as follows:
Step 1: Open a new document: File -> New (or) Select "New Test"
from the WinRunner's Welcome screen.
Step 2: Open (run) the application to be tested.
Step 3: Start recording a test case.
Create ->Record - Context Sensitive (or) click on the toolbar's "Record" button once, to record in
Context Sensitive mode.
Step 4: Select the application to be tested by clicking on the application's title bar.
Step 5: Perform all the actions to be recorded.
Step 6: Once all required actions are recorded, stop the recording.
Create -> Stop (or) Click on the toolbar's "Stop" button to stop the recording WinRunner
generates the script for the recoded actions.
Mapping the GUI,
 When WinRunner runs a test, it uses the GUI map to locate objects. It reads an object's
description in the GUI map and then looks for an object with the same properties in the
application being tested. Each of these objects in the GUI Map file will be having a logical name
and a physical description.
 There are two views in the GUI Map Editor, which enable you to display the contents of either:
(i) the entire GUI map
(ii) an individual GUI map file
(i) the entire GUI map
 When viewing the contents of specific GUI map files, you can expand the GUI Map Editor to view
two GUI map files simultaneously. This enables you to easily copy or move descriptions between
files.
 To view the contents of individual GUI map files, choose View GUI Files.
(ii) an individual GUI map file
 In the GUI Map Editor, objects are displayed in a tree under the icon of the window in which they
appear. When you double-click a window name or icon in the tree, you can view all the objects it
contains. To concurrently view all the objects in the tree, choose View Expand Objects Tree. To
viewwindows only, choose ViewCollapse Objects Tree.
 When you view the entire GUI map, you can select the Show Physical Description check box to
display the physical description of any object you select in the Windows/Objects list.
 When you view the contents of a single GUI map file, the GUI Map Editor automatically displays
the physical description.
 Suppose the WordPad window is in your GUI map file. If you select Show Physical
Description and click the WordPad window name or icon in the window list, the following
physical description is displayed in the middle pane of the GUI Map Editor:
(7) Working with Test:
 WinRunner facilitates easy test creation by recording how you work on your application. As you
point and click GUI (Graphical User Interface) objects in your application, WinRunner generates
a test script in the C-like Test Script Language (TSL).
 You can further enhance your test scripts with manual programming.
 User can create tests using recording or programming or by both. While recording, each
operation performed by the user generates a statement in the Test Script Language (TSL).

Page 5
Software Testing Methodologies Unit IV
 These statements are displayed as a test script in a test window. User can then enhance the
recorded test script, either by typing in additional TSL functions and programming elements or by
using WinRunner’s visual programming tool, the Function Generator, or using the Function
Viewer.
(8) Checkpoints:
 Checkpoints allow user to compare the current behavior of the application being tested to its
behavior in an earlier version. If any mismatches are found, WinRunner captures them as actual
results.
 User can add four types of checkpoints to test scripts they are
(i)GUI Checkpoints
(ii)Bitmap Checkpoints
(iii)Text checkpoints
(iv)Database checkpoints
(i) GUI checkpoints
 It verifies information about GUI objects. For example, user can check that a button is enabled or
see which item is selected in a list. There are three types of GUI Check points they are
(a)For Single Property
(b)For Object/Window
(c)For Multiple Objects
(a) GUI checkpoint for single property:-
 User can check a single property of a GUI object. For example, user can check whether a button
is enabled or disabled or whether an item in a list is selected.
(b) GUI checkpoint for object/window:-
 User can create a GUI checkpoint to check a single object in the application being tested.
 User can either check the object with its default properties or user can specify multiple properties
to check.
(c) GUI checkpoint for multiple objects:-
 User can create a GUI checkpoint to check multiple objects in the application being tested. User
can either check the object with its default properties or user can specify multiple properties of
multiple objects to check.
(ii) Bitmap Checkpoint :
 It checks an object, a window, or an area of a screen in the application as a bitmap. While
creating a test, user can indicate what user want to check. WinRunner captures the specified
bitmap, stores it in the expected results folder (exp) of the test, and inserts a checkpoint in the
test script. While running the test, WinRunner compares the bitmap currently displayed in the
application being tested with the expected bitmap stored earlier.
 In the event of a mismatch, WinRunner captures the current actual bitmap and generates a
difference bitmap. By comparing the three bitmaps (expected, actual, and difference), user can
identify the nature of the discrepancy there are two types of bitmap check points they are
(a) Bitmap Checkpoint for Object/Window: -
 User can capture a bitmap of any window or object in the application by pointing to it.
(b) Bitmap Checkpointfor Screen Area:-
 User defines any rectangular area of the screen and captures it as a bitmap for comparison.
(iii) Text checkpoints
 It reads and check text in GUI objects and in areas of the screen. While creating a test user has
to point to an object or a window containing text. WinRunner reads the text and writes a TSL
statement to the test script.
 Later user can add simple programming elements to test scripts to verify the contents of the text.
User should use a text checkpoint on a GUI object only when a GUI checkpoint cannot be used
Page 6
Software Testing Methodologies Unit IV
to check the text property. There are two types of Text checkpoints they are
From Object/Window
From Screen Area
(iv) Database checkpoints
 It checks the contents and the number of rows and columns of a result set, which is based on a
query user, create on database. There are three types of database check points they are
(a) Default Check:-
 Used to check the entire contents of a result set, Default Check are useful when the expected
results can be established before the test run.
(b) Custom Check:-
 Used to check the partial contents, the number of rows, and the number of columns of a result
set.
(c) Runtime Record Check:-
 User can create runtime database record checkpoints in order to compare the values displayed in
the application during the test run with the corresponding values in the database.
(9) Test Script Language & Enhancing Test
 TSL stands for “Test Scripting Language”. The test scripts are written in Test Scripting Language
in winrunner. TSL is an enhanced, C-like programming language designed for testing.
 The advantages of TSL are:
It is easy to use.
It is similar to other programming languages. ...
It is a high level language.
 When you record a test, a test script is generated in Mercury Interactive’s Test Script Language
(TSL). Each line WinRunner generates in the test script is a statement.
 A statement is any expression that is followed by a semicolon. Each TSL statement in the test
script represents keyboard and/or mouse input to the application being tested. A single statement
may be longer than one line in the test script.
 TSL is a C-like programming language designed for creating test scripts. It combines functions
developed specifically for testing with general purpose programming language features such as
variables, control-flow statements, arrays, and user-defined functions. You enhance a recorded
test script simply by typing programming elements into the test window, If you program a test
script by typing directly into the test window, remember to include a semicolon at the end of each
statement.
 TSL is easy to use because you do not have to compile. You simply record or type in the test
script and immediately execute the test.
 TSL includes four types of functions:
 Context Sensitive functions perform specific tasks on GUI objects, such as clicking a button
or selecting an item from a list. Function names, such as button_press andlist_select_item,
reflect the function’s purpose.
 Analog functions depict mouse clicks, keyboard input, and the exact coordinates traveled by
the mouse.
 Standard functions perform general purpose programming tasks, such as sending messages
to a report or performing calculations.
 Customization functions allow you to adapt WinRunner to your testing environment.
 WinRunner includes a visual programming tool which helps you to quickly and easily add TSL
functions to your tests. For more information, see “Generating Functions.”
 This chapter introduces some basic programming concepts and shows you how to use a few
simple programming techniques in order to create more powerful tests. For more information,
refer to the following documentation:

Page 7
Software Testing Methodologies Unit IV

(10) Running and Debugging Tests

(i) Create Tests
 Next, you create test scripts by recording, programming, or a combination of both. While
recording tests, insert checkpoints where you want to check the response of the application being
tested. You can insert checkpoints that check GUI objects, bitmaps, and databases.
 During this process, WinRunner captures data and saves it as expected results—the expected
response of the application being tested.
(ii) Debug Tests
 You run tests in Debug mode to make sure they run smoothly. You can set breakpoints, monitor
variables, and control how tests are run to identify and isolate defects.
 Test results are saved in the debug folder, which you can discard once you’ve finished debugging
the test.
 When WinRunner runs a test, it checks each script line for basic syntax errors, like incorrect
syntax or missing elements in If, While, Switch, and For statements.
 You can use the Syntax Check options (Tools Syntax Check) to check for these types of syntax
errors before running your test.
(iii) Run Tests
 You run tests in Verify mode to test your application. Each time WinRunner encounters a
checkpoint in the test script, it compares the current data of the application being tested to the
expected data captured earlier.
 If any mismatches are found, WinRunner captures them as actual results.
(11) Analyzing Results:
 After you run a test, you can view the results in the Test Results window. The appearance of this
window depends on the Report View option you select in the Runcategory of the General
Options dialog box.
 There are two types of Test Results Views:
(i) WinRunner report view
 Displays the test results in a Windows-style viewer.
 If you run a test that includes a call to a QuickTest test, the WinRunner report view displays only
basic information about the results of the QuickTest test.
 When running tests that call QuickTest tests, it is recommended to use the Unified report view.
(ii) Unified report view
 Displays the results in an HTML-style viewer.
 The unified TestFusion report viewer is identical to the style used for QuickTest Professional test
results.
 If you run a test that includes a call to a QuickTest test (version 6.5 or later), the unified report
view enables you to view detailed results of each step in the called QuickTest test.
 Regardless of the selected report view, the test results window always contains a description of
the major events that occurred during the test run, such as GUI, bitmap, or database
checkpoints, file comparisons, and error messages. It also includes tables and pictures to help
you analyze the results.
(12) Batch Tests,
 A batch test is a test script that calls other tests.
 You program a batch test by typing call statements directly into the test window and selecting the
Run in batch mode option in the Run category of the General Options dialog box before you
execute the test.

Page 8
Software Testing Methodologies Unit IV
 A batch test is a test script that calls other tests. You program a batch test by typing call
statements directly into the test window and selecting the Run in batch mode option in
the Run category of the General Options dialog box before you execute the test.
 A batch test may include programming elements such as loops and decision making statements.
Loops enable a batch test to run called tests a specified number of times.
 Decision-making statements such as if/else and switch condition test execution on the results of
a test called previously by the same batch script.
 See “Enhancing Your Test Scripts with Programming,” for more information.
 You execute a batch test in the same way that you execute a regular test.
 Choose a mode (Verify, Update, or Debug) from the list on the toolbar and choose Test > Run
from Top. See “Understanding Test Runs,” for more information.
 When you run a batch test, WinRunner opens and executes each called test. All messages are
suppressed so that the tests are run without interruption.
 If you run the batch test in Verify mode, the current test results are compared to the expected
test results saved earlier.
 If you are running the batch test in order to update expected results, new expected results are
created in the expected results folder for each test.
 See “Storing Batch Test Results” below for more information. When the batch test run is
completed, you can view the test results in the Test Results window.
 Note that if your tests contain TSL texit statements, WinRunner interprets these statements
differently for a batch test run than for a regular test run. During a regular test
run, texit terminates test execution.
 During a batch test run, texit halts execution of the current test only and control is returned to the
batch test.
(13) Rapid Test Script Wizard
 The Rapid test script wizard is the fastest way of performing the test process. It systematically
opens up all the windows in the application, stores the learnt information in the GUI Map file and
generates the test cases based on the information learnt from the application.
 It is possible to apply these tests only on those applications, which open windows upon
performing some task (like clicking a button, selecting the menu item etc). Let us apply this
wizard on the Calculator application whose GUI is shown in Figure.

Page 9