test suite for igraph_ring.c

[Minh Van Nguyen]

As of revision 2309, the test suite for rings in examples/simple/igraph_ring.c is next to nothing. The attached patch adds a bunch of tests for igraph_ring().

[Minh Van Nguyen (mvngu)]

After carefully checking my previous patch, I noticed some problems I missed. See the new patch. Here are additions in the new patch:

--- ring-test-suite.diff 2011-02-05 10:00:39.427174071 +1100
+++ ring-test-suite2.diff 2011-02-05 10:01:35.135174070 +1100
@@ -1,7 +1,7 @@
 === modified file 'examples/simple/igraph_ring.c'
 --- examples/simple/igraph_ring.c 2006-03-04 15:49:27 +0000
-+++ examples/simple/igraph_ring.c 2011-02-04 04:40:40 +0000
-@@ -1,29 +1,841 @@
++++ examples/simple/igraph_ring.c 2011-02-04 22:38:34 +0000
+@@ -1,29 +1,847 @@
  /* -*- mode: C -*- */
 -/*
 +/*
@@ -70,7 +70,7 @@
 + /* number of vertices = number of edges */
 + nedges = igraph_ecount(&g);
 + nverts = igraph_vcount(&g);
-+ if ((n != nverts) || (nverts != nedges)) {
++ if (n != nverts || nverts != nedges) {
 + return 3;
 + }
 + /* girth = number of vertices */
@@ -139,6 +139,7 @@
 + return 11;
 + }
 + igraph_destroy(&g);
++ IGRAPH_FINALLY_CLEAN(1);
 +
 + /* Boundary case: undirected (circular) ring on two vertices. */
 + /* The generated ring is the undirected graph with two vertices, which */
@@ -285,6 +286,7 @@
 + return 28;
 + }
 + igraph_destroy(&g);
++ IGRAPH_FINALLY_CLEAN(1);
 +
 + /* Boundary case: undirected noncircular ring on two vertices. */
 + /* The generated ring is equivalent to the undirected graph with two */
@@ -443,7 +445,8 @@
 + if (0 != igraph_vector_size(&v)) {
 + return 47;
 + }
-+ igraph_destroy(&g);
++ igraph_vector_destroy(&v);
++ IGRAPH_FINALLY_CLEAN(1);
 + IGRAPH_VECTOR_INIT_FINALLY(&v, n);
 + IGRAPH_CHECK(igraph_degree(&g, &v, igraph_vss_all(), IGRAPH_ALL,
 + IGRAPH_LOOPS));
@@ -465,6 +468,7 @@
 + return 49;
 + }
 + igraph_destroy(&g);
++ IGRAPH_FINALLY_CLEAN(1);
 +
 + /* Boundary case: directed circular ring on two vertices. */
 + /* This is equivalent to a directed version of the line graph on two */
@@ -654,6 +658,7 @@
 + return 70;
 + }
 + igraph_destroy(&g);
++ IGRAPH_FINALLY_CLEAN(1);
 +
 + /* Boundary case: directed noncircular ring on one vertex. */
 + /* There is no such ring. The generated graph is the null graph. */
@@ -666,6 +671,7 @@
 + return 71;
 + }
 + igraph_destroy(&g);
++ IGRAPH_FINALLY_CLEAN(1);
 +
 + /* Boundary case: directed noncircular ring on two vertices. */
 + /* The generated ring is equivalent to a directed version of the line */

If you think the patch is too long, I can separate it out into logical chunks to help with the review process.

[Gábor Csárdi (gabor.csardi)]

Dear Minh,

I really appreciate the amount of work you have put into this and your other patches. However, with this test suite I have some concerns.

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.

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

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.

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.

What do you think?

Best,
Gabor

[Minh Van Nguyen (mvngu)]

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

[Gábor Csárdi (gabor.csardi)]

I completely agree with you in general. All I am saying, is that we need to keep a balance. Writing overly extensive tests for trivial code is a waste of time and effort, not just now, but future time and future effort as well. E.g. if you test that igraph_ring() generates just the right graph, then you don't need to test the number of edges, the girth, etc., they will be obviously right.

As for having more accessible code examples, I was thinking about the following. In the help comments before a given function, one could give something like \example examples/simple/igraph_ring.c and then the source code of this files would be included in the help, beautified, possibly with links to other functions, etc. This is relatively easy to implement and can be very useful, especially that we already have a lot of code in examples/simple.

[Minh Van Nguyen (mvngu)]

> I completely agree with you in general. All I am saying, is that we need
> to keep a balance. Writing overly extensive tests for trivial code is a
> waste of time and effort, not just now, but future time and future
> effort as well. E.g. if you test that igraph_ring() generates just the
> right graph, then you don't need to test the number of edges, the girth,
> etc., they will be obviously right.

What is logically valid some time is not in line with what is output by a program. There is little point in us carrying on this discussion further. Our effort should be directed at other tasks relating to igraph. From the supplied patch, salvage what you want and merge it or reject the patch altogether. I don't mind either way.

> As for having more accessible code examples, I was thinking about the
> following. In the help comments before a given function, one could give
> something like \example examples/simple/igraph_ring.c and then the
> source code of this files would be included in the help, beautified,
> possibly with links to other functions, etc. This is relatively easy to
> implement and can be very useful, especially that we already have a lot
> of code in examples/simple.

That would be nice. Kind of mirror the idea of doctests in Python. Of course in this case, the code in the \example block would actually compile and work as claimed. As examples under examples/simple/ can be long, it would be much better to provide a link to the relevant example file or a page with the file's content but beautified somehow. But I have no idea how to implement any of the above features.

[Gábor Csárdi (gabor.csardi)]

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/424