Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / graphical.py @ 5cef0f13

History | View | Annotate | Download (13.1 KB)

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
    if not nx.utils.is_list_of_ints(deg_sequence):
76
        # check for a type that can be converted to int. Like numpy.int64
77
        ds = []
78
        for d in deg_sequence:
79
            try:
80
                intd = int(d)
81
            except ValueError:
82
                raise nx.NetworkXError("Invalid type in deg_sequence: not an integer")
83
            if intd != d:
84
                raise nx.NetworkXError("Invalid type in deg_sequence: not an integer")
85
            ds.append(intd)
86
        deg_sequence = ds
87
    p = len(deg_sequence)
88
    num_degs = [0] * p
89
    dmax, dmin, dsum, n = 0, p, 0, 0
90
    for d in deg_sequence:
91
        # Reject if degree is negative or larger than the sequence length
92
        if d < 0 or d >= p:
93
            raise nx.NetworkXUnfeasible
94
        # Process only the non-zero integers
95
        elif d > 0:
96
            dmax, dmin, dsum, n = max(dmax, d), min(dmin, d), dsum + d, n + 1
97
            num_degs[d] += 1
98
    # Reject sequence if it has odd sum or is oversaturated
99
    if dsum % 2 or dsum > n * (n - 1):
100
        raise nx.NetworkXUnfeasible
101
    return dmax, dmin, dsum, n, num_degs
102

    
103

    
104
def is_valid_degree_sequence_havel_hakimi(deg_sequence):
105
    r"""Returns True if deg_sequence can be realized by a simple graph.
106

107
    The validation proceeds using the Havel-Hakimi theorem.
108
    Worst-case run time is $O(s)$ where $s$ is the sum of the sequence.
109

110
    Parameters
111
    ----------
112
    deg_sequence : list
113
        A list of integers where each element specifies the degree of a node
114
        in a graph.
115

116
    Returns
117
    -------
118
    valid : bool
119
        True if deg_sequence is graphical and False if not.
120

121
    Notes
122
    -----
123
    The ZZ condition says that for the sequence d if
124

125
    .. math::
126
        |d| >= \frac{(\max(d) + \min(d) + 1)^2}{4*\min(d)}
127

128
    then d is graphical.  This was shown in Theorem 6 in [1]_.
129

130
    References
131
    ----------
132
    .. [1] I.E. Zverovich and V.E. Zverovich. "Contributions to the theory
133
       of graphic sequences", Discrete Mathematics, 105, pp. 292-303 (1992).
134

135
    [havel1955]_, [hakimi1962]_, [CL1996]_
136

137
    """
138
    try:
139
        dmax, dmin, dsum, n, num_degs = _basic_graphical_tests(deg_sequence)
140
    except nx.NetworkXUnfeasible:
141
        return False
142
    # Accept if sequence has no non-zero degrees or passes the ZZ condition
143
    if n == 0 or 4 * dmin * n >= (dmax + dmin + 1) * (dmax + dmin + 1):
144
        return True
145

    
146
    modstubs = [0] * (dmax + 1)
147
    # Successively reduce degree sequence by removing the maximum degree
148
    while n > 0:
149
        # Retrieve the maximum degree in the sequence
150
        while num_degs[dmax] == 0:
151
            dmax -= 1
152
        # If there are not enough stubs to connect to, then the sequence is
153
        # not graphical
154
        if dmax > n - 1:
155
            return False
156

    
157
        # Remove largest stub in list
158
        num_degs[dmax], n = num_degs[dmax] - 1, n - 1
159
        # Reduce the next dmax largest stubs
160
        mslen = 0
161
        k = dmax
162
        for i in range(dmax):
163
            while num_degs[k] == 0:
164
                k -= 1
165
            num_degs[k], n = num_degs[k] - 1, n - 1
166
            if k > 1:
167
                modstubs[mslen] = k - 1
168
                mslen += 1
169
        # Add back to the list any non-zero stubs that were removed
170
        for i in range(mslen):
171
            stub = modstubs[i]
172
            num_degs[stub], n = num_degs[stub] + 1, n + 1
173
    return True
