[Nauty] Sortedness of canonically labeled sparse graphs

[Brendan McKay]

Dear Nick,

Indeed, you have found a discrepancy between the manual and the
program.  Thanks for reporting it.

To tell others what we are talking about, in the sparse form of nauty (also
used by Traces), the list of neighbours of each vertex are not required to
be in numerical order.  The question is whether the canonical graph made
by nauty (or Traces) should have sorted lists.  At the moment nauty does
not sort the lists and the manual is wrong about this.

To compare two canonical graphs, there is a procedure aresame_sg() which
compares two labelled graphs without assuming they are sorted.  At least
for large graphs, it will be faster than sorting first. I recommend you use
that unless you are doing something more complicated like hashing or
sorting arrays of graphs.

One time sorting the lists is a good idea is before writing in sparse6
format.  Otherwise you won't get consistent files.  Graph6 output does
not depend on the order of the lists.

I need to review this issue carefully and might change the behaviour.

Good idea about "const".  I should use it more often.

Cheers, Brendan.

On 11/03/2016 4:20 AM, Nick Matteo wrote:
> 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
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> http://mailman.anu.edu.au/mailman/listinfo/nauty