Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
→Description: rm :-indents (MOS:INDENT); change list type |
||
Line 13:
===Definition===
[[Image:control flow graph of function with loop and an if statement without loop back.svg|thumb|250px|right|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). On exiting the loop, there is a conditional statement (group below the loop), and finally the program exits at the blue node. This graph has 9 edges, 8 nodes, and 1 [[connected component (graph theory)|connected component]], so the cyclomatic complexity of the program is {{math|1=9
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 being linearly dependent if there is a subset of one or more paths where the [[symmetric difference]] of their edge sets is empty. For instance, 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 evaluates to TRUE and another one where it evaluates to FALSE, so the complexity would be 2. Two nested single-condition IFs, or one IF with two conditions, would produce a complexity of 3.
Mathematically, the cyclomatic complexity of a [[Structured programming|structured program]]{{efn|1=Here "structured" means in particular "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| url=https://books.google.com/books?id=vtNWAAAAMAAJ&pg=PA3 | volume=SE-2| doi=10.1109/tse.1976.233837|s2cid=9116234}}</ref>
where
[[Image:control flow graph of function with loop and an if statement.svg|thumb|250px|The same function as above, represented using the alternative formulation, where each exit point is connected back to the entry point. This graph has 10 edges, 8 nodes, and 1 [[connected component (graph theory)|connected component]], which also results in a cyclomatic complexity of 3 using the alternative formulation ({{math|1=10
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]], and 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" />
This may be seen as calculating the number of [[linearly independent cycle]]s that exist in the graph, i.e. those cycles that do not contain other cycles within themselves. Note that 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}} is always equal to 1. So 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, however, be applied to several such programs or subprograms at the same time (e.g., to all of the methods in a class), and in these cases {{mvar|P}} will be equal to the number of programs in question, as each subprogram will appear as a disconnected subset of the graph.
McCabe showed that the cyclomatic complexity of any structured program with only one entry point and one exit point is equal to the number of decision points (i.e., "if" statements or conditional loops) contained in that program plus one. However, 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: ... |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 languages like <code>IF cond1 AND cond2 THEN ...</code> should be counted in terms of predicate variables involved, i.e. 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=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: ... |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 languages like <code>IF cond1 AND cond2 THEN ...</code> should be counted in terms of predicate variables involved, i.e. 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|
Line 47 ⟶ 45:
Cyclomatic complexity may be extended to a program with multiple exit points; in this case it is equal to
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>
===Explanation in terms of algebraic topology===
Line 76 ⟶ 66:
For the more topologically inclined, cyclomatic complexity can alternatively be defined as a relative [[Betti number]], the size of a [[relative homology]] group:
which is read as "the rank of the first homology group of the graph ''G'', relative to the terminal nodes ''t''". This is a technical way of saying "the number of linearly independent paths through the flow graph from an entry to an exit", where:
* "linearly independent" corresponds to homology, and means one does not double-count backtracking;
Line 85 ⟶ 75:
Alternatively, one can compute this via absolute Betti number (absolute homology – not relative) by identifying (gluing together) all the terminal nodes on a given component (or equivalently, draw paths connecting the exits to the entrance), in which case (calling the new, augmented graph <math>\tilde G</math>, which is {{clarify|reason=something is missing here|date=November 2013}}), one obtains
It can also be computed via [[homotopy]]. If one considers a (connected) control-flow graph as a 1-dimensional [[CW complex]] called <math>X</math>, then the [[fundamental group]] of <math>X</math> will be <math>\pi_1(X) \cong \Z^{*n}</math>. The value of <math>n+1</math> is the cyclomatic complexity. The fundamental group counts how many loops there are through the graph, up to homotopy, and hence aligns with what we would intuitively expect.
| |||