Process model의 Complexity(Simplicity) 계산법 (2) (Cyclomatic Metric이란?)

 저번 포스팅에서 우리는 프로세스 모델의 complexity를 계산하는 방법 중 하나인 Cardoso Metric에 대해 알아보았다. 이번 포스팅에서는 프로세스 모델의 complexity를 계산하는 또 다른 방법인 Cyclomatic Metric에 대해 알아보겠다.

Cyclomatic Metric이란?

 Cyclomatic Metric은 그래프에서의 Vertex(노드)와 Edge의 개수에 집중한다. 예를 들어 ,다음과 같은 두 그래프가 있다고 하자.

두 개의 그래프

왼쪽 그래프와 오른쪽 그래프는 vertex의 개수는 같지만, 오른쪽 그래프의 edge 개수가 더 작다. 즉, 같은 노드의 개수를 가지고 있지만 오른쪽 그래프가 나타낼 수 있는 behavior의 경우의 수가 더 작고, 달리 말하면 오른쪽 그래프가 왼쪽 그래프에 비해 단순하다. 이러한 점에서 착안하여 Cyclomatric metric은 복잡도를 다음과 같은 식으로 표현한다. 

Cyclomatic metric의 정의

여기에서 E는 edge의 개수, V는 vertex(노드)의 개수, p는 해당 그래프의 connected component의 개수이다. 그러므로 위 예시 그래프에서 왼쪽 그래프의 CM은 9 - 6 + 1 = 4, 오른쪽 그래프는 7 - 6 + 1 = 2로 왼쪽 그래프의 complexity가 더 높음을 알 수 있다.

 

Extended Cyclomatic Metric

 위의 Cyclomatic Metric을 Process Model (Workflow net)로 적용시키려면 어떻게 해야할까? 해당 페트리넷의 

Reachability Graph를 찾고, (이를 찾는 과정은 링크된 포스팅으로 대체한다.) 이에 대해서 위의 Cyclomatic Metric을 적용시키면 된다. 이를 식으로 정의하면 다음과 같다. 

Extended Cyclomatic Metric의 정의

 이것이 그냥 Cyclomatic Metric과 다른 점은, 그래프가 페트리넷의 Reachability graph라는 점, 그리고 p가 connected component가 아닌 strongly connected component라는 점이다. 그것 외에는 위의 Cyclomatic metric과 똑같다고 생각하면 된다.

 

 이번 포스팅에서는 Cardoso Metric에 이어 프로세스 모델의 복잡도를 계산하는 방법 중 하나인 Cyclomatic Metric에 대해 알아보았다. 방법 자체가 그렇게 복잡한 방법이 아니라 글이 많이 짧다.. 이외에도 Structuredness metric 등 다양한 복잡도를 계산하는 알고리즘이 존재한다. 이러한 다양한 계산 방법에 대해서는 다음 포스팅에서 알아보겠다. 

References

1. Lassen, Kristian & Aalst, Wil. (2009). Complexity metrics for Workflow nets. Information & Software Technology. 51. 610-626. 10.1016/j.infsof.2008.08.005. 

2. T. J. McCabe, "A Complexity Measure," in IEEE Transactions on Software Engineering, vol. SE-2, no. 4, pp. 308-320, Dec. 1976.