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-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
The code is in two files
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
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.
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
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
sparsegraph types of
course -- simple representations without extra info.
Temporary memory is allocated in the Nauty way with
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
vpar.gp for many vpar operations in PARI/GP.
for some other graph (and tree) creation, in Perl.
This page Copyright 2022 Kevin Ryde, except for the GPLv3 logo which is Copyright Free Software Foundation and used here in accordance with its terms.
(Back to the sitemap,