In the previous post on combinatorial testing, I mentionned that Cartesian product was not a good solution when the number of domains and their dimension grew, because of obvious explosion of the number of tests.

A common approach to this problem is to consider a set of combination to create all the possible 2-tuples between the domains. It is called  PairWize or AllPairs suites generation. In TestFu.Operations, I decided to implement the algorithms found in [1]. Currently only the A1 algorithm is implemented. A2 and A4 should follow soon. Note that those algorithms are constructive, memory cheap and fast.

PairWize suite generation

The use of the PairWize algorithm is straightforward and follows the same semantics as the cartesian product. In the example below, we want to generate the allpairs for 3 domains of respective size 2,3,4.

int[] array1 = new int[] { 1, 2 };
char[] array2 = new char[] { 'a', 'b','c' };
string[] array3 = new string[] { "a", "combinatorial", "hello","world" };

int i = 1;
foreach (ITuple tuple in Products.PairWize(array1, array2, array3))
{
    Console.WriteLine("{0}: {1}",i++, tuple);
}

-- output
1: 1, a, a
2: 1, a, combinatorial
3: 2, a, a
4: 1, a, hello
5: 1, a, a
6: 1, a, world
7: 2, a, a
8: 2, b, a
9: 1, b, combinatorial
10: 2, b, combinatorial
11: 2, b, hello
12: 1, b, combinatorial
13: 2, b, world
14: 2, b, combinatorial
15: 1, c, a
16: 1, c, hello
17: 1, c, combinatorial
18: 2, c, hello
19: 1, c, hello
20: 1, c, world
21: 2, c, hello
22: 2, c, a
23: 1, c, world
24: 2, c, combinatorial
25: 2, c, world
26: 2, c, hello
27: 1, c, world
28: 2, c, world

If you wish to compare with the article, this is the output for a (k,l) = (7,3) and for the bipartite graphs A1 = {0,1,2,3} B1={4,5,6}, A2 = {0,4,2,3} B2={1,5,6} and A3 = {0,1,5,3} B3={4,2,6}. Remember that if we want to generate the test cases using the Cartesian product, we would have 3^7 = 2187 tests to run.

1: 0, 0, 0, 0, 0, 0, 0
2: 0, 0, 0, 0, 1, 1, 1
3: 1, 0, 0, 0, 0, 1, 1
4: 0, 1, 0, 0, 1, 0, 1
5: 0, 0, 0, 0, 2, 2, 2
6: 2, 0, 0, 0, 0, 2, 2
7: 0, 2, 0, 0, 2, 0, 2
8: 1, 1, 1, 1, 0, 0, 0
9: 0, 1, 1, 1, 1, 0, 0
10: 1, 0, 1, 1, 0, 1, 0
11: 1, 1, 1, 1, 1, 1, 1
12: 1, 1, 1, 1, 2, 2, 2
13: 2, 1, 1, 1, 1, 2, 2
14: 1, 2, 1, 1, 2, 1, 2
15: 2, 2, 2, 2, 0, 0, 0
16: 0, 2, 2, 2, 2, 0, 0
17: 2, 0, 2, 2, 0, 2, 0
18: 2, 2, 2, 2, 1, 1, 1
19: 1, 2, 2, 2, 2, 1, 1
20: 2, 1, 2, 2, 1, 2, 1
21: 2, 2, 2, 2, 2, 2, 2

Compairing results with AllPairs

For 10 domains with 10 values each, the TestFu algorithm generate 370 test suite. The AllPairs tool generate 177 which is roughly 50% less. This behavior was expected by the algorithm author. A greedy algorithm on the output could lower our result. Note that the tests were generate in 36.419ms which shows the efficiency of the algorithm.

References:

[1] Efficient Algorithms for Generation of Combinatorial Covering Suites, by Adrian Dumitrescu