순환 복잡도(cyclomatic complexity)는 소프트웨어 모듈 하나에 든 결정 논리의 양을 재는 척도이고, 모듈의 제어 흐름 그래프 구조만으로 정해진다.[1] McCabe는 1976년 논문에서 프로그램 복잡도를 관리하고 통제하려고 그래프 이론에 기반한 이 복잡도 척도를 제안했다.[2]
정의
모듈은 입구와 출구가 하나씩인 함수나 서브루틴이고, C에서는 함수다. 제어 흐름 그래프의 간선의 수 와 노드의 수 으로 모듈의 순환 복잡도 를 다음과 같이 정의한다.[1]
이 값은 그래프 이론의 순환수에, 출구 노드에서 입구 노드로 가는 가상 간선 몫 1을 더한 것이다. 순환수는 다음과 같다.[1]
는 순환수를, 는 값이 그래프의 함수라는 것을 나타낸다.[1]
세는 법
같은 값을 그래프를 그리지 않고 셀 수도 있다. 판정이 모두 두 갈래이고, 나가는 간선이 정확히 둘인 판정 노드가 개면 이다. 소스 코드에서는 if 문이나 while 문 같은 두 갈래 판정마다 1을 더한다.[1]
흐름 그래프가 간선이 교차하지 않는 평면 그래프면, 는 그래프가 평면을 나누는 영역의 수와 같다. 그래프 바깥의 무한 영역도 하나로 센다. 이는 오일러 공식에서 나온다.[1]
불 연산자는 단락 평가를 하면 하나마다 1을 더하고(C의 &&, Ada의 and then), 완전 평가를 하면 더하지 않는다(Ada의 and). 단락 연산자를 그래프에서 감추고 세는 방식도 있지만, 이렇게 만든 그래프는 단락 식에 부작용이 없음을 확인하지 않는 한 테스트에 쓰지 않는다. 소스에서 셀 때는 언어 구문을 해석하는 방식을 일관되게 지킨다.[1]
모듈 여럿의 복잡도
모듈 여럿으로 된 설계에서 호출되는 모듈의 코드를 호출하는 모듈 안에 펼치지 않고 모듈마다 제어 흐름 그래프를 따로 두면, 설계 전체는 모듈의 그래프를 연결 요소로 갖는 그래프 하나가 된다. 연결 요소마다 가상 간선을 하나씩 더해야 하므로, 연결 요소가 개인 이 그래프의 순환 복잡도는 다음과 같다.[3]
모듈이 하나면 이어서 위의 정의와 같다. 이 값은 모듈마다의 순환 복잡도를 더한 값과 같다.[3]
상한
McCabe가 처음 제안한 순환 복잡도의 상한은 10이다. Watson과 McCabe는 NIST SP 500-235에서 상한 10을 뒷받침하는 근거가 많고, 15까지의 상한도 성공적으로 쓰였다고 보았다. 두 사람은 10을 넘는 상한을 숙련된 인력, 형식적 설계, 현대적 프로그래밍 언어, 구조적 프로그래밍, 코드 워크스루, 포괄적인 테스트 계획 같은 이점을 갖춘 프로젝트에만 쓰기를 권했다.[1]
Klocwork는 순환 복잡도 임곗값을 아래 네 범주로 둔다.[4]
| 순환 복잡도 | 위험 평가 |
|---|---|
| 위험이 크지 않은 단순한 모듈 | |
| 위험이 보통인 더 복잡한 모듈 | |
| 위험이 높은 복잡한 모듈 | |
| 위험이 매우 높은 테스트할 수 없는 프로그램 |