Revision history [back]

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 G

Then you can find a random graph not containing any C_3:

sage: G = my_random_graph_excluding(graphs.CycleGraph(3), 7)

Note that subgraph_search search for a copy of C in G. If you want to avoid only C as an induced subgraph, you should replace G.subgraph_search(C) by G.subgraph_search(C, induced=True).

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 G

Then you can find a random graph not containing any C_3:$C_3$:

sage: G = my_random_graph_excluding(graphs.CycleGraph(3), 7)

Note that subgraph_search search G.subgraph_search(C) searches for a copy of C in G. If you want to avoid only C C as an induced subgraph, 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$.

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 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$.