# Source code for networkx.algorithms.regular

```"""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"]

[docs]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

[docs]@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)

[docs]@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
----------
..  "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

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):
for (outer, neighbor, edge_attrs) in zip(
self.outer_vertices, neighbors, edge_attrs
):
for core in self.core_vertices:
for outer in self.outer_vertices:
self.g.remove_node(self.original)

def restore_node(self):
for outer in self.outer_vertices:
for neighbor, edge_attrs in list(adj_view.items()):
if neighbor not in self.core_vertices:
break
g.remove_nodes_from(self.outer_vertices)
g.remove_nodes_from(self.core_vertices)

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):
for (outer, inner, (neighbor, edge_attrs)) in zip(
):
for core in self.core_vertices:
for inner in self.inner_vertices:
self.g.remove_node(self.original)

def restore_node(self):
for outer in self.outer_vertices:
for neighbor, edge_attrs in adj_view.items():
if neighbor not in self.core_vertices:
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
for node, degree in list(g.degree):
if k < degree / 2.0:
else:

# 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, edge) not in matching:
g.remove_edge(edge, edge)