Ask Your Question

How to list all the connected graphs with 9 vertices?

asked 2014-09-26 06:31:29 -0500

Soloman gravatar image

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()
edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted

answered 2014-09-27 15:59:03 -0500

dazedANDconfused gravatar image

updated 2014-09-27 19:33:18 -0500

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]]

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.

edit flag offensive delete link more


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.

tmonteil gravatar imagetmonteil ( 2014-10-02 10:39:11 -0500 )edit

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.

dazedANDconfused gravatar imagedazedANDconfused ( 2014-10-02 12:20:29 -0500 )edit

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 !

tmonteil gravatar imagetmonteil ( 2014-10-03 07:29:05 -0500 )edit

answered 2014-09-27 13:56:07 -0500

updated 2014-09-27 13:57:05 -0500


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.


edit flag offensive delete link more


Perhaps 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())

tmonteil gravatar imagetmonteil ( 2014-09-27 15:58:02 -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

1 follower


Asked: 2014-09-26 06:31:29 -0500

Seen: 419 times

Last updated: Sep 27 '14