EPIC: Support iterative reading of sparse6 and incremental sparse6 formats

[john-boyer-phd]

Nauty supports output of a "sparse6" and incremental "sparse6" file formats to contain all graphs generated according to its parameterization. Subject to some experimentation, it is likely that the incremental "sparse6" format could significantly improve performance of algorithm testing, i.e., performance and output from command lines of the form planarity -t [-q] C I O.

• Begin by using Nauty to generate all simple undirected graphs of order 10 and each of the possible numbers of edges in separate files. Do this for both the "graph6" and the incremental "spase6" formats so that we can get a sense of when "graph6" is less versus more efficient in terms of storage than incremental "sparse6". It may be necessary to also do this for order 9 and 11 to get a better sense.

The incremental "sparse6" format is expected to helps in the following ways:

• More of the files generated may be able to fit entirely into memory such that read iteration of graph reading occurs over an in-memory string rather than against a file.
• Rather than reinitializing and fully rebuilding each graph to be tested with an algorithm, the incremental format offers the possibility of simply adding an edge or edges to a previously given graph.

If the incremental "sparse6" format looks promising enough, then further work will be done to define the work items in this epic.

For transformation of the first graph in a file to the "sparse6" format, the letter 's' is used, i.e., planarity -t [-q] -ts I O. Since only one graph is transformed, the incremental format is not applicable as an output format.