Cyclomatic complexity: Difference between revisions

Revision as of 13:34, 27 February 2024

Revision as of 13:48, 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}}.]]

TheThere are a number of ways to define cyclomatic complexity of a section of [[source code]]. One common way is the number of linearly independent [[path (graph theory)|paths]] within it; a set of paths is linearly independent if for any two paths in the set, neitherhave of theirdifferent edge sets is a 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.

TheAnother way to define the cyclomatic complexity of a [[Structured programming|structured program]]{{efn|1=Here, "structured" means "with a single exit ([[return statement]]) per function".}} is definedto withlook reference toat 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>

<math display="block">M = E - N + 2P,</math>

Line 25:

[[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.-->]]

An alternative formulation of this 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" />

<math display="block">M = E - N + P.</math>