Content deleted Content added
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 |
|||
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:▼
* 1 - 10: Simple procedure, little risk▼
* 11 - 20: More complex, moderate risk▼
* 21 - 50: Complex, high risk▼
* > 50: Untestable code, very high risk▼
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.
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 [[binary logarithm|2-logarithm]] of the number of elements in the cycle space.
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==
| |||