ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 05 Jun 2012 12:27:50 +0200using nauty optional spkg for canonical labelinghttps://ask.sagemath.org/question/9029/using-nauty-optional-spkg-for-canonical-labeling/Hello all. I have a project in involving enumeration of some combinatorial objects that makes use of canonical labeling of graphs to eliminate branches of a search tree that (up to automorphism) have already been handled at some prior stage in the search. Finding canonical labelings is by far the most computationally expensive thing happening, so I'd like to try to speed it up by using nauty instead of the implementation that comes with sage.
I have a couple of questions about this: First, as I understand it there's an optional nauty spkg that, according to a dev list email thread I saw contains a python binding for nauty, here's a link for that:
http://comments.gmane.org/gmane.comp.mathematics.sage.devel/16288
On the other hand, having installed the nauty spkg and searched a bit, I don't see any way to access that binding from sage. So my first question is: Was this python binding included in the spkg and how does one access it if so?
The other question is about how much difference can be expected using nauty. Has anyone ever made a direct comparison between the two implementations of the algorithm?Sun, 03 Jun 2012 20:10:31 +0200https://ask.sagemath.org/question/9029/using-nauty-optional-spkg-for-canonical-labeling/Answer by Nathann for <p>Hello all. I have a project in involving enumeration of some combinatorial objects that makes use of canonical labeling of graphs to eliminate branches of a search tree that (up to automorphism) have already been handled at some prior stage in the search. Finding canonical labelings is by far the most computationally expensive thing happening, so I'd like to try to speed it up by using nauty instead of the implementation that comes with sage.</p>
<p>I have a couple of questions about this: First, as I understand it there's an optional nauty spkg that, according to a dev list email thread I saw contains a python binding for nauty, here's a link for that:</p>
<p><a href="http://comments.gmane.org/gmane.comp.mathematics.sage.devel/16288">http://comments.gmane.org/gmane.comp....</a></p>
<p>On the other hand, having installed the nauty spkg and searched a bit, I don't see any way to access that binding from sage. So my first question is: Was this python binding included in the spkg and how does one access it if so?</p>
<p>The other question is about how much difference can be expected using nauty. Has anyone ever made a direct comparison between the two implementations of the algorithm?</p>
https://ask.sagemath.org/question/9029/using-nauty-optional-spkg-for-canonical-labeling/?answer=13654#post-id-13654Could you be looking for something like graphs.nauty_geng ? `:-)`
NathannMon, 04 Jun 2012 17:39:05 +0200https://ask.sagemath.org/question/9029/using-nauty-optional-spkg-for-canonical-labeling/?answer=13654#post-id-13654Comment by atsign for <p>Could you be looking for something like graphs.nauty_geng ? <code>:-)</code></p>
<p>Nathann</p>
https://ask.sagemath.org/question/9029/using-nauty-optional-spkg-for-canonical-labeling/?comment=19688#post-id-19688No, that's not what I'm looking for. That is a wrapper for a command line utility that comes with nauty. It enumerates graphs according to certain parameters. The functionality I want is canonical labeling of graphs. This is available in nauty through its C libraries and through its command line utilities. As I said, I've seen it claimed that sage provides access to these features, but I do not see how. Perhaps another question whose answer would be just as good for me is: How can you find out what modules, classes, and so forth are provided by a given spkg? Is there something more systematic than search_doc, search_def, etc.?Tue, 05 Jun 2012 12:27:50 +0200https://ask.sagemath.org/question/9029/using-nauty-optional-spkg-for-canonical-labeling/?comment=19688#post-id-19688