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

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 3

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 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.