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.Fri, 03 Oct 2014 14:29:05 +0200How to list all the connected graphs with 9 vertices?https://ask.sagemath.org/question/24299/how-to-list-all-the-connected-graphs-with-9-vertices/ What I want to do is exactly to list all the connected graphs with 9 vertices which are also `is_long_hole_free()==False`, i.e., contains an induced cycle of length at least 5. But I can only list all the graphs with a given number of vertices, for example
G = GraphQuery(display_cols=['graph6'], num_vertices=2)
L = G.get_graphs_list()
graphs_list.show_graphs(L)
Fri, 26 Sep 2014 13:31:29 +0200https://ask.sagemath.org/question/24299/how-to-list-all-the-connected-graphs-with-9-vertices/Answer by vdelecroix for <p>What I want to do is exactly to list all the connected graphs with 9 vertices which are also <code>is_long_hole_free()==False</code>, i.e., contains an induced cycle of length at least 5. But I can only list all the graphs with a given number of vertices, for example</p>
<pre><code>G = GraphQuery(display_cols=['graph6'], num_vertices=2)
L = G.get_graphs_list()
graphs_list.show_graphs(L)
</code></pre>
https://ask.sagemath.org/question/24299/how-to-list-all-the-connected-graphs-with-9-vertices/?answer=24313#post-id-24313Hi,
The GraphQuery command is about consulting the database of small graphs. If you want to actually build the list from scratch use:
sage: from itertools import ifilter
sage: f = lambda g: g.is_connected() and not g.is_long_hole_free()
sage: for g in ifilter(f, graphs(6)):
....: print g
Graph on 6 vertices
Graph on 6 vertices
....
Graph on 6 vertices
If you want to create the list and not just iterate through them you can use
sage: L = filter(f, graphs(6))
sage: graphs_list.show_graphs(L)
Note that the same method would work with a graph query as well. But whatever you chose it will take forever with 9 vertices.
VincentSat, 27 Sep 2014 20:56:07 +0200https://ask.sagemath.org/question/24299/how-to-list-all-the-connected-graphs-with-9-vertices/?answer=24313#post-id-24313Comment by tmonteil for <p>Hi,</p>
<p>The GraphQuery command is about consulting the database of small graphs. If you want to actually build the list from scratch use:</p>
<pre><code>sage: from itertools import ifilter
sage: f = lambda g: g.is_connected() and not g.is_long_hole_free()
sage: for g in ifilter(f, graphs(6)):
....: print g
Graph on 6 vertices
Graph on 6 vertices
....
Graph on 6 vertices
</code></pre>
<p>If you want to create the list and not just iterate through them you can use</p>
<pre><code>sage: L = filter(f, graphs(6))
sage: graphs_list.show_graphs(L)
</code></pre>
<p>Note that the same method would work with a graph query as well. But whatever you chose it will take forever with 9 vertices.</p>
<p>Vincent</p>
https://ask.sagemath.org/question/24299/how-to-list-all-the-connected-graphs-with-9-vertices/?comment=24315#post-id-24315Perhaps the following is easier to read and undertand:
G = (g for g in graphs(6) if g.is_connected() and not g.is_long_hole_free())Sat, 27 Sep 2014 22:58:02 +0200https://ask.sagemath.org/question/24299/how-to-list-all-the-connected-graphs-with-9-vertices/?comment=24315#post-id-24315Answer by dazedANDconfused for <p>What I want to do is exactly to list all the connected graphs with 9 vertices which are also <code>is_long_hole_free()==False</code>, i.e., contains an induced cycle of length at least 5. But I can only list all the graphs with a given number of vertices, for example</p>
<pre><code>G = GraphQuery(display_cols=['graph6'], num_vertices=2)
L = G.get_graphs_list()
graphs_list.show_graphs(L)
</code></pre>
https://ask.sagemath.org/question/24299/how-to-list-all-the-connected-graphs-with-9-vertices/?answer=24316#post-id-24316According to the [documentation](http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_database.html), GraphQuery is for interfacing with a database that has graphs up to 7 vertices but your question wants graphs on 9 vertices. When I wrote code similar to below using GraphQuery rather than list(graphs( the code stopped working at 8 vertices. The following code should work in a notebook:
M = []
L = list(graphs(9))
for i in range(0,len(L)):
if not L[i].is_long_hole_free() and L[i].is_connected():
M += [L[i]]
graphs_list.show_graphs(M)
I say **should** because I've had it running for over 2.5 hours and still no result. Of course, rendering thousands upon thousands of graphs will take a lot of time. On my quad core with 8 gigs of RAM, 8 vertices worked. But it took about 10 minutes and gobbled up over 90 percent of my RAM. EDIT: Still no result after 5 hours so I stopped it.Sat, 27 Sep 2014 22:59:03 +0200https://ask.sagemath.org/question/24299/how-to-list-all-the-connected-graphs-with-9-vertices/?answer=24316#post-id-24316Comment by tmonteil for <p>According to the <a href="http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_database.html">documentation</a>, GraphQuery is for interfacing with a database that has graphs up to 7 vertices but your question wants graphs on 9 vertices. When I wrote code similar to below using GraphQuery rather than list(graphs( the code stopped working at 8 vertices. The following code should work in a notebook:</p>
<pre><code>M = []
L = list(graphs(9))
for i in range(0,len(L)):
if not L[i].is_long_hole_free() and L[i].is_connected():
M += [L[i]]
graphs_list.show_graphs(M)
</code></pre>
<p>I say <strong>should</strong> because I've had it running for over 2.5 hours and still no result. Of course, rendering thousands upon thousands of graphs will take a lot of time. On my quad core with 8 gigs of RAM, 8 vertices worked. But it took about 10 minutes and gobbled up over 90 percent of my RAM. EDIT: Still no result after 5 hours so I stopped it.</p>
https://ask.sagemath.org/question/24299/how-to-list-all-the-connected-graphs-with-9-vertices/?comment=24374#post-id-24374This approach actually doubles the time and costs a lot of memory. First you create a list with all graphs and then you enumerates all elements of the list. It is faster to do "for i in graphs(9)" so that you avoid using all the memory in storing a huge list. This is the benefits of iterators. Moreover, if you want to deal with all elements of a list L, it is useless to count the number of elements in L and then call "L[i]" ; instead you can just do "for i in L:". Moreover in python 2, range(0,len(L)) will create another new list and use again a lot of memory.Thu, 02 Oct 2014 17:39:11 +0200https://ask.sagemath.org/question/24299/how-to-list-all-the-connected-graphs-with-9-vertices/?comment=24374#post-id-24374Comment by dazedANDconfused for <p>According to the <a href="http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_database.html">documentation</a>, GraphQuery is for interfacing with a database that has graphs up to 7 vertices but your question wants graphs on 9 vertices. When I wrote code similar to below using GraphQuery rather than list(graphs( the code stopped working at 8 vertices. The following code should work in a notebook:</p>
<pre><code>M = []
L = list(graphs(9))
for i in range(0,len(L)):
if not L[i].is_long_hole_free() and L[i].is_connected():
M += [L[i]]
graphs_list.show_graphs(M)
</code></pre>
<p>I say <strong>should</strong> because I've had it running for over 2.5 hours and still no result. Of course, rendering thousands upon thousands of graphs will take a lot of time. On my quad core with 8 gigs of RAM, 8 vertices worked. But it took about 10 minutes and gobbled up over 90 percent of my RAM. EDIT: Still no result after 5 hours so I stopped it.</p>
https://ask.sagemath.org/question/24299/how-to-list-all-the-connected-graphs-with-9-vertices/?comment=24375#post-id-24375Yes. It was a quick attempt to brute force the answer; it worked quickly enough on 8 vertices so I figured I'd try it on 9 and clean up the code later. But a huge time expense is rendering the graphs. There are too many as you can see just from the output of 8 vertices.Thu, 02 Oct 2014 19:20:29 +0200https://ask.sagemath.org/question/24299/how-to-list-all-the-connected-graphs-with-9-vertices/?comment=24375#post-id-24375Comment by tmonteil for <p>According to the <a href="http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_database.html">documentation</a>, GraphQuery is for interfacing with a database that has graphs up to 7 vertices but your question wants graphs on 9 vertices. When I wrote code similar to below using GraphQuery rather than list(graphs( the code stopped working at 8 vertices. The following code should work in a notebook:</p>
<pre><code>M = []
L = list(graphs(9))
for i in range(0,len(L)):
if not L[i].is_long_hole_free() and L[i].is_connected():
M += [L[i]]
graphs_list.show_graphs(M)
</code></pre>
<p>I say <strong>should</strong> because I've had it running for over 2.5 hours and still no result. Of course, rendering thousands upon thousands of graphs will take a lot of time. On my quad core with 8 gigs of RAM, 8 vertices worked. But it took about 10 minutes and gobbled up over 90 percent of my RAM. EDIT: Still no result after 5 hours so I stopped it.</p>
https://ask.sagemath.org/question/24299/how-to-list-all-the-connected-graphs-with-9-vertices/?comment=24384#post-id-24384With your approach, you could have written:
{{{
M = []
for G in graphs(9):
if not G.is_long_hole_free() and G.is_connected():
M.append(G)
}}}
or even directly
{{{
M = [G for G in graphs(9) if not G.is_long_hole_free() and G.is_connected()]
}}}
This would have saved the construction and storage of both L and range(0,len(L)). It does not solves the problem since we are still far behind the objective, just a kind remark about your code that could save you time and space in other occasions !Fri, 03 Oct 2014 14:29:05 +0200https://ask.sagemath.org/question/24299/how-to-list-all-the-connected-graphs-with-9-vertices/?comment=24384#post-id-24384