[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