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)
According to the documentation, 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.
This 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.
Yes. 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.
With 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 !
Hi,
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.
Vincent
Asked: 2014-09-26 13:31:29 +0200
Seen: 1,149 times
Last updated: Sep 28 '14
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.