Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/generators/cographs.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 r"""Generators for cographs | |
2 | |
3 A cograph is a graph containing no path on four vertices. | |
4 Cographs or $P_4$-free graphs can be obtained from a single vertex | |
5 by disjoint union and complementation operations. | |
6 | |
7 References | |
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 """ | |
14 import networkx as nx | |
15 from networkx.utils import py_random_state | |
16 | |
17 __all__ = ["random_cograph"] | |
18 | |
19 | |
20 @py_random_state(1) | |
21 def random_cograph(n, seed=None): | |
22 r"""Returns a random cograph with $2 ^ n$ nodes. | |
23 | |
24 A cograph is a graph containing no path on four vertices. | |
25 Cographs or $P_4$-free graphs can be obtained from a single vertex | |
26 by disjoint union and complementation operations. | |
27 | |
28 This generator starts off from a single vertex and performes disjoint | |
29 union and full join operations on itself. | |
30 The decision on which operation will take place is random. | |
31 | |
32 Parameters | |
33 ---------- | |
34 n : int | |
35 The order of the cograph. | |
36 seed : integer, random_state, or None (default) | |
37 Indicator of random number generation state. | |
38 See :ref:`Randomness<randomness>`. | |
39 | |
40 Returns | |
41 ------- | |
42 G : A random graph containing no path on four vertices. | |
43 | |
44 See Also | |
45 -------- | |
46 full_join | |
47 union | |
48 | |
49 References | |
50 ---------- | |
51 .. [1] D.G. Corneil, H. Lerchs, L.Stewart Burlingham, | |
52 "Complement reducible graphs", | |
53 Discrete Applied Mathematics, Volume 3, Issue 3, 1981, Pages 163-174, | |
54 ISSN 0166-218X. | |
55 """ | |
56 R = nx.empty_graph(1) | |
57 | |
58 for i in range(n): | |
59 RR = nx.relabel_nodes(R.copy(), lambda x: x + len(R)) | |
60 | |
61 if seed.randint(0, 1) == 0: | |
62 R = nx.full_join(R, RR) | |
63 else: | |
64 R = nx.disjoint_union(R, RR) | |
65 | |
66 return R |