Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'd like to preface this that this question is similar, but my question doesn't involve randomness, just finicky determinism, so the answer of "use a known seed" doesn't really apply. Likewise, this question is similar, but again, I'm not expecting the algorithm to ever fail -- I just don't know which way it will be correct.

This question came about while testing graph algorithms. but is by no means limited to them. Some algorithms such as A* can have multiple correct answers. Depending on your exact implementation you may get any one of several answers, each of which are equally correct. This can make them difficult to test, though, because you don't know which one it's going to spit out ahead of time, and it's very time consuming to compute the answers by hand.

In my specific case, I got around it by modifying Floyd-Warshall to spit out every possible shortest path, and spent the time hand testing that. It had the benefit of being a good feature in its own right. Then I could test other functions in terms of the known correct paths from FW (if the returned path is any one of the paths returned by FW for that start/end pair, it's correct). Of course, this only works for dense graphs due to how FW works, but it's still nice.

However, that may not always be viable for all algorithms with this characteristic. So far, the best answer I've come up with is to test for the characteristics of a correct answer, rather than the correct answer itself. To go back to shortest path algorithms, you can check the cost of the returned path against the known right cost and make sure the path is valid.

This works, but it can run the risk of not verifying everything correctly the more criteria for correctness there are, especially if the verification is itself complex (e.g. while correct algorithms exist, verifying a minimum spanning tree is a known hard problem; probably harder than constructing the MST itself), in which case you now have to extensively test your testing code. Worse: presumably you have to construct an MST to test an MST verification algorithm so you now have a great scenario where your MST test relies on your MST verification algorithm working, and your MST verification algorithm test relies on your MST generation code working.

Finally, there's the "cheap way", which involves observing the output, verifying it by hand, then hard coding the test to test the output you just verified, but that's not a great idea since you may have to revise the test every time you change the implementation a little (which is what automated testing is supposed to avoid).

Obviously the answer depends on the exact algorithm you're testing to a degree, but I was wondering if there were any "best practices" for verifying algorithms that have several definite, deterministic "correct" outputs, but those precise correct outputs are difficult to know ahead of time, and possibly hard to even verify after the fact.

share|improve this question
2  
If the language allows it you could prove correctness instead of testing it –  miniBill Apr 24 at 23:18
    
There is lots of text, but no question. So, what exactly are you asking? –  BЈовић Apr 29 at 5:08
    
@BЈовић "How should I test implementations of algorithms with multiple and/or difficult to verify correct outputs?" I'm not sure how to make that much clearer, sorry. I'll grant that it could be considered a bit broad depending on your perspective, but I don't think it's undefined. –  Jsor Apr 29 at 6:03
    
I still don't understand. Your algorithm doesn't depend on randomness, and yet it can still produces different outputs. That doesn't make sense at all. Every algorithm, for set inputs, must have same outputs. And that is what is done and tested in unit tests. Even the algorithm in the paper you linked. –  BЈовић Apr 29 at 6:28
    
@BЈовић Of course it's deterministic, but it's also very sensitive to, e.g. the order the graph returns a node's successors. It can cause a bit of a butterfly effect. Whether you push vertex A on a stack before vertex B will lead to a different output if both lead to a shortest path. Using library functions like non-stable sorts or min-heaps just exacerbates the problem. –  Jsor Apr 29 at 9:53

2 Answers 2

up vote 3 down vote accepted
+100

I'm not sure you are trying to test the correct property, and this causes your ambiguity.

Graph algorithms do not aim at finding some shortest path (this is a side effect), but to minimize or maximize some cost function defined on the set of edges and vertices. Thus, you can check the correctness of a solution by testing for the final value of this functional and asserting that the first and last nodes are the ones actually required.

If you can pre-compute the final cost function value for each possible path (usually unrealistic), then you just have to check that the cost of the solution provided by the implementation under test is equal to the minimum cost among this set (absolute comparison). If you "just" have a gold standard algorithm and/or implementation, then you should compare the cost of its output with the one of the algorithm under test (relative comparison)

For example, a naive test setup would be:

  1. Compute all possible paths between Va and Vb in the test graph with a greedy algorithm.
  2. Compute the cost function (for example, the length if all your edge weights are equal to 1) for each of these paths and find the minimum value.
  3. Apply the algorithm under test.
  4. Make an assertion in your unit test that the tested algorithm cost value is equal to the minimum of the greedy solutions.

If you want to know more about graph based optimization, you can have a look at Yuri Boykov's publications here, though in another context (Computer Vision problems).

share|improve this answer
    
I upvoted, but I'll wait a bit to accept. This is the "test for the characteristics of a correct answer" I mentioned in the question. The problem always comes in making sure you're verifying the right thing. For instance, at once point I was checking the returned cost and making sure the path was valid. Of course the path was valid! It was only the start node! So I had to alter the tests to make sure the path itself actually had the returned, correct cost. Silly mistake, sure, but the more interactions like this your output has, the more likely they are. –  Jsor Apr 29 at 9:59
    
@Jsor in my point of view, it is the continuous improvement benefit of testing: you can't figure out all the correctness properties of the solution at first, then go one day into some failure, improve your test and so on. –  sansuiso Apr 29 at 10:12
    
This answer recommends testing for characteristics of the correct answer, but the important thing is to choose which characteristics make a good test. In this example, verifying that the answer is a path from A to B and that the cost function equals the minimum value gives you two criteria that all correct answers will satisfy, while no incorrect answers will satisfy both criteria. If this answer had not already been given, I would have recommended something similar. Admittedly it is often not easy to know which characteristics to test. –  David K May 1 at 16:40

I think the direct answer to your question is to choose better test cases. I wonder about the test cases you are using. The graphs you use can be CANNED graphs where it is relatively easy for a human to determine the expected response. Try to figure out the "edge" cases that you want to be sure your algorithm handles and create a canned graph for each of the particular edge cases that is easy for a human to compute. For example, in the Djikstra algorithm case, you can probably create some 5x5 or 7x7 graphs that cover all your edge cases, even though your real system might be 500x500.

Then as a final sanity check you can create a more realistic graph test case or two. But in any event, I think sansuiso has it spot on where it is pointed out that you need to be sure you are testing for the correct property.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.