Complessità ciclomatica

La complessità ciclomatica, o complessità condizionale, è una metrica software. Sviluppata da Thomas J. McCabe nel 1976, è utilizzata per misurare la complessità di un programma. Misura direttamente il numero di cammini linearmente indipendenti attraverso il grafo di controllo di flusso.

La complessità ciclomatica è calcolata utilizzando il grafo di controllo di flusso del programma: i nodi del grafo corrispondono a gruppi indivisibili di istruzioni, mentre gli archi connettono due nodi se il secondo gruppo di istruzioni può essere eseguito immediatamente dopo il primo gruppo. La complessità ciclomatica può, inoltre, essere applicata a singole funzioni, moduli, metodi o classi di un programma.

Descrizione

Un grafo di controllo di flusso di un semplice programma. Il programma inizia l'esecuzione dal nodo rosso, poi entra nel ciclo. In uscita dal ciclo, c'è un'istruzione condizionale e alla fine il programma termina al nodo blu. Per questo grafo $e$ = 9, $n$ = 8 e $p$ = 1, quindi la complessità ciclomatica vale 3.

La complessità ciclomatica di una sezione di codice è il numero di cammini linearmente indipendenti attraverso il codice sorgente. Per esempio, se il codice sorgente non contiene punti decisionali come IF o cicli FOR, allora la complessità sarà 1, poiché esiste un solo cammino nel sorgente (e quindi nel grafo). Se il codice ha un singolo IF contenente una singola condizione, allora ci saranno due cammini possibili: il primo se l'IF viene valutato a TRUE e un secondo se l'IF viene valutato a FALSE.

La definizione di "cammini linearmente indipendenti" risiede nella definizione di lineare indipendenza a livello algebrico, semplicemente estesa ai cammini su grafi orientati. Una complessità ciclomatica di 5, significa che 5 è il numero massimo di cammini possibili tra loro indipendenti e ogni altro cammino possibile sul grafo si può costruire a partire da uno di quei 5 (vale a dire una combinazione lineare di uno di essi). Trovare i 5 cammini indipendenti significa trovare una base per l'insieme di tutti i possibili cammini di un dato grafo G.

Matematicamente, la complessità ciclomatica di un programma strutturato è definita in riferimento ad un grafo diretto contenente i blocchi base di un programma con un arco tra due blocchi se il controllo può passare dal primo al secondo (il "grafo di controllo di flusso"). La complessità è quindi definita come:

$v(G)=e-n+2p$

dove

$v(G)$ = complessità ciclomatica del grafo G;

$e$ = il numero di archi del grafo;

$n$ = il numero di nodi del grafo;

$p$ = il numero di componenti connesse.

La stessa funzione di prima, mostrata come grafo fortemente connesso per il calcolo con il metodo alternativo. Per questo grafo, $e$ = 10, $n$ = 8 e $p$ = 1, quindi la complessità ciclomatica vale 3.

Un'alternativa è quella di utilizzare un grafo nel quale ogni punto di uscita è a sua volta connesso con il punto d'ingresso. In questo caso, il grafo è detto fortemente connesso, e quindi la complessità ciclomatica è uguale al "numero" ciclomatico del suo grafo (anche conosciuto come il primo numero di Betti), che è definito come:

$v(G)=e-n+p$

E qui si ritrova anche il motivo del nome di tale complessità.

Per un singolo programma (o una funzione o un metodo), $p$ è sempre uguale ad 1. La complessità ciclomatica può, chiaramente, essere applicata a più programmi o sottoprogrammi contemporaneamente (es. tutti i metodi di una classe), e in questi casi $p$ corrisponde al numero dei programmi/sottoprogrammi in questione, poiché un singolo sottoprogramma apparirà come una componente connessa del grafo.

Formule alternative

Contare i predicati

Nella proposta originale di McCabe, erano fornite anche due formule per il calcolo più rapido della complessità ciclomatica. La prima (e largamente più diffusa) si basa sul fatto che è possibile dimostrare che la complessità ciclomatica di ogni programma strutturato (singolo punto di ingresso/uscita) vale:

$\pi +1$

dove

$\pi$ = il numero di punti decisionali (es. IF, FOR, WHILE etc.) contenuti nel programma.

