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