Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/graphical.py: 10%
154 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Test sequences for graphiness.
2"""
3import heapq
5import networkx as nx
7__all__ = [
8 "is_graphical",
9 "is_multigraphical",
10 "is_pseudographical",
11 "is_digraphical",
12 "is_valid_degree_sequence_erdos_gallai",
13 "is_valid_degree_sequence_havel_hakimi",
14]
17@nx._dispatch(graphs=None)
18def is_graphical(sequence, method="eg"):
19 """Returns True if sequence is a valid degree sequence.
21 A degree sequence is valid if some graph can realize it.
23 Parameters
24 ----------
25 sequence : list or iterable container
26 A sequence of integer node degrees
28 method : "eg" | "hh" (default: 'eg')
29 The method used to validate the degree sequence.
30 "eg" corresponds to the Erdős-Gallai algorithm
31 [EG1960]_, [choudum1986]_, and
32 "hh" to the Havel-Hakimi algorithm
33 [havel1955]_, [hakimi1962]_, [CL1996]_.
35 Returns
36 -------
37 valid : bool
38 True if the sequence is a valid degree sequence and False if not.
40 Examples
41 --------
42 >>> G = nx.path_graph(4)
43 >>> sequence = (d for n, d in G.degree())
44 >>> nx.is_graphical(sequence)
45 True
47 To test a non-graphical sequence:
48 >>> sequence_list = [d for n, d in G.degree()]
49 >>> sequence_list[-1] += 1
50 >>> nx.is_graphical(sequence_list)
51 False
53 References
54 ----------
55 .. [EG1960] Erdős and Gallai, Mat. Lapok 11 264, 1960.
56 .. [choudum1986] S.A. Choudum. "A simple proof of the Erdős-Gallai theorem on
57 graph sequences." Bulletin of the Australian Mathematical Society, 33,
58 pp 67-70, 1986. https://doi.org/10.1017/S0004972700002872
59 .. [havel1955] Havel, V. "A Remark on the Existence of Finite Graphs"
60 Casopis Pest. Mat. 80, 477-480, 1955.
61 .. [hakimi1962] Hakimi, S. "On the Realizability of a Set of Integers as
62 Degrees of the Vertices of a Graph." SIAM J. Appl. Math. 10, 496-506, 1962.
63 .. [CL1996] G. Chartrand and L. Lesniak, "Graphs and Digraphs",
64 Chapman and Hall/CRC, 1996.
65 """
66 if method == "eg":
67 valid = is_valid_degree_sequence_erdos_gallai(list(sequence))
68 elif method == "hh":
69 valid = is_valid_degree_sequence_havel_hakimi(list(sequence))
70 else:
71 msg = "`method` must be 'eg' or 'hh'"
72 raise nx.NetworkXException(msg)
73 return valid
76def _basic_graphical_tests(deg_sequence):
77 # Sort and perform some simple tests on the sequence
78 deg_sequence = nx.utils.make_list_of_ints(deg_sequence)
79 p = len(deg_sequence)
80 num_degs = [0] * p
81 dmax, dmin, dsum, n = 0, p, 0, 0
82 for d in deg_sequence:
83 # Reject if degree is negative or larger than the sequence length
84 if d < 0 or d >= p:
85 raise nx.NetworkXUnfeasible
86 # Process only the non-zero integers
87 elif d > 0:
88 dmax, dmin, dsum, n = max(dmax, d), min(dmin, d), dsum + d, n + 1
89 num_degs[d] += 1
90 # Reject sequence if it has odd sum or is oversaturated
91 if dsum % 2 or dsum > n * (n - 1):
92 raise nx.NetworkXUnfeasible
93 return dmax, dmin, dsum, n, num_degs
96@nx._dispatch(graphs=None)
97def is_valid_degree_sequence_havel_hakimi(deg_sequence):
98 r"""Returns True if deg_sequence can be realized by a simple graph.
100 The validation proceeds using the Havel-Hakimi theorem
101 [havel1955]_, [hakimi1962]_, [CL1996]_.
102 Worst-case run time is $O(s)$ where $s$ is the sum of the sequence.
104 Parameters
105 ----------
106 deg_sequence : list
107 A list of integers where each element specifies the degree of a node
108 in a graph.
110 Returns
111 -------
112 valid : bool
113 True if deg_sequence is graphical and False if not.
115 Examples
116 --------
117 >>> G = nx.Graph([(1, 2), (1, 3), (2, 3), (3, 4), (4, 2), (5, 1), (5, 4)])
118 >>> sequence = (d for _, d in G.degree())
119 >>> nx.is_valid_degree_sequence_havel_hakimi(sequence)
120 True
122 To test a non-valid sequence:
123 >>> sequence_list = [d for _, d in G.degree()]
124 >>> sequence_list[-1] += 1
125 >>> nx.is_valid_degree_sequence_havel_hakimi(sequence_list)
126 False
128 Notes
129 -----
130 The ZZ condition says that for the sequence d if
132 .. math::
133 |d| >= \frac{(\max(d) + \min(d) + 1)^2}{4*\min(d)}
135 then d is graphical. This was shown in Theorem 6 in [1]_.
137 References
138 ----------
139 .. [1] I.E. Zverovich and V.E. Zverovich. "Contributions to the theory
140 of graphic sequences", Discrete Mathematics, 105, pp. 292-303 (1992).
141 .. [havel1955] Havel, V. "A Remark on the Existence of Finite Graphs"
142 Casopis Pest. Mat. 80, 477-480, 1955.
143 .. [hakimi1962] Hakimi, S. "On the Realizability of a Set of Integers as
144 Degrees of the Vertices of a Graph." SIAM J. Appl. Math. 10, 496-506, 1962.
145 .. [CL1996] G. Chartrand and L. Lesniak, "Graphs and Digraphs",
146 Chapman and Hall/CRC, 1996.
147 """
148 try:
149 dmax, dmin, dsum, n, num_degs = _basic_graphical_tests(deg_sequence)
150 except nx.NetworkXUnfeasible:
151 return False
152 # Accept if sequence has no non-zero degrees or passes the ZZ condition
153 if n == 0 or 4 * dmin * n >= (dmax + dmin + 1) * (dmax + dmin + 1):
154 return True
156 modstubs = [0] * (dmax + 1)
157 # Successively reduce degree sequence by removing the maximum degree
158 while n > 0:
159 # Retrieve the maximum degree in the sequence
160 while num_degs[dmax] == 0:
161 dmax -= 1
162 # If there are not enough stubs to connect to, then the sequence is
163 # not graphical
164 if dmax > n - 1:
165 return False
167 # Remove largest stub in list
168 num_degs[dmax], n = num_degs[dmax] - 1, n - 1
169 # Reduce the next dmax largest stubs
170 mslen = 0
171 k = dmax
172 for i in range(dmax):
173 while num_degs[k] == 0:
174 k -= 1
175 num_degs[k], n = num_degs[k] - 1, n - 1
176 if k > 1:
177 modstubs[mslen] = k - 1
178 mslen += 1
179 # Add back to the list any non-zero stubs that were removed
180 for i in range(mslen):
181 stub = modstubs[i]
182 num_degs[stub], n = num_degs[stub] + 1, n + 1
183 return True
186@nx._dispatch(graphs=None)
187def is_valid_degree_sequence_erdos_gallai(deg_sequence):
188 r"""Returns True if deg_sequence can be realized by a simple graph.
190 The validation is done using the Erdős-Gallai theorem [EG1960]_.
192 Parameters
193 ----------
194 deg_sequence : list
195 A list of integers
197 Returns
198 -------
199 valid : bool
200 True if deg_sequence is graphical and False if not.
202 Examples
203 --------
204 >>> G = nx.Graph([(1, 2), (1, 3), (2, 3), (3, 4), (4, 2), (5, 1), (5, 4)])
205 >>> sequence = (d for _, d in G.degree())
206 >>> nx.is_valid_degree_sequence_erdos_gallai(sequence)
207 True
209 To test a non-valid sequence:
210 >>> sequence_list = [d for _, d in G.degree()]
211 >>> sequence_list[-1] += 1
212 >>> nx.is_valid_degree_sequence_erdos_gallai(sequence_list)
213 False
215 Notes
216 -----
218 This implementation uses an equivalent form of the Erdős-Gallai criterion.
219 Worst-case run time is $O(n)$ where $n$ is the length of the sequence.
221 Specifically, a sequence d is graphical if and only if the
222 sum of the sequence is even and for all strong indices k in the sequence,
224 .. math::
226 \sum_{i=1}^{k} d_i \leq k(k-1) + \sum_{j=k+1}^{n} \min(d_i,k)
227 = k(n-1) - ( k \sum_{j=0}^{k-1} n_j - \sum_{j=0}^{k-1} j n_j )
229 A strong index k is any index where d_k >= k and the value n_j is the
230 number of occurrences of j in d. The maximal strong index is called the
231 Durfee index.
233 This particular rearrangement comes from the proof of Theorem 3 in [2]_.
235 The ZZ condition says that for the sequence d if
237 .. math::
238 |d| >= \frac{(\max(d) + \min(d) + 1)^2}{4*\min(d)}
240 then d is graphical. This was shown in Theorem 6 in [2]_.
242 References
243 ----------
244 .. [1] A. Tripathi and S. Vijay. "A note on a theorem of Erdős & Gallai",
245 Discrete Mathematics, 265, pp. 417-420 (2003).
246 .. [2] I.E. Zverovich and V.E. Zverovich. "Contributions to the theory
247 of graphic sequences", Discrete Mathematics, 105, pp. 292-303 (1992).
248 .. [EG1960] Erdős and Gallai, Mat. Lapok 11 264, 1960.
249 """
250 try:
251 dmax, dmin, dsum, n, num_degs = _basic_graphical_tests(deg_sequence)
252 except nx.NetworkXUnfeasible:
253 return False
254 # Accept if sequence has no non-zero degrees or passes the ZZ condition
255 if n == 0 or 4 * dmin * n >= (dmax + dmin + 1) * (dmax + dmin + 1):
256 return True
258 # Perform the EG checks using the reformulation of Zverovich and Zverovich
259 k, sum_deg, sum_nj, sum_jnj = 0, 0, 0, 0
260 for dk in range(dmax, dmin - 1, -1):
261 if dk < k + 1: # Check if already past Durfee index
262 return True
263 if num_degs[dk] > 0:
264 run_size = num_degs[dk] # Process a run of identical-valued degrees
265 if dk < k + run_size: # Check if end of run is past Durfee index
266 run_size = dk - k # Adjust back to Durfee index
267 sum_deg += run_size * dk
268 for v in range(run_size):
269 sum_nj += num_degs[k + v]
270 sum_jnj += (k + v) * num_degs[k + v]
271 k += run_size
272 if sum_deg > k * (n - 1) - k * sum_nj + sum_jnj:
273 return False
274 return True
277@nx._dispatch(graphs=None)
278def is_multigraphical(sequence):
279 """Returns True if some multigraph can realize the sequence.
281 Parameters
282 ----------
283 sequence : list
284 A list of integers
286 Returns
287 -------
288 valid : bool
289 True if deg_sequence is a multigraphic degree sequence and False if not.
291 Examples
292 --------
293 >>> G = nx.MultiGraph([(1, 2), (1, 3), (2, 3), (3, 4), (4, 2), (5, 1), (5, 4)])
294 >>> sequence = (d for _, d in G.degree())
295 >>> nx.is_multigraphical(sequence)
296 True
298 To test a non-multigraphical sequence:
299 >>> sequence_list = [d for _, d in G.degree()]
300 >>> sequence_list[-1] += 1
301 >>> nx.is_multigraphical(sequence_list)
302 False
304 Notes
305 -----
306 The worst-case run time is $O(n)$ where $n$ is the length of the sequence.
308 References
309 ----------
310 .. [1] S. L. Hakimi. "On the realizability of a set of integers as
311 degrees of the vertices of a linear graph", J. SIAM, 10, pp. 496-506
312 (1962).
313 """
314 try:
315 deg_sequence = nx.utils.make_list_of_ints(sequence)
316 except nx.NetworkXError:
317 return False
318 dsum, dmax = 0, 0
319 for d in deg_sequence:
320 if d < 0:
321 return False
322 dsum, dmax = dsum + d, max(dmax, d)
323 if dsum % 2 or dsum < 2 * dmax:
324 return False
325 return True
328@nx._dispatch(graphs=None)
329def is_pseudographical(sequence):
330 """Returns True if some pseudograph can realize the sequence.
332 Every nonnegative integer sequence with an even sum is pseudographical
333 (see [1]_).
335 Parameters
336 ----------
337 sequence : list or iterable container
338 A sequence of integer node degrees
340 Returns
341 -------
342 valid : bool
343 True if the sequence is a pseudographic degree sequence and False if not.
345 Examples
346 --------
347 >>> G = nx.Graph([(1, 2), (1, 3), (2, 3), (3, 4), (4, 2), (5, 1), (5, 4)])
348 >>> sequence = (d for _, d in G.degree())
349 >>> nx.is_pseudographical(sequence)
350 True
352 To test a non-pseudographical sequence:
353 >>> sequence_list = [d for _, d in G.degree()]
354 >>> sequence_list[-1] += 1
355 >>> nx.is_pseudographical(sequence_list)
356 False
358 Notes
359 -----
360 The worst-case run time is $O(n)$ where n is the length of the sequence.
362 References
363 ----------
364 .. [1] F. Boesch and F. Harary. "Line removal algorithms for graphs
365 and their degree lists", IEEE Trans. Circuits and Systems, CAS-23(12),
366 pp. 778-782 (1976).
367 """
368 try:
369 deg_sequence = nx.utils.make_list_of_ints(sequence)
370 except nx.NetworkXError:
371 return False
372 return sum(deg_sequence) % 2 == 0 and min(deg_sequence) >= 0
375@nx._dispatch(graphs=None)
376def is_digraphical(in_sequence, out_sequence):
377 r"""Returns True if some directed graph can realize the in- and out-degree
378 sequences.
380 Parameters
381 ----------
382 in_sequence : list or iterable container
383 A sequence of integer node in-degrees
385 out_sequence : list or iterable container
386 A sequence of integer node out-degrees
388 Returns
389 -------
390 valid : bool
391 True if in and out-sequences are digraphic False if not.
393 Examples
394 --------
395 >>> G = nx.DiGraph([(1, 2), (1, 3), (2, 3), (3, 4), (4, 2), (5, 1), (5, 4)])
396 >>> in_seq = (d for n, d in G.in_degree())
397 >>> out_seq = (d for n, d in G.out_degree())
398 >>> nx.is_digraphical(in_seq, out_seq)
399 True
401 To test a non-digraphical scenario:
402 >>> in_seq_list = [d for n, d in G.in_degree()]
403 >>> in_seq_list[-1] += 1
404 >>> nx.is_digraphical(in_seq_list, out_seq)
405 False
407 Notes
408 -----
409 This algorithm is from Kleitman and Wang [1]_.
410 The worst case runtime is $O(s \times \log n)$ where $s$ and $n$ are the
411 sum and length of the sequences respectively.
413 References
414 ----------
415 .. [1] D.J. Kleitman and D.L. Wang
416 Algorithms for Constructing Graphs and Digraphs with Given Valences
417 and Factors, Discrete Mathematics, 6(1), pp. 79-88 (1973)
418 """
419 try:
420 in_deg_sequence = nx.utils.make_list_of_ints(in_sequence)
421 out_deg_sequence = nx.utils.make_list_of_ints(out_sequence)
422 except nx.NetworkXError:
423 return False
424 # Process the sequences and form two heaps to store degree pairs with
425 # either zero or non-zero out degrees
426 sumin, sumout, nin, nout = 0, 0, len(in_deg_sequence), len(out_deg_sequence)
427 maxn = max(nin, nout)
428 maxin = 0
429 if maxn == 0:
430 return True
431 stubheap, zeroheap = [], []
432 for n in range(maxn):
433 in_deg, out_deg = 0, 0
434 if n < nout:
435 out_deg = out_deg_sequence[n]
436 if n < nin:
437 in_deg = in_deg_sequence[n]
438 if in_deg < 0 or out_deg < 0:
439 return False
440 sumin, sumout, maxin = sumin + in_deg, sumout + out_deg, max(maxin, in_deg)
441 if in_deg > 0:
442 stubheap.append((-1 * out_deg, -1 * in_deg))
443 elif out_deg > 0:
444 zeroheap.append(-1 * out_deg)
445 if sumin != sumout:
446 return False
447 heapq.heapify(stubheap)
448 heapq.heapify(zeroheap)
450 modstubs = [(0, 0)] * (maxin + 1)
451 # Successively reduce degree sequence by removing the maximum out degree
452 while stubheap:
453 # Take the first value in the sequence with non-zero in degree
454 (freeout, freein) = heapq.heappop(stubheap)
455 freein *= -1
456 if freein > len(stubheap) + len(zeroheap):
457 return False
459 # Attach out stubs to the nodes with the most in stubs
460 mslen = 0
461 for i in range(freein):
462 if zeroheap and (not stubheap or stubheap[0][0] > zeroheap[0]):
463 stubout = heapq.heappop(zeroheap)
464 stubin = 0
465 else:
466 (stubout, stubin) = heapq.heappop(stubheap)
467 if stubout == 0:
468 return False
469 # Check if target is now totally connected
470 if stubout + 1 < 0 or stubin < 0:
471 modstubs[mslen] = (stubout + 1, stubin)
472 mslen += 1
474 # Add back the nodes to the heap that still have available stubs
475 for i in range(mslen):
476 stub = modstubs[i]
477 if stub[1] < 0:
478 heapq.heappush(stubheap, stub)
479 else:
480 heapq.heappush(zeroheap, stub[0])
481 if freeout < 0:
482 heapq.heappush(zeroheap, freeout)
483 return True