ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 10 Jun 2019 07:35:33 -0500Iterating over all non isomorphic connected graphs of given orderhttp://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/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](http://cs.anu.edu.au/~bdm/data/graphs.html).
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](http://www.sagemath.org/doc/reference/sage/graphs/graph_database.html) 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:
1. Is there a way to iterate over all connected (nonisomorphic) graphs of order 11?
2. Is there a databse for these graphs already present in sage?
3. Has anyone considered integrating (and extending) the data from McKay's site into sage?
Mon, 25 Jun 2012 23:33:20 -0500http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/Answer by Nathann for <p>Hello!</p>
<p>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 <a href="http://cs.anu.edu.au/~bdm/data/graphs.html">here</a>.</p>
<p>Now I would like to test the results on at least all connected graphs on 11 vertices.</p>
<p>Looking at the documentation I've found that there is a <a href="http://www.sagemath.org/doc/reference/sage/graphs/graph_database.html">graph database</a> in sage. However, trying just the first example resulted in some errors :</p>
<blockquote>
<p>RuntimeError <br/>
Traceback (most recent call last)</p>
<p>/home/a/<ipython console=""> in
<module>()</p>
<p>/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], \</p>
<p>RuntimeError: Failure to fetch query.</p>
</blockquote>
<p>What I would like to ask is the following:</p>
<ol>
<li><p>Is there a way to iterate over all connected (nonisomorphic) graphs of order 11?</p></li>
<li><p>Is there a databse for these graphs already present in sage?</p></li>
<li><p>Has anyone considered integrating (and extending) the data from McKay's site into sage?</p></li>
</ol>
http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?answer=13771#post-id-13771Hellooooooo !!
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/sage/graphs/graph_generators.html#sage.graphs.graph_generators.GraphGenerators.nauty_geng
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 `:-)`
NathannTue, 26 Jun 2012 00:38:11 -0500http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?answer=13771#post-id-13771Comment by slelievre for <p>Hellooooooo !!</p>
<p>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 !</p>
<p>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.</p>
<p>Afterwards you will bd able to use the nauty_geng method, with a "-c" flag that probably interests you.</p>
<p><a href="http://www.sagemath.org/doc/reference/sage/graphs/graph_generators.html#sage.graphs.graph_generators.GraphGenerators.nauty_geng">http://www.sagemath.org/doc/reference...</a></p>
<p>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 <code>:-)</code></p>
<p>Nathann</p>
http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=46896#post-id-46896Note: Nauty was made a standard package in [Sage Trac ticket 19919](https://trac.sagemath.org/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.Mon, 10 Jun 2019 07:35:33 -0500http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=46896#post-id-46896Comment by Jernej for <p>Hellooooooo !!</p>
<p>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 !</p>
<p>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.</p>
<p>Afterwards you will bd able to use the nauty_geng method, with a "-c" flag that probably interests you.</p>
<p><a href="http://www.sagemath.org/doc/reference/sage/graphs/graph_generators.html#sage.graphs.graph_generators.GraphGenerators.nauty_geng">http://www.sagemath.org/doc/reference...</a></p>
<p>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 <code>:-)</code></p>
<p>Nathann</p>
http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=19501#post-id-19501That was very helpful, thank you!Tue, 26 Jun 2012 05:27:06 -0500http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=19501#post-id-19501Answer by fidbc for <p>Hello!</p>
<p>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 <a href="http://cs.anu.edu.au/~bdm/data/graphs.html">here</a>.</p>
<p>Now I would like to test the results on at least all connected graphs on 11 vertices.</p>
<p>Looking at the documentation I've found that there is a <a href="http://www.sagemath.org/doc/reference/sage/graphs/graph_database.html">graph database</a> in sage. However, trying just the first example resulted in some errors :</p>
<blockquote>
<p>RuntimeError <br/>
Traceback (most recent call last)</p>
<p>/home/a/<ipython console=""> in
<module>()</p>
<p>/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], \</p>
<p>RuntimeError: Failure to fetch query.</p>
</blockquote>
<p>What I would like to ask is the following:</p>
<ol>
<li><p>Is there a way to iterate over all connected (nonisomorphic) graphs of order 11?</p></li>
<li><p>Is there a databse for these graphs already present in sage?</p></li>
<li><p>Has anyone considered integrating (and extending) the data from McKay's site into sage?</p></li>
</ol>
http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?answer=13769#post-id-13769Hi!
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.Tue, 26 Jun 2012 05:42:16 -0500http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?answer=13769#post-id-13769Comment by G-Sage for <p>Hi!</p>
<p>1) As <a href="/users/30/nathann/">@Nathann</a> pointed out, you can install nauty by using</p>
<pre><code>$ sage -i nauty
</code></pre>
<p>Once nauty is installed you can just iterate through connected graphs on 11 vxs with</p>
<pre><code>sage: for g in graphs.nauty_geng('-c 11'):
test_property(g)
</code></pre>
<p>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?</p>
<p>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! :)</p>
<p>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.</p>
http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=19347#post-id-19347As 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.Wed, 25 Jul 2012 04:29:02 -0500http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=19347#post-id-19347Comment by G-Sage for <p>Hi!</p>
<p>1) As <a href="/users/30/nathann/">@Nathann</a> pointed out, you can install nauty by using</p>
<pre><code>$ sage -i nauty
</code></pre>
<p>Once nauty is installed you can just iterate through connected graphs on 11 vxs with</p>
<pre><code>sage: for g in graphs.nauty_geng('-c 11'):
test_property(g)
</code></pre>
<p>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?</p>
<p>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! :)</p>
<p>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.</p>
http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=19346#post-id-19346By 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.Wed, 25 Jul 2012 04:32:20 -0500http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=19346#post-id-19346Comment by fidbc for <p>Hi!</p>
<p>1) As <a href="/users/30/nathann/">@Nathann</a> pointed out, you can install nauty by using</p>
<pre><code>$ sage -i nauty
</code></pre>
<p>Once nauty is installed you can just iterate through connected graphs on 11 vxs with</p>
<pre><code>sage: for g in graphs.nauty_geng('-c 11'):
test_property(g)
</code></pre>
<p>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?</p>
<p>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! :)</p>
<p>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.</p>
http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=19498#post-id-19498That is strange, it worked for me out of the box.Tue, 26 Jun 2012 09:03:48 -0500http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=19498#post-id-19498Comment by Jernej for <p>Hi!</p>
<p>1) As <a href="/users/30/nathann/">@Nathann</a> pointed out, you can install nauty by using</p>
<pre><code>$ sage -i nauty
</code></pre>
<p>Once nauty is installed you can just iterate through connected graphs on 11 vxs with</p>
<pre><code>sage: for g in graphs.nauty_geng('-c 11'):
test_property(g)
</code></pre>
<p>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?</p>
<p>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! :)</p>
<p>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.</p>
http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=19499#post-id-19499I am running Sage Version 5.0, Release Date: 2012-05-14.
Tue, 26 Jun 2012 06:53:48 -0500http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=19499#post-id-19499Comment by rodolpheg for <p>Hi!</p>
<p>1) As <a href="/users/30/nathann/">@Nathann</a> pointed out, you can install nauty by using</p>
<pre><code>$ sage -i nauty
</code></pre>
<p>Once nauty is installed you can just iterate through connected graphs on 11 vxs with</p>
<pre><code>sage: for g in graphs.nauty_geng('-c 11'):
test_property(g)
</code></pre>
<p>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?</p>
<p>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! :)</p>
<p>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.</p>
http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=24076#post-id-24076Sorry, 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."Tue, 09 Sep 2014 16:25:58 -0500http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=24076#post-id-24076Comment by fidbc for <p>Hi!</p>
<p>1) As <a href="/users/30/nathann/">@Nathann</a> pointed out, you can install nauty by using</p>
<pre><code>$ sage -i nauty
</code></pre>
<p>Once nauty is installed you can just iterate through connected graphs on 11 vxs with</p>
<pre><code>sage: for g in graphs.nauty_geng('-c 11'):
test_property(g)
</code></pre>
<p>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?</p>
<p>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! :)</p>
<p>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.</p>
http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=24093#post-id-24093As you mention: "Please use 'sage -i nauty' from a shell prompt instead." This means you should run `sage -i nauty` from your terminal program (without going into sage).Wed, 10 Sep 2014 20:33:05 -0500http://ask.sagemath.org/question/9112/iterating-over-all-non-isomorphic-connected-graphs-of-given-order/?comment=24093#post-id-24093