Arunkumar Khannur's Software Testing Knowledge Center
   
 
  • Step 2: Count number of nodes in flow graph, n
  • Step 3: Count number of edges in flow graph, e
  • Step 4: Determine Cyclomatic complexity , V(g) = e-n+2
  • Step 5: Determine a basis set of linearly independent paths.
  • Step 6: Prepare test cases that will force execution of each path in the basis set.

11.6 Cyclomatic Complexity

Cyclomatic complexity measures the amount of decision logic in a single software module. It is used for two related purposes in the structured testing methodology.

  • First, it gives recommended number of independent paths from entry to exit in a programming element or its representation.
  • Second, it is used during all phases of the software lifecycle, beginning with design, to keep software reliable, testable, and manageable

Cyclomatic complexity is based entirely on the structure of software's control flow graph. For each module, Cyclomatic complexity is defined to be Cyclomatic complexity, v(G) = e - n + 2
where,
v refers to the cyclomatic number in graph theory
G indicates that the complexity is a function of the graph
e represents number of edges
n represents nodes in the control flow graph

The cyclomatic number in graph theory is defined as e - n + 1. Program control flow graphs are not strongly connected, but they become strongly connected when a "virtual edge" is added connecting the exit node to the entry node. The cyclomatic complexity definition for program control flow graphs is derived from the cyclomatic number formula by simply adding one to represent the contribution of the virtual edge. This definition makes the cyclomatic complexity equal the number of independent paths through the standard control flow graph model, and avoids explicit mention of the virtual edge.

Cyclomatic Complexity and its relationship with Programming Complexity


As we know, overly complex modules are harder to understand. Because of this, such modules are: more prone to errors, hard to test and are harder to modify. Cyclomatic Complexity calculation helps to decide whether the module under test consideration is overly complex or is well written. Hence, during Code-based Testing, testers shall arrive at Cyclomatic Complexity of each programming module, based on the value of it, force appropriate action by the developers to write program with limited Cyclomatic Complexity. It is recommended to limit the value of Cyclomatic Complexity to 10 with active involvement of developers. Following are the guidelines to interpret structure of the based on value of Cyclomatic Complexity:

  • If value of Cyclomatic Complexity is more than 10, the structure of the module is overly complex. Thus ask the developer to re-construct the module.
  • If value of Cyclomatic Complexity is more than 5 and less than 10, the structure of the module is complex indicating that the logic is difficult to test. Thus such a module shall be allocated to experience testers
  • If value of Cyclomatic Complexity is less than 5, the structure of the module is simple indicating that the logic is easy to test. Thus such a module may be allocated to less experienced testers.

Cyclomatic Complexity & Test Cases

The word "cyclomatic" comes from the number of fundamental (or basic) cycles in connected, undirected graphs. More importantly, it also gives the number of independent paths through strongly connected directed graphs. A strongly connected graph is one in which each node can be reached from any other node by following directed edges in the graph.

The cyclomatic complexity equal the number of independent paths through the standard control flow graph model, Cyclomatic complexity equal the number of independent paths through the standard control flow graph model. This requires us to find the number of elements of a basis set of control flow paths through the module.

Arriving at Cyclomatic Complexity

From program module, we can arrive at Cyclomatic complexity by using following steps. Here the number of test cases required to test the program module is equal to the number of linearly independent paths in the basis set corresponding to the graph. The steps are:
  • Step 1: Draw a corresponding flow graph using following flow graph representations for different programming constructs using Flow Graphical Representations of Program Elements (See Fig. 4.4 Flow Graphical Representations of Program Constructs)

Thus, Cyclomatic complexity can be characterized as the number of elements of a basis set of control flow paths through the module.

Illustration


For the following programming element
function sdivisor (n: integer): integer;
   var d {current divisor and member of odd sequence},
   R{integer less than or equal to square root of n}: integer;
   begin {finds the smallest exact divisor of an integer n, returns 1 if n prime}
    {assert: n>0}
   if not odd(n) then
     sdivisor:=2
  else
begin {terminate search for smallest divisor at sqrt (n)}
   r: = trunc(sqrt(n));
   d: =3;
   {invariant: d= < r+1^no odd integer in [3..d-2] exactly
   divides n}
   while (n mod d < >0) and (d < r) do d: = d+2;
   {assert: d is smallest exact divisor or n^d = < r V (d = < r+1)^n
   is prime}
   if n mod d =0 then
     sdivisor :=d
   else
     sdivisor :=1
   end
end

  • Draw a flow graph
  • Calculate Cyclomatic Complexity
  • Specify your recommendation as a tester about the code
  • Arrive at independent paths

Note: Split the compound logical statements into simple ones while addressing the question
 
 
Khannur's Book
Arunkumar Khannur, Software Testing - Techniques and Applications, Published by Pearson Publications, 2011 (ISBN:978-81-317-5836-6; Pages:341 + xxii)
Follow Khannur
         
Khannur's Company
ISQT Process & Consulting Services Pvt. Ltd., Bangalore, INDIA
Khannur's Software Testing Forum
STEP-AUTO 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