Protected: Measuring Complexity

In this post I want to examine one way of measuring code complexity or other similar processes such as business logic. There are already several algorithms available for measuring code complexity such as Cyclomatic Complexity, the article Programming Tools: Code Complexity Metrics gives an overview of several complexity metrics.

We want to measure code complexity by somehow mapping the problem to one of packing. The idea is to map code to a set of 2d polygons (one way is to have each class be its own polygon) and then measure the complexity of the set of 2d polygons through packing. The complexity metric I use for a set, S, of 2d polygons is the density of the best 2d packing of S.

First the mapping of code to polygons needs to be defined. For an object oriented language each object (by object I mean a Java or C++ class) is mapped to its own polygon, similarly for a functional language each function is mapped to a polygon. For the remainder of this article I’ll assume the language is object oriented.

The mapping from a class to a polygon needs to use some simple measures of complexity.

1. The number of calls to distinct functions outside the class (by distinct I mean two calls to strlen() would count as 1 call to a distinct outside function).
2. The number of functions insides the class (this may need merging with 3).
3. The total number of branches inside the class (by branch I mean an if-then statement, case statement, or any similar construct).

Let P be the polygon to be mapped from an object O. The number of vertices of P equals 1. The average interior angle of P will be equal to the interior angle of a regular polygon with 1 vertices but the standard deviation of the interior angles of P will be equal to 2 + 3 (A linear scaling factor might be needed). By perturbering the interior angle of P a more complex shape is created. The element of randomness does mean that the mapping is non-deterministic but that’s not a large problem because measuring code complexity is fundamentally a fuzzy task.

My next post will finally describe a slightly different algorithm for solving tangram puzzles.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s