Is it possible to generate random graphs free of certain forbidden structures? For example, graphs without C3.
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.
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:
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 GThen you can find a random graph not containing any C3:
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 C3.
@tmonteil Thank you so much for your suggestions. It is really helpful. The function you mentioned above G.subgraph_search() together with function minor() found by following @dazedANDconfused 's instruction are exactly what I need in my research. Thank you guys for your patient explanations.
Asked: 10 years ago
Seen: 1,378 times
Last updated: Oct 02 '14
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
Yes. 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 C3. Random graphs [here] http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_generators.html
@dazedANDconfused Thank you so much for sharing. I checked the pages you mentioned above, and it is really helpful, especially two functions concerning minors.