People consider software testing boring and cheap. Let’s prove them wrong by taking you to a direct graph journey. The post is aligned with the Black Box Software Testing Foundations course (BBST) designed by Rebecca Fiedler, Cem Kaner, and James Bach.

Every program (even those fancy machine learning memory beasts), have paths and subpaths:

A Path through a program has an entry and exit points. The program starts at the entry point and ends at the exit point. Note that stop does not mean program exit, because the program usually waits in a loop for new path execution.

A Sub-path starts and ends anywhere in the program. An N length sub-path runs through precisely N statements.

Directed Graph Notation

We can use directed graph notation to describe possible paths through the program.

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by edges, where the edges have a direction associated with them [Wikipedia].

More information about the directed graph for testers could be found in Paul Jorgensen” s (2008) Software Testing: A Craftsman’s Approach (3rd Ed.).

Example

Let’s take the following directed graph as an example:

We have four paths, two binary branches at two nodes, 2 x 2 = 4.

START => B => D => F => END

START => B => C => D => F => END

START => B => D => E => F => END

START => B => C => D => E => F => END

Think of it as data flow. But with how many variables? If we have only one variable in which value is set in nodes B to 5, in C to 7 and in E to 9, in that case, you need to test three paths. Because node E would override action in node C.

X = 5

X = 7

X = 9

X = 9

But if the program manipulates two variables, you need to test all four paths. In node B we set X = 1, Y = 1. In node C we set X = 2 and in node E we set Y = 3. For every four paths, in the end, we have different combination values for X and Y:

X = 1, Y = 1

X = 2, Y = 1

X = 1, Y = 3

X = 2, Y = 3

For the same directed graph that models a program, we have different numbers of test cases, depending on how data is manipulated through graph paths.