Editing Cyclomatic complexity (section)

===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}}.]]
There are multiple 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 <math>S</math> of paths is linearly independent if the edge set of any path <math>P</math> in <math>S</math> is not the union of edge sets of the paths in some subset of <math>S/P</math>. 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|IF statement]], there would be two paths through the code: one where the IF statement is TRUE and another one where it is FALSE. Here, the complexity would be 2. Two nested single-condition IFs, or one IF with two conditions, would produce a complexity of 3.

Another way to define the cyclomatic complexity of a program is to look at its [[control-flow graph]], 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>

where
*{{mvar|E}} = the number of edges of the graph.
*{{mvar|N}} = the number of nodes of the graph.
*{{mvar|P}} = the number of [[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.-->]]

An alternative formulation of this, as originally proposed, 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]]. Here, 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>

This may be seen as calculating the number of [[linearly independent cycle]]s that exist in the graph: those cycles that do not contain other cycles within themselves. Because each exit point loops back to the entry point, there is at least one such cycle for each exit point.

For a single program (or subroutine or method), {{mvar|P}} always equals 1; a simpler formula for a single subroutine is<ref name="Laplante2007">{{cite book|author=Philip A. Laplante|title=What Every Engineer Should Know about Software Engineering|date=25 April 2007|publisher=CRC Press|isbn=978-1-4200-0674-2|page=176}}</ref>
<math display="block">M = E - N + 2.</math>

Cyclomatic complexity may be applied to several such programs or subprograms at the same time (to all of the methods in a class, for example). In these cases, {{mvar|P}} will equal the number of programs in question, and each subprogram will appear as a disconnected subset of the graph.

McCabe showed that the cyclomatic complexity of a structured program with only one entry point and one exit point is equal to the number of decision points ("if" statements or conditional loops) contained in that program plus one. This is true only for decision points counted at the lowest, machine-level instructions.<ref>{{cite web|
url=https://www.froglogic.com/blog/tip-of-the-week/what-is-cyclomatic-complexity/| title=What exactly is cyclomatic complexity?|quote=To compute a graph representation of code, we can simply disassemble its assembly code and create a graph following the rules:&nbsp;... |first=Sébastien|last=Fricker|date=April 2018|website=froglogic GmbH|access-date=October 27, 2018}}</ref> Decisions involving compound predicates like those found in [[high-level language]]s like <code>IF cond1 AND cond2 THEN ...</code> should be counted in terms of predicate variables involved. In this example, one should count two decision points because at machine level it is equivalent to <code>IF cond1 THEN IF cond2 THEN ...</code>.<ref name="mccabe76"/><ref name="ecst">{{cite book|
title=Encyclopedia of Computer Science and Technology|
author1=J. Belzer |author2=A. Kent |author3=A. G. Holzman |author4=J. G. Williams|
publisher=CRC Press|year=1992|
pages=367–368}}</ref>

Cyclomatic complexity may be extended to a program with multiple exit points. In this case, it is equal to
<math display="block">\pi - s + 2,</math>
where <math>\pi</math> is the number of decision points in the program and {{mvar|s}} is the number of exit points.<ref name="ecst" /><ref name="harrison">{{cite journal | journal=Software: Practice and Experience | title=Applying Mccabe's complexity measure to multiple-exit programs | author=Harrison | date=October 1984 | doi=10.1002/spe.4380141009 | volume=14 | issue=10 | pages=1004–1007 | s2cid=62422337}}</ref>