Cyklomatisk komplexitet

Cyklomatisk komplexitet av ett program är ett  strukturellt (eller topologiskt) mått på komplexiteten hos ett datorprogram . Måttet utvecklades av Thomas J. McCabe 1976.

Vid beräkning av den cyklomatiska komplexiteten används styrflödesdiagrammet för programmet. Grafens noder motsvarar odelbara grupper av programkommandon, de är förbundna med riktade kanter om gruppen av kommandon som motsvarar den andra noden kan utföras omedelbart efter gruppen av kommandon för den första noden. Cyklomatisk komplexitet kan också beräknas för enskilda funktioner , moduler , metoder eller klasser inom ett program.

McCabe använde beräkningen av cyklomatisk komplexitet vid testning . Metoden han föreslog var att testa varje linjärt oberoende väg genom programmet, i vilket fall antalet tester som behövs är lika med programmets cyklomatiska komplexitet. [ett]

Beskrivning

Den cyklomatiska komplexiteten hos ett stycke programkod är antalet linjärt oberoende vägar genom programkoden . Till exempel, om källkoden inte innehåller några förgreningspunkter eller loopar, är komplexiteten en eftersom det bara finns en väg genom koden. Om koden har en enda sats IFsom innehåller ett enkelt villkor, så finns det två vägar genom koden: en om villkoret för satsen IFär sant TRUEoch en om FALSE.

Matematiskt bestäms den cyklomatiska komplexiteten för ett strukturerat program [2]  med hjälp av en riktad graf , vars noder är programblock sammankopplade med kanter, om kontroll kan överföras från ett block till ett annat. Då definieras komplexiteten som: [3] :

M = E - N + 2 P ,

var:

M = cyklomatisk komplexitet, E = antal kanter i grafen, N = antal noder i grafen, P = antal anslutningskomponenter .

En annan formulering använder en graf där varje utgångspunkt är kopplad till en ingångspunkt. I det här fallet är grafen starkt kopplad , och programmets cyklomatiska komplexitet är lika med den grafens cyklomatiska nummer (även känt som det första Betti-talet ), vilket definieras som [3]

M = E - N + P. _

Denna definition kan ses som att beräkna antalet linjärt oberoende cykler som finns i en graf, det vill säga de cykler som inte innehåller andra cykler. Eftersom varje utgångspunkt är ansluten till en ingångspunkt finns det åtminstone en cykel för varje utgångspunkt.

För ett enkelt program, eller subrutin, eller metod är P alltid 1. Cyklomatisk komplexitet kan dock gälla för flera sådana program eller subrutiner (till exempel för alla metoder i en klass ), i vilket fall P är lika med antalet subrutiner i fråga, eftersom varje subrutin kan representeras som en oberoende del av grafen.

Det kan visas att den cyklomatiska komplexiteten för ett strukturerat program med endast en ingångspunkt och en utgångspunkt är ekvivalent med antalet förgreningspunkter (det vill säga uttalanden ifeller villkorsslingor) som finns i det programmet plus en. [3] [4]

Cyklomatisk komplexitet kan utökas till ett program med flera utgångspunkter; i det här fallet är det [4] [5]

π − s + 2,

var:

π är antalet grenpunkter i programmet, s  är antalet utgångspunkter.

Formell definition

Formellt kan cyklomatisk komplexitet definieras som det relativa Betti-talet :

det vill säga "den första homologin av grafen G med avseende på terminalnoderna t . Detta är ett annat sätt att säga "antalet linjärt oberoende vägar genom grafen från ingång till utgång".

Den cyklomatiska komplexiteten kan också beräknas i termer av det absoluta Betti-talet (med absolut homologi, inte relativ) genom att sammanfoga alla terminalnoder för en given komponent (vilket är ekvivalent med att ansluta utgångspunkter med ingångspunkt), i detta fall för en ny, utökad, graf

Applikation

Begränsar komplexiteten i utvecklingen

En av McCabes ursprungliga användningsområden var att begränsa komplexiteten hos program under utveckling. Han rekommenderar att programmerare måste beräkna komplexiteten hos de moduler de utvecklar och att dela upp modulerna i mindre när den cyklomatiska komplexiteten för dessa moduler överstiger tio. [3] Denna praxis införlivades av NIST i strukturella testmetoder med observationen att sedan McCabes ursprungliga publicering har valet av 10 fått starkt stöd, men i vissa fall kan det vara lämpligt att lätta på begränsningen och tillåta moduler upp till komplexitet 15. I denna metod inser man att det ibland kan finnas skäl att gå över den överenskomna gränsen. Detta är formulerat som en rekommendation: "För varje modul bör cyklomatisk komplexitet antingen begränsas till överenskomna gränser, eller så bör en skriftlig förklaring av varför gränsen överskrids tillhandahållas."

Applikation i mjukvarutestning

En annan användning av cyklomatisk komplexitet är att bestämma antalet tester som krävs för fullständig kodtäckning .

Det är användbart eftersom den cyklomatiska komplexiteten hos M har två egenskaper, för en viss modul :

• M  är en övre uppskattning för antalet tester som ger täckning av förhållanden (grenpoäng);
• M  är en lägre uppskattning av antalet rutter genom kontrollflödesdiagrammet och därmed antalet tester för att slutföra vägtäckningen.

Som en del av andra mätvärden

Cyklomatisk komplexitet används som en av parametrarna i underhållsindexet [ 6 ] . 

Anteckningar

1. ↑ AJ Sobey. Huvudprovväg . Hämtad 2 maj 2009. Arkiverad från originalet 26 april 2012. (obestämd)
2. ↑ Här betyder termen "strukturerad" att programmet endast har en utgångspunkt.
3. ↑ 1 2 3 4 McCabe. Ett komplexitetsmått  // IEEE  -transaktioner på mjukvaruteknik : journal. - 1976. - December. - S. 308-320 . Arkiverad från originalet den 29 december 2009.
4. ↑ 1 2 Belzer, Kent, Holzman och Williams. Encyclopedia of Computer Science and Technology  (engelska) . - CRC Press , 1992. - P. 367-368.
5. ↑ Harrison. Tillämpa Mccabes komplexitetsmått på program med flera utgångar  //  Software: Practice and Experience: journal. - J Wiley & Sons, 1984. - Oktober.
6. ↑ Linda M. Laird, M. Carol Brennan John. Mjukvarumätning och uppskattning: ett praktiskt tillvägagångssätt. Wiley & Sons, 2006.