NPATH Complexity Demystified

“NPATH, which counts the acyclic execution paths through a function, is an objective measure of software complexity related to the ease with which software can be comprehensively tested.”[1]  This is the definition from an article written in 1988 by Brian Nejmeh.  As informative as this is, my eyes glazed over half way into it.

So what the heck is acyclic execution anyway?  The definition of acyclic is something that doesn’t form part of a cycle.  So essentially what we are talking about is the number of paths or routes from one end of the code to the other.  In other words, how many different ways can you take to move through a function or method.

Let’s take an example:

We have 2 if-else statements here.  NPATH complexity is basically multiplicative.  What I mean by that is that when you have 2 statements that each have 2 options, you have 4 possible paths, a third if statement would increase it to 8, a 4th would be 16 and so on.  Eight if statements in a function gives you 256 paths through the code. (2*2*2*2*2*2*2*2).

The goal is to limit your NPATH complexity in a given method down to 200 or less.  Some say cyclomatic complexity does not go far enough on its own to account for the multplicative effect of introducing several choices that have to be made as you move through the code.  Personally, I check against both metrics, beacause you can exceed 200 paths with fewer than 10 decision points.  I think it just make sense to use both metrics.

As with other complexity metrics, this one can be checked with PHP Mess Detector (phpmd).  The importance of staying under the 200 path threshold is realized when you develop tests and start trying to debug.  The solution to high NPATH complexity is as simple as focusing or keeping your code recfactored to put things into small enough parts that they are not overly complex.

In the end, NPATH is a pretty common sense metric, as it will make your code easier to work on.  It will also enable you to develop easier to implement unit tests and if you do have a problem, it is much easier to debug a few smaller functions than it is to debug one huge one.

Best of Luck



, ,

  1. #1 by Grayson Koonce on November 14, 2012 - 11:57 pm

    Great post :)

    You mention that you check against both metrics, but only seem to list 1; keeping acyclic execution below 200. Am I missing something?

    • #2 by Andrew on November 15, 2012 - 7:38 am

      Sorry, this is what happens when I write late at night. The other metric I was referring to was my previous post about Cyclomatic Complexity. So essentially I meant that I check against both cyclomatic and Npath complexity. Cheers!

Comments are closed.