[Nauty] Sortedness of canonically labeled sparse graphs
Nick Matteo
kundor at kundor.org
Fri Mar 11 04:20:42 AEDT 2016
Hello,
I read in the user guide (nug26.pdf, page 51) that "The canonically
labelled graph produced by nauty is guaranteed to already have sorted
contiguous adjacency lists." But this doesn't seem to be the case.
When comparing the arrays cg.e of various canonically labeled graphs
cg, I find that it's necessary to call sortlists_sg(&cg) first.
Indeed, even for a triangle, the canonically labeled graph returned by
sparsenauty has cg.e = 1,2,0,2,1,0, where the neighbors of vertex 2
are not listed in order.
Code for this example can be seen at
https://www.dropbox.com/s/6kv8m4ro8iq3soc/canon-unsorted.c?dl=0
So it seems either the documentation or the program is mistaken ;-)
On a completely unrelated note, would you consider changing the
declaration of alloc_error in nauty.h and nautil.c to
alloc_error(const char*), rather than alloc_error(char*)? This
shouldn't affect anything, but it will make the compiler complain less
when using DYNALLOC1 and friends in a C++ program.
Thanks,
Nick Matteo
More information about the Nauty
mailing list