How do you unit-test code using graph structures?

Question

I am writing (recursive) code that is navigating a dependency graph looks for cycles or contradictions in the dependencies. However, I am not sure how to approach unit testing this. The problem is that one of our main concerns is will the code handle on all the interesting graph structures that can arise and making sure that all nodes will be handled appropriately.

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.

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.

---

PS- If it matters, all edges in my graph are labelled "must have" xor "cannot have" and there are no trivial cycles, and there is only one edge between any two nodes.

---

PPS- This additional problem statement was originally posted by the question's author in a comment below:

For all vertices N in forest F, for all vertices M, in F, such that if there are any walks between N and M they all must either use only edges labelled 'conflict' or 'requires'.

Answer 1

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.

Answer 2

No testing whatsoever is going to be able to be sufficient in this case, not even tons of real world data or fuzzing. A 100% code coverage, or even 100% path coverage is insufficient to test recursive functions.

Either the recursive function stands up to a formal proof (shouldn't be that difficult in this case), or it doesn't. If the code is too intertwined with application specific code to rule out side effects, that's where to start.

The algorithm itself sounds like a simple flooding algorithm, similar to a simple broad first search, with the addition of a blacklist which must not intersect with the list of visited nodes, run from all nodes.

foreach nodes as node
    foreach nodes as tmp
        tmp.status = unmarked

    tovisit = []
    tovisit.push(node)
    node.status = required

    while |tovisit| > 0 do
        next = tovisit.pop()
        foreach next.requires as requirement
            if requirement.status = unmarked
                tovisit.push(requirement)
                requirement.status = required
            else if requirement.status = blacklisted
                return false
        foreach next.collides as collision
            if collision.status = unmarked
                requirement.status = blacklisted
            else if requirement.status = required
                return false
return true

This iterative algorithm fulfills the condition that no dependency may be required and blacklisted at the same time, for graphs of arbitrary structure, starting from any arbitrary artifact whereby the starting artifact is always required.

While it may or may not be as fast as your own implementation, it can be proven that it terminates for all cases (as for each iteration of the outer loop each element can only be pushed once onto the tovisit queue), it floods the entire reachable graph (inductive proof), and it detects all cases where an artifact is required to be required and blacklisted simultaneously, starting from each node.

If you can show that your own implementation has the same characteristics, you can prove correctness without resulting to unit testing. Only the basic methods for pushing and popping from queues, counting queue length, iterating over properties and alike need to be tested and shown to be free of side effects.

EDIT: What this algorithm does not prove, is your graph being free of cycles. Directed acyclic graphs are a well researched topic though, so finding a ready made algorithm to prove this property should be easy as well.

As you can see, there is no need to reinvent the wheel, at all.

Answer 3

1. Randomized test generation

Write an algorithm that generates graphs, have it generate a few hundred (or more) random graphs and throw each at your algorithm.

Keep the random seed of the graphs that cause interesting failures and add those as unit tests.

2. Hard-code tricky parts

Some graphs structures that you know are tricky you can code in right away, or write some code that combines them and pushes them to your algorithm.

3. Generate exhaustive list

But, if you want to be sure "the code could handle all the conceivable permutations you'll find in real world data.", you need to generate this data not from random seed, but by walking though all permutations. (This is done when testing subway rail signal systems, and gives you enormous amounts of cases that takes ages to test. For metro subways, the system is bounded, so there is an upper limit to the number of permutations. Not sure how your case applies)

Answer 4

You are using phrases like "all the interesting graph structures" and "handled appropriately". Unless you have ways to test your code against all of those structures and determine if the code handles the graph appropriately, you can only use tools such as test coverage analysis.

I suggest you start by finding and testing with a number of interesting graph structures and determine what the appropriate handling would be and see that the code does that. Then, you can start perturbing those graphs into a) broken graphs that violate rules or b) not-so-interesting graphs that have problems; see if your code properly fails to handle them.

Answer 5

You could try doing a topological sort and seeing if it succeeds. If it doesn't, then you have at least one cycle.

Answer 6

When it comes to this sort of hard to test algorithm I would go for the TDD, where you build the algorithm based on tests,

TDD in short,

• write the test
• see it's failing
• modify the code
• make sure all tests are passing
• refactor

and repeat the cycle,

In this particular situation,

1. First test would be, single node graph where algorithm should not return any cycles
2. Second one would be three node graph with no cycle where algorithm should not return any cycles
3. Next one would be to use three node graph with a cycle where algorithm should not return any cycles
4. Now you could test it against a bit more complex cycle depending on possibilities

One important aspect in this method is you need to always add a test for possible step (where you split possible scenarios into simple tests), and when you cover all possible scenarios usually algorithm gets evolved automatically.

Finally you need to add one or more complicated Integration tests to see if there any unforeseen issues (such as stack-overflow errors / performance errors when your graph is very large and when you use recursion)

Answer 7

