[Software Engineering] 싸이클로매틱 복잡도(순환 복잡도)

싸이클로매틱 복잡도(순환 복잡도)

싸이클로매틱 복잡도, 혹은 순환 복잡도는 제어 그래프(흐름 그래프)의 정확성을 검증하는 데 유용하고 폐곡선의 수를 이용하여 복잡도 V(G)를 구할수도 있으며 노드(node, N)와 간선(edge, E)의 수를 이용하여 복잡도 V(G)를 구할 수도 있다.

 

먼저 폐곡선의 개념을 이해해보자. 위 그림은 폐곡선 두 개와 개곡선 두 개가 나열되어 있는 그림이다.

폐곡선(closed curve)의 정의는 "시점과 종점이 일치하는 곡선"이다. 즉, 닫힌 곡선을 말하므로 위 그림에서는 왼쪽으로부터 첫 번째, 두 번째 곡선이 폐곡선에 해당한다.

다음으로, 개곡선(open curve)은 영어 단어 그대로 열린 곡선, 즉, 닫혀있지 않은 곡선으로 위 그림에서는 왼쪽으로부터 세 번째, 네 번째 곡선이 개곡선에 해당한다.

 

싸이클로매틱 복잡도를 구할 때 폐곡선을 활용한 방법으로는 제어 그래프에서 폐곡선을 모두 찾고 1을 더해주면 된다. 1을 더해주는 이유는 폐곡선 밖의 영역, 즉, 전체 영역에 대해서도 복잡도를 1만큼 증가시켜야 하기 때문이다.

 

다음으로, 노드와 엣지를 이용하여 싸이클로매틱 복잡도를 구하는 방법을 알아보기 위해 노드와 간선에 대해 알아보자. 노드와 간선은 주로 그래프, 트리 자료구조에서 쓰는 용어로써 아래의 그림을 통해 이해하자.

위 그림에서는 원 안에 0, 1, 2와 같은 수가 기입되어 있다. 이렇게 원으로 표기하는 것들이 노드이다. 그리고 노드와 노드 간의 관계를 표현하기 위해 이어준 선을 간선이라고 한다.

이제 노드의 수와 간선의 갯수를 셀 수 있겠는가? 위 그림에서는 노드도 3개, 간선도 3개이다.

 

노드와 간선의 수를 이용하여 싸이클로매틱 복잡도를 구하는 방법은 간선의 수 - 노드의 수 + 2이다. 공식이니 암기하자.

 

가령, 위 그림과 같이 제어 그래프가 주어질 때 오늘 학습한 두 가지 방법으로 모두 풀어보자.

폐곡선을 이용한 방법으로 먼저 풀어보면, a→b→c 를 이루는 부분에 폐곡선이 1개가 있으며, a→c→d를 이루는 부분에도 폐곡선이 1개가 존재한다. 그리고 c→d를 이루는 부분도 폐곡선이 1개 존재한다. 따라서 외부 전체 영역(d→a→b→c 밖)의 복잡도를 1만큼 더하면 3+1=4

즉, 답은 나. 4이다.

 

노드와 간선의 수를 활용하여 구해보자.

위 문제에서 노드의 수는 4개, 간선의 수는 6개라는 것을 쉽게 확인할 수 있다.

따라서 싸이클로매틱 복잡도는 간선의 수 - 노드의 수 + 2 이므로, 6-4+2 = 4이다.

즉, 답은 나. 4이다.

 

두 방법을 활용하여 구한 값 모두 동일하므로 정확하게 구했음을 확인할 수 있다.

 

마지막으로 위에 문제를 한번 풀어보자.

싸이클로매틱 복잡도 = 폐곡선의 수 + 1 = 2(a→b+a→c, c→d→a) + 1 = 3

싸이클로매틱 복잡도 = 간선의 수 - 노드의 수 + 2 = 6 - 5 + 2 = 3

 

만약 위 문제도 쉽게 이해했다면, 싸이클로매틱 복잡도를 완전히 이해한 것이다.