"""用于计算和验证正则图的函数。"""
import networkx as nx
from networkx.utils import not_implemented_for
__all__ = ["is_regular", "is_k_regular", "k_factor"]
[docs]
@nx._dispatchable
def is_regular(G):
"""确定图 ``G`` 是否为正则图。
正则图是指每个顶点的度数相同的图。正则有向图是指每个顶点的入度和出度相等的图。
Parameters
----------
G : NetworkX 图
Returns
-------
bool
给定的图或有向图是否为正则图。
Examples
--------
>>> G = nx.DiGraph([(1, 2), (2, 3), (3, 4), (4, 1)])
>>> nx.is_regular(G)
True
"""
if len(G) == 0:
raise nx.NetworkXPointlessConcept("Graph has no nodes.")
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")
@nx._dispatchable
def is_k_regular(G, k):
"""确定图 ``G`` 是否为 k-正则图。
k-正则图是指每个顶点的度数均为 k 的图。
Parameters
----------
G : NetworkX 图
Returns
-------
bool
给定图是否为 k-正则图。
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")
@nx._dispatchable(preserve_edge_attrs=True, returns_graph=True)
def k_factor(G, k, matching_weight="weight"):
"""计算图 G 的 k-因子
图的 k-因子是一个 k-正则的生成子图。
G 的 k-正则生成子图是一个包含 G 的每个顶点和 G 的边子集的子图，使得每个顶点的度数为 k。
Parameters
----------
G : NetworkX 图
无向图
matching_weight: 字符串, 可选 (默认='weight')
对应于边权重的边数据键。
用于寻找最大权重的完美匹配。
如果键未找到，则使用 1 作为权重。
Returns
-------
G2 : NetworkX 图
G 的 k-因子
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
