Comment 4 for bug 712913

Revision history for this message
Minh Van Nguyen (mvngu) wrote :

> igraph_ring() is a pretty simple function. OK, this is because it calls
> igraph_lattice(), which can do a bit more than just generating ring and line graphs.
> Still, igraph_lattice() is less than 100 lines of code. Your test suite is about 800
> lines. This seems to be out of proportion for me.

My understanding is that it's OK for a function's test suite to be out of proportion (in terms of lines of code) with respect to the function itself. When you take into account branch test coverage, boundary value tests, conformance to known mathematical properties, etc., you're really looking at having a test suite that will be out of proportion with respect to the function it's testing. A thorough test suite can serve as a suite of regression tests. I really like how the SQLite team tests SQLite; see

http://www.sqlite.org/testing.html

Beginners to igraph such as myself face the daunting task of learning how to use igraph's C library. The one place where beginners (especially myself) look for examples is in the tutorial (if there is any) or the directory of examples as found under example/. The more varied the examples the easier it is for beginners to learn how to use igraph's C library.

In test-driven development, a function that is not tested (with respect to known results) can be considered broken. Take the example of the function igraph_watts_strogatz_game() in src/games.c. It's simple and less than 50 lines of code, yet it's broken because it detracts from the original Watts-Strogatz model as published in

* D. J. Watts and S. H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 393(6684):440--442, 1998.

I consider the present implementation of igraph_watts_strogatz_game() to be an extension of the original Watts-Strogatz model. Here are my reasons why I consider this function broken. Until recently, the function igraph_watts_strogatz_game() could generate a rewired graph that has loop edges, but the original Watts-Strogatz model doesn't allow loop edges in any rewired graph. Fortunately, the issue of loop edges was fixed at

https://bugs.launchpad.net/igraph/+bug/712381

and I thank you for that fix. Another reason why igraph_watts_strogatz_game() is broken is that it can generate a rewired graph that is actually a multigraph, which detracts from the original Watts-Strogatz model. Grep'ing through C files under examples/simple/ fails to show up any tests that uses the function igraph_watts_strogatz_game(). There are plenty of rooms for users to think that igraph_watts_strogatz_game() will generate a rewired graph that conforms to the original Watts-Strogatz model, i.e. a rewired graph that is simple and doesn't change the number of edges and vertices. But that is not the case and users are not likely to notice this until they actually carefully inspect the graph generated by igraph_watts_strogatz_game(). Having plenty of documented and commented tests for igraph_watts_strogatz_game() should alleviate such potential confusion.

> We need to maintain this code in the future, and even if you don't change the
> testing code too often, sometimes you need to, e.g. API changes are quite frequent
> in igraph, because a lot of the API is messy, or new functionality is added. In
> these cases we need to change the tests as well. And this requires effort and time.
> (In general, I'm not talking about igraph_ring() now.)

A reason to have an extensive test suite for the igraph C library is to detect regressions. An API change can result in a failed test; one need to see why the test fail and change accordingly. That's just a normal part of maintaining code. Of course one could have minimal test code to lessen the time and effort required for maintenance. But that doesn't give a user much confidence that a function works or that the result it generates conforms to known mathematical properties. An extensive test suite for a function helps to build confidence in the correctness of the function.

> As for igraph_ring(), I would prefer some more concise tests, e.g. I don't see any
> need checking the girth of the graph, or even the number of edges. Just test the
> boundary cases, i.e. 0, 1, 2, 3, vertices, query the full edge list to see that it
> is all right and that's it.

There's a very simple way to compute the girth of an undirected circular ring (i.e. a cycle graph): the required girth is just the number of vertices. One need to ensure that the above generated ring does indeed satisfy this known property. Again this comes back to the issue of building confidence in the correctness of the result generated by igraph_ring(): whether the generated graph satisfies some known mathematical properties. One could get carried away with testing a larger list of known properties for the cycle graph, but we don't need to go that far; just a tiny list of known simple properties for now is good enough.

> Or maybe just store the edges of the correct graphs, and then see whether they are
> isomorphic to the ones create by igraph_ring(). Maybe this is the simplest, and it
> can be done with more readable code. I.e. something like:
>
> igraph_real_t edges_undirected_circular_3[] = {0,1, 1,2, 2,0 };
> igraph_real_t edges_undirected_line_3[] = {0,1, 1,2 };
> ...
> igraph_ring(&g, 3, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1);
> if (! check_ring(&g, edges_undirected_circular)) return 1;
> ....
>
> where check_ring() creates a graph from the given edge list and checks that it is
> isomorphic to the supplied graph.

Now you're giving me an itch to scratch :-) Give me some time to write some examples of such tests.