Category: Rapid Software Testing

Coaching – Pairwise, de Bruijn & Gray Code – Part 2

In my last post, I discussed the beginnings of an approach [suggested by James Bach] for testing transition combinations efficiently. To recap – we have a 5 change, 3125 line set of Pairwise results which correlate to a total number of changes (or test actions) to be performed of 15625. We want to execute this set of changes in the most efficient manner possible, preferably by reducing the number of actions . This means eliminating duplicate or overlapping combinations.

Harry Robinson provided me with some pointers in achieving this goal (as did James of course by pointing me in his direction in the first instance). In particular, his excellent paper on Graph Theory Techniques in Model Based Testing. He explains how to construct a 2 switch “safecracker” or de Bruijn sequence. You can see the results of applying the de Bruijn 2 switch algorithm to my model below.

Things are starting to look pretty complex though. Each node has a total of 10 edges, 5 incoming and 5 outgoing. Our next move would be to traverse the graph above and document the resulting sequence, however you can already begin to see that this is likely to prove troublesome and, if performed manually – error prone.

In addition, the graph above only provides 2 switch cover; i.e. all 2 change combinations. We need all 5 change combinations. Generating a 5 switch graph and traversal sequence manually will be exponentially more difficult.

Thankfully, we don’t have to. We can go here and get the algorithm applied to our model with 5 switch cover instead. If we do this, we end up with a 3129 change sequence (actually 3125 changes +4 delimiting [loop] digits) instead of our original 15625. A 200% improvement.

All we need to do now is map the values from the generated sequence to our actions, and we’re good to go.

Of course, the eagle eyed among you will observe that there appears to be some repetition [of combinations of actions] still, and there is. But what the de Bruijn sequence has achieved is “is the shortest string that contains all possible permutations (order matters) of a particular length [5] from a given set” (Math Illuminated).

What, you want proof that the algorithm works? Well good! So would I. But proving an already peer reviewed set of calculations is beyond the scope of this article. If you want to do some reading around though (you can follow some of the links in this blog) and post any comments you have below. I’ll be more than happy to respond!

Now how does Gray code fit into all this? Stay tuned for part 3…

Hello and Welcome

I'm Simon Knight, Tester turned Product Manager. Helping design awesome products for testers.


GiottoPress by Enrique Chavez