Nautyextra

This is unfinished C code for miscellaneous extra functions on graphs (graph theory graphs) with the Nauty library and its data types. Some "vpar" tree operations are included too.

Nautyextra is free software (free as in freedom), published under the terms of the GNU General Public License (v3 or higher). Download version 0 here,

nautyextra-0.tar.gz (207k, and sig)

The present state is unfinished, everything may change wildly, but much may be useful or inspiring already. Function areas include

• convenience helpers
• Some simplified interfaces
• Special calculations like independent sets
• Diagnostic prints
• Create particular graphs

The code is in two files nautyextra.c and nautyextra-wip.c. The distinction is/was to be that the "wip" is work in progress ideas or names not yet sure. But presently everything is undecided.

The sources include a few rough development programs. Program devel/sequences.c goes through small graphs with geng and calculates integer sequences of various graph measures. Those not in the OEIS (at the time of writing!) are marked.

Vpar

Some vpar (vertex parent array) tree and forest functions are included. They don't depend on the Nauty library or data types and ought to e split out independently.

One thing undecided for the vpar is whether to be 0-based or 1-based vertex numbers. The current code is 1-based, but think 0-based is more C-like and would match Nauty.

The idea of 1-based had been to match the output of the gentreeg program (which can be compiled into a program too), and it matched my vpar.gp in PARI/GP (where vectors are 1-based) for bringing algorithms straight across. The gentreeg consideration would go if some vpar code includes its own free tree iterators.

As a data type, vpar is simple to create and change. It'd be perfectly possible to keep more info like lists of children or an upwards traversal desired by various algorithms. It's a matter of some complexity holding onto extra info or partial info, versus possibly repeating some work. The same is true of the Nauty graph and sparsegraph types of course -- simple representations without extra info.

Other Notes

Temporary memory is allocated in the Nauty way with DYNALLSTAT etc, but with some sharing of a single-file block of memory instead of per-function. Rumour has it Nauty might change to something alloca() or similar anyway. Could think about that here already anyway. The only question would be whether stack will have as much space as main memory when working with big graphs. Maybe would like a compile-time option.