More Augmentation Timings and Conclusions

The previous post showed some rough timings for generating all graphs on n vertices. I've repeated this for graphs where the vertex degree is limited to 4, which is more relevant to molecule generation. Here is the data in the same format:

The series have also been expanded to graphs on 9 vertices, as it takes less time overall to generate degree-limited graphs. However, the main conclusion that I draw - at the moment - from these two timing data charts is this; the choice of canonical augmentation method doesn't make a huge difference.

A lot of variables are unaccounted for here, of course. Each of the five variants of this method could be implemented more efficiently (especially the edge-augmentation methods). Also, there may be other issues that only occur with multigraphs (as with molecules). It seems unlikely that these will overcome the difference between OMG's 18-45 ms per structure and Molgen's 0.008-0.009 ms (from the paper, page 11).

Comments