Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Functions for computing and verifying regular graphs."""
3import networkx as nx
4from networkx.utils import not_implemented_for
6__all__ = ["is_regular", "is_k_regular", "k_factor"]
9@nx._dispatchable
10def is_regular(G):
11 """Determines whether a graph is regular.
13 A regular graph is a graph where all nodes have the same degree. A regular
14 digraph is a graph where all nodes have the same indegree and all nodes
15 have the same outdegree.
17 Parameters
18 ----------
19 G : NetworkX graph
21 Returns
22 -------
23 bool
24 Whether the given graph or digraph is regular.
26 Examples
27 --------
28 >>> G = nx.DiGraph([(1, 2), (2, 3), (3, 4), (4, 1)])
29 >>> nx.is_regular(G)
30 True
32 """
33 if len(G) == 0:
34 raise nx.NetworkXPointlessConcept("Graph has no nodes.")
35 n1 = nx.utils.arbitrary_element(G)
36 if not G.is_directed():
37 d1 = G.degree(n1)
38 return all(d1 == d for _, d in G.degree)
39 else:
40 d_in = G.in_degree(n1)
41 in_regular = (d_in == d for _, d in G.in_degree)
42 d_out = G.out_degree(n1)
43 out_regular = (d_out == d for _, d in G.out_degree)
44 return all(in_regular) and all(out_regular)
47@not_implemented_for("directed")
48@nx._dispatchable
49def is_k_regular(G, k):
50 """Determines whether the graph ``G`` is a k-regular graph.
52 A k-regular graph is a graph where each vertex has degree k.
54 Parameters
55 ----------
56 G : NetworkX graph
58 Returns
59 -------
60 bool
61 Whether the given graph is k-regular.
63 Examples
64 --------
65 >>> G = nx.Graph([(1, 2), (2, 3), (3, 4), (4, 1)])
66 >>> nx.is_k_regular(G, k=3)
67 False
69 """
70 return all(d == k for n, d in G.degree)
73@not_implemented_for("directed")
74@not_implemented_for("multigraph")
75@nx._dispatchable(preserve_edge_attrs=True, returns_graph=True)
76def k_factor(G, k, matching_weight="weight"):
77 """Compute a `k`-factor of a graph.
79 A `k`-factor of a graph is a spanning `k`-regular subgraph.
80 A spanning `k`-regular subgraph of `G` is a subgraph that contains
81 each node of `G` and a subset of the edges of `G` such that each
82 node has degree `k`.
84 Parameters
85 ----------
86 G : NetworkX graph
87 An undirected graph.
89 k : int
90 The degree of the `k`-factor.
92 matching_weight: string, optional (default="weight")
93 Edge attribute name corresponding to the edge weight.
94 If not present, the edge is assumed to have weight 1.
95 Used for finding the max-weighted perfect matching.
97 Returns
98 -------
99 NetworkX graph
100 A `k`-factor of `G`.
102 Examples
103 --------
104 >>> G = nx.Graph([(1, 2), (2, 3), (3, 4), (4, 1)])
105 >>> KF = nx.k_factor(G, k=1)
106 >>> KF.edges()
107 EdgeView([(1, 2), (3, 4)])
109 References
110 ----------
111 .. [1] "An algorithm for computing simple k-factors.",
112 Meijer, Henk, Yurai Núñez-Rodríguez, and David Rappaport,
113 Information processing letters, 2009.
114 """
115 # Validate minimum degree requirement.
116 if any(d < k for _, d in G.degree):
117 raise nx.NetworkXUnfeasible("Graph contains a vertex with degree less than k")
119 g = G.copy()
120 gadgets = []
122 # Replace each node with a gadget.
123 for node, degree in G.degree:
124 is_large = k >= degree / 2.0
126 # Create gadget nodes.
127 outer = [(node, i) for i in range(degree)]
128 if is_large:
129 core = [(node, i) for i in range(degree, 2 * degree - k)]
130 inner = []
131 else:
132 core = [(node, i) for i in range(2 * degree, 2 * degree + k)]
133 inner = [(node, i) for i in range(degree, 2 * degree)]
135 # Connect gadget nodes to neighbors.
136 g.add_edges_from(zip(outer, inner))
137 for outer_n, (neighbor, attrs) in zip(outer, g[node].items()):
138 g.add_edge(outer_n, neighbor, **attrs)
140 # Add internal edges.
141 g.add_edges_from((u, v) for u in core for v in (outer if is_large else inner))
143 g.remove_node(node)
144 gadgets.append((node, outer, core, inner))
146 # Find perfect matching.
147 m = nx.max_weight_matching(g, maxcardinality=True, weight=matching_weight)
148 if not nx.is_perfect_matching(g, m):
149 raise nx.NetworkXUnfeasible(
150 "Cannot find k-factor because no perfect matching exists"
151 )
153 # Keep only edges in matching.
154 g.remove_edges_from(e for e in g.edges if e not in m and e[::-1] not in m)
156 # Restore original nodes and remove gadgets.
157 for node, outer, core, inner in gadgets:
158 g.add_node(node)
159 core_set = set(core)
160 for outer_n in outer:
161 for neighbor, attrs in g._adj[outer_n].items():
162 if neighbor not in core_set:
163 g.add_edge(node, neighbor, **attrs)
164 break
165 g.remove_nodes_from(outer + core + inner)
167 return g