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.Thu, 02 Oct 2014 14:22:01 +0200How to generate random graphs free of certain structures?https://ask.sagemath.org/question/24365/how-to-generate-random-graphs-free-of-certain-structures/Is it possible to generate random graphs free of certain forbidden structures? For example, graphs without $C_3$.
Or is it possible to test whether a graph is free of some forbidden structures?
If it is positive, then it would be of great help in my research. Looking forward to all comments and suggestions.Wed, 01 Oct 2014 15:28:02 +0200https://ask.sagemath.org/question/24365/how-to-generate-random-graphs-free-of-certain-structures/Comment by Han for <p>Is it possible to generate random graphs free of certain forbidden structures? For example, graphs without $C_3$.</p>
<p>Or is it possible to test whether a graph is free of some forbidden structures? </p>
<p>If it is positive, then it would be of great help in my research. Looking forward to all comments and suggestions.</p>
https://ask.sagemath.org/question/24365/how-to-generate-random-graphs-free-of-certain-structures/?comment=24371#post-id-24371@dazedandconfused Thank you so much for sharing. I checked the pages you mentioned above, and it is really helpful, especially two functions concerning minors.Thu, 02 Oct 2014 14:01:17 +0200https://ask.sagemath.org/question/24365/how-to-generate-random-graphs-free-of-certain-structures/?comment=24371#post-id-24371Comment by dazedANDconfused for <p>Is it possible to generate random graphs free of certain forbidden structures? For example, graphs without $C_3$.</p>
<p>Or is it possible to test whether a graph is free of some forbidden structures? </p>
<p>If it is positive, then it would be of great help in my research. Looking forward to all comments and suggestions.</p>
https://ask.sagemath.org/question/24365/how-to-generate-random-graphs-free-of-certain-structures/?comment=24367#post-id-24367Yes. See, for example, the post "How to list all the connected graphs with 9 vertices?" (http://ask.sagemath.org/question/24299/how-to-list-all-the-connected-graphs-with-9-vertices/) where there is code for generating all graphs on a fixed number of vertices that are connected and long_hole_free. [This page] http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph.html has some of the properties you can test for. Is_triangle_free would be checking for no $C_3$. Random graphs [here] http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_generators.htmlWed, 01 Oct 2014 16:13:43 +0200https://ask.sagemath.org/question/24365/how-to-generate-random-graphs-free-of-certain-structures/?comment=24367#post-id-24367Answer by tmonteil for <p>Is it possible to generate random graphs free of certain forbidden structures? For example, graphs without $C_3$.</p>
<p>Or is it possible to test whether a graph is free of some forbidden structures? </p>
<p>If it is positive, then it would be of great help in my research. Looking forward to all comments and suggestions.</p>
https://ask.sagemath.org/question/24365/how-to-generate-random-graphs-free-of-certain-structures/?answer=24369#post-id-24369I am pretty sure there is no random generation of graphs forbidding some structure in Sage. So, what is possible is to use a rejection algorithm : pick random graphs of a given size with equal probability until you found one that forbids the given structure. For example, you can do:
sage: def my_random_graph_excluding(C, size):
....: assert(C.size() <= size), "No chance to find any graph of size {} containing {}".format(n,C)
....: while True:
....: G = graphs.RandomGNP(size, 0.5)
....: if G.subgraph_search(C) is None:
....: return G
Then you can find a random graph not containing any $C_3$:
sage: G = my_random_graph_excluding(graphs.CycleGraph(3), 7)
Of course this method can take a long time for big size if the set of admissible graphs is small compared to the set of all graphs.
Note that ``G.subgraph_search(C)`` searches for a copy of ``C`` in ``G``. If you want to avoid only ``C`` as an induced subgraph of ``G``, you should replace ``G.subgraph_search(C)`` by ``G.subgraph_search(C, induced=True)``. Of course it does not matter for the special case where ``C`` is $C_3$.
Wed, 01 Oct 2014 22:21:15 +0200https://ask.sagemath.org/question/24365/how-to-generate-random-graphs-free-of-certain-structures/?answer=24369#post-id-24369Comment by Han for <p>I am pretty sure there is no random generation of graphs forbidding some structure in Sage. So, what is possible is to use a rejection algorithm : pick random graphs of a given size with equal probability until you found one that forbids the given structure. For example, you can do:</p>
<pre><code>sage: def my_random_graph_excluding(C, size):
....: assert(C.size() <= size), "No chance to find any graph of size {} containing {}".format(n,C)
....: while True:
....: G = graphs.RandomGNP(size, 0.5)
....: if G.subgraph_search(C) is None:
....: return G
</code></pre>
<p>Then you can find a random graph not containing any $C_3$:</p>
<pre><code>sage: G = my_random_graph_excluding(graphs.CycleGraph(3), 7)
</code></pre>
<p>Of course this method can take a long time for big size if the set of admissible graphs is small compared to the set of all graphs.</p>
<p>Note that <code>G.subgraph_search(C)</code> searches for a copy of <code>C</code> in <code>G</code>. If you want to avoid only <code>C</code> as an induced subgraph of <code>G</code>, you should replace <code>G.subgraph_search(C)</code> by <code>G.subgraph_search(C, induced=True)</code>. Of course it does not matter for the special case where <code>C</code> is $C_3$.</p>
https://ask.sagemath.org/question/24365/how-to-generate-random-graphs-free-of-certain-structures/?comment=24373#post-id-24373@tmonteil Thank you so much for your suggestions. It is really helpful. The function you mentioned above <code> G.subgraph_search()</code> together with function <code>minor()</code> found by following @dazedANDconfused 's instruction are exactly what I need in my research. Thank you guys for your patient explanations.Thu, 02 Oct 2014 14:22:01 +0200https://ask.sagemath.org/question/24365/how-to-generate-random-graphs-free-of-certain-structures/?comment=24373#post-id-24373