Content deleted Content added
No edit summary Tags: Mobile edit Mobile app edit Android app edit |
→Definition: Add math tags and fix reference |
||
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|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 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
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|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]], 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),
:
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
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|
Line 42:
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|
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
:
where
journal=Software: Practice and Experience|
title=Applying Mccabe's complexity measure to multiple-exit programs|
| |||