Cyclomatic complexity is a software metric (measurement) concept in computational complexity theory. It was developed by Thomas McCabe and is used to generally measure the complexity of a program. It directly measures the number of linearly independent paths through a program's source code.
The concept, although not the method, is somewhat similar to that of general text complexity measured by the Flesch-Kincaid Readability Test.
Cyclomatic complexity is computed using a graph that describes the control flow of the program. The nodes of the graph correspond to the commands of a program. A directed edge connects two nodes, if the second command might be executed immediately after the first command.
Definition
- M = E − N + P
where
- M = cyclomatic complexity
- E = the number of edges of the graph
- N = the number of nodes of the graph
- P = the number of connected components.
"M" is alternatively defined to be one larger than the number of decision points (IFs, UNTILs, ENDs...) in a module (function, procedure, chart node, etc.), or more generally a system.
Alternative definition
- v(G) = e - n + 2
- G is a program's flowgraph
- e is the number of arcs in the flowgraph
- n is the number of nodes in the flowgraph
Insert non-formatted text here
===Alternative Way === [KK] 02/02/06
Theres another simple way to get this "Cyclomatic Number", just count the "No. of Closed Loops" in the flow graph & increment it by 1. i.e.
M = "No. of closed loops" + 1
where
M = Cyclomatic Number
There should be atleast "M" number of testcases for testing the particular flowgraph. This is the bare-minimum necessity to test the flowgraph.
Key Concept
McCabe's rule of thumb is that "modules" with M of ten or more are error-prone. CASE structures are an exception. Due to their structure, they can have more than ten decisions without increasing the likelihood of errors.
The Cyclomatic complexity of a section of source code is the count of the number of paths through the source code. For instance if the source code contained no decision points such as IF statements or FOR loops, the complexity would be 1 since there is only a single path through the code. If the code had a single IF statement there would be two paths through the code, one path where the IF statement is evaluated as TRUE and one path where the IF statement is evaluated as FALSE.
Cyclomatic complexity is normally calculated by creating a graph of the source code with each line of source code being a node on the graph and arrows between the nodes showing the execution pathways. As some programming languages can be quite terse and compact, a source code statement when developing the graph may actually create several nodes in the graph (for instance when using the C and C++ language "?" conditional operator (also known as the "ternary operator") within a function call interface).
In general, in order to fully test a module all execution paths through the module should be exercised. This implies a module with a high complexity number requires more testing effort than a module with a lower value since the higher complexity number indicates more pathways through the code. This also implies that a module with higher complexity is more difficult for a programmer to understand since the programmer must understand the different pathways and the results of those pathways.
One would also expect that a module with higher complexity would tend to have lower cohesion (less than functional cohesion) than a module with lower complexity. The possible correlation between higher complexity measure with a lower level of cohesion is predicated on a module with more decision points generally implementing more than a single well defined function. However there are certain types of modules that one would expect to have a high complexity number, such as user interface (UI) modules containing source code for data validation and error recovery.
Example Graph
See also
External links
- Cyclomatic complexity - at Software Engineering Institute, Carnegie Mellon University
- Python complexity - Journyx provides McCabe-like cyclomatic complexity analysis tools for analyzing Python code (which are written in Perl).
- McCabe Software, Inc. - Founded by cyclomatic complexity inventor Thomas McCabe, McCabe Software, Inc. provides a suite of complexity analysis and test coverage tools with support for several programming languages.
- Run-Time Systems - Cyclomatic Complexity Calculator for Delphi.