Kilka uwag na ten temat, które bezczynnie piszę ...
W szczególności dla równania Wikipedii M = E - N + 2P
To równanie jest bardzo błędne .
Z jakiegoś powodu McCabe rzeczywiście używa go w swoim oryginalnym artykule („A Complexity Measure”, IEEE Transactions on Software Engineering, Vo .. SE-2, No.4, December 1976), ale bez uzasadnienia i po przytoczeniu właściwej formuła na pierwszej stronie, którą jest
v (G) = e - v + p
(Tutaj elementy formuły zostały ponownie oznaczone)
W szczególności McCabe odwołuje się do książki C.Berge, Graphs and Hypergraphs (w skrócie poniżej G&HG). Bezpośrednio z tej książki :
Definicja (strona 27 na dole G&HG):
Cyklomatyczna liczba v (G) (niekierowanego) wykresu G (który może mieć kilka odłączonych elementów) jest zdefiniowana jako:
v (G) = e - v + p
gdzie e = liczba krawędzi, v = liczba wierzchołków, p = liczba połączonych komponentów
Twierdzenie (strona 29 na górze G&HG) (nieużywane przez McCabe):
Cyklomatyczna liczba v (G) na wykresie G jest równa maksymalnej liczbie niezależnych cykli
Cykl jest sekwencją wierzchołków wyjściowych i kończących się na tym samym wierzchołek z każdymi dwoma kolejnymi wierzchołkami w sekwencji przylegających do siebie na wykresie.
Intuicyjnie zestaw cykli jest niezależny, jeśli żadnego z cykli nie można zbudować z innych poprzez nałożenie spacerów.
Twierdzenie (strona 29 środek G&HG) (używane przez McCabe):
Na silnie połączonym wykresie G liczba cykliczna jest równa maksymalnej liczbie liniowo niezależnych obwodów.
Obwód jest cykl bez powtórzeń wierzchołkach i krawędziach dozwolony.
Mówi się, że ukierunkowany wykres jest silnie połączony, jeśli każdy wierzchołek jest osiągalny z każdego innego wierzchołka, przechodząc przez krawędzie w wyznaczonym kierunku.
Zauważ, że tutaj przeszliśmy z niekierowanych wykresów do silnie powiązanych wykresów (które są skierowane ... Berge nie wyjaśnia tego całkowicie)
McCabe stosuje teraz powyższe twierdzenie, aby uzyskać prosty sposób obliczenia „McCabe Cyclomatic Complexity Number” (CCN) w ten sposób:
Biorąc pod uwagę ukierunkowany wykres reprezentujący „topologię skoku” procedury (wykres przepływu instrukcji), z wyznaczonym wierzchołkiem reprezentującym unikalny punkt wejścia i wyznaczonym wierzchołkiem reprezentującym unikalny punkt wyjścia (wierzchołek punktu wyjścia może wymagać „zbudowania” dodając go w przypadku wielu powrotów), utwórz silnie połączony wykres, dodając skierowaną krawędź od wierzchołka punktu wyjścia do wierzchołka punktu wejścia, dzięki czemu wierzchołek punktu wejścia będzie osiągalny z dowolnego innego wierzchołka.
McCabe twierdzi teraz (raczej myląco mogę powiedzieć), że cykliczna liczba zmodyfikowanego wykresu przepływu instrukcji „jest zgodna z naszym intuicyjnym pojęciem„ minimalnej liczby ścieżek ””, więc wykorzystamy tę liczbę jako miarę złożoności.
Fajnie, więc:
Cyklomatyczną liczbę złożoności zmodyfikowanego wykresu przepływu instrukcji można określić, zliczając „najmniejsze” obwody na niekierowanym wykresie. Nie jest to szczególnie trudne dla człowieka lub maszyny, ale zastosowanie powyższego twierdzenia daje nam jeszcze łatwiejszy sposób jego ustalenia:
v (G) = e - v + p
jeśli pominąć kierunkowość krawędzi.
We wszystkich przypadkach bierzemy pod uwagę tylko jedną procedurę, więc na całym wykresie jest tylko jeden podłączony element, a więc:
v (G) = e - v + 1.
W przypadku rozważenia oryginalnego wykresu bez dodanej krawędzi „wyjścia do wejścia” , uzyskuje się po prostu:
ṽ (G) = ẽ - v + 2
jako ẽ = e - 1
Zilustrujmy to na przykładzie McCabe z jego artykułu:
Mamy tutaj:
- e = 10
- v = 6
- p = 1 (jeden składnik)
- v (G) = 5 (wyraźnie liczymy 5 cykli)
Wzór na liczbę cykliczną mówi:
v (G) = e - v + p
co daje 5 = 10 - 6 + 1 i tak jest poprawne!
„Cyklomatyczna liczba złożoności McCabe'a” podana w jego pracy to
5 = 9 - 6 + 2 (w artykule nie podano dalszych wyjaśnień)
które okazuje się być poprawne (daje v (G)), ale z niewłaściwych powodów, tj. używamy:
ṽ (G) = ẽ - v + 2
a zatem ṽ (G) = v (G) ... uff!
Ale czy ten środek jest dobry?
W dwóch słowach: niezbyt
- Nie jest całkowicie jasne, jak ustanowić „wykres przepływu instrukcji” procedury, szczególnie jeśli obsługa wyjątków i rekurencja wchodzą w obraz. Zauważ, że McCabe zastosował swój pomysł do kodu napisanego w FORTRAN 66 , języku bez rekurencji, bez wyjątków i prostej strukturze wykonywania.
- Fakt, że procedura z decyzją i procedura z pętlą dają ten sam CCN, nie jest dobrym znakiem.
- Jeszcze mniej dobry jest fakt, że
forpętle i whilepętle są obsługiwane w ten sam sposób (zauważ, że w C można nadużywać fordo wyrażania whilew inny sposób; tutaj mówię o ścisłej for (int i=0;i<const_val;i++)pętli). Wiemy z teoretycznej informatyki, że te dwie konstrukcje dają całkowicie różne moce obliczeniowe: funkcje prymitywno-rekurencyjne, jeśli jesteś tylko wyposażony for, częściowe funkcje μ-rekurencyjne, jeśli jesteś wyposażony while.
- Eksperyment mający ekspertów ocenić złożoność kodu pokazuje, że CCN nie oddają ideę „kodu złożoności”, a także innych środków, w szczególności nauki oprogramowania Halstead za i Shao and Wangs' poznawczego rozmiaru funkcjonalnego (ten ostatni jest najwyraźniej zwycięzca), patrz: Zastosowanie trzech wskaźników złożoności poznawczej, Międzynarodowa konferencja nt. postępów w dziedzinie technologii informacyjno-komunikacyjnych w regionach wschodzących, 12–15 grudnia 2012 r.
- Weryfikacja empiryczna pokazuje, że (przynajmniej w przypadku dojrzałego kodu) CCN jest silnie skorelowana liniowo z LOC (liniami kodu), tj. CCN zwiększa się naturalnie wraz z długością procedury i równie dobrze można użyć liczby LOC do wyrażenia złożoności. Lepszym miernikiem niż bezwzględny CCN może być CCN / LOC. Zobacz w szczególności: Ponownie przeanalizowane wskaźniki złożoności cyklicznej - DSpace @ MIT i Rola empiryzmu w poprawie niezawodności przyszłego oprogramowania