Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/generators/cographs.py: 46%

1r"""Generators for cographs 

2 

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. 

6 

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""" 

14import networkx as nx 

15from networkx.utils import py_random_state 

16 

17__all__ = ["random_cograph"] 

18 

19 

20@py_random_state(1) 

21@nx._dispatch(graphs=None) 

22def random_cograph(n, seed=None): 

23 r"""Returns a random cograph with $2 ^ n$ nodes. 

24 

25 A cograph is a graph containing no path on four vertices. 

26 Cographs or $P_4$-free graphs can be obtained from a single vertex 

27 by disjoint union and complementation operations. 

28 

29 This generator starts off from a single vertex and performs disjoint 

30 union and full join operations on itself. 

31 The decision on which operation will take place is random. 

32 

33 Parameters 

34 ---------- 

35 n : int 

36 The order of the cograph. 

37 seed : integer, random_state, or None (default) 

38 Indicator of random number generation state. 

39 See :ref:`Randomness<randomness>`. 

40 

41 Returns 

42 ------- 

43 G : A random graph containing no path on four vertices. 

44 

45 See Also 

46 -------- 

47 full_join 

48 union 

49 

50 References 

51 ---------- 

52 .. [1] D.G. Corneil, H. Lerchs, L.Stewart Burlingham, 

53 "Complement reducible graphs", 

54 Discrete Applied Mathematics, Volume 3, Issue 3, 1981, Pages 163-174, 

55 ISSN 0166-218X. 

56 """ 

57 R = nx.empty_graph(1) 

58 

59 for i in range(n): 

60 RR = nx.relabel_nodes(R.copy(), lambda x: x + len(R)) 

61 

62 if seed.randint(0, 1) == 0: 

63 R = nx.full_join(R, RR) 

64 else: 

65 R = nx.disjoint_union(R, RR) 

66 

67 return R