Complexitatea ciclomatică

Complexitatea ciclomatică a unui program este o  măsură structurală (sau topologică) a complexității unui program de calculator . Măsura a fost dezvoltată de Thomas J. McCabe în 1976.

La calcularea complexității ciclomatice se utilizează graficul fluxului de control al programului. Nodurile graficului corespund grupurilor indivizibile de comenzi de program, ele sunt conectate prin muchii direcționate dacă grupul de comenzi corespunzător celui de-al doilea nod poate fi executat imediat după grupul de comenzi al primului nod. Complexitatea ciclomatică poate fi calculată și pentru funcții individuale , module , metode sau clase dintr-un program.

McCabe a folosit calculul complexității ciclomatice în testare . Metoda propusă de el a fost de a testa fiecare rută liniar independentă prin program, caz în care numărul de teste necesare este egal cu complexitatea ciclomatică a programului. [unu]

Descriere

Complexitatea ciclomatică a unei bucăți de cod de program este numărul de rute liniar independente prin codul de program . De exemplu, dacă codul sursă nu conține puncte de ramificare sau bucle, atunci complexitatea este una deoarece există o singură rută prin cod. Dacă codul are o singură instrucțiune IFcare conține o condiție simplă, atunci există două căi prin cod: una dacă condiția declarației IFeste adevărată TRUEși una dacă FALSE.

Matematic, complexitatea ciclomatică a unui program structurat [2]  este determinată cu ajutorul unui graf direcționat , ale cărui noduri sunt blocuri de program legate prin muchii, dacă controlul poate fi transferat de la un bloc la altul. Apoi complexitatea este definită astfel: [3] :

M = E − N + 2 P ,

Unde:

M = complexitate ciclomatică, E = numărul de muchii din grafic, N = numărul de noduri din grafic, P = numărul de componente de conectivitate .

O altă formulare folosește un grafic în care fiecare punct de ieșire este conectat la un punct de intrare. În acest caz, graficul este puternic conectat , iar complexitatea ciclomatică a programului este egală cu numărul ciclomatic al graficului respectiv (cunoscut și ca primul număr Betti ), care este definit ca [3]

M = E − N + P .

Această definiție poate fi considerată ca calcularea numărului de cicluri liniar independente care există într-un grafic, adică acele cicluri care nu conțin alte cicluri. Deoarece fiecare punct de ieșire este conectat la un punct de intrare, există cel puțin un ciclu pentru fiecare punct de ieșire.

Pentru un program simplu, sau subrutină sau metodă, P este întotdeauna 1. Cu toate acestea, complexitatea ciclomatică se poate aplica mai multor astfel de programe sau subrutine (de exemplu, tuturor metodelor dintr-o clasă ), caz în care P este egal cu numărul de subprogramele în cauză, deoarece fiecare subprogram poate fi reprezentat ca o parte independentă a graficului.

Se poate demonstra că complexitatea ciclomatică a oricărui program structurat cu un singur punct de intrare și un punct de ieșire este echivalentă cu numărul de puncte de ramificație (adică instrucțiuni ifsau bucle condiționate) conținute în programul respectiv plus unu. [3] [4]

Complexitatea ciclomatică poate fi extinsă la un program cu mai multe puncte de ieșire; în acest caz este [4] [5]

π − s + 2,

Unde:

π este numărul de puncte de ramificație din program, s  este numărul de puncte de ieșire.

Definiție formală

Formal, complexitatea ciclomatică poate fi definită ca numărul relativ Betti :

adică „prima omologie a graficului G în raport cu nodurile terminale t . Acesta este un alt mod de a spune „numărul de căi liniar independente prin grafic de la intrare la ieșire”.

De asemenea, complexitatea ciclomatică poate fi calculată în termeni de număr Betti absolut (folosind omologie absolută, nu relativă) prin unirea tuturor nodurilor terminale ale unei componente date (ceea ce este echivalent cu conectarea punctelor de ieșire cu punctul de intrare), în acest caz pentru un nou, extins, grafic

Aplicație

Limitarea complexității în dezvoltare

Una dintre utilizările originale ale lui McCabe a fost limitarea complexității programelor în timpul dezvoltării. El recomandă programatorilor să li se ceară să calculeze complexitatea modulelor pe care le dezvoltă și să împartă modulele în altele mai mici ori de câte ori complexitatea ciclomatică a acelor module depășește zece. [3] Această practică a fost încorporată de NIST în metodologia de testare structurală cu observația că, de la publicația originală a lui McCabe, alegerea a 10 a primit un sprijin puternic, dar în unele cazuri poate fi adecvat să se relaxeze restricția și să se permită module până la complexitate. 15. În această metodologie se recunoaște că uneori pot exista motive pentru a depăși limita convenită. Aceasta este formulată ca o recomandare: „Pentru fiecare modul, complexitatea ciclomatică ar trebui fie limitată la limitele convenite, fie ar trebui furnizată o explicație scrisă a motivului pentru care a fost depășită limita”.

Aplicație în testarea software-ului

O altă utilizare a complexității ciclomatice este determinarea numărului de teste necesare pentru acoperirea completă a codului .

Este util deoarece complexitatea ciclomatică a lui M are două proprietăți, pentru un anumit modul :

• M  este o estimare superioară a numărului de teste care asigură acoperirea condițiilor (puncte de ramificație);
• M  este o estimare mai mică pentru numărul de rute prin graficul fluxului de control și, prin urmare, numărul de teste pentru a finaliza acoperirea traseului.

Ca parte a altor valori

Complexitatea ciclomatică este utilizată ca unul dintre parametrii indicelui de menținere [ 6 ] . 

Note

1. ↑ AJ Sobey. Principalul traseu de testare . Preluat la 2 mai 2009. Arhivat din original la 26 aprilie 2012. (nedefinit)
2. ↑ Aici termenul „structurat” înseamnă că programul are un singur punct de ieșire.
3. ↑ 1 2 3 4 McCabe. O măsură de complexitate  //  Tranzacții IEEE privind ingineria software : jurnal. - 1976. - Decembrie. - P. 308-320 . Arhivat din original pe 29 decembrie 2009.
4. ↑ 1 2 Belzer, Kent, Holzman și Williams. Enciclopedia informatică și tehnologie  (engleză) . - CRC Press , 1992. - P. 367-368.
5. ↑ Harrison. Aplicarea măsurării complexității lui Mccabe la programele cu ieșiri multiple  //  Software: Practică și experiență : jurnal. - J Wiley & Sons, 1984. - Octombrie.
6. ↑ Linda M. Laird, M. Carol Brennan John. Măsurarea și estimarea software-ului: o abordare practică. Wiley & Sons, 2006.