Ask Your Question

using nauty optional spkg for canonical labeling

asked 2012-06-03 13:10:31 -0500

atsign gravatar image

updated 2015-01-13 14:52:18 -0500

FrédéricC gravatar image

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:

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?

edit retag flag offensive close merge delete

1 answer

Sort by » oldest newest most voted

answered 2012-06-04 10:39:05 -0500

Nathann gravatar image

Could you be looking for something like graphs.nauty_geng ? :-)


edit flag offensive delete link more


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 gravatar imageatsign ( 2012-06-05 05:27:50 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2012-06-03 13:10:31 -0500

Seen: 416 times

Last updated: Jun 04 '12