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.Sat, 03 Dec 2016 20:15:29 +0100How can I count the number of cycles of special length in a graph in sage?https://ask.sagemath.org/question/35837/how-can-i-count-the-number-of-cycles-of-special-length-in-a-graph-in-sage/I have tried the `G.subgraph_search_count(graphs.CycleGraph(4))`but it doesn't lead to the correct answer,
any help would be appreciated.Thu, 01 Dec 2016 09:07:54 +0100https://ask.sagemath.org/question/35837/how-can-i-count-the-number-of-cycles-of-special-length-in-a-graph-in-sage/Comment by fidbc for <p>I have tried the <code>G.subgraph_search_count(graphs.CycleGraph(4))</code>but it doesn't lead to the correct answer,
any help would be appreciated.</p>
https://ask.sagemath.org/question/35837/how-can-i-count-the-number-of-cycles-of-special-length-in-a-graph-in-sage/?comment=35877#post-id-35877Would it suffice to divide by the size of the automorphism group of the subgraph that is being searched for, perhaps? In other words, are you trying to count non labelled occurrences of cycles? For the particular case stated in your question, dividing by 8 might do the trick.Fri, 02 Dec 2016 17:00:46 +0100https://ask.sagemath.org/question/35837/how-can-i-count-the-number-of-cycles-of-special-length-in-a-graph-in-sage/?comment=35877#post-id-35877Comment by M95 for <p>I have tried the <code>G.subgraph_search_count(graphs.CycleGraph(4))</code>but it doesn't lead to the correct answer,
any help would be appreciated.</p>
https://ask.sagemath.org/question/35837/how-can-i-count-the-number-of-cycles-of-special-length-in-a-graph-in-sage/?comment=35881#post-id-35881Yes ,That's what I'm trying to do,but what is 8 that it should be divided by?Fri, 02 Dec 2016 20:10:26 +0100https://ask.sagemath.org/question/35837/how-can-i-count-the-number-of-cycles-of-special-length-in-a-graph-in-sage/?comment=35881#post-id-35881Comment by fidbc for <p>I have tried the <code>G.subgraph_search_count(graphs.CycleGraph(4))</code>but it doesn't lead to the correct answer,
any help would be appreciated.</p>
https://ask.sagemath.org/question/35837/how-can-i-count-the-number-of-cycles-of-special-length-in-a-graph-in-sage/?comment=35900#post-id-35900I meant you should divide by 8 if you are searching 4-cycles, since the size of the automorphism group of the 4-cycle is 8. See answer below for further details.Sat, 03 Dec 2016 17:49:39 +0100https://ask.sagemath.org/question/35837/how-can-i-count-the-number-of-cycles-of-special-length-in-a-graph-in-sage/?comment=35900#post-id-35900Answer by fidbc for <p>I have tried the <code>G.subgraph_search_count(graphs.CycleGraph(4))</code>but it doesn't lead to the correct answer,
any help would be appreciated.</p>
https://ask.sagemath.org/question/35837/how-can-i-count-the-number-of-cycles-of-special-length-in-a-graph-in-sage/?answer=35902#post-id-35902Seems like you are searching for non labelled occurrences of cycles. In such case dividing by the size of the automorphism group of the graph that is being searched for might do the trick. Say you are trying to count the number of unlabelled appearances of graph `H` in graph `G`. You can define
subgraph_count = lambda G,H: G.subgraph_search_cound(H)/H.automorphism_group(return_group=False,order=True)
and then use
G=graphs.Grid2dGraph(3,3)
H=graphs.CycleGraph(4)
subgraph_count(G,H)
This should output `4`, as expected.
For the particular case of cycles, if you are searching for cycles of length `k` then it suffices to divide by `2*k`, so the following should work.
cycle_subgraph_count = lambda G,k: G.subgraph_search_cound(graphs.CycleGraph(k))/(2*k)
then
G=graphs.Grid2dGraph(10,10)
cycle_subgraph_count(G,4)
should output `81`.Sat, 03 Dec 2016 18:06:47 +0100https://ask.sagemath.org/question/35837/how-can-i-count-the-number-of-cycles-of-special-length-in-a-graph-in-sage/?answer=35902#post-id-35902Comment by M95 for <p>Seems like you are searching for non labelled occurrences of cycles. In such case dividing by the size of the automorphism group of the graph that is being searched for might do the trick. Say you are trying to count the number of unlabelled appearances of graph <code>H</code> in graph <code>G</code>. You can define</p>
<pre><code>subgraph_count = lambda G,H: G.subgraph_search_cound(H)/H.automorphism_group(return_group=False,order=True)
</code></pre>
<p>and then use</p>
<pre><code>G=graphs.Grid2dGraph(3,3)
H=graphs.CycleGraph(4)
subgraph_count(G,H)
</code></pre>
<p>This should output <code>4</code>, as expected.</p>
<p>For the particular case of cycles, if you are searching for cycles of length <code>k</code> then it suffices to divide by <code>2*k</code>, so the following should work.</p>
<pre><code>cycle_subgraph_count = lambda G,k: G.subgraph_search_cound(graphs.CycleGraph(k))/(2*k)
</code></pre>
<p>then</p>
<pre><code>G=graphs.Grid2dGraph(10,10)
cycle_subgraph_count(G,4)
</code></pre>
<p>should output <code>81</code>.</p>
https://ask.sagemath.org/question/35837/how-can-i-count-the-number-of-cycles-of-special-length-in-a-graph-in-sage/?comment=35903#post-id-35903Thank you so much,I got it.Sat, 03 Dec 2016 19:32:40 +0100https://ask.sagemath.org/question/35837/how-can-i-count-the-number-of-cycles-of-special-length-in-a-graph-in-sage/?comment=35903#post-id-35903Comment by fidbc for <p>Seems like you are searching for non labelled occurrences of cycles. In such case dividing by the size of the automorphism group of the graph that is being searched for might do the trick. Say you are trying to count the number of unlabelled appearances of graph <code>H</code> in graph <code>G</code>. You can define</p>
<pre><code>subgraph_count = lambda G,H: G.subgraph_search_cound(H)/H.automorphism_group(return_group=False,order=True)
</code></pre>
<p>and then use</p>
<pre><code>G=graphs.Grid2dGraph(3,3)
H=graphs.CycleGraph(4)
subgraph_count(G,H)
</code></pre>
<p>This should output <code>4</code>, as expected.</p>
<p>For the particular case of cycles, if you are searching for cycles of length <code>k</code> then it suffices to divide by <code>2*k</code>, so the following should work.</p>
<pre><code>cycle_subgraph_count = lambda G,k: G.subgraph_search_cound(graphs.CycleGraph(k))/(2*k)
</code></pre>
<p>then</p>
<pre><code>G=graphs.Grid2dGraph(10,10)
cycle_subgraph_count(G,4)
</code></pre>
<p>should output <code>81</code>.</p>
https://ask.sagemath.org/question/35837/how-can-i-count-the-number-of-cycles-of-special-length-in-a-graph-in-sage/?comment=35904#post-id-35904You're welcome! If this worked for you, you can mark the answer as accepted ;-)Sat, 03 Dec 2016 20:15:29 +0100https://ask.sagemath.org/question/35837/how-can-i-count-the-number-of-cycles-of-special-length-in-a-graph-in-sage/?comment=35904#post-id-35904