using nauty optional spkg for canonical labeling

 1 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? asked Jun 03 '12 atsign 11 ● 3

1 Answer:

 0 Could you be looking for something like graphs.nauty_geng ? :-) Nathann posted Jun 04 '12 Nathann 555 ● 5 ● 16 No, 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.?atsign (Jun 05 '12)

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!
[hide preview]

Stats:

Asked: Jun 03 '12

Seen: 234 times

Last updated: Jun 04 '12

Related questions

powered by ASKBOT version 0.7.22
Copyright Sage, 2010. Some rights reserved under creative commons license.