While usually 100% line or branch coverage is sufficient to be confident that some code works, it feels like even with 100% path coverage you'd still have doubts.
It seems to me that you're falling into the trap of thinking that code coverage is the deciding metric here and not the quality of the tests that cover the code.
I'll not go on a long tangent, but this is precisely my issue with code coverage as a metric. It's not inherently bad by itself, but it becomes a distraction from the true value of testing: considering the necessary edge cases. If you're going to spend effort somewhere, spend it on writing high-quality tests rather than casting a wider (but still thin) net over the codebase.
I suspect that the issue with code coverage as a metric has been brought to your attention due to the recursive nature of the code, and that you understand that the coverage metric does not account for how many layers of recursion there is.
Based on code coverage alone, you could test your recursive method in a way that it wouldn't even recurse once, and the coverage would tell you that you covered it 100%.
In a way, you are lucky to have such a clear example of why code coverage is a nonsensical metric. I'm genuinely going to remember this because it's a fantastic example.
will the code handle on all the interesting graph structures that can arise and making sure that all nodes will be handled appropriately.
Or, more abstractly:
will the code handle on all the [scenarios] that can arise and making sure that [the unit under test will behave] appropriately.
That's pretty much the concern for everyone who writes unit tests. It also follows the same progression every time:
- List all relevant scenarios that you can think of.
- For each scenario:
- Design your test data and mocks to represent this scenario
- Write a test that asserts the correct behavior in this scenario.
- Over time, if it turns out you forgot a scenario, add it to the suite (i.e. repeat the second bullet point for that scenario.
- Over time, as the codebase changes, re-evaluate your test suite. Some scenarios may have become moot, or new scenarios may have entered the picture. This requires contextual knowledge that cannot be explicitly described in a general guideline.
That's really just it. I don't see a way in which your question is any different.
One more detail though:
So, how does one go about selecting graph structures for test cases to have confidence that their code could handle all the conceivable permutations you'll find in real world data.
Warning: I'm taking the pedantically long route so I can definitely cover any concern you have, no matter how niche or esoteric. If you tire of it, skip to the section after the
For example, if I want to test
myMethod(myEnum), this is an inherently finite set of possible test cases, as it is based on the finite set of enum values. But there are cases where your possible test cases are infinite, or practically so.
Technically speaking, due to how our hardware works, any point of data is strictly finite. Even though a mathematician can conclude that
add(int a, int b) has an infinite range of possible inputs, the computer hardware limits how many possible integer values there are. It's a lot, and I'm not saying you have to test for every integer against every other integer, but it is technically a finite set that you could write every possible test scenario for.
You might think that recursive data structures are technically infinite, e.g. when testing
myMethod(myNode). In a way, that is correct, because they can forever expand downwards (theoretically), but in reality you're still limited by your machine's memory (whether ROM or RAM) and therefore there is a cap on how many recursive nodes you can physically hold.
You would be correct in concluding that any test result then only counts as a conclusive result for the amount of memory that the test used, and the test result cannot be relied on if you run your code on a different machine with more memory available.
I've taken the long way round to get here, but I hope that at some point you started agreeing that trying to cover all possible scenarios is quite quickly turning into more effort than it renders value.
Your question started from the idea of being able to perfectly capture all possible cases, and I used the above section to take that intention towards its logical conclusion. I hope you reconsidered your intention somewhere on that path.
In reality, it's much more productive to cover the bases that you know need covering. Instead of then trying to proactively go and explore to find more edge cases, it's easier to just wait for a bug to arise, identify that it's related to an edge case that you had not yet considered, and then extend the test suite to now include it.
In other words, you only add the edge cases that have had at least 1 real world occurrence, and you don't have to risk wasting time on covering edge cases that will never occur even if theoretically possible.