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

1"""Functions related to the Mycielski Operation and the Mycielskian family 

2of graphs. 

3 

4""" 

5 

6import networkx as nx 

7from networkx.utils import not_implemented_for 

8 

9__all__ = ["mycielskian", "mycielski_graph"] 

10 

11 

12@not_implemented_for("directed") 

13@not_implemented_for("multigraph") 

14@nx._dispatch 

15def mycielskian(G, iterations=1): 

16 r"""Returns the Mycielskian of a simple, undirected graph G 

17 

18 The Mycielskian of graph preserves a graph's triangle free 

19 property while increasing the chromatic number by 1. 

20 

21 The Mycielski Operation on a graph, :math:`G=(V, E)`, constructs a new 

22 graph with :math:`2|V| + 1` nodes and :math:`3|E| + |V|` edges. 

23 

24 The construction is as follows: 

25 

26 Let :math:`V = {0, ..., n-1}`. Construct another vertex set 

27 :math:`U = {n, ..., 2n}` and a vertex, `w`. 

28 Construct a new graph, `M`, with vertices :math:`U \bigcup V \bigcup w`. 

29 For edges, :math:`(u, v) \in E` add edges :math:`(u, v), (u, v + n)`, and 

30 :math:`(u + n, v)` to M. Finally, for all vertices :math:`u \in U`, add 

31 edge :math:`(u, w)` to M. 

32 

33 The Mycielski Operation can be done multiple times by repeating the above 

34 process iteratively. 

35 

36 More information can be found at https://en.wikipedia.org/wiki/Mycielskian 

37 

38 Parameters 

39 ---------- 

40 G : graph 

41 A simple, undirected NetworkX graph 

42 iterations : int 

43 The number of iterations of the Mycielski operation to 

44 perform on G. Defaults to 1. Must be a non-negative integer. 

45 

46 Returns 

47 ------- 

48 M : graph 

49 The Mycielskian of G after the specified number of iterations. 

50 

51 Notes 

52 ----- 

53 Graph, node, and edge data are not necessarily propagated to the new graph. 

54 

55 """ 

56 

57 M = nx.convert_node_labels_to_integers(G) 

58 

59 for i in range(iterations): 

60 n = M.number_of_nodes() 

61 M.add_nodes_from(range(n, 2 * n)) 

62 old_edges = list(M.edges()) 

63 M.add_edges_from((u, v + n) for u, v in old_edges) 

64 M.add_edges_from((u + n, v) for u, v in old_edges) 

65 M.add_node(2 * n) 

66 M.add_edges_from((u + n, 2 * n) for u in range(n)) 

67 

68 return M 

69 

70 

71@nx._dispatch(graphs=None) 

72def mycielski_graph(n): 

73 """Generator for the n_th Mycielski Graph. 

74 

75 The Mycielski family of graphs is an infinite set of graphs. 

76 :math:`M_1` is the singleton graph, :math:`M_2` is two vertices with an 

77 edge, and, for :math:`i > 2`, :math:`M_i` is the Mycielskian of 

78 :math:`M_{i-1}`. 

79 

80 More information can be found at 

81 http://mathworld.wolfram.com/MycielskiGraph.html 

82 

83 Parameters 

84 ---------- 

85 n : int 

86 The desired Mycielski Graph. 

87 

88 Returns 

89 ------- 

90 M : graph 

91 The n_th Mycielski Graph 

92 

93 Notes 

94 ----- 

95 The first graph in the Mycielski sequence is the singleton graph. 

96 The Mycielskian of this graph is not the :math:`P_2` graph, but rather the 

97 :math:`P_2` graph with an extra, isolated vertex. The second Mycielski 

98 graph is the :math:`P_2` graph, so the first two are hard coded. 

99 The remaining graphs are generated using the Mycielski operation. 

100 

101 """ 

102 

103 if n < 1: 

104 raise nx.NetworkXError("must satisfy n >= 0") 

105 

106 if n == 1: 

107 return nx.empty_graph(1) 

108 

109 else: 

110 return mycielskian(nx.path_graph(2), n - 2)