ioftools / networkxMiCe / networkxmaster / networkx / generators / mycielski.py @ 5cef0f13
History  View  Annotate  Download (3.36 KB)
1 
# Copyright (C) 20102019 by


2 
# Aric Hagberg <hagberg@lanl.gov>

3 
# Dan Schult <dschult@colgate.edu>

4 
# Pieter Swart <swart@lanl.gov>

5 
# All rights reserved.

6 
# BSD license.

7  
8 
"""Functions related to the Mycielski Operation and the Mycielskian family

9 
of graphs.

10 

11 
"""

12  
13 
import networkx as nx 
14 
from networkx.utils import not_implemented_for 
15  
16 
__all__ = ['mycielskian', 'mycielski_graph'] 
17  
18  
19 
@not_implemented_for('directed') 
20 
@not_implemented_for('multigraph') 
21 
def mycielskian(G, iterations=1): 
22 
r"""Returns the Mycielskian of a simple, undirected graph G

23 

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

25 
property while increasing the chromatic number by 1.

26 

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

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

29 

30 
The construction is as follows:

31 

32 
Let :math:`V = {0, ..., n1}`. Construct another vertex set

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

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

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

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

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

38 

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

40 
process iteratively.

41 

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

43 

44 
Parameters

45 


46 
G : graph

47 
A simple, undirected NetworkX graph

48 
iterations : int

49 
The number of iterations of the Mycielski operation to

50 
perform on G. Defaults to 1. Must be a nonnegative integer.

51 

52 
Returns

53 


54 
M : graph

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

56 

57 
Notes

58 


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

60 

61 
"""

62  
63 
n = G.number_of_nodes() 
64 
M = nx.convert_node_labels_to_integers(G) 
65  
66 
for i in range(iterations): 
67 
n = M.number_of_nodes() 
68 
M.add_nodes_from(range(n, 2 * n)) 
69 
old_edges = list(M.edges())

70 
M.add_edges_from((u, v + n) for u, v in old_edges) 
71 
M.add_edges_from((u + n, v) for u, v in old_edges) 
72 
M.add_node(2 * n)

73 
M.add_edges_from((u + n, 2 * n) for u in range(n)) 
74  
75 
return M

76  
77  
78 
def mycielski_graph(n): 
79 
"""Generator for the n_th Mycielski Graph.

80 

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

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

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

84 
:math:`M_{i1}`.

85 

86 
More information can be found at

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

88 

89 
Parameters

90 


91 
n : int

92 
The desired Mycielski Graph.

93 

94 
Returns

95 


96 
M : graph

97 
The n_th Mycielski Graph

98 

99 
Notes

100 


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

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

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

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

105 
The remaining graphs are generated using the Mycielski operation.

106 

107 
"""

108  
109 
if n < 1: 
110 
raise nx.NetworkXError("must satisfy n >= 0") 
111  
112 
if n == 1: 
113 
return nx.empty_graph(1) 
114  
115 
else:

116 
return mycielskian(nx.path_graph(2), n  2) 