Unit-testing – What should you test with unit tests

If you went with the first option, each method would be isolated and tested independently, but you would never really know that they can really work together properly.

If your methods are truly independent this shouldn't matter. Your second method should:

a) Work correctly when presented with valid data.

b) Fail sensibly and consistently when presented with invalid data.

Equally your first method should do the same. So as long as you handle the error cases they will work together properly.

If you want to test that the methods work correctly together then that's integration testing, not unit testing.

We keep thinking that we have all the tricky ones covered and then we realise that a certain structure causes problems we hadn't considered before. Testing every tricky that we can think of is what we are doing.

That sounds like a good start. I guess you already tried to apply some classic techniques like boundary value analysis or equivalence partitioning, as you already mentioned coverage based testing. After you invested a lot of time in constructing good test cases, you will come to a point where you, your team and also your testers (if you have those) run out of ideas. And that's the point where you should leave the path of unit testing and start testing with as much real world data as you can.

It should be obvious that you should try to pick a big diversity of graphs from your production data. Maybe you have to write some additional tools or programs just for that part of the process. The hard part here is probably to verify the correctness of your programs output, when you put ten thousand different real world graphs into your program, how will you know if your program produces always the correct output? Obviously you cannot check than manually. So if you are lucky, you may be able to make a second, very simple implementation of your dependency check, which might not fulfill your performance expectations, but is easier to verify than your original algorithm. You should also try to integrate a lot of plausibility checks directly into your program (for example, make some bookkeeping if your graph search hit every node and every edge of the graph).

Finally, learn to accept that every test can only proof the existence of bugs, but not the absence of bugs.