[Nauty] Sortedness of canonically labeled sparse graphs

Nick Matteo kundor at kundor.org
Sat Mar 12 05:50:47 AEDT 2016


Hi Brendan,
Thanks for looking into it! It is not a problem to call sortlists_sg
afterward—probably changing the manual is the way to go.

On Thu, Mar 10, 2016 at 6:43 PM, Brendan McKay <Brendan.McKay at anu.edu.au> wrote:
> 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.

In my case I am generating a lot of cubic graphs and discarding
isomorphs. When the canonical graphs are sorted, I can put the
adjacency lists in a std::set. If I've generated k graphs, this has
log(k) lookup time, instead of comparing each new graph to all k
previously found ones—it gives a dramatic speed improvement.

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

Also changing gt_abort(char*) to gt_abort(const char*) in gtools.h
would fix the warnings when including that file in a C++ program.

Thanks,
Nick Matteo



More information about the Nauty mailing list