1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
|
"""Functions for computing and verifying regular graphs."""
import networkx as nx
from networkx.utils import not_implemented_for
__all__ = ["is_regular", "is_k_regular", "k_factor"]
@nx.dispatch("is_regular")
def is_regular(G):
"""Determines whether the graph ``G`` is a regular graph.
A regular graph is a graph where each vertex has the same degree. A
regular digraph is a graph where the indegree and outdegree of each
vertex are equal.
Parameters
----------
G : NetworkX graph
Returns
-------
bool
Whether the given graph or digraph is regular.
Examples
--------
>>> G = nx.DiGraph([(1, 2), (2, 3), (3, 4), (4, 1)])
>>> nx.is_regular(G)
True
"""
n1 = nx.utils.arbitrary_element(G)
if not G.is_directed():
d1 = G.degree(n1)
return all(d1 == d for _, d in G.degree)
else:
d_in = G.in_degree(n1)
in_regular = all(d_in == d for _, d in G.in_degree)
d_out = G.out_degree(n1)
out_regular = all(d_out == d for _, d in G.out_degree)
return in_regular and out_regular
@nx.dispatch("is_k_regular")
@not_implemented_for("directed")
def is_k_regular(G, k):
"""Determines whether the graph ``G`` is a k-regular graph.
A k-regular graph is a graph where each vertex has degree k.
Parameters
----------
G : NetworkX graph
Returns
-------
bool
Whether the given graph is k-regular.
Examples
--------
>>> G = nx.Graph([(1, 2), (2, 3), (3, 4), (4, 1)])
>>> nx.is_k_regular(G, k=3)
False
"""
return all(d == k for n, d in G.degree)
@not_implemented_for("directed")
@not_implemented_for("multigraph")
def k_factor(G, k, matching_weight="weight"):
"""Compute a k-factor of G
A k-factor of a graph is a spanning k-regular subgraph.
A spanning k-regular subgraph of G is a subgraph that contains
each vertex of G and a subset of the edges of G such that each
vertex has degree k.
Parameters
----------
G : NetworkX graph
Undirected graph
matching_weight: string, optional (default='weight')
Edge data key corresponding to the edge weight.
Used for finding the max-weighted perfect matching.
If key not found, uses 1 as weight.
Returns
-------
G2 : NetworkX graph
A k-factor of G
Examples
--------
>>> G = nx.Graph([(1, 2), (2, 3), (3, 4), (4, 1)])
>>> G2 = nx.k_factor(G, k=1)
>>> G2.edges()
EdgeView([(1, 2), (3, 4)])
References
----------
.. [1] "An algorithm for computing simple k-factors.",
Meijer, Henk, Yurai Núñez-Rodríguez, and David Rappaport,
Information processing letters, 2009.
"""
from networkx.algorithms.matching import is_perfect_matching, max_weight_matching
class LargeKGadget:
def __init__(self, k, degree, node, g):
self.original = node
self.g = g
self.k = k
self.degree = degree
self.outer_vertices = [(node, x) for x in range(degree)]
self.core_vertices = [(node, x + degree) for x in range(degree - k)]
def replace_node(self):
adj_view = self.g[self.original]
neighbors = list(adj_view.keys())
edge_attrs = list(adj_view.values())
for (outer, neighbor, edge_attrs) in zip(
self.outer_vertices, neighbors, edge_attrs
):
self.g.add_edge(outer, neighbor, **edge_attrs)
for core in self.core_vertices:
for outer in self.outer_vertices:
self.g.add_edge(core, outer)
self.g.remove_node(self.original)
def restore_node(self):
self.g.add_node(self.original)
for outer in self.outer_vertices:
adj_view = self.g[outer]
for neighbor, edge_attrs in list(adj_view.items()):
if neighbor not in self.core_vertices:
self.g.add_edge(self.original, neighbor, **edge_attrs)
break
g.remove_nodes_from(self.outer_vertices)
g.remove_nodes_from(self.core_vertices)
class SmallKGadget:
def __init__(self, k, degree, node, g):
self.original = node
self.k = k
self.degree = degree
self.g = g
self.outer_vertices = [(node, x) for x in range(degree)]
self.inner_vertices = [(node, x + degree) for x in range(degree)]
self.core_vertices = [(node, x + 2 * degree) for x in range(k)]
def replace_node(self):
adj_view = self.g[self.original]
for (outer, inner, (neighbor, edge_attrs)) in zip(
self.outer_vertices, self.inner_vertices, list(adj_view.items())
):
self.g.add_edge(outer, inner)
self.g.add_edge(outer, neighbor, **edge_attrs)
for core in self.core_vertices:
for inner in self.inner_vertices:
self.g.add_edge(core, inner)
self.g.remove_node(self.original)
def restore_node(self):
self.g.add_node(self.original)
for outer in self.outer_vertices:
adj_view = self.g[outer]
for neighbor, edge_attrs in adj_view.items():
if neighbor not in self.core_vertices:
self.g.add_edge(self.original, neighbor, **edge_attrs)
break
self.g.remove_nodes_from(self.outer_vertices)
self.g.remove_nodes_from(self.inner_vertices)
self.g.remove_nodes_from(self.core_vertices)
# Step 1
if any(d < k for _, d in G.degree):
raise nx.NetworkXUnfeasible("Graph contains a vertex with degree less than k")
g = G.copy()
# Step 2
gadgets = []
for node, degree in list(g.degree):
if k < degree / 2.0:
gadget = SmallKGadget(k, degree, node, g)
else:
gadget = LargeKGadget(k, degree, node, g)
gadget.replace_node()
gadgets.append(gadget)
# Step 3
matching = max_weight_matching(g, maxcardinality=True, weight=matching_weight)
# Step 4
if not is_perfect_matching(g, matching):
raise nx.NetworkXUnfeasible(
"Cannot find k-factor because no perfect matching exists"
)
for edge in g.edges():
if edge not in matching and (edge[1], edge[0]) not in matching:
g.remove_edge(edge[0], edge[1])
for gadget in gadgets:
gadget.restore_node()
return g
|
