Jump to content
  • Advertisement
Sign in to follow this  
Chad Smith

AETG Algorithm

This topic is 1413 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I first want to start off by saying that this is an assignment.  While I do need some help I am not looking for the answer on the exact implementation or for someone to write the code for me.  I'm really just looking to get a little help on getting my head around the algorithm without getting my head stuck on the abstract idea of it and some ideas to build on.


Anyway, the assignment is to implement the AETG algorithm that generates combinatorial test suites.  For example: Lets say that we have this very simple table as an example for us to work from:


f0 | f1 | f2 | f3


0  | 3  | 6  | 9


1  | 4  | 7  | 10


2  | 5  | 8  | 11 



Simple enough, it has 4 factors and 3 levels.  I get that we have a total of 34 total different combinations. 


Now I need to create all the pairs and in the assignment I only have to support 2-way coverage.  So to work from the example I gave above here some pairs:

Note: these aren't all the pairs to create of course, just a quick example

{0,3} {0,6} {0,9}

{1,3} {1,6} {1,9}

{2,3} {2,6} {2,9}

so on and so on, until you have all the pairs


And then the suite that covers all pairs and report or save the smallest test suite.  

While when working it out by hand I get this and I seem to understand the basics of it and could solve it by hand given enough time.  I felt if I could solve it that way then I could sit down and put the thought process I did by hand into code, though nothing really seems to be coming out and I am struggling to put this thought process into code and I think it is because that is all my understanding of this algorithm is, just very basic.  I've tried to read some papers on it though the abstract approach to it gets me a little lost in a few areas.  Sadly combinatorical math is not my strong suit at all.


So here is my though process and what I am looking at and what I have so far:

  1. Create the initial covering array/table (like the example I gave at the start of this post).  I am just using my own 2D dynamic array class I created (Basically a wrapper of std::vector< std::vector<int> >
  2. Enumerate all the pairs.  I was thinking of just using another 2D dynamic array.  When I find all the pairs for that row, pushing that row into the dynamic array and just noting that two indexs right next to each other are the pairs.  This though seems like it'd be incredibly slow when the in the end the program uses 50 candidates and that there should be an easier way that I am missing.  Though I also know that it can be evil to try to optimize  something before something gets working.
  3. Create a test suite that uses all pairs.  Report/Save it to the user.  I can see just a 2D Dynamic Array working for this.  Then just reporting that array to the user (printing it out or saving the array to a file).

As you can see I have a pretty bare bone basic knowledge of it and each paper I read on it i just seem to confuse myself more with with the abstract view they seem to give.  With that I am struggling knowing about this algorithm and hoping someone here could try to explain some things, really anything about it.


Is there something I should look at or have any ideas for me?  Right now I am stuck on the loop to enumerate all the pairs.  If I was doing it on paper I would just start on the top left and pair that up with everything to the right of it (using example from above, that'd give me the pairs)

{0,3} {0,4} {0,5} {0,6} {0,7} {0,8} {0,9} {0,10} {0,11}

then just move down to the next row in that column, then move to the next column once I have done all the rows for a column.  Though I seem to be struggling in putting that into the correct for loop.


Thanks for any ideas anyone may have.  I'll take any ideas in trying to translating it into code.




Edited by Chad Smith

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!