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…

- Simon

P.S If you're interested in learning more about performance testing, checkout my Performance Testing 101 course here.


  • Simon,

    Thanks for writing about this. I’ve downloaded the Harry Robinson article and look forward to reading it. Harry is fantastic. His presentation at CAST last year was superb.

    I’ve had a bunch of conversations with James about pairwise /allpairs / combinatorial testing and we started talking a bit about transition models like the one you’re written about here. I still have stuff to learn in this area. Not enough is written about it and I haven’t found the time to study up on it yet. Your post has given me more motivation to do so. Thanks.

    Finally, you mentioned you used TVG to create your pairwise tests. Please check out Hexawise as a possible alternative if you run into any limitations with your existing tool. I’m committed to continuing to make it available to most testers at no cost and to using the bulk of our revenues from big firms to continuously improving it.


    • Simon Knight says:

      Thanks for reading Justin. I’ve heard a bit about Hexawise, but I didn’t realise it was free so will certainly check it out at the soonest opportunity!

  • […] Coaching – Pairwise, de Bruijn & Gray Code – Part 2 Written by: Simon Knight […]