Da notare che in questo caso non si fa riferimento al grafo di controllo di flusso, e quindi il calcolo è largamente più semplice e rapido; basta semplicemente "contare" gli IF, FOR, WHILE etc.

Contare le regioni del grafo

La seconda formula si basa ancora sul grafo ma anziché considerare gli archi e i nodi, considera le regioni (zone) che essi formano. Il numero di regioni corrisponde alla complessità ciclomatica. L'assunto di ciò si basa sulla formula di Eulero applicata ai grafi planari che dice che se $G$ è un grafo planare con $n$ vertici (nodi), $e$ archi e $r$ regioni allora:

$n-e+r=2$

da cui

$r=e-n+2$

quindi il numero di regioni coincide con la complessità ciclomatica.

Proprietà

Sia $G$ un grafo di controllo di flusso di un programma e $v(G)$ la sua complessità, è possibile esporre brevemente alcune proprietà:

1. $v(G)\geq 1$;
2. $v(G)$ è il numero massimo di cammini linearmente indipendenti in $G$;
3. Inserire o eliminare istruzioni funzionali (functional statements) a $G$, non influenza $v(G)$;
4. $G$ ha un solo cammino se e solo se $v(G)=1$;
5. Inserire un nuovo arco in $G$ incrementa $v(G)$ di un'unità;
6. $v(G)$ dipende solamente dalla struttura decisionale di $G$.

Estensioni della complessità ciclomatica

Esiste tuttavia un limite a tale complessità. Essa è stata definita in termini di programmi/sottoprogrammi con un singolo punto di ingresso e di uscita. Non è quindi possibile (o perlomeno non sarebbe formalmente corretto) calcolare la complessità di programmi che, ad esempio, abbiano più punti di uscita.. In tal senso numerosi studi hanno esteso la definizione iniziale cercando di comprendere anche programmi di questo tipo.

Singolo ingresso - Uscita multipla

La complessità ciclomatica può essere estesa ad un programma con più punti di uscita. In questo caso vale:

$v(G)=\pi -e+2$

dove

$\pi$ = il numero di punti decisionali;

$e$ = il numero di punti di uscita.

Chiaramente la nuova definizione è consistente, ovvero vale anche per programmi con un singolo punto di uscita ($e=1$), riottenendo la formula precedente.

Applicazioni

Limitare la complessità durante la fase di sviluppo

Una della applicazioni originali era di limitare la complessità di funzioni durante lo sviluppo; McCabe raccomandava che i programmatori contassero la complessità dei moduli in sviluppo, e li dividessero in moduli più piccoli, qualora tale complessità avesse superato 10.. Tale pratica è stata adottata dalla "Metodologia di Test Strutturato" del NIST, osservando che dalla pubblicazione dell'articolo originale, il valore di 10 ha ricevuto una sostanziale accettazione, ma in certe circostanze può essere appropriato rilassare tale restrizione e permettere moduli con una complessità anche di 15. Qualora questo limite venga tuttavia superato, tale metodologia suggeriva di spiegare il perché del superamento.

Implicazioni nella fase di testing del software

Un'applicazione della complessità ciclomatica è determinare il numero di casi di test che sono necessari per l'analisi di coverage di una particolare funzione/subroutine.

È utile per via di due proprietà della complessità ciclomatica $v(G)$:

• $v(G)$ è un limite superiore al numero di test necessari per raggiungere un coverage completo di una data funzione;
• $v(G)$ è un limite inferiore per il numero di cammini all'interno del grafo di controllo di flusso. Assumendo che ogni test sia un cammino, il numero di casi necessari per raggiungere un coverage sui cammini è uguale al numero di cammini che possono effettivamente essere presi. Tuttavia alcuni cammini possono essere impossibili (o "infiniti") quindi questo numero può essere a volte inferiore a $v(G)$.

Quindi la relazione che ne emerge è la seguente:

$coverage\,\leq complessita'\,ciclomatica\leq numero\,di\,cammini$

Per esempio, si consideri un programma che consiste di due if-then-else sequenziali.

Il grafo di controllo di flusso del codice a fianco; il nodo rosso è il punto di ingresso, e il blu quello d'uscita. L'uscita è stata connessa all'entrata per rendere il grafo fortemente connesso.

if( c1() )
   f1();
else
   f2();

if( c2() )
   f3();
else
   f4();

