Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/regular.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Functions for computing and verifying regular graphs.""" | |
2 import networkx as nx | |
3 from networkx.utils import not_implemented_for | |
4 | |
5 __all__ = ["is_regular", "is_k_regular", "k_factor"] | |
6 | |
7 | |
8 def is_regular(G): | |
9 """Determines whether the graph ``G`` is a regular graph. | |
10 | |
11 A regular graph is a graph where each vertex has the same degree. A | |
12 regular digraph is a graph where the indegree and outdegree of each | |
13 vertex are equal. | |
14 | |
15 Parameters | |
16 ---------- | |
17 G : NetworkX graph | |
18 | |
19 Returns | |
20 ------- | |
21 bool | |
22 Whether the given graph or digraph is regular. | |
23 | |
24 """ | |
25 n1 = nx.utils.arbitrary_element(G) | |
26 if not G.is_directed(): | |
27 d1 = G.degree(n1) | |
28 return all(d1 == d for _, d in G.degree) | |
29 else: | |
30 d_in = G.in_degree(n1) | |
31 in_regular = all(d_in == d for _, d in G.in_degree) | |
32 d_out = G.out_degree(n1) | |
33 out_regular = all(d_out == d for _, d in G.out_degree) | |
34 return in_regular and out_regular | |
35 | |
36 | |
37 @not_implemented_for("directed") | |
38 def is_k_regular(G, k): | |
39 """Determines whether the graph ``G`` is a k-regular graph. | |
40 | |
41 A k-regular graph is a graph where each vertex has degree k. | |
42 | |
43 Parameters | |
44 ---------- | |
45 G : NetworkX graph | |
46 | |
47 Returns | |
48 ------- | |
49 bool | |
50 Whether the given graph is k-regular. | |
51 | |
52 """ | |
53 return all(d == k for n, d in G.degree) | |
54 | |
55 | |
56 @not_implemented_for("directed") | |
57 @not_implemented_for("multigraph") | |
58 def k_factor(G, k, matching_weight="weight"): | |
59 """Compute a k-factor of G | |
60 | |
61 A k-factor of a graph is a spanning k-regular subgraph. | |
62 A spanning k-regular subgraph of G is a subgraph that contains | |
63 each vertex of G and a subset of the edges of G such that each | |
64 vertex has degree k. | |
65 | |
66 Parameters | |
67 ---------- | |
68 G : NetworkX graph | |
69 Undirected graph | |
70 | |
71 weight: string, optional (default='weight') | |
72 Edge data key corresponding to the edge weight. | |
73 Used for finding the max-weighted perfect matching. | |
74 If key not found, uses 1 as weight. | |
75 | |
76 Returns | |
77 ------- | |
78 G2 : NetworkX graph | |
79 A k-factor of G | |
80 | |
81 References | |
82 ---------- | |
83 .. [1] "An algorithm for computing simple k-factors.", | |
84 Meijer, Henk, Yurai Núñez-Rodríguez, and David Rappaport, | |
85 Information processing letters, 2009. | |
86 """ | |
87 | |
88 from networkx.algorithms.matching import max_weight_matching | |
89 from networkx.algorithms.matching import is_perfect_matching | |
90 | |
91 class LargeKGadget: | |
92 def __init__(self, k, degree, node, g): | |
93 self.original = node | |
94 self.g = g | |
95 self.k = k | |
96 self.degree = degree | |
97 | |
98 self.outer_vertices = [(node, x) for x in range(degree)] | |
99 self.core_vertices = [(node, x + degree) for x in range(degree - k)] | |
100 | |
101 def replace_node(self): | |
102 adj_view = self.g[self.original] | |
103 neighbors = list(adj_view.keys()) | |
104 edge_attrs = list(adj_view.values()) | |
105 for (outer, neighbor, edge_attrs) in zip( | |
106 self.outer_vertices, neighbors, edge_attrs | |
107 ): | |
108 self.g.add_edge(outer, neighbor, **edge_attrs) | |
109 for core in self.core_vertices: | |
110 for outer in self.outer_vertices: | |
111 self.g.add_edge(core, outer) | |
112 self.g.remove_node(self.original) | |
113 | |
114 def restore_node(self): | |
115 self.g.add_node(self.original) | |
116 for outer in self.outer_vertices: | |
117 adj_view = self.g[outer] | |
118 for neighbor, edge_attrs in list(adj_view.items()): | |
119 if neighbor not in self.core_vertices: | |
120 self.g.add_edge(self.original, neighbor, **edge_attrs) | |
121 break | |
122 g.remove_nodes_from(self.outer_vertices) | |
123 g.remove_nodes_from(self.core_vertices) | |
124 | |
125 class SmallKGadget: | |
126 def __init__(self, k, degree, node, g): | |
127 self.original = node | |
128 self.k = k | |
129 self.degree = degree | |
130 self.g = g | |
131 | |
132 self.outer_vertices = [(node, x) for x in range(degree)] | |
133 self.inner_vertices = [(node, x + degree) for x in range(degree)] | |
134 self.core_vertices = [(node, x + 2 * degree) for x in range(k)] | |
135 | |
136 def replace_node(self): | |
137 adj_view = self.g[self.original] | |
138 for (outer, inner, (neighbor, edge_attrs)) in zip( | |
139 self.outer_vertices, self.inner_vertices, list(adj_view.items()) | |
140 ): | |
141 self.g.add_edge(outer, inner) | |
142 self.g.add_edge(outer, neighbor, **edge_attrs) | |
143 for core in self.core_vertices: | |
144 for inner in self.inner_vertices: | |
145 self.g.add_edge(core, inner) | |
146 self.g.remove_node(self.original) | |
147 | |
148 def restore_node(self): | |
149 self.g.add_node(self.original) | |
150 for outer in self.outer_vertices: | |
151 adj_view = self.g[outer] | |
152 for neighbor, edge_attrs in adj_view.items(): | |
153 if neighbor not in self.core_vertices: | |
154 self.g.add_edge(self.original, neighbor, **edge_attrs) | |
155 break | |
156 self.g.remove_nodes_from(self.outer_vertices) | |
157 self.g.remove_nodes_from(self.inner_vertices) | |
158 self.g.remove_nodes_from(self.core_vertices) | |
159 | |
160 # Step 1 | |
161 if any(d < k for _, d in G.degree): | |
162 raise nx.NetworkXUnfeasible("Graph contains a vertex with degree less than k") | |
163 g = G.copy() | |
164 | |
165 # Step 2 | |
166 gadgets = [] | |
167 for node, degree in list(g.degree): | |
168 if k < degree / 2.0: | |
169 gadget = SmallKGadget(k, degree, node, g) | |
170 else: | |
171 gadget = LargeKGadget(k, degree, node, g) | |
172 gadget.replace_node() | |
173 gadgets.append(gadget) | |
174 | |
175 # Step 3 | |
176 matching = max_weight_matching(g, maxcardinality=True, weight=matching_weight) | |
177 | |
178 # Step 4 | |
179 if not is_perfect_matching(g, matching): | |
180 raise nx.NetworkXUnfeasible( | |
181 "Cannot find k-factor because no perfect matching exists" | |
182 ) | |
183 | |
184 for edge in g.edges(): | |
185 if edge not in matching and (edge[1], edge[0]) not in matching: | |
186 g.remove_edge(edge[0], edge[1]) | |
187 | |
188 for gadget in gadgets: | |
189 gadget.restore_node() | |
190 | |
191 return g |