My understanding of the problem, as originally stated and then updated by comments under Macke's reply, includes the following: 1) both edge types (dependencies and conflicts) are directed; 2) if two nodes are connected by one edge, they must not be connected by another, even if it is of the other type or in reverse; 3) if a path between two nodes can be constructed by mixing edges of different types, then that is an error, rather than a circumstance that is ignored; 4) If there is a path between two nodes using edges of one type, then there may not be another path between them using edges of the other type; 5) cycles of either a single edge type or mixed edge types are not permitted (from a guess at the application, I am not sure that conflict-only cycles are an error, but this condition can be removed, if not.)

Furthermore, I will assume the data structure used does not prevent violations of these requirements being expressed (for example, a graph violating condition 2 could not be expressed in a map from node-pair to (type, direction) if the node-pair always has the least-numbered node first.) If certain errors cannot be expressed, it reduces the number of cases to be considered.

There are actually three graphs that can be considered here: the two of exclusively one edge type, and the mixed graph formed by the union of one of each of the two types. You can use this to systematically generate all graphs up to some number of nodes. First generate all possible graphs of N nodes having no more than one edge between any two ordered pairs of nodes (ordered pairs because these are directed graphs.) Now take all possible pairs of these graphs, one representing dependencies and the other representing conflicts, and form the union of each pair.

If your data structure cannot express violations of condition 2, you can significantly reduce the cases to be considered by only constructing all possible conflict graphs that fit within the spaces of the dependency graphs, or vice-versa. Otherwise, you can detect violations of condition 2 while forming the union.

On a breadth-first traversal of the combined graph from the first node, you can build the set of all paths to every reachable node, and as you do so, you can check for violations of all the conditions (for cycle detection, you could use Tarjan's algorithm.)

You only have to consider paths from the first node, even if the graph is disconnected, because paths from any other node will appear as paths from the first node in some other case.

If mixed-edge paths can simply be ignored, rather than being errors (condition 3), it is sufficient to consider the dependency and conflict graphs independently, and check that if a node is reachable in one, it is not in the other.

If you remember the paths found in examining graphs of N-1 nodes, you can use them as the starting point for generating and evaluating graphs of N nodes.

This does not generate multiple edges of the same type between nodes, but it could be extended to do so. This would greatly increase the number of cases however, so it would be better if the code being tested made this impossible to represent, or failing that, filtered out all such cases beforehand.

The key to writing an oracle like this is to keep it as simple as possible, even if that means being inefficient, so that you can establish trust in it (ideally through arguments for its correctness, backed up by testing.)

Once you have the means to generate test cases, and you trust the oracle you have created to accurately separate the good from the bad, you might use this to drive the automated testing of the target code. If that is not feasible, your next best option is to comb through the results for distinctive cases. The oracle can classify the errors it finds, and give you some information about the accepted cases, such as the number and length of paths of each type, and whether there are any nodes that are at the start of both types of path, and this could help you look for cases you have not seen before.

Answer 8

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 </pedantry> separator.

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.

</pedantry>

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.

Answer 9

While this does not directly answer your question, since I think you were looking for more theory with a sprinkle of practice, I'd like to point out that you can de-compose the problem of testing code into graph structures as one of generating a graph structure and then verifying properties of that graph structure after some algorithm has updated the structure.

I do this all the time with a tool in C# called AutoFixture. I independently specify how to construct an object graph for type A, which may contain a type B:

var fixture = new AutoFixture.Fixture().Customize((ICustomization) new AutoMoqCustomization());
fixture.Customize<A>(x => x
  .With(x.B, fixture.Create<B>));
fixture.Customize<B>(x => x
  .With(x.Name, fixture.Create<string>());

// create concrete object instances
var aa = fixture.Create<A>();

// from this point onwards, type B should always return the same object instance
Fixture.Freeze<B>();

var aaa = fixture.Create<A>();
var bb = fixture.Create<B>();
Assert.Equal(aaa.B, bb);

Additionally, you can create policies for how to recursively construct these graphs. For example, AutoFixture has OmitOnRecursionBehavior and ThrowingRecursionBehavior as dual to one another.

For testing Object-Relational Mapping persistence layers, I often need to test the composition of two types of graphs, one superimposed on the other: a metadata graph describing how entities in a database relate to one another, and then an example graph of actual entities linked together. Executing a Persist() method call then has to apply Floyd-Warshall and calculate the unique path through the graph such that each entity is persisted once, and in the right order. To do that, I de-compose the problem into that of building graphs and verifying properties of graphs after Create, Read, Update, Delete. - And it can be further extended to things like Soft Delete, Rename, etc. depending on business requirements.

A more thoughtful way to go about this is discussed by John Hughes in his famous talk, Functional Programming: A Secret Weapon for Software Testing, where he discusses property-based testing in Haskell with QuickCheck.

For example, this could be useful if you are trying to prove certain connectedness properties of your graph under concurrent update. I suspect this is where algorithms for graphs, like yours, go from fairly easy to quite hard to verify!

Broadly, distributed systems testing is a special case of concurrent graph update testing, and because of this, the tool jepsen is widely used to verify ACID properties and other write durability characteristics of distributed, eventually consistent database systems, including verifying properties like causal consistency. Jepsen has been used to identify various record corruption issues with MongoDB, and, in fact, QuickCheck was first used to identify cache coherence issues with a rather popular in-memory caching product.