Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/graphical.py @ 1:56ad4e20f292 draft

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