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.Wed, 17 Apr 2013 11:51:29 +0200generate all (not necessarily induced) subgraphs of a graphhttps://ask.sagemath.org/question/10031/generate-all-not-necessarily-induced-subgraphs-of-a-graph/I want to, given a Sage graph G, generate all subgraphs of G and check them for some property, and store in a list those which satisfy the propery. What I'm doing currently seems very inefficient:
graphs_i_want=[]
for g in graphs.nauty_geng(str(G.order())):
if G.subgraph_search(g):
if check(g):
graphs_i_want.append(g.graph6_string())
`check(g)` checks that g satisfies the properties I want, and it's done. Actually the code above works completely - it gives a list of the graph6 strings for every subgraph of G. However, I think it's overkill to check through all graphs, and it's also pretty slow for graphs larger than 6 vertices or so. I need it to work for more, up to maybe 15.
An iterator would be fine. I just need to check each of the graphs for some property. The code could be something like this:
graphs_i_want=[]
for g in all_subsets_generator(G):
if check(g):
graphs_i_want.append(g.graph6_string())
where `all_subsets_generator(G)` iterates over all subsets of G.
Thanks for any advice. Let me know if more information is needed.Tue, 16 Apr 2013 16:56:12 +0200https://ask.sagemath.org/question/10031/generate-all-not-necessarily-induced-subgraphs-of-a-graph/Answer by fidbc for <p>I want to, given a Sage graph G, generate all subgraphs of G and check them for some property, and store in a list those which satisfy the propery. What I'm doing currently seems very inefficient:</p>
<pre><code>graphs_i_want=[]
for g in graphs.nauty_geng(str(G.order())):
if G.subgraph_search(g):
if check(g):
graphs_i_want.append(g.graph6_string())
</code></pre>
<p><code>check(g)</code> checks that g satisfies the properties I want, and it's done. Actually the code above works completely - it gives a list of the graph6 strings for every subgraph of G. However, I think it's overkill to check through all graphs, and it's also pretty slow for graphs larger than 6 vertices or so. I need it to work for more, up to maybe 15.</p>
<p>An iterator would be fine. I just need to check each of the graphs for some property. The code could be something like this:</p>
<pre><code>graphs_i_want=[]
for g in all_subsets_generator(G):
if check(g):
graphs_i_want.append(g.graph6_string())
</code></pre>
<p>where <code>all_subsets_generator(G)</code> iterates over all subsets of G.</p>
<p>Thanks for any advice. Let me know if more information is needed.</p>
https://ask.sagemath.org/question/10031/generate-all-not-necessarily-induced-subgraphs-of-a-graph/?answer=14796#post-id-14796You could try the following
E=Set(G.edges())
V=G.vertices()
for s in E.subsets():
H=Graph()
H.add_edges( s )
#If you are interested only in spanning subgraphs you have to include this line
H.add_vertices( V )
if check( H ):
graphs_you_want.append( H.graph6_string() )
One thing to keep in mind is that you might want to get the canonical label of `H` into the list of graphs you want (in case you are interested in non labelled subgraphs). This could help avoid duplicates (isomorphic graphs) in the list.
This does not guarantee it will be faster, it will take the same time (maybe more) as your first approach when `G` is the complete graph.Tue, 16 Apr 2013 17:19:22 +0200https://ask.sagemath.org/question/10031/generate-all-not-necessarily-induced-subgraphs-of-a-graph/?answer=14796#post-id-14796Comment by vermette for <p>You could try the following</p>
<pre><code>E=Set(G.edges())
V=G.vertices()
for s in E.subsets():
H=Graph()
H.add_edges( s )
#If you are interested only in spanning subgraphs you have to include this line
H.add_vertices( V )
if check( H ):
graphs_you_want.append( H.graph6_string() )
</code></pre>
<p>One thing to keep in mind is that you might want to get the canonical label of <code>H</code> into the list of graphs you want (in case you are interested in non labelled subgraphs). This could help avoid duplicates (isomorphic graphs) in the list.</p>
<p>This does not guarantee it will be faster, it will take the same time (maybe more) as your first approach when <code>G</code> is the complete graph.</p>
https://ask.sagemath.org/question/10031/generate-all-not-necessarily-induced-subgraphs-of-a-graph/?comment=17875#post-id-17875thanks, this is what I want. my graphs are relatively sparse, so I think it should be faster. I didn't know much about `.edges()` or `.add_edges()`, those are quite useful. to handle the isomorphic graphs, I added just before appending graphs which pass `check()` the following: `H_can=H.canonical_label()`, then `graphs_you_want.append( H_can.graph6_string() )` to append. after it runs, `list(set(graphs_you_want))` removes duplicates (and is fairly fast because the list is short). thanks again~Wed, 17 Apr 2013 11:51:29 +0200https://ask.sagemath.org/question/10031/generate-all-not-necessarily-induced-subgraphs-of-a-graph/?comment=17875#post-id-17875