Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/graphical.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 """Test sequences for graphiness. | |
2 """ | |
3 import heapq | |
4 import networkx as nx | |
5 | |
6 __all__ = [ | |
7 "is_graphical", | |
8 "is_multigraphical", | |
9 "is_pseudographical", | |
10 "is_digraphical", | |
11 "is_valid_degree_sequence_erdos_gallai", | |
12 "is_valid_degree_sequence_havel_hakimi", | |
13 ] | |
14 | |
15 | |
16 def is_graphical(sequence, method="eg"): | |
17 """Returns True if sequence is a valid degree sequence. | |
18 | |
19 A degree sequence is valid if some graph can realize it. | |
20 | |
21 Parameters | |
22 ---------- | |
23 sequence : list or iterable container | |
24 A sequence of integer node degrees | |
25 | |
26 method : "eg" | "hh" (default: 'eg') | |
27 The method used to validate the degree sequence. | |
28 "eg" corresponds to the Erdős-Gallai algorithm, and | |
29 "hh" to the Havel-Hakimi algorithm. | |
30 | |
31 Returns | |
32 ------- | |
33 valid : bool | |
34 True if the sequence is a valid degree sequence and False if not. | |
35 | |
36 Examples | |
37 -------- | |
38 >>> G = nx.path_graph(4) | |
39 >>> sequence = (d for n, d in G.degree()) | |
40 >>> nx.is_graphical(sequence) | |
41 True | |
42 | |
43 References | |
44 ---------- | |
45 Erdős-Gallai | |
46 [EG1960]_, [choudum1986]_ | |
47 | |
48 Havel-Hakimi | |
49 [havel1955]_, [hakimi1962]_, [CL1996]_ | |
50 """ | |
51 if method == "eg": | |
52 valid = is_valid_degree_sequence_erdos_gallai(list(sequence)) | |
53 elif method == "hh": | |
54 valid = is_valid_degree_sequence_havel_hakimi(list(sequence)) | |
55 else: | |
56 msg = "`method` must be 'eg' or 'hh'" | |
57 raise nx.NetworkXException(msg) | |
58 return valid | |
59 | |
60 | |
61 def _basic_graphical_tests(deg_sequence): | |
62 # Sort and perform some simple tests on the sequence | |
63 deg_sequence = nx.utils.make_list_of_ints(deg_sequence) | |
64 p = len(deg_sequence) | |
65 num_degs = [0] * p | |
66 dmax, dmin, dsum, n = 0, p, 0, 0 | |
67 for d in deg_sequence: | |
68 # Reject if degree is negative or larger than the sequence length | |
69 if d < 0 or d >= p: | |
70 raise nx.NetworkXUnfeasible | |
71 # Process only the non-zero integers | |
72 elif d > 0: | |
73 dmax, dmin, dsum, n = max(dmax, d), min(dmin, d), dsum + d, n + 1 | |
74 num_degs[d] += 1 | |
75 # Reject sequence if it has odd sum or is oversaturated | |
76 if dsum % 2 or dsum > n * (n - 1): | |
77 raise nx.NetworkXUnfeasible | |
78 return dmax, dmin, dsum, n, num_degs | |
79 | |
80 | |
81 def is_valid_degree_sequence_havel_hakimi(deg_sequence): | |
82 r"""Returns True if deg_sequence can be realized by a simple graph. | |
83 | |
84 The validation proceeds using the Havel-Hakimi theorem. | |
85 Worst-case run time is $O(s)$ where $s$ is the sum of the sequence. | |
86 | |
87 Parameters | |
88 ---------- | |
89 deg_sequence : list | |
90 A list of integers where each element specifies the degree of a node | |
91 in a graph. | |
92 | |
93 Returns | |
94 ------- | |
95 valid : bool | |
96 True if deg_sequence is graphical and False if not. | |
97 | |
98 Notes | |
99 ----- | |
100 The ZZ condition says that for the sequence d if | |
101 | |
102 .. math:: | |
103 |d| >= \frac{(\max(d) + \min(d) + 1)^2}{4*\min(d)} | |
104 | |
105 then d is graphical. This was shown in Theorem 6 in [1]_. | |
106 | |
107 References | |
108 ---------- | |
109 .. [1] I.E. Zverovich and V.E. Zverovich. "Contributions to the theory | |
110 of graphic sequences", Discrete Mathematics, 105, pp. 292-303 (1992). | |
111 | |
112 [havel1955]_, [hakimi1962]_, [CL1996]_ | |
113 | |
114 """ | |
115 try: | |
116 dmax, dmin, dsum, n, num_degs = _basic_graphical_tests(deg_sequence) | |
117 except nx.NetworkXUnfeasible: | |
118 return False | |
119 # Accept if sequence has no non-zero degrees or passes the ZZ condition | |
120 if n == 0 or 4 * dmin * n >= (dmax + dmin + 1) * (dmax + dmin + 1): | |
121 return True | |
122 | |
123 modstubs = [0] * (dmax + 1) | |
124 # Successively reduce degree sequence by removing the maximum degree | |
125 while n > 0: | |
126 # Retrieve the maximum degree in the sequence | |
127 while num_degs[dmax] == 0: | |
128 dmax -= 1 | |
129 # If there are not enough stubs to connect to, then the sequence is | |
130 # not graphical | |
131 if dmax > n - 1: | |
132 return False | |
133 | |
134 # Remove largest stub in list | |
135 num_degs[dmax], n = num_degs[dmax] - 1, n - 1 | |
136 # Reduce the next dmax largest stubs | |
137 mslen = 0 | |
138 k = dmax | |
139 for i in range(dmax): | |
140 while num_degs[k] == 0: | |
141 k -= 1 | |
142 num_degs[k], n = num_degs[k] - 1, n - 1 | |
143 if k > 1: | |
144 modstubs[mslen] = k - 1 | |
145 mslen += 1 | |
146 # Add back to the list any non-zero stubs that were removed | |
147 for i in range(mslen): | |
148 stub = modstubs[i] | |
149 num_degs[stub], n = num_degs[stub] + 1, n + 1 | |
150 return True | |
151 | |
152 | |
153 def is_valid_degree_sequence_erdos_gallai(deg_sequence): | |
154 r"""Returns True if deg_sequence can be realized by a simple graph. | |
155 | |
156 The validation is done using the Erdős-Gallai theorem [EG1960]_. | |
157 | |
158 Parameters | |
159 ---------- | |
160 deg_sequence : list | |
161 A list of integers | |
162 | |
163 Returns | |
164 ------- | |
165 valid : bool | |
166 True if deg_sequence is graphical and False if not. | |
167 | |
168 Notes | |
169 ----- | |
170 | |
171 This implementation uses an equivalent form of the Erdős-Gallai criterion. | |
172 Worst-case run time is $O(n)$ where $n$ is the length of the sequence. | |
173 | |
174 Specifically, a sequence d is graphical if and only if the | |
175 sum of the sequence is even and for all strong indices k in the sequence, | |
176 | |
177 .. math:: | |
178 | |
179 \sum_{i=1}^{k} d_i \leq k(k-1) + \sum_{j=k+1}^{n} \min(d_i,k) | |
180 = k(n-1) - ( k \sum_{j=0}^{k-1} n_j - \sum_{j=0}^{k-1} j n_j ) | |
181 | |
182 A strong index k is any index where d_k >= k and the value n_j is the | |
183 number of occurrences of j in d. The maximal strong index is called the | |
184 Durfee index. | |
185 | |
186 This particular rearrangement comes from the proof of Theorem 3 in [2]_. | |
187 | |
188 The ZZ condition says that for the sequence d if | |
189 | |
190 .. math:: | |
191 |d| >= \frac{(\max(d) + \min(d) + 1)^2}{4*\min(d)} | |
192 | |
193 then d is graphical. This was shown in Theorem 6 in [2]_. | |
194 | |
195 References | |
196 ---------- | |
197 .. [1] A. Tripathi and S. Vijay. "A note on a theorem of Erdős & Gallai", | |
198 Discrete Mathematics, 265, pp. 417-420 (2003). | |
199 .. [2] I.E. Zverovich and V.E. Zverovich. "Contributions to the theory | |
200 of graphic sequences", Discrete Mathematics, 105, pp. 292-303 (1992). | |
201 | |
202 [EG1960]_, [choudum1986]_ | |
203 """ | |
204 try: | |
205 dmax, dmin, dsum, n, num_degs = _basic_graphical_tests(deg_sequence) | |
206 except nx.NetworkXUnfeasible: | |
207 return False | |
208 # Accept if sequence has no non-zero degrees or passes the ZZ condition | |
209 if n == 0 or 4 * dmin * n >= (dmax + dmin + 1) * (dmax + dmin + 1): | |
210 return True | |
211 | |
212 # Perform the EG checks using the reformulation of Zverovich and Zverovich | |
213 k, sum_deg, sum_nj, sum_jnj = 0, 0, 0, 0 | |
214 for dk in range(dmax, dmin - 1, -1): | |
215 if dk < k + 1: # Check if already past Durfee index | |
216 return True | |
217 if num_degs[dk] > 0: | |
218 run_size = num_degs[dk] # Process a run of identical-valued degrees | |
219 if dk < k + run_size: # Check if end of run is past Durfee index | |
220 run_size = dk - k # Adjust back to Durfee index | |
221 sum_deg += run_size * dk | |
222 for v in range(run_size): | |
223 sum_nj += num_degs[k + v] | |
224 sum_jnj += (k + v) * num_degs[k + v] | |
225 k += run_size | |
226 if sum_deg > k * (n - 1) - k * sum_nj + sum_jnj: | |
227 return False | |
228 return True | |
229 | |
230 | |
231 def is_multigraphical(sequence): | |
232 """Returns True if some multigraph can realize the sequence. | |
233 | |
234 Parameters | |
235 ---------- | |
236 sequence : list | |
237 A list of integers | |
238 | |
239 Returns | |
240 ------- | |
241 valid : bool | |
242 True if deg_sequence is a multigraphic degree sequence and False if not. | |
243 | |
244 Notes | |
245 ----- | |
246 The worst-case run time is $O(n)$ where $n$ is the length of the sequence. | |
247 | |
248 References | |
249 ---------- | |
250 .. [1] S. L. Hakimi. "On the realizability of a set of integers as | |
251 degrees of the vertices of a linear graph", J. SIAM, 10, pp. 496-506 | |
252 (1962). | |
253 """ | |
254 try: | |
255 deg_sequence = nx.utils.make_list_of_ints(sequence) | |
256 except nx.NetworkXError: | |
257 return False | |
258 dsum, dmax = 0, 0 | |
259 for d in deg_sequence: | |
260 if d < 0: | |
261 return False | |
262 dsum, dmax = dsum + d, max(dmax, d) | |
263 if dsum % 2 or dsum < 2 * dmax: | |
264 return False | |
265 return True | |
266 | |
267 | |
268 def is_pseudographical(sequence): | |
269 """Returns True if some pseudograph can realize the sequence. | |
270 | |
271 Every nonnegative integer sequence with an even sum is pseudographical | |
272 (see [1]_). | |
273 | |
274 Parameters | |
275 ---------- | |
276 sequence : list or iterable container | |
277 A sequence of integer node degrees | |
278 | |
279 Returns | |
280 ------- | |
281 valid : bool | |
282 True if the sequence is a pseudographic degree sequence and False if not. | |
283 | |
284 Notes | |
285 ----- | |
286 The worst-case run time is $O(n)$ where n is the length of the sequence. | |
287 | |
288 References | |
289 ---------- | |
290 .. [1] F. Boesch and F. Harary. "Line removal algorithms for graphs | |
291 and their degree lists", IEEE Trans. Circuits and Systems, CAS-23(12), | |
292 pp. 778-782 (1976). | |
293 """ | |
294 try: | |
295 deg_sequence = nx.utils.make_list_of_ints(sequence) | |
296 except nx.NetworkXError: | |
297 return False | |
298 return sum(deg_sequence) % 2 == 0 and min(deg_sequence) >= 0 | |
299 | |
300 | |
301 def is_digraphical(in_sequence, out_sequence): | |
302 r"""Returns True if some directed graph can realize the in- and out-degree | |
303 sequences. | |
304 | |
305 Parameters | |
306 ---------- | |
307 in_sequence : list or iterable container | |
308 A sequence of integer node in-degrees | |
309 | |
310 out_sequence : list or iterable container | |
311 A sequence of integer node out-degrees | |
312 | |
313 Returns | |
314 ------- | |
315 valid : bool | |
316 True if in and out-sequences are digraphic False if not. | |
317 | |
318 Notes | |
319 ----- | |
320 This algorithm is from Kleitman and Wang [1]_. | |
321 The worst case runtime is $O(s \times \log n)$ where $s$ and $n$ are the | |
322 sum and length of the sequences respectively. | |
323 | |
324 References | |
325 ---------- | |
326 .. [1] D.J. Kleitman and D.L. Wang | |
327 Algorithms for Constructing Graphs and Digraphs with Given Valences | |
328 and Factors, Discrete Mathematics, 6(1), pp. 79-88 (1973) | |
329 """ | |
330 try: | |
331 in_deg_sequence = nx.utils.make_list_of_ints(in_sequence) | |
332 out_deg_sequence = nx.utils.make_list_of_ints(out_sequence) | |
333 except nx.NetworkXError: | |
334 return False | |
335 # Process the sequences and form two heaps to store degree pairs with | |
336 # either zero or non-zero out degrees | |
337 sumin, sumout, nin, nout = 0, 0, len(in_deg_sequence), len(out_deg_sequence) | |
338 maxn = max(nin, nout) | |
339 maxin = 0 | |
340 if maxn == 0: | |
341 return True | |
342 stubheap, zeroheap = [], [] | |
343 for n in range(maxn): | |
344 in_deg, out_deg = 0, 0 | |
345 if n < nout: | |
346 out_deg = out_deg_sequence[n] | |
347 if n < nin: | |
348 in_deg = in_deg_sequence[n] | |
349 if in_deg < 0 or out_deg < 0: | |
350 return False | |
351 sumin, sumout, maxin = sumin + in_deg, sumout + out_deg, max(maxin, in_deg) | |
352 if in_deg > 0: | |
353 stubheap.append((-1 * out_deg, -1 * in_deg)) | |
354 elif out_deg > 0: | |
355 zeroheap.append(-1 * out_deg) | |
356 if sumin != sumout: | |
357 return False | |
358 heapq.heapify(stubheap) | |
359 heapq.heapify(zeroheap) | |
360 | |
361 modstubs = [(0, 0)] * (maxin + 1) | |
362 # Successively reduce degree sequence by removing the maximum out degree | |
363 while stubheap: | |
364 # Take the first value in the sequence with non-zero in degree | |
365 (freeout, freein) = heapq.heappop(stubheap) | |
366 freein *= -1 | |
367 if freein > len(stubheap) + len(zeroheap): | |
368 return False | |
369 | |
370 # Attach out stubs to the nodes with the most in stubs | |
371 mslen = 0 | |
372 for i in range(freein): | |
373 if zeroheap and (not stubheap or stubheap[0][0] > zeroheap[0]): | |
374 stubout = heapq.heappop(zeroheap) | |
375 stubin = 0 | |
376 else: | |
377 (stubout, stubin) = heapq.heappop(stubheap) | |
378 if stubout == 0: | |
379 return False | |
380 # Check if target is now totally connected | |
381 if stubout + 1 < 0 or stubin < 0: | |
382 modstubs[mslen] = (stubout + 1, stubin) | |
383 mslen += 1 | |
384 | |
385 # Add back the nodes to the heap that still have available stubs | |
386 for i in range(mslen): | |
387 stub = modstubs[i] | |
388 if stub[1] < 0: | |
389 heapq.heappush(stubheap, stub) | |
390 else: | |
391 heapq.heappush(zeroheap, stub[0]) | |
392 if freeout < 0: | |
393 heapq.heappush(zeroheap, freeout) | |
394 return True |