|
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>
==={{anchor|Explanation in terms of algebraic topology}}Algebraic topology===
An ''even subgraph'' of a graph (also known as an [[Eulerian path|Eulerian subgraph]]) is one where 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. In the following, even subgraphsSubgraphs 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 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.
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 constituteform a basis for the cycle space. Hence, theThe 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> above for the cyclomatic number follows.<ref>{{cite book
|last=Diestel
|first=Reinhard
}}</ref>
For the more topologically inclined, cyclomaticCyclomatic complexity can alternativelyalso 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 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; ▼* "paths" corresponds to ''first'' homology: a path is a 1-dimensional object; ▼* "relative" means the path must begin and end at an entry or exit point. ▼
▲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:
This corresponds to the intuitive notion of cyclomatic complexity, and can be calculated as above.
▲* "linearly independent" corresponds to homology ,; andbacktracking means one doesis not double- count backtracking;counted
▲* "paths" corresponds to ''first '' homology :; a path is a 1one-dimensional object ;
▲* "relative" means the path must begin and end at an entry (or exit ) point.
Alternatively,This onecyclomatic complexity can computebe thiscalculated. viaIt absolutemay Bettialso numberbe (absolutecomputed homologyvia –absolute not[[Betti relative)number]] by identifying (gluing together) all the terminal nodes on a given component, (or equivalently, drawdrawing paths connecting the exits to the entrance),. in which case (calling theThe new, augmented graph <math>\tilde G</math>, which is {{clarify|reason=something is missing here|date=November 2013}}), one obtains
<math display="block">M = b_1(\tilde G) = \operatorname{rank}H_1(\tilde G).</math>
It can also be computed via [[homotopy]]. If one considers a (connected) control-flow graph asis considered a 1one-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, andaligning hence aligns with what we would intuitivelyas expectexpected.
This corresponds to the characterization of cyclomatic complexity as "number of loops plus number of components".
=== Interpretation ===
| 