Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1r"""Generators for cographs
3A cograph is a graph containing no path on four vertices.
4Cographs or $P_4$-free graphs can be obtained from a single vertex
5by disjoint union and complementation operations.
7References
8----------
9.. [0] D.G. Corneil, H. Lerchs, L.Stewart Burlingham,
10 "Complement reducible graphs",
11 Discrete Applied Mathematics, Volume 3, Issue 3, 1981, Pages 163-174,
12 ISSN 0166-218X.
13"""
15import networkx as nx
16from networkx.utils import py_random_state
18__all__ = ["random_cograph"]
21@py_random_state(1)
22@nx._dispatchable(graphs=None, returns_graph=True)
23def random_cograph(n, seed=None):
24 r"""Returns a random cograph with $2 ^ n$ nodes.
26 A cograph is a graph containing no path on four vertices.
27 Cographs or $P_4$-free graphs can be obtained from a single vertex
28 by disjoint union and complementation operations.
30 This generator starts off from a single vertex and performs disjoint
31 union and full join operations on itself.
32 The decision on which operation will take place is random.
34 Parameters
35 ----------
36 n : int
37 The order of the cograph.
38 seed : integer, random_state, or None (default)
39 Indicator of random number generation state.
40 See :ref:`Randomness<randomness>`.
42 Returns
43 -------
44 G : A random graph containing no path on four vertices.
46 See Also
47 --------
48 full_join
49 union
51 References
52 ----------
53 .. [1] D.G. Corneil, H. Lerchs, L.Stewart Burlingham,
54 "Complement reducible graphs",
55 Discrete Applied Mathematics, Volume 3, Issue 3, 1981, Pages 163-174,
56 ISSN 0166-218X.
57 """
58 R = nx.empty_graph(1)
60 for i in range(n):
61 RR = nx.relabel_nodes(R.copy(), lambda x: x + len(R))
63 if seed.randint(0, 1) == 0:
64 R = nx.full_join(R, RR)
65 else:
66 R = nx.disjoint_union(R, RR)
68 return R