Iterating over all non isomorphic connected graphs of given order

asked 2012-06-26 06:33:20 +0100

Jernej
67 ●3 ●4 ●12

Hello!

I would like to iterate over all connected non isomorphic graphs and test some properties. For all the graphs on less than 11 vertices I've used the data available in graph6 format here.

Now I would like to test the results on at least all connected graphs on 11 vertices.

Looking at the documentation I've found that there is a graph database in sage. However, trying just the first example resulted in some errors :

RuntimeError
Traceback (most recent call last)

/home/a/<ipython console=""> in <module>()

/usr/lib/sage/local/lib/python2.7/site-packages/sage/databases/sql_db.pyc in show(self, **kwds) 664 cur.execute(self.__query_string__, self.__param_tuple__) 665 except: --> 666 raise RuntimeError('Failure to fetch query.') 667 668 print _create_print_table(cur, [des[0] for des in cur.description], \

RuntimeError: Failure to fetch query.

What I would like to ask is the following:

Is there a way to iterate over all connected (nonisomorphic) graphs of order 11?
Is there a databse for these graphs already present in sage?
Has anyone considered integrating (and extending) the data from McKay's site into sage?

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2012-06-26 07:38:11 +0100

Nathann
1615 ●2 ●15 ●36

Hellooooooo !!

I can't answer for the graph database problem (no Sage installed on my computer), but there is a way for you to use Nauty through Sage !

If you have not installed the spkg already, you can do it by typing sage -i nauty in a console, or something like install_package("nauty") from the inside of Sage.

Afterwards you will bd able to use the nauty_geng method, with a "-c" flag that probably interests you.

http://www.sagemath.org/doc/reference...

Note that 11 is probably the limit of graphs that you can enumerate from within Sage, where most of the time is spent converting Nauty's graphs to Sage objects :-)

Nathann

edit flag offensive delete link

Comments

That was very helpful, thank you!

Jernej ( 2012-06-26 12:27:06 +0100 )edit

Note: Nauty was made a standard package in Sage Trac ticket 19919, merged in Sage 7.1.beta6 (which was released 2016-03-03). Since then, the sage -i nauty step is no longer necessary.

slelievre ( 2019-06-10 14:35:33 +0100 )edit

add a comment

answered 2012-06-26 12:42:16 +0100

fidbc

2423 ●4 ●26 ●61

Hi!

1) As @Nathann pointed out, you can install nauty by using

$ sage -i nauty

Once nauty is installed you can just iterate through connected graphs on 11 vxs with

sage: for g in graphs.nauty_geng('-c 11'):
          test_property(g)

2) There is a graph database, but apparently it only contains graphs up to 7 nodes (up to 8 in an optional package). Btw, I did not get any errors when running the example, what version of sage are you running?

3) It might not be worth incorporating this data into sage, it is even faster to generate it using geng than to download it or even writing it to the hard drive! :)

Although 1) might solve the problem, my suggestion would be to use geng from the command line and generate the g6 strings for all connected graphs on 11 vertices and store them in a file. Then just use sage to iterate through this file generating one graph at a time and testing properties.

edit flag offensive delete link

Comments

I am running Sage Version 5.0, Release Date: 2012-05-14.

Jernej ( 2012-06-26 13:53:48 +0100 )edit

That is strange, it worked for me out of the box.

fidbc ( 2012-06-26 16:03:48 +0100 )edit

As to your suggestion to write all graph6 strings to a file, there are over 1 billion non-ismorphic connected graphs of order 11. Each one is a string of characters, 11 characters long. If 1 character is 1 byte, then that's 11 billion bytes, or approximately 11 GB, 3 or 4 or 5 times Sage itself. I didn't include any space for commas and/or spaces to separate the strings. I guess you could get away without them since every graph6 string of a graph of order 11 is 11 characters long. Just use 1. It's pretty fast.

G-Sage ( 2012-07-25 11:29:02 +0100 )edit

By the way, there are over 165 billion at order 12 and over 50 trillion at order 13. So, as Nathann said, 11 might be about as far as you can go. By the way, you can also limit by edges for g in graphs.nauty_geng("11 10:23 -c") gives all graphs of order 11 with between 10 and 23 edges that are connected. This could help you get a little farther over a long period of time.

G-Sage ( 2012-07-25 11:32:20 +0100 )edit

Sorry, I'm quite new to sage: where should I type "sage -i nauty" to install it? I tried it in a sage terminal session, and got SyntaxError as a result. I also tried evaluating "install_package("nauty")" in the browser, in a new worksheet, and I got : "The Sage function 'install_packages' is currently broken: it does not correctly install new packages. Please use 'sage -i nauty' from a shell prompt instead."

rodolpheg ( 2014-09-09 23:25:58 +0100 )edit

see more comments

Your Answer

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

Add Answer

Iterating over all non isomorphic connected graphs of given order

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Iterating over all non isomorphic connected graphs of given order edit

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Iterating over all non isomorphic connected graphs of given order