This week, I spent most of my time testing the Rocs graph-layout-plugin. I needed to test the method that applies the force-based layout algorithm to a graph, whose signature is the following.
static void applyForceBasedLayout(GraphDocumentPtr document, const qreal nodeRadius, const qreal margin, const qreal areaFactor, const qreal repellingForce, const qreal attractionForce, const bool randomizeInitialPositions, const quint32 seed);
Unfortunately, there is not much that is guaranteed by this method. Basically, given a graph and some parameters, it tries to find positions for each node in such a way that, if we draw the graph using these positions, it will look nice. What does it mean for the drawing of a graph to look nice? How can we test it? This is a subjective concept, and there is no clear way to test it. But there is still something that can be done: non-functional tests.
Before going to the non-functional part, I decided to deal with the easy and familiar functional tests. I was not precise in my description of the method deliberately. Actually, there is at least one guarantee that it should provide: if we draw each node as a circle of radius nodeRadius with centers at the positions calculated by the method, these circles should respect a left-margin and a top-margin of length margin. This was a nice opportunity for me to try the QtTest framework. I wrote a data-driven Unit Test and everything went well.
Back to the non-functional part, I decided to write a quality benchmark. The idea is to measure some aesthetic criteria of the layouts generated for various classes of graphs. The metrics already implemented are: number of edge crosses, number of edges that cross some other edges, number of node intersections and number of nodes that intersect some other node. Although there is no formal definition of a nice layout, keeping the values of these metrics low seems to be desirable. Currently, I already implemented generators for paths, circles, trees and complete graphs. For each one of these classes of graph, I generate a number of graphs, apply the layout algorithm a certain number of times to each of them, and calculate summary statistics for each one of the considered aesthetic metrics.
For now, there is only one layout algorithm which can applied to any graph. The idea of the quality benchmark is to compare it to other layouts algorithms I will implement. But it does not mean that the quality benchmark is currently useless. Actually, the results I got were quite revealing. The good part is that there were no intersection between nodes. But the results about edge crossing are not so good. Despite my efforts in tuning the parameters, the algorithm can fail to eliminate all edge crosses even for very simple graphs such as paths and circles. Fortunately, choosing parameter values specifically for a graph can sometimes help, and the user can do that in the graph-layout-plugin user interface.