Spaces:
Sleeping
Sleeping
| """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"] | |
| 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 | |
| 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) | |
| 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 | |