Graph Theory | Cyclomatic complexity

What is Graph Matrix?

• A graph matrix is a square matrix whose size represents the number of nodes in the control flow graph. 

• Each row and column in the matrix identifies a node and the entries in the matrix represent the edges or links between these nodes.

• Conventionally, nodes are denoted by digits, and edges are denoted by letters.

Example:

Graph Examples

Since the graph has 4 nodes, so the graph matrix would have a dimension of 4 X 4. Matrix entries will be filled as follows :

• (1, 1) will be filled with ‘a’ as an edge exists from node 1 to node 1

• (1, 2) will be filled with ‘b’ as an edge exists from node 1 to node 2. It is important to note that (2, 1) will not be filled as the edge is unidirectional and not bidirectional

• (1, 3) will be filled with ‘c’ as edge c exists from node 1 to node 3
• (2, 4) will be filled with ‘d’ as edge exists from node 2 to node 4
• (3, 4) will be filled with ‘e’ as an edge exists from node 3 to node 4

Connection Matrix

• A connection matrix is a matrix defined with edge weight. 

• In simple form, when a connection exists between two nodes of the control flow graph, then the edge weight is 1, otherwise, it is 0. 

• However, 0 is not usually entered in the matrix cells to reduce the complexity.

Example:

The weight of the edges is simply replaced by 1 and the cells which were empty before are left as it is, i.e., representing 0.

A connection matrix is used to find the cyclomatic complexity of the control graph.

Steps to compute the cyclomatic complexity :

• Count the number of 1s in each row and write it at the end of the row

• Subtract 1 from this count for each row (Ignore the row if its count is 0)

• Add the count of each row calculated previously

• Add 1 to this total count

• The final sum in Step 4 is the cyclomatic complexity of the control flow graph

Other methods to calculate cyclomatic complexity :

• Cyclomatic complexity = e – n + 2 * p

Where, 

      e : no. of edges

      n : no. of nodes

      p :  no. of disconnected parts of the flow graph

• Cyclomatic complexity = p + 1

Where, 

      p:  no. predicate nodes contained in the control flow graph

• Cyclomatic complexity = Number of regions in the graph + 1

 

Example:

1)

Nodes: 7

Edges: 7

Connected components: 1

Cyclomatic complexity = E-N + 2*p = 7-7+2

2)

Cyclomatic complexity = p+1 = 1+1 = 2

3)

Cyclomatic complexity = no. of regions + 1 = 1+1 = 2

Next: Unit-2