Nauty vs SageMath speed comparisons?

[Stefan]

Hi guys,

Everybody knows nauty (and maybe traces?) is the state of the art in graph isomorphism and canonical labeling of graphs. What I don't know (but maybe you do?) is how far SageMath is lagging behind. Did anyone do any testing on this? I saw a mention of a paper by Robert Miller, but the link was dead.

I'd appreciate any pointers!

Cheers,

Stefan.

[Dima Pasechnik]

On Monday, 5 October 2015 11:14:54 UTC-7, Stefan wrote:

Everybody knows nauty (and maybe traces?) is the state of the art in graph isomorphism and canonical labeling of graphs. What I don't know (but maybe you do?) is how far SageMath is lagging behind. Did anyone do any testing on this? I saw a mention of a paper by Robert Miller, but the link was dead.

nauty is an optional package in Sage, and is used for (di)graph generation. Not sure whether you can use it for graph isomorphism in Sage easily, though.

sage -i nauty 

Then you do e.g.

sage: list(digraphs.tournaments_nauty(5))

[Nathann Cohen]

Hello,

 

Not sure whether you can use it for graph isomorphism in Sage easily, though.

Nop, currently Graph.is_isomorphic does not call it. Could be nice though, as it would then become possible to compare the two.

The method Graph.is_isomorphic can call "bliss", though. Which was solidly faster than our own implementation of it when it was added.

Nathann 

[David Joyner]

Google for the 2007 thread

open source "nauty"

by Robert Miller.

If sage/boxen was still around, the directory rlmill might have some old slides.

My very vague memory is that the cython versions were comparable to nauty
and that saying "Everybody knows nauty (and maybe traces?) is the

state of the art in graph

isomorphism and canonical labeling of graphs" is debatable since
everyone also knows
Robert's implementation in cython has been around since 2008:-)



> Cheers,
>

[Robert Miller]

I don't think we were ever competitive with nauty speed-wise. But the
code has been written to a very high level of generality and is
capable of working with any objects whose symmetry groups are
interpreted in S_n with only a small amount of work. It has also been
through a lot of debugging and use, and I haven't had a bug report in
years.

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.



--
Robert L. Miller
http://www.rlmiller.org/
http://www.linkedin.com/in/drrlm

[Nathann Cohen]

> The method Graph.is_isomorphic can call "bliss", though. Which was solidly
> faster than our own implementation of it when it was added.

sorry: Graph.automorphism_group()

Nathann

[Stefan]

Yeah, that one doesn't have any timings. I guess someone should sit down and run some tests. Not sure if it'll be me, I'm swamped with work :(

[Siddharth Bhat]

Hey, I've wanted to contribute to sage, and graphs and groups provided by sage is something I use quite often. So, I was wondering how I could help with the issue? If you'd be okay mentoring me, that'd be great :)

[kcrisman]

Wasn't there some email relatively recently where the author of nauty said it was actually okay to use in Sage (e.g., he gave a separate license than his usual one)?

[Jeroen Demeyer]

On 2015-10-06 15:15, kcrisman wrote:
> Wasn't there some email relatively recently where the author of nauty
> said it was actually okay to use in Sage

Yes, there was. However his statement was very vague, it was not clear
what he really meant. I don't think that anybody ever asked for further
clarification.

[Stefan]

Hi Siddharth,

I won't be able to mentor you. If I were to go about doing this thoroughly, I would look at the kinds of tests carried out in the literature on graph isomorphism (specifically here: http://arxiv.org/pdf/1301.1493v1.pdf ) and redo these (or very similar) tests with the listed algorithms as well as with SageMath.

Sadly, I have no time to mentor you on this.

[Nathann Cohen]

Hello,

> Hey, I've wanted to contribute to sage, and graphs and groups provided by sage is something I use quite often. So, I was wondering how I could help with the issue? If you'd be okay mentoring me, that'd be great :)

Well, a first step would be to expose 'nauty' is is_isomorphic. A
first step may be to enable something like
"is_isomorphic(algorithm='nauty')" (for example), and if it proves to
be faster in all cases that could become the default behavior of
is_isomorphic when Nauty is locally installed.

Nathann

[Dima Pasechnik]