In questo esempio, due test sono sufficienti per raggiungere un coverage completo del codice, mentre quattro sono necessari per un coverage completo dei cammini (tutti i cammini possibili). La complessità ciclomatica del programma vale 3 (può essere calcolata mediante una qualunque delle formule sopra menzionate).

In generale, per poter testare in modo completo un modulo, tutti i possibili cammini dovrebbero essere analizzati. Questo implica che un modulo con una complessità elevata, richieda più testing di un modulo a complessità inferiore. Questo implica anche che un modulo particolarmente complesso sarà più difficile da capire per un programmatore, poiché dovrà riuscire a identificare i cammini e i loro risultati.

Sfortunatamente, testare tutti i possibili cammini non è sempre praticabile. Si consideri l'esempio di cui sopra, a cui ogni volta si aggiunge un altro if-then-else. Tale modifica comporterebbe un raddoppiamento dei possibili cammini. Se il programma crescesse ancora, raggiungerebbe un punto in cui fare testing diventerebbe impraticabile.

Una strategia di testing comune, utilizzata ad esempio dalla "Metodologia di Test Strutturato" del NIST, è utilizzare la complessità ciclomatica di un modulo per determinare il numero di test a "scatola bianca" (white-box) che sono richiesti per ottenere un coverage sufficiente per il modulo. In quasi tutti i casi, in accordo con questa metodologia, un modulo dovrebbe avere esattamente tanti test quanto è il valore della complessità ciclomatica; in molti casi, questo numero è adeguato a ricoprire tutti i casi (cammini) rilevanti per il modulo.

Come esempio di una funzione che richiede più di un semplice coverage per essere testata accuratamente, si consideri ancora l'esempio di cui sopra, ma si assuma che, per evitare l'occorrenza di un bug, ogni chiamata a f1() o f3() deve chiamare anche l'altra. Assumendo che i risultati di c1() e c2() siano indipendenti, questo suggerisce che la funzione così presentata contenga dei bug. Il semplice coverage ci permetterebbe di testarla con due test e un possibile insieme di test (volutamente erroneo) potrebbe essere il seguente:

• c1() ritorna TRUE e c2() ritorna TRUE;
• c1() ritorna FALSE e c2() ritorna FALSE.

Nessuno dei due test farebbe notare il bug. Se, tuttavia, si utilizza la complessità ciclomatica (= 3) per indicare il numero di test necessari, a questo insieme di test si aggiungerebbero uno dei seguenti:

• c1() ritorna TRUE e c2() ritorna FALSE;
• c1() ritorna FALSE e c2() ritorna TRUE.

Indipendentemente da quale di scelga, entrambi esporrebbero il bug.

Coesione

Ci si aspetterebbe che un modulo ad elevata complessità abbia una minore coesione di un modulo con una complessità inferiore. La relazione tra elevata complessità e bassi livelli di coesione si basa sul fatto che un modulo con più punti decisionali generalmente implementerà più di una singola funzione ben definita. In uno studio del 2005 ha mostrato forti corrispondenze tra le metriche di complessità e il livello di Coesione nelle classi prese in esame.

Relazioni sul numero di errori

Degli studi hanno trovato una forte relazione tra la complessità ciclomatica e il numero di errori nel codice. Moduli che hanno elevata complessità tendono a contenere un numero elevato di errori. Per esempio, in uno studio del 2008 si sono analizzate classi open-source di applicazioni Java e sono state divise in due categorie in base a quanto frequentemente venivano riscontrati errori in esse. Si è trovato una forte correlazione tra complessità e gli errori trovati, e si è calcolato che classi con una complessità di 11 avevano una probabilità di contenere errori dello 0.28, che si alzava a 0.98 con una complessità di 74.

Tuttavia, altri studi sul controllo delle dimensioni dei programmi (utilizzando ad esempio metriche tipo numero di linee di codice) sono generalmente meno conclusive.

Voci correlate

• Struttura di controllo
• Metriche software
• Software engineering
• Collaudo del software

Collegamenti esterni

• A Complexity Measure - McCabe's original paper in IEEE Transactions on Software Engineering Vol. 2, No. 4, p. 308 (1976)
• NIST Special Publication 500-235 Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric, su hissa.ncsl.nist.gov. URL consultato il 15 maggio 2009 (archiviato dall'url originale il 21 maggio 2007).
• McCabe official home page, su mccabe.com.