Definizione di Complessità Ciclomatica
Nell’ambito dell’ingegneria del software e più precisamente nelle metriche del software, la complessità ciclomatica (CC) è usata per valutare la complessità di un algoritmo ed è interamente basata sulla struttura del grafo che rappresenta l’algoritmo stesso. Riferendosi ad un grafo che rappresenta l’algoritmo (si veda la figura seguente) e posto:
- v(G): numero ciclomatico relativo al grafo G
- L: numero di archi nel grafo
- N: numero di nodi del grafo
- P: numero dei componenti del grafo disconnessi
Si ha:
v(G) = L – N +2*P
In un grafo G fortemente connesso, la complessità ciclomatica è uguale al numero di percorsi linearmente indipendenti. Per una sequenza dove è presente un solo percorso (non ci sono scelte né opzioni) allora sarà necessario un solo caso di test. Se invece è presente un If loop allora avrò due scelte cioè due percorsi alternativi: se la condizione è vera verrà testato un percorso, se la condizione è falsa verrà testato l’altro. In generale se sono presenti tanti If loop allora avrò tante scelte che generano dei percorsi multipli, ad ognuno dei quali è associato un caso di test. La Figura seguente mostra un esempio di calcolo della CC per quattro strutture di programmi elementari.
Proprietà Complessità Ciclomatica
La CC ha diverse proprietà:
- v(G)>=1
- v(G)= numero massimo di percorsi linearmente indipendenti in G
- L’inserimento o l’eliminazione di espressioni in G non influenza
- G ha un solo percorso solo se
- Inserendo un nuovo arco in G, aumenta di 1
- dipende solo dalla struttura decisionale di G
Si può dimostrare inoltre che la Complessità Ciclomatica di un programma è uguale al numero di nodi decisionali più 1:
v(G) = num_decisioni +1
Di fatto, il concetto di CC è legato a quello della testabilità, infatti minore è la complessità e maggiore è la facilità di esecuzione dei test.