Archive for October, 2008

How to count paths through my code, and why is this important?

People are often confused about the idea of counting and testing paths through a program, and why this is important. If a program contains selection structures or certain loop structure, each time a program runs, different statements may be executed. For example a program with a single IF structure has two possible paths. That’s because there are two ways the program might behave when it encounters an IF structure. If the test is true the program goes into the IF section and executes the statements. If the test if false the program skips the statements in the IF section entirely. SO .. two paths.  The same is true for a program with a single an IF..ELSE structure. If the test is true the program goes into the IF section and executes the statements. If the test if false the program skips the statements in the IF section and executes the statements in the ELSE section

So in either case there are two possible paths through the program and it’s important to test for either to ensure that the program runs correctly if the test is true and also if the test is false.

If a program contains two separate IF or IF..ELSE structures, then there are four possible paths through the program. The two tests could be both be true, or the first could be true and the second false, or the first could be false and the second true, or both tests could be false.  So you would want to test all four of these paths to be sure that the program behaves correctly under each condition.

If a program contains chained IF..ELSE structures, you would count the number of paths simply by looking how many routes there through the entire structure. For example the following code contains two If..ELSE structures chained together which permits three paths:

if ($sales >= 500)
$bonus = 500;
elseif ($sales >= 250)
$bonus = 250;
$bonus = 0;

An event-controlled loop structure can be considered to have at least two paths in that the test may be immediately false in which case the loop is not executed at all, or the test is true at least once in which case the loop is executed at least once.  Of course the loop structure might include selection or other loop structures which would increase the number of paths.

When a test condition includes AND or OR operators to combine multiple tests that together generate a single overall result, you could say that this still generates two possible paths, since the overall test will be true or false, so there are two routes though the code. In this textbook I have considered a separate path for each test within the overall test condition, since each should be tested. SO for example, I have considered:

if ($sales >= 500 and $yearsOfService > 2)
$bonus = 500;
$bonus = 0;

to contain four paths: $sales >= 500 is true and $yearsOfService > 2 is true, or $sales >= 500 is true and $yearsOfService > 2 is false, or $sales >= 500 is false and $yearsOfService > 2 is true, or $sales >= 500 is false and $yearsOfService > 2 is false.

Even relatively small programs may contain a number of selection structures and loops, you can see that this quickly becomes unmanagable. For example a program that contains eight separate OF or IF..ELSE structures, and a chained IF..ELSE structrure with six different paths would contain a total of 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 7,  or 1792 paths! Add just a few more selection structures and the numberof paths goes much higher. Even a medium-size program contains so many paths that complete testing becomes extremely difficult. This is one reason why programs so often contain bugs – it is extremely difficult to test all possible paths, and at a certain level of complexity it literally becomes impossible. Which is not reassuring when you consider that software controls many of the systems on which we depend for our well-being.

An important approach that reduces the difficulty of testing and provides many other benefits is code modularity, often termed a “divide and conquer” approach. By breaking programs down into separate modules (functions and objects), pieces of code can be tested separately, and then assembled when each separate piece  is known to work correctly. Of course the code must also be tested after assembly to ensure that the various pieces interact correctly. Code modularity is also important for effective software design, reusability, documentation, and maintenance.


Leave a Comment