Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/generators/mycielski.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
1 # Copyright (C) 2010-2019 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:`2|V| + 1` nodes and :math:`3|E| + |V|` edges.
29
30 The construction is as follows:
31
32 Let :math:`V = {0, ..., n-1}`. 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 non-negative 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_{i-1}`.
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)