Flow graph is an effective aid in path testing. However, path tracing with the use of flow graphs may be a cumbersome and time consuming activity. As the size of graph increases, manual path tracing becomes difficult and leads to errors. A link can be missed or covered twice. So the idea is to develop a software tool, which will help in basis path testing.

Graph matrix, a data structure, is the solution that can assist in developing a tool for automation of path tracing because the properties of graph matrices are fundamental to test tool building. Moreover, testing theory can be explained on the basis of graphs. Graph theorems can be proved easily with the help of graph matrices. So graph matrices are very useful for understanding the testing theory.

1. Graph Matrix

A graph matrix is a square matrix whose rows and columns are equal to the number of nodes in the flow graph. Each row and column identifies a particular node and matrix entries represent a connection between the nodes.

The following points describe a graph matrix:

• Each cell in the matrix can be a direct connection or link between one node to another node.
• If there is a connection from node 'a' to node 'b', then it does not mean that there is connection from node 'b' to node 'a'.
• Conventionally, to represent a graph matrix, digits are used for nodes and letter symbols for edges or connections.

2. Connection Matrix

Till now, we have learnt how to represent a flow graph into a matrix representation. However, this matrix is just a tabular representation and does not provide any useful information. If we add link weights to each cell entry, then graph matrix can be used as a powerful tool in testing. The links between two nodes are assigned a link weight, which becomes the entry in the cell of matrix. The link weight provides information about control flow.

In the simplest form, when the connection exists, then the link weight is 1 , otherwise 0 (but 0 is not) entered in the cell entry of matrix to reduce the complexity). A matrix defined with link weights is called a connection matrix.

3. Use of Connection Matrix in Finding Cyclomatic Complexity Number

Connection matrix is used to see the control flow of the program. Further, it is used to find the cyclomatic complexity number of the flow graph. Given below is the procedure to find the cyclomatic number from the connection matrix:

Step 1: For each row, count the number of 1 $\mathrm{s}$ and write it in front of that row.

Step 2:Subtract 1 from that count. Ignore the blank rows, if any.

Step 3: Add the final count of each row.

Step 4: Add 1 to the sum calculated in Step 3.

Step 5: The final sum in Step 4 is the cyclomatic number of the graph.

4. Use of Graph Matrix for Finding Set of All Paths

Another purpose of developing graph matrices is to produce a set of all paths between all nodes. It may be of interest in path tracing to find k-link paths from one node. For example, how many 2-link paths are there from one node to another node? This process is done for every node resulting in the set of all paths. This set can be obtained with the help of matrix operations. The main objective is to use matrix operations to obtain the set of all paths between all nodes. The set of all paths between all nodes is easily expressed in terms of matrix operations.

The power operation on matrix expresses the relation between each pair of nodes via intermediate nodes under the assumption that the relation is transitive (mostly, relations used in testing are transitive). For example, the square of matrix represents path segments that are 2 -links long. Similarly, the cube). power of matrix represents path segments that are 3 -links long.

Generalizing, we can say that mth power of the matrix represents path segments that are m-links long.