Content deleted Content added
Streamlined text; corrected grammar and punctuation |
Synapse554 (talk | contribs) m Moved to section on algebraic topology to its own heading, given its different context compared to the rest of the article |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 1:
{{Short description|Measure of the structural complexity of a software program}}
'''Cyclomatic complexity''' is a [[software metric]] used to indicate the [[Programming complexity|complexity of a program]]. It is a quantitative measure of the number of linearly independent
Cyclomatic complexity is computed using the [[control-flow graph]] of the program. The nodes of the [[
One [[software testing|testing]] strategy, called [[basis path testing]] by McCabe who first proposed it, is to test each linearly independent path through the program. In this case, the number of test cases will equal the cyclomatic complexity of the program.<ref>{{cite web|
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}}.]]
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>
Line 21:
*{{mvar|E}} = the number of edges of the graph.
*{{mvar|N}} = the number of nodes of the graph.
*{{mvar|P}} = the number of [[
[[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.-->]]
Line 36:
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: ... |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
title=Encyclopedia of Computer Science and Technology|
author1=J. Belzer |author2=A. Kent |author3=A. G. Holzman |author4=J. G. Williams|
Line 46:
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>
=== Interpretation ===▼
==={{anchor|Explanation in terms of algebraic topology}}Algebraic topology===▼
In his presentation "Software Quality Metrics to Identify Risk"<ref>{{cite web |url=http://www.mccabe.com/ppt/SoftwareQualityMetricsToIdentifyRisk.ppt |title=Software Quality Metrics to Identify Risk |author=Thomas McCabe Jr. |year=2008 |archive-url=https://web.archive.org/web/20220329072759/http://www.mccabe.com/ppt/SoftwareQualityMetricsToIdentifyRisk.ppt |archive-date=2022-03-29 |url-status=live}}</ref> for the Department of Homeland Security, Tom McCabe introduced the following categorization of cyclomatic complexity:▼
An even subgraph of a graph (also known as an [[Eulerian path|Eulerian subgraph]]) is one in which every [[Vertex (graph theory)|vertex]] is [[Graph (discrete mathematics)#Graph|incident]] with an even number of edges. Such subgraphs are unions of cycles and isolated vertices. Subgraphs will be identified with their edge sets, which is equivalent to only considering those even subgraphs which contain all vertices of the full graph.▼
* 1 - 10: Simple procedure, little risk▼
The set of all even subgraphs of a graph is closed under [[symmetric difference]], and may thus be viewed as a vector space over [[GF(2)]]. This vector space is called the cycle space of the graph. The [[cyclomatic number]] of the graph is defined as the dimension of this space. Since GF(2) has two elements and the cycle space is necessarily finite, the cyclomatic number is also equal to the [[Natural logarithm of 2|2-logarithm]] of the number of elements in the cycle space.▼
* 11 - 20: More complex, moderate risk▼
* 21 - 50: Complex, high risk▼
* > 50: Untestable code, very high risk▼
A basis for the cycle space is easily constructed by first fixing a [[Glossary of graph theory#Trees|spanning forest]] of the graph, and then considering the cycles formed by one edge not in the forest and the path in the forest connecting the endpoints of that edge. These cycles form a basis for the cycle space. The cyclomatic number also equals the number of edges not in a maximal spanning forest of a graph. Since the number of edges in a maximal spanning forest of a graph is equal to the number of vertices minus the number of components, the formula <math>E-N+P</math> defines the cyclomatic number.<ref>{{cite book▼
▲An even subgraph of a graph (also known as an [[Eulerian path|Eulerian subgraph]]) is one in which every [[
▲The set of all even subgraphs of a graph is closed under [[symmetric difference]], and may thus be viewed as a [[vector space]] over [[GF(2)]]. This vector space is called the cycle space of the graph. The [[cyclomatic number]] of the graph is defined as the [[dimension (vector space)|dimension]] of this space. Since GF(2) has two elements and the cycle space is necessarily finite, the cyclomatic number is also equal to the [[
Cyclomatic complexity can also be defined as a relative [[Betti number]], the size of a [[relative homology]] group:▼
▲A [[basis (linear algebra)|basis]] for the cycle space is easily constructed by first fixing a [[Glossary of graph theory#Trees|spanning forest]] of the graph, and then considering the cycles formed by one edge not in the forest and the path in the forest connecting the endpoints of that edge. These cycles form a basis for the cycle space. The cyclomatic number also equals the number of edges not in a maximal spanning forest of a graph. Since the number of edges in a maximal spanning forest of a graph is equal to the number of vertices minus the number of components, the formula <math>E-N+P</math> defines the cyclomatic number.<ref>{{cite book |last=Diestel |first=Reinhard |title=Graph theory |publisher=Springer |year=2000 |isbn=978-0-387-98976-1 |edition=2 |series=Graduate texts in mathematics '''173''' |___location=New York}}</ref>
▲Cyclomatic complexity can also be defined as a relative [[Betti number]], the size of a [[relative homology]] group:<math display="block">M := b_1(G,t) := \operatorname{rank}H_1(G,t),</math>
which is read as "the rank of the first [[Homology (mathematics)|homology]] group of the graph ''G'' relative to the [[Tree (data structure)#Terminology|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:
Line 76 ⟶ 72:
It can also be computed via [[homotopy]]. If a (connected) control-flow graph is considered a one-dimensional [[CW complex]] called <math>X</math>, 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, aligning as expected.
▲=== Interpretation ===
▲In his presentation "Software Quality Metrics to Identify Risk"<ref>{{cite web |url=http://www.mccabe.com/ppt/SoftwareQualityMetricsToIdentifyRisk.ppt |title=Software Quality Metrics to Identify Risk |author=Thomas McCabe Jr. |year=2008 |archive-url=https://web.archive.org/web/20220329072759/http://www.mccabe.com/ppt/SoftwareQualityMetricsToIdentifyRisk.ppt |archive-date=2022-03-29 |url-status=live}}</ref> for the Department of Homeland Security, Tom McCabe introduced the following categorization of cyclomatic complexity:
▲* 1 - 10: Simple procedure, little risk
▲* 11 - 20: More complex, moderate risk
▲* 21 - 50: Complex, high risk
▲* > 50: Untestable code, very high risk
==Applications==
Line 120 ⟶ 108:
[[File:Control flow graph of function with two if else statements.svg|thumb|250px|right|The control-flow graph of the source code above; the red circle is the entry point of the function, and the blue circle is the exit point. The exit has been connected to the entry to make the graph strongly connected.]]
In this example, two test cases are sufficient to achieve a complete branch coverage, while four are necessary for complete path coverage. The cyclomatic complexity of the program is 3 (as the strongly connected graph for the program contains
In general, in order to fully test a module, all execution paths through the module should be exercised. This implies a module with a high complexity number requires more testing effort than a module with a lower value since the higher complexity number indicates more pathways through the code. This also implies that a module with higher complexity is more difficult to understand since the programmer must understand the different pathways and the results of those pathways.
| |||