Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/generators/mycielski.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 """Functions related to the Mycielski Operation and the Mycielskian family | |
2 of graphs. | |
3 | |
4 """ | |
5 | |
6 import networkx as nx | |
7 from 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 def mycielskian(G, iterations=1): | |
15 r"""Returns the Mycielskian of a simple, undirected graph G | |
16 | |
17 The Mycielskian of graph preserves a graph's triangle free | |
18 property while increasing the chromatic number by 1. | |
19 | |
20 The Mycielski Operation on a graph, :math:`G=(V, E)`, constructs a new | |
21 graph with :math:`2|V| + 1` nodes and :math:`3|E| + |V|` edges. | |
22 | |
23 The construction is as follows: | |
24 | |
25 Let :math:`V = {0, ..., n-1}`. Construct another vertex set | |
26 :math:`U = {n, ..., 2n}` and a vertex, `w`. | |
27 Construct a new graph, `M`, with vertices :math:`U \bigcup V \bigcup w`. | |
28 For edges, :math:`(u, v) \in E` add edges :math:`(u, v), (u, v + n)`, and | |
29 :math:`(u + n, v)` to M. Finally, for all vertices :math:`u \in U`, add | |
30 edge :math:`(u, w)` to M. | |
31 | |
32 The Mycielski Operation can be done multiple times by repeating the above | |
33 process iteratively. | |
34 | |
35 More information can be found at https://en.wikipedia.org/wiki/Mycielskian | |
36 | |
37 Parameters | |
38 ---------- | |
39 G : graph | |
40 A simple, undirected NetworkX graph | |
41 iterations : int | |
42 The number of iterations of the Mycielski operation to | |
43 perform on G. Defaults to 1. Must be a non-negative integer. | |
44 | |
45 Returns | |
46 ------- | |
47 M : graph | |
48 The Mycielskian of G after the specified number of iterations. | |
49 | |
50 Notes | |
51 ------ | |
52 Graph, node, and edge data are not necessarily propagated to the new graph. | |
53 | |
54 """ | |
55 | |
56 n = G.number_of_nodes() | |
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 def mycielski_graph(n): | |
72 """Generator for the n_th Mycielski Graph. | |
73 | |
74 The Mycielski family of graphs is an infinite set of graphs. | |
75 :math:`M_1` is the singleton graph, :math:`M_2` is two vertices with an | |
76 edge, and, for :math:`i > 2`, :math:`M_i` is the Mycielskian of | |
77 :math:`M_{i-1}`. | |
78 | |
79 More information can be found at | |
80 http://mathworld.wolfram.com/MycielskiGraph.html | |
81 | |
82 Parameters | |
83 ---------- | |
84 n : int | |
85 The desired Mycielski Graph. | |
86 | |
87 Returns | |
88 ------- | |
89 M : graph | |
90 The n_th Mycielski Graph | |
91 | |
92 Notes | |
93 ----- | |
94 The first graph in the Mycielski sequence is the singleton graph. | |
95 The Mycielskian of this graph is not the :math:`P_2` graph, but rather the | |
96 :math:`P_2` graph with an extra, isolated vertex. The second Mycielski | |
97 graph is the :math:`P_2` graph, so the first two are hard coded. | |
98 The remaining graphs are generated using the Mycielski operation. | |
99 | |
100 """ | |
101 | |
102 if n < 1: | |
103 raise nx.NetworkXError("must satisfy n >= 0") | |
104 | |
105 if n == 1: | |
106 return nx.empty_graph(1) | |
107 | |
108 else: | |
109 return mycielskian(nx.path_graph(2), n - 2) |