Where was that? Well, we might ask for details, why not? It currently says:

Permission is hereby given for use and/or distribution with the exception of sale for profit or application with nontrivial military significance. You must not remove this copyright notice, and you must document any changes that you make to this program. This software is subject to this copyright only, irrespective of any copyright attached to any package of which this is a part.

[Dima Pasechnik]

for it be " faster in all cases" one would need a proper cython interface to it.

Nathann

[Siddharth Bhat]

Cool. I'm up for doing that. So.. I need to bring nauty using cython and call the is_isomorphic function?

--
You received this message because you are subscribed to a topic in the Google Groups "sage-devel" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-devel/mKZ1Ar1lJG0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sage-devel+...@googlegroups.com.

[Julien Puydt]

Hi,

This is indeed the nauty license I know about, and this is definitely
completely GPL-incompatible so can't go into anything (sage, Debian, etc).

Snark on #sagemath

[Jori Mäntysalo]

On Tue, 6 Oct 2015, Dima Pasechnik wrote:

>>> Wasn't there some email relatively recently where the author of nauty
>>> said it was actually okay to use in Sage

>> Yes, there was. However his statement was very vague, it was not clear
>> what he really meant. I don't think that anybody ever asked for further
>> clarification.

I think that somebody did, but I am not sure.

> Where was that? Well, we might ask for details, why not? It currently says:
>
> Permission is hereby given for use and/or distribution with the exception of sale for
> profit or application with nontrivial military significance.

It started with http://trac.sagemath.org/ticket/14110 . I jumped in and
now we kind of have code to generate posets faster. But it can not be
integrated into Sage.

--
Jori Mäntysalo

[Nathann Cohen]

> Cool. I'm up for doing that. So.. I need to bring nauty using cython and
> call the is_isomorphic function?

If Nauty proves much better than our current implementation then that
is what we will need: a fast way to call Nauty. And that means Cython.

This being said, writing a cython interface with Nauty may not be
exactly "quick and clean": thus, if you need to have an idea of how
fast you can expect it to be, you can first try to call Nauty "the
dirty way", by creating a file on which you would then call the
executable. It's up to you.

Also, be aware that we currently have an interface with a software
called bliss, which is used (when installed) in
Graph.automorphism_group and can also compute a canonical labelling
(though that part is not exposed at the moment).

It may be quicker to test (though it's a different software) as all
main pieces are available (the package, a cython file defining the
right structures, etc).

Nathann

[Jori Mäntysalo]

On Wed, 7 Oct 2015, Nathann Cohen wrote:

> If Nauty proves much better than our current implementation then that is
> what we will need: a fast way to call Nauty. And that means Cython.

I know nothing, but to cite Wikipedia: "There are several competing
practical algorithms for graph isomorphism, due to McKay (1981) - - While
they seem to perform well on random graphs, a major drawback of these
algorithms is their exponential time performance in the worst case."

So maybe we should have both current algorithm and Nauty.

--
Jori Mäntysalo

[Nathann Cohen]

> So maybe we should have both current algorithm and Nauty.

In my own experience, the isomorphism test has *never* been either
slow nor the slowest part of my code.

If it was too slow for your usage then having new interfaces makes
sense, otherwise it would just be for the sake of collecting them.

Nathann

[Jeroen Demeyer]

On 2015-10-07 07:49, Jori Mäntysalo wrote:
>>> Yes, there was. However his statement was very vague, it was not clear
>>> what he really meant. I don't think that anybody ever asked for further
>>> clarification.
>
> I think that somebody did, but I am not sure.

I don't see any evidence of that. I don't think that he was asked
further clarification. Given that you already communicated with him for
#14110, maybe you could ask?

Jeroen.

[Jori Mäntysalo]

On Wed, 7 Oct 2015, Jeroen Demeyer wrote:

> I don't see any evidence of that. I don't think that he was asked further
> clarification. Given that you already communicated with him for #14110, maybe
> you could ask?

But I know a little about programming, nothing about copyright laws or
psychology! Anybody else to volunteer...?

--
Jori Mäntysalo

[Dima Pasechnik]

I've just asked Brendan. We'll see.

 

--
Jori Mäntysalo