Cyclomatic complexity - Connection matrix

Connection Matrix  - cyclomatic complexity

Each node on the flow graph is identified by numbers, while each edge is identified by letters. A letter entry is made in the matrix to correspond to a connection between two nodes. For example node 3 is connected to node 4 by edge b.to this point, the graph matrix is nothing more than a tabular representation of a flow graph. However by adding a link weight to each matrix entry, the graph matrix can become a powerful tool for evaluating program control structure during testing. The link weight provides additional information about control flow. In its simplest form, the link weight is 1 (a connection exists) or 0(a connection does not exist). To illustrate we use the simplest weighting to indicate connections (0 or 1).

Each letter has been replaced with a 1, indicating that a connection exists (zeros have been excluded for clarity). Represented in this form, the graph matrix is called a connection matrix.

In the connection matrix, each row with two or more entries represents a predicate node. Therefore performing the arithmetic shown to the right of the connection matrix provides us with a method for determining Cyclomatic complexity.

Implementation

The control flow graph can be implemented using the adjacency matrix data structure. The procedure for creating the connection matrix from a control flow graph can be stated as a two dimensional array is declared. Its size is equal to the number of nodes in the flow graph.
construct the adjacency matrix Aij = 1 if there is an edge from node i to node j.
Aij = 0 if there is no edge.

The complexity can be found out from this adjacency matrix using the procedure below.

1. for each row, find out the number of 1’s in it. Sutract 1 from this. Save the result
2. after doing step 1 on all rows, sum the results and add 1. this will give the Cyclomatic complexity.