174

    
175

    
176
def is_valid_degree_sequence_erdos_gallai(deg_sequence):
177
    r"""Returns True if deg_sequence can be realized by a simple graph.
178

179
    The validation is done using the Erdős-Gallai theorem [EG1960]_.
180

181
    Parameters
182
    ----------
183
    deg_sequence : list
184
        A list of integers
185

186
    Returns
187
    -------
188
    valid : bool
189
        True if deg_sequence is graphical and False if not.
190

191
    Notes
192
    -----
193

194
    This implementation uses an equivalent form of the Erdős-Gallai criterion.
195
    Worst-case run time is $O(n)$ where $n$ is the length of the sequence.
196

197
    Specifically, a sequence d is graphical if and only if the
198
    sum of the sequence is even and for all strong indices k in the sequence,
199

200
     .. math::
201

202
       \sum_{i=1}^{k} d_i \leq k(k-1) + \sum_{j=k+1}^{n} \min(d_i,k)
203
             = k(n-1) - ( k \sum_{j=0}^{k-1} n_j - \sum_{j=0}^{k-1} j n_j )
204

205
    A strong index k is any index where d_k >= k and the value n_j is the
206
    number of occurrences of j in d.  The maximal strong index is called the
207
    Durfee index.
208

209
    This particular rearrangement comes from the proof of Theorem 3 in [2]_.
210

211
    The ZZ condition says that for the sequence d if
212

213
    .. math::
214
        |d| >= \frac{(\max(d) + \min(d) + 1)^2}{4*\min(d)}
215

216
    then d is graphical.  This was shown in Theorem 6 in [2]_.
217

218
    References
219
    ----------
220
    .. [1] A. Tripathi and S. Vijay. "A note on a theorem of Erdős & Gallai",
221
       Discrete Mathematics, 265, pp. 417-420 (2003).
222
    .. [2] I.E. Zverovich and V.E. Zverovich. "Contributions to the theory
223
       of graphic sequences", Discrete Mathematics, 105, pp. 292-303 (1992).
224

225
    [EG1960]_, [choudum1986]_
226
    """
227
    try:
228
        dmax, dmin, dsum, n, num_degs = _basic_graphical_tests(deg_sequence)
229
    except nx.NetworkXUnfeasible:
230
        return False
231
    # Accept if sequence has no non-zero degrees or passes the ZZ condition
232
    if n == 0 or 4 * dmin * n >= (dmax + dmin + 1) * (dmax + dmin + 1):
233
        return True
234

    
235
    # Perform the EG checks using the reformulation of Zverovich and Zverovich
236
    k, sum_deg, sum_nj, sum_jnj = 0, 0, 0, 0
237
    for dk in range(dmax, dmin - 1, -1):
238
        if dk < k + 1:            # Check if already past Durfee index
239
            return True
240
        if num_degs[dk] > 0:
241
            run_size = num_degs[dk]  # Process a run of identical-valued degrees
242
            if dk < k + run_size:     # Check if end of run is past Durfee index
243
                run_size = dk - k     # Adjust back to Durfee index
244
            sum_deg += run_size * dk
245
            for v in range(run_size):
246
                sum_nj += num_degs[k + v]
247
                sum_jnj += (k + v) * num_degs[k + v]
248
            k += run_size
249
            if sum_deg > k * (n - 1) - k * sum_nj + sum_jnj:
250
                return False
251
    return True
252

    
253

    
254
def is_multigraphical(sequence):
255
    """Returns True if some multigraph can realize the sequence.
256

257
    Parameters
258
    ----------
259
    sequence : list
260
        A list of integers
261

262
    Returns
263
    -------
264
    valid : bool
265
        True if deg_sequence is a multigraphic degree sequence and False if not.
266

267
    Notes
268
    -----
269
    The worst-case run time is $O(n)$ where $n$ is the length of the sequence.
270

271
    References
272
    ----------
273
    .. [1] S. L. Hakimi. "On the realizability of a set of integers as
274
       degrees of the vertices of a linear graph", J. SIAM, 10, pp. 496-506
275
       (1962).
276
    """
277
    deg_sequence = list(sequence)
278
    if not nx.utils.is_list_of_ints(deg_sequence):
279
        return False
280
    dsum, dmax = 0, 0
281
    for d in deg_sequence:
282
        if d < 0:
283
            return False
284
        dsum, dmax = dsum + d, max(dmax, d)
285
    if dsum % 2 or dsum < 2 * dmax:
286
        return False
287
    return True
288

    
289

    
290
def is_pseudographical(sequence):
291
    """Returns True if some pseudograph can realize the sequence.
292

293
    Every nonnegative integer sequence with an even sum is pseudographical
294
    (see [1]_).
295

296
    Parameters
297
    ----------
298
    sequence : list or iterable container
299
        A sequence of integer node degrees
300

301
    Returns
302
    -------
303
    valid : bool
304
      True if the sequence is a pseudographic degree sequence and False if not.
305

306
    Notes
307
    -----
308
    The worst-case run time is $O(n)$ where n is the length of the sequence.
309

310
    References
311
    ----------
312
    .. [1] F. Boesch and F. Harary. "Line removal algorithms for graphs
313
       and their degree lists", IEEE Trans. Circuits and Systems, CAS-23(12),
314
       pp. 778-782 (1976).
315
    """
316
    s = list(sequence)
317
    if not nx.utils.is_list_of_ints(s):
318
        return False
319
    return sum(s) % 2 == 0 and min(s) >= 0
320

    
321

    
322
def is_digraphical(in_sequence, out_sequence):
323
    r"""Returns True if some directed graph can realize the in- and out-degree
324
    sequences.
325

326
    Parameters
327
    ----------
328
    in_sequence : list or iterable container
329
        A sequence of integer node in-degrees
330

331
    out_sequence : list or iterable container
332
        A sequence of integer node out-degrees
333

334
    Returns
335
    -------
336
    valid : bool
337
      True if in and out-sequences are digraphic False if not.
338

339
    Notes
340
    -----
341
    This algorithm is from Kleitman and Wang [1]_.
342
    The worst case runtime is $O(s \times \log n)$ where $s$ and $n$ are the
343
    sum and length of the sequences respectively.
344

345
    References
346
    ----------
347
    .. [1] D.J. Kleitman and D.L. Wang
348
       Algorithms for Constructing Graphs and Digraphs with Given Valences
349
       and Factors, Discrete Mathematics, 6(1), pp. 79-88 (1973)
350
    """
351
    in_deg_sequence = list(in_sequence)
352
    out_deg_sequence = list(out_sequence)
353
    if not nx.utils.is_list_of_ints(in_deg_sequence):
354
        return False
355
    if not nx.utils.is_list_of_ints(out_deg_sequence):
356
        return False
357
    # Process the sequences and form two heaps to store degree pairs with
358
    # either zero or non-zero out degrees
359
    sumin, sumout, nin, nout = 0, 0, len(in_deg_sequence), len(out_deg_sequence)
360
    maxn = max(nin, nout)
361
    maxin = 0
362
    if maxn == 0:
363
        return True
364
    stubheap, zeroheap = [], []
365
    for n in range(maxn):
366
        in_deg, out_deg = 0, 0
367
        if n < nout:
368
            out_deg = out_deg_sequence[n]
369
        if n < nin:
370
            in_deg = in_deg_sequence[n]
371
        if in_deg < 0 or out_deg < 0:
372
            return False
373
        sumin, sumout, maxin = sumin + in_deg, sumout + out_deg, max(maxin, in_deg)
374
        if in_deg > 0:
375
            stubheap.append((-1 * out_deg, -1 * in_deg))
376
        elif out_deg > 0:
377
            zeroheap.append(-1 * out_deg)
378
    if sumin != sumout:
379
        return False
380
    heapq.heapify(stubheap)
381
    heapq.heapify(zeroheap)
382

    
383
    modstubs = [(0, 0)] * (maxin + 1)
384
    # Successively reduce degree sequence by removing the maximum out degree
385
    while stubheap:
386
        # Take the first value in the sequence with non-zero in degree
387
        (freeout, freein) = heapq.heappop(stubheap)
388
        freein *= -1
389
        if freein > len(stubheap) + len(zeroheap):
390
            return False
391

    
392
        # Attach out stubs to the nodes with the most in stubs
393
        mslen = 0
394
        for i in range(freein):
395
            if zeroheap and (not stubheap or stubheap[0][0] > zeroheap[0]):
396
                stubout = heapq.heappop(zeroheap)
397
                stubin = 0
398
            else:
399
                (stubout, stubin) = heapq.heappop(stubheap)
400
            if stubout == 0:
401
                return False
402
            # Check if target is now totally connected
403
            if stubout + 1 < 0 or stubin < 0:
404
                modstubs[mslen] = (stubout + 1, stubin)
405
                mslen += 1
406

    
407
        # Add back the nodes to the heap that still have available stubs
408
        for i in range(mslen):
409
            stub = modstubs[i]
410
            if stub[1] < 0:
411
                heapq.heappush(stubheap, stub)
412
            else:
413
                heapq.heappush(zeroheap, stub[0])
414
        if freeout < 0:
415
            heapq.heappush(zeroheap, freeout)
416
    return True