There are many possible ways to canonically augment graphs, but here I'm picking two pairs of possibilities - vertex vs edge augmentation, and filtering duplicates vs picking a representative from symmetrically equivalent positions. So, the four algorithms are vertex/filter (V/Fil), vertex/symmetric (V/Sym), edge/filter (E/Fil), and edge/symmetric (E/Sym).
Here is a graph of log-average timings (in milliseconds) of the four implementations running on graphs of 4-8 vertices. One very important caveat is that the graph counts for 7 and 8 vertices are not 100% correct.
The rows in blue on the table (4, 5, 6, 7, 8) are the log-averages of rows abov; so 4 = log(average(4a, 4b, 4c)), etc. The full spreadsheet is available here on github (as a .numbers file), or the code is here. I'm not particularly confident in the crude System.getTimeMilliseconds() as a timing method.
However, the striking thing to me is that these numbers suggest that for larger input sizes (n > 6), V/Sym is consistently better than E/Fil. In other words, augmenting by vertex at non-equivalent positions may be faster than augmenting by edges and then filtering duplicates.
One final point that is relevant for molecule generation is that these graphs have no degree-limit apart from n-1 edges for a graph on n. So the behaviour could be different for low-degree graphs (deg <= 4) especially since there will be less symmetries (I think?) for each parent.
Here is a graph of log-average timings (in milliseconds) of the four implementations running on graphs of 4-8 vertices. One very important caveat is that the graph counts for 7 and 8 vertices are not 100% correct.
The rows in blue on the table (4, 5, 6, 7, 8) are the log-averages of rows abov; so 4 = log(average(4a, 4b, 4c)), etc. The full spreadsheet is available here on github (as a .numbers file), or the code is here. I'm not particularly confident in the crude System.getTimeMilliseconds() as a timing method.
However, the striking thing to me is that these numbers suggest that for larger input sizes (n > 6), V/Sym is consistently better than E/Fil. In other words, augmenting by vertex at non-equivalent positions may be faster than augmenting by edges and then filtering duplicates.
One final point that is relevant for molecule generation is that these graphs have no degree-limit apart from n-1 edges for a graph on n. So the behaviour could be different for low-degree graphs (deg <= 4) especially since there will be less symmetries (I think?) for each parent.
Comments