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.Mon, 01 Apr 2019 04:51:57 +0200Create program to find which graphs contain specific subgraphhttps://ask.sagemath.org/question/45952/create-program-to-find-which-graphs-contain-specific-subgraph/ Hello, I am pretty new to Sage, and am discovering all the wonderful things it can do. I know how to ask Sage to generate a list of graphs that satisfy particular properties. To do this I "call" a program named "nauty". For example, if I would like to generate all graphs with 10 vertices, 25 edges, and clique number 4 I type the following:
sage: g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
Now say that I want to check which of these graphs contain a particular subgraph. For example, say I want to know which one of these graphs contain a 5-cycle. How can I ask Sage to go through the list of graphs in g10 and tell me this information?
Thank you in advance!Sat, 30 Mar 2019 18:56:30 +0100https://ask.sagemath.org/question/45952/create-program-to-find-which-graphs-contain-specific-subgraph/Answer by dazedANDconfused for <p>Hello, I am pretty new to Sage, and am discovering all the wonderful things it can do. I know how to ask Sage to generate a list of graphs that satisfy particular properties. To do this I "call" a program named "nauty". For example, if I would like to generate all graphs with 10 vertices, 25 edges, and clique number 4 I type the following:</p>
<p>sage: g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]</p>
<p>Now say that I want to check which of these graphs contain a particular subgraph. For example, say I want to know which one of these graphs contain a 5-cycle. How can I ask Sage to go through the list of graphs in g10 and tell me this information?</p>
<p>Thank you in advance!</p>
https://ask.sagemath.org/question/45952/create-program-to-find-which-graphs-contain-specific-subgraph/?answer=45956#post-id-45956How about:
g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
for g in g10:
if g.subgraph_search(H,induced=False):
g.show()
After defining the subgraph you want, the cycle on 5 vertices, look through the graphs in g10 and figure out if it has H, not necessarily induced. It then prints out the graphs.
The documentation for subgraph_search is [here](http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.subgraph_search).
**EDIT:**
With respect to your comment below, I think that it is possible but I don't know enough of the intricacies of the graph theory commands. Consider this code.
g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
K = graphs.CompleteGraph(4)
for g in g10:
if g.subgraph_search(H,induced=False):
for p in g.subgraph_search_iterator(K,induced=True):
for v in p:
if g.degree(v)<6:
print "False"
print p
g.show()
else:
print "True"
For each graph in g10 it looks for a non-induced C_5. If the graph has it then it looks for an induced K_4. When it finds it, it looks at all the vertices in it (the subgraph p which is a K_4) and looks to see if the degree of any vertex is less than 6. If so, it prints out "False", the 4 vertices inducing K_4 and the graph from g10 that they are a subgraph of. If you didn't require the graph to have H then you can easily modify the code to what you want.Sun, 31 Mar 2019 04:57:42 +0200https://ask.sagemath.org/question/45952/create-program-to-find-which-graphs-contain-specific-subgraph/?answer=45956#post-id-45956Comment by merluza for <p>How about:</p>
<pre><code>g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
for g in g10:
if g.subgraph_search(H,induced=False):
g.show()
</code></pre>
<p>After defining the subgraph you want, the cycle on 5 vertices, look through the graphs in g10 and figure out if it has H, not necessarily induced. It then prints out the graphs.
The documentation for subgraph_search is <a href="http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.subgraph_search">here</a>.</p>
<p><strong>EDIT:</strong>
With respect to your comment below, I think that it is possible but I don't know enough of the intricacies of the graph theory commands. Consider this code.</p>
<pre><code>g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
K = graphs.CompleteGraph(4)
for g in g10:
if g.subgraph_search(H,induced=False):
for p in g.subgraph_search_iterator(K,induced=True):
for v in p:
if g.degree(v)<6:
print "False"
print p
g.show()
else:
print "True"
</code></pre>
<p>For each graph in g10 it looks for a non-induced C_5. If the graph has it then it looks for an induced K_4. When it finds it, it looks at all the vertices in it (the subgraph p which is a K_4) and looks to see if the degree of any vertex is less than 6. If so, it prints out "False", the 4 vertices inducing K_4 and the graph from g10 that they are a subgraph of. If you didn't require the graph to have H then you can easily modify the code to what you want.</p>
https://ask.sagemath.org/question/45952/create-program-to-find-which-graphs-contain-specific-subgraph/?comment=45971#post-id-45971Thank you!! You are a lifesaver! I was unaware of subgraph_search_iterator tool, this is wonderful.Mon, 01 Apr 2019 04:14:58 +0200https://ask.sagemath.org/question/45952/create-program-to-find-which-graphs-contain-specific-subgraph/?comment=45971#post-id-45971Comment by dazedANDconfused for <p>How about:</p>
<pre><code>g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
for g in g10:
if g.subgraph_search(H,induced=False):
g.show()
</code></pre>
<p>After defining the subgraph you want, the cycle on 5 vertices, look through the graphs in g10 and figure out if it has H, not necessarily induced. It then prints out the graphs.
The documentation for subgraph_search is <a href="http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.subgraph_search">here</a>.</p>
<p><strong>EDIT:</strong>
With respect to your comment below, I think that it is possible but I don't know enough of the intricacies of the graph theory commands. Consider this code.</p>
<pre><code>g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
K = graphs.CompleteGraph(4)
for g in g10:
if g.subgraph_search(H,induced=False):
for p in g.subgraph_search_iterator(K,induced=True):
for v in p:
if g.degree(v)<6:
print "False"
print p
g.show()
else:
print "True"
</code></pre>
<p>For each graph in g10 it looks for a non-induced C_5. If the graph has it then it looks for an induced K_4. When it finds it, it looks at all the vertices in it (the subgraph p which is a K_4) and looks to see if the degree of any vertex is less than 6. If so, it prints out "False", the 4 vertices inducing K_4 and the graph from g10 that they are a subgraph of. If you didn't require the graph to have H then you can easily modify the code to what you want.</p>
https://ask.sagemath.org/question/45952/create-program-to-find-which-graphs-contain-specific-subgraph/?comment=45972#post-id-45972There is an extensive, almost 900 page, pdf reference doc just on graph theory which is available [here](http://doc.sagemath.org/pdf/en/reference/graphs/graphs.pdf).Mon, 01 Apr 2019 04:51:57 +0200https://ask.sagemath.org/question/45952/create-program-to-find-which-graphs-contain-specific-subgraph/?comment=45972#post-id-45972Comment by merluza for <p>How about:</p>
<pre><code>g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
for g in g10:
if g.subgraph_search(H,induced=False):
g.show()
</code></pre>
<p>After defining the subgraph you want, the cycle on 5 vertices, look through the graphs in g10 and figure out if it has H, not necessarily induced. It then prints out the graphs.
The documentation for subgraph_search is <a href="http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.subgraph_search">here</a>.</p>
<p><strong>EDIT:</strong>
With respect to your comment below, I think that it is possible but I don't know enough of the intricacies of the graph theory commands. Consider this code.</p>
<pre><code>g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
K = graphs.CompleteGraph(4)
for g in g10:
if g.subgraph_search(H,induced=False):
for p in g.subgraph_search_iterator(K,induced=True):
for v in p:
if g.degree(v)<6:
print "False"
print p
g.show()
else:
print "True"
</code></pre>
<p>For each graph in g10 it looks for a non-induced C_5. If the graph has it then it looks for an induced K_4. When it finds it, it looks at all the vertices in it (the subgraph p which is a K_4) and looks to see if the degree of any vertex is less than 6. If so, it prints out "False", the 4 vertices inducing K_4 and the graph from g10 that they are a subgraph of. If you didn't require the graph to have H then you can easily modify the code to what you want.</p>
https://ask.sagemath.org/question/45952/create-program-to-find-which-graphs-contain-specific-subgraph/?comment=45964#post-id-45964Thank you for your help. Would you also happen to know how I can ask Sage to give me graphs in g10 that also satisfy the condition that every vertex in a 4-clique has degree at least 6?Sun, 31 Mar 2019 20:02:03 +0200https://ask.sagemath.org/question/45952/create-program-to-find-which-graphs-contain-specific-subgraph/?comment=45964#post-id-45964