Cyclomatic complexity: Difference between revisions

Revision as of 08:50, 10 February 2024

Revision as of 13:34, 27 February 2024

Line 12:

===Definition===

[[Image:control flow graph of function with loop and an if statement without loop back.svg|thumb|upright=1.1|alt=See caption|A control-flow graph of a simple program. The program begins executing at the red node, then enters a loop (group of three nodes immediately below the red node). Exiting the loop, there is a conditional statement (group below the loop) and the program exits at the blue node. This graph has nine edges, eight nodes and one [[connected component (graph theory)|connected component]], so the program's cyclomatic complexity is {{math|1=9 − 8 + 2×1 = 3}}.]]

The cyclomatic complexity of a section of [[source code]] is the number of [[linearly independent]] [[path (graph theory)|paths]] within it; a set of paths is linearly dependentindependent if therefor isany a subset of one (or more)two paths wherein the [[symmetricset, difference]]neither of their edge sets is emptya subset of the other. If the source code contained no [[Control flow|control flow statements]] (conditionals or decision points) the complexity would be 1, since there would be only a single path through the code. If the code had one single-condition IF statement, there would be two paths through the code: one where the IF statement is TRUE and another one where it is FALSE, so the complexity would be 2. Two nested single-condition IFs, or one IF with two conditions, would produce a complexity of 3.

The cyclomatic complexity of a [[Structured programming|structured program]]{{efn|1=Here, "structured" means "with a single exit ([[return statement]]) per function".}} is defined with reference to the [[control-flow graph]] of the program, a [[directed graph]] containing the [[basic block]]s of the program, with an edge between two basic blocks if control may pass from the first to the second. The complexity {{mvar|M}} is then defined as<ref name="mccabe76">{{cite journal| last=McCabe|date=December 1976| journal=IEEE Transactions on Software Engineering|issue=4| pages=308–320| title=A Complexity Measure | volume=SE-2| doi=10.1109/tse.1976.233837|s2cid=9116234}}</ref>

Line 23:

*{{mvar|P}} = the number of [[connected component (graph theory)|connected components]].

[[Image:control flow graph of function with loop and an if statement.svg|thumb|upright=1.1|The same function, represented using the alternative formulation where each exit point is connected back to the entry point. This graph has 10 edges, eight nodes and one [[connected component (graph theory)|connected component]], which also results in a cyclomatic complexity of 3 using the alternative formulation ({{math|1=10 − 8 + 1 = 3}}).]] <!-- Do not change this to 4. This has been done thrice, but 3 is the correct answer. Read the paragraph below for the explanation of why: -->]]

An alternative formulation is to use a graph in which each exit point is connected back to the entry point. In this case, the graph is [[strongly connected]]; the cyclomatic complexity of the program is equal to the [[cyclomatic number]] of its graph (also known as the [[Betti number#Example 2: the first Betti number in graph theory|first Betti number]]), which is defined as<ref name="mccabe76" />