Ciklomatikus komplexitás

A program ciklomatikus összetettsége a számítógépi  program összetettségének szerkezeti (vagy topológiai) mértéke . Az intézkedést Thomas J. McCabe dolgozta ki 1976-ban.

A ciklomatikus komplexitás kiszámításakor a program vezérlési folyamatgrafikonját használjuk. A gráf csomópontjai oszthatatlan programparancscsoportoknak felelnek meg, irányított élekkel kapcsolódnak össze, ha a második csomóponthoz tartozó parancscsoport közvetlenül az első csomópont parancscsoportja után végrehajtható. A ciklomatikus komplexitás kiszámítható a programon belüli egyes funkciókra , modulokra , metódusokra vagy osztályokra is.

McCabe a ciklomatikus komplexitás számítását használta a tesztelés során . Az általa javasolt módszer az volt, hogy minden lineárisan független útvonalat teszteljenek a programon keresztül, ebben az esetben a szükséges tesztek száma megegyezik a program ciklomatikus összetettségével. [egy]

Leírás

Egy programkód ciklomatikus összetettsége a programkódon keresztüli lineárisan független útvonalak száma . Például, ha a forráskód nem tartalmaz elágazási pontokat vagy ciklusokat, akkor a bonyolultság egy, mert csak egy útvonal vezet a kódon keresztül. Ha a kód egyetlen utasítást IFtartalmaz, amely egy egyszerű feltételt tartalmaz, akkor a kódon keresztül két útvonal van: az egyik, ha az utasítás IFfeltétele igaz, a TRUEmásik pedig, ha FALSE.

Matematikailag egy strukturált program ciklomatikus összetettségét [2]  egy irányított gráf segítségével határozzuk meg , melynek csomópontjai élekkel összekötött programblokkok, ha a vezérlés átvihető egyik blokkról a másikra. Ekkor a komplexitást a következőképpen határozzuk meg: [3] :

M = E − N + 2 P ,

ahol:

M = ciklomatikus komplexitás, E = a grafikon éleinek száma, N = csomópontok száma a grafikonon, P = a csatlakozási összetevők száma .

Egy másik megfogalmazás olyan grafikont használ, amelyben minden kilépési pont egy belépési ponthoz kapcsolódik. Ebben az esetben a gráf erősen összefügg , és a program ciklomatikus komplexitása megegyezik a gráf ciklomatikus számával (más néven az első Betti-számmal ), amelyet a következőképpen definiálunk: [3]

M = E − N + P .

Ezt a definíciót úgy tekinthetjük, mint a gráfban létező lineárisan független ciklusok számának kiszámítását , vagyis azon ciklusok számát, amelyek nem tartalmaznak más ciklusokat. Mivel minden kilépési pont egy belépési ponthoz kapcsolódik, minden kilépési ponthoz legalább egy ciklus tartozik.

Egy egyszerű program, szubrutin vagy metódus esetén P mindig 1. A ciklomatikus komplexitás azonban több ilyen programra vagy szubrutinra is vonatkozhat (például egy osztály összes metódusára ), amely esetben P egyenlő a szóban forgó szubrutinokat , mivel minden szubrutin a gráf független részeként ábrázolható.

Kimutatható, hogy bármely, csak egy belépési és egy kilépési ponttal rendelkező strukturált program ciklomatikus összetettsége megegyezik az adott programban található elágazási pontok (azaz utasítások ifvagy feltételes ciklusok) számával plusz egy. [3] [4]

A ciklomatikus komplexitás kiterjeszthető több kilépési ponttal rendelkező programra is; ebben az esetben ez [4] [5]

π − s + 2,

ahol:

π a program elágazási pontjainak száma, s  a kilépési pontok száma.

Formális definíció

Formálisan a ciklomatikus komplexitás relatív Betti-számként definiálható :

vagyis "a G gráf első homológiája a t terminális csomópontokhoz képest . Ez egy másik módja annak, hogy "a grafikonon a bemenettől a kimenetig vezető lineárisan független utak száma".

Ezenkívül a ciklomatikus komplexitás kiszámítható az abszolút Betti-szám alapján (abszolút homológiát használva, nem relatív) egy adott komponens összes terminális csomópontjának összekapcsolásával (ami egyenértékű a kilépési pontok belépési ponttal történő összekapcsolásával), ebben az esetben egy új, bővített, grafikon

Alkalmazás

A fejlesztés bonyolultságának korlátozása

McCabe egyik eredeti célja az volt, hogy korlátozza a programok bonyolultságát a fejlesztés során. Azt javasolja, hogy a programozók számítsák ki az általuk kifejlesztett modulok összetettségét, és osszák fel a modulokat kisebbekre, ha a modulok ciklomatikus összetettsége meghaladja a tízet. [3] Ezt a gyakorlatot a NIST beépítette a strukturális tesztelés módszertanába azzal a megfigyeléssel, hogy McCabe eredeti publikációja óta a 10-es választás erős támogatást kapott, de bizonyos esetekben célszerű lehet enyhíteni a korlátozást és engedélyezni a modulokat a komplexitásig. 15. Ebben a módszertanban elismert tény, hogy néha indokolt lehet a megállapodás szerinti határérték túllépése. Ez ajánlásként fogalmazódik meg: "Minden modul esetében a ciklomatikus komplexitást vagy a megállapodás szerinti határértékekre kell korlátozni, vagy írásos magyarázatot kell adni arra, hogy miért lépték túl a határt."

Alkalmazás a szoftvertesztelésben

A ciklomatikus komplexitás másik felhasználási módja a teljes kódlefedettséghez szükséges tesztek számának meghatározása .

Ez azért hasznos, mert az M ciklomatikus komplexitásának két tulajdonsága van egy adott modulusra :

Más mérőszámok részeként

A ciklomatikus komplexitás a karbantarthatósági index egyik paramétere [ 6 ] . 

Jegyzetek

  1. ↑ AJ Sobey. Fő vizsgálati útvonal . Letöltve: 2009. május 2. Az eredetiből archiválva : 2012. április 26..
  2. ↑ Itt a "strukturált" kifejezés azt jelenti, hogy a programnak csak egy kilépési pontja van.
  3. ↑ 1 2 3 4 McCabe. A komplexitás mértéke  // IEEE-  tranzakciók a szoftverfejlesztésen : folyóirat. - 1976. - december. - P. 308-320 . Az eredetiből archiválva : 2009. december 29.
  4. ↑ 1 2 Belzer, Kent, Holzman és Williams. Encyclopedia of Computer Science and Technology  (angol) . - CRC Press , 1992. - P. 367-368.
  5. ↑ Harrison. Mccabe összetettségi mértékének alkalmazása többszörös kilépésű programokra  //  Szoftver: gyakorlat és tapasztalat : napló. - J Wiley & Sons, 1984. - október.
  6. ↑ Linda M. Laird, M. Carol Brennan John. Szoftver mérés és becslés: gyakorlati megközelítés. Wiley & Sons, 2006.