Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / generators / degree_seq.py @ 5cef0f13

History | View | Annotate | Download (29.9 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2004-2019 by
3
#    Aric Hagberg <hagberg@lanl.gov>
4
#    Dan Schult <dschult@colgate.edu>
5
#    Pieter Swart <swart@lanl.gov>
6
#    All rights reserved.
7
#    BSD license.
8
#
9
# Authors: Aric Hagberg (aric.hagberg@gmail.com)
10
#          Pieter Swart (swart@lanl.gov)
11
#          Dan Schult (dschult@colgate.edu)
12
#          Joel Miller (joel.c.miller.research@gmail.com)
13
#          Nathan Lemons (nlemons@gmail.com)
14
#          Brian Cloteaux (brian.cloteaux@nist.gov)
15
"""Generate graphs with a given degree sequence or expected degree sequence.
16
"""
17
from __future__ import division
18

    
19
import heapq
20
from itertools import chain
21
from itertools import combinations
22
# In Python 3, the function is `zip_longest`, in Python 2 `izip_longest`.
23
try:
24
    from itertools import zip_longest
25
except ImportError:
26
    from itertools import izip_longest as zip_longest
27
import math
28
from operator import itemgetter
29

    
30
import networkx as nx
31
from networkx.utils import random_weighted_sample, py_random_state
32

    
33
__all__ = ['configuration_model',
34
           'directed_configuration_model',
35
           'expected_degree_graph',
36
           'havel_hakimi_graph',
37
           'directed_havel_hakimi_graph',
38
           'degree_sequence_tree',
39
           'random_degree_sequence_graph']
40

    
41
chaini = chain.from_iterable
42

    
43

    
44
def _to_stublist(degree_sequence):
45
    """Returns a list of degree-repeated node numbers.
46

47
    ``degree_sequence`` is a list of nonnegative integers representing
48
    the degrees of nodes in a graph.
49

50
    This function returns a list of node numbers with multiplicities
51
    according to the given degree sequence. For example, if the first
52
    element of ``degree_sequence`` is ``3``, then the first node number,
53
    ``0``, will appear at the head of the returned list three times. The
54
    node numbers are assumed to be the numbers zero through
55
    ``len(degree_sequence) - 1``.
56

57
    Examples
58
    --------
59

60
    >>> degree_sequence = [1, 2, 3]
61
    >>> _to_stublist(degree_sequence)
62
    [0, 1, 1, 2, 2, 2]
63

64
    If a zero appears in the sequence, that means the node exists but
65
    has degree zero, so that number will be skipped in the returned
66
    list::
67

68
    >>> degree_sequence = [2, 0, 1]
69
    >>> _to_stublist(degree_sequence)
70
    [0, 0, 2]
71

72
    """
73
    return list(chaini([n] * d for n, d in enumerate(degree_sequence)))
74

    
75

    
76
def _configuration_model(deg_sequence, create_using, directed=False,
77
                         in_deg_sequence=None, seed=None):
78
    """Helper function for generating either undirected or directed
79
    configuration model graphs.
80

81
    ``deg_sequence`` is a list of nonnegative integers representing the
82
    degree of the node whose label is the index of the list element.
83

84
    ``create_using`` see :func:`~networkx.empty_graph`.
85

86
    ``directed`` and ``in_deg_sequence`` are required if you want the
87
    returned graph to be generated using the directed configuration
88
    model algorithm. If ``directed`` is ``False``, then ``deg_sequence``
89
    is interpreted as the degree sequence of an undirected graph and
90
    ``in_deg_sequence`` is ignored. Otherwise, if ``directed`` is
91
    ``True``, then ``deg_sequence`` is interpreted as the out-degree
92
    sequence and ``in_deg_sequence`` as the in-degree sequence of a
93
    directed graph.
94

95
    .. note::
96

97
       ``deg_sequence`` and ``in_deg_sequence`` need not be the same
98
       length.
99

100
    ``seed`` is a random.Random or numpy.random.RandomState instance
101

102
    This function returns a graph, directed if and only if ``directed``
103
    is ``True``, generated according to the configuration model
104
    algorithm. For more information on the algorithm, see the
105
    :func:`configuration_model` or :func:`directed_configuration_model`
106
    functions.
107

108
    """
109
    n = len(deg_sequence)
110
    G = nx.empty_graph(n, create_using)
111
    # If empty, return the null graph immediately.
112
    if n == 0:
113
        return G
114
    # Build a list of available degree-repeated nodes.  For example,
115
    # for degree sequence [3, 2, 1, 1, 1], the "stub list" is
116
    # initially [0, 0, 0, 1, 1, 2, 3, 4], that is, node 0 has degree
117
    # 3 and thus is repeated 3 times, etc.
118
    #
119
    # Also, shuffle the stub list in order to get a random sequence of
120
    # node pairs.
121
    if directed:
122
        pairs = zip_longest(deg_sequence, in_deg_sequence, fillvalue=0)
123
        # Unzip the list of pairs into a pair of lists.
124
        out_deg, in_deg = zip(*pairs)
125

    
126
        out_stublist = _to_stublist(out_deg)
127
        in_stublist = _to_stublist(in_deg)
128

    
129
        seed.shuffle(out_stublist)
130
        seed.shuffle(in_stublist)
131
    else:
132
        stublist = _to_stublist(deg_sequence)
133
        # Choose a random balanced bipartition of the stublist, which
134
        # gives a random pairing of nodes. In this implementation, we
135
        # shuffle the list and then split it in half.
136
        n = len(stublist)
137
        half = n // 2
138
        seed.shuffle(stublist)
139
        out_stublist, in_stublist = stublist[:half], stublist[half:]
140
    G.add_edges_from(zip(out_stublist, in_stublist))
141
    return G
142

    
143

    
144
@py_random_state(2)
145
def configuration_model(deg_sequence, create_using=None, seed=None):
146
    """Returns a random graph with the given degree sequence.
147

148
    The configuration model generates a random pseudograph (graph with
149
    parallel edges and self loops) by randomly assigning edges to
150
    match the given degree sequence.
151

152
    Parameters
153
    ----------
154
    deg_sequence :  list of nonnegative integers
155
        Each list entry corresponds to the degree of a node.
156
    create_using : NetworkX graph constructor, optional (default MultiGraph)
157
        Graph type to create. If graph instance, then cleared before populated.
158
    seed : integer, random_state, or None (default)
159
        Indicator of random number generation state.
160
        See :ref:`Randomness<randomness>`.
161

162
    Returns
163
    -------
164
    G : MultiGraph
165
        A graph with the specified degree sequence.
166
        Nodes are labeled starting at 0 with an index
167
        corresponding to the position in deg_sequence.
168

169
    Raises
170
    ------
171
    NetworkXError
172
        If the degree sequence does not have an even sum.
173

174
    See Also
175
    --------
176
    is_graphical
177

178
    Notes
179
    -----
180
    As described by Newman [1]_.
181

182
    A non-graphical degree sequence (not realizable by some simple
183
    graph) is allowed since this function returns graphs with self
184
    loops and parallel edges.  An exception is raised if the degree
185
    sequence does not have an even sum.
186

187
    This configuration model construction process can lead to
188
    duplicate edges and loops.  You can remove the self-loops and
189
    parallel edges (see below) which will likely result in a graph
190
    that doesn't have the exact degree sequence specified.
191

192
    The density of self-loops and parallel edges tends to decrease as
193
    the number of nodes increases. However, typically the number of
194
    self-loops will approach a Poisson distribution with a nonzero mean,
195
    and similarly for the number of parallel edges.  Consider a node
196
    with *k* stubs. The probability of being joined to another stub of
197
    the same node is basically (*k* - *1*) / *N*, where *k* is the
198
    degree and *N* is the number of nodes. So the probability of a
199
    self-loop scales like *c* / *N* for some constant *c*. As *N* grows,
200
    this means we expect *c* self-loops. Similarly for parallel edges.
201

202
    References
203
    ----------
204
    .. [1] M.E.J. Newman, "The structure and function of complex networks",
205
       SIAM REVIEW 45-2, pp 167-256, 2003.
206

207
    Examples
208
    --------
209
    You can create a degree sequence following a particular distribution
210
    by using the one of the distribution functions in
211
    :mod:`~networkx.utils.random_sequence` (or one of your own). For
212
    example, to create an undirected multigraph on one hundred nodes
213
    with degree sequence chosen from the power law distribution:
214

215
    >>> sequence = nx.random_powerlaw_tree_sequence(100, tries=5000)
216
    >>> G = nx.configuration_model(sequence)
217
    >>> len(G)
218
    100
219
    >>> actual_degrees = [d for v, d in G.degree()]
220
    >>> actual_degrees == sequence
221
    True
222

223
    The returned graph is a multigraph, which may have parallel
224
    edges. To remove any parallel edges from the returned graph:
225

226
    >>> G = nx.Graph(G)
227

228
    Similarly, to remove self-loops:
229

230
    >>> G.remove_edges_from(nx.selfloop_edges(G))
231

232
    """
233
    if sum(deg_sequence) % 2 != 0:
234
        msg = 'Invalid degree sequence: sum of degrees must be even, not odd'
235
        raise nx.NetworkXError(msg)
236

    
237
    G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
238
    if G.is_directed():
239
        raise nx.NetworkXNotImplemented('not implemented for directed graphs')
240

    
241
    G = _configuration_model(deg_sequence, G, seed=seed)
242

    
243
    return G
244

    
245

    
246
@py_random_state(3)
247
def directed_configuration_model(in_degree_sequence,
248
                                 out_degree_sequence,
249
                                 create_using=None, seed=None):
250
    """Returns a directed_random graph with the given degree sequences.
251

252
    The configuration model generates a random directed pseudograph
253
    (graph with parallel edges and self loops) by randomly assigning
254
    edges to match the given degree sequences.
255

256
    Parameters
257
    ----------
258
    in_degree_sequence :  list of nonnegative integers
259
       Each list entry corresponds to the in-degree of a node.
260
    out_degree_sequence :  list of nonnegative integers
261
       Each list entry corresponds to the out-degree of a node.
262
    create_using : NetworkX graph constructor, optional (default MultiDiGraph)
263
        Graph type to create. If graph instance, then cleared before populated.
264
    seed : integer, random_state, or None (default)
265
        Indicator of random number generation state.
266
        See :ref:`Randomness<randomness>`.
267

268
    Returns
269
    -------
270
    G : MultiDiGraph
271
        A graph with the specified degree sequences.
272
        Nodes are labeled starting at 0 with an index
273
        corresponding to the position in deg_sequence.
274

275
    Raises
276
    ------
277
    NetworkXError
278
        If the degree sequences do not have the same sum.
279

280
    See Also
281
    --------
282
    configuration_model
283

284
    Notes
285
    -----
286
    Algorithm as described by Newman [1]_.
287

288
    A non-graphical degree sequence (not realizable by some simple
289
    graph) is allowed since this function returns graphs with self
290
    loops and parallel edges.  An exception is raised if the degree
291
    sequences does not have the same sum.
292

293
    This configuration model construction process can lead to
294
    duplicate edges and loops.  You can remove the self-loops and
295
    parallel edges (see below) which will likely result in a graph
296
    that doesn't have the exact degree sequence specified.  This
297
    "finite-size effect" decreases as the size of the graph increases.
298

299
    References
300
    ----------
301
    .. [1] Newman, M. E. J. and Strogatz, S. H. and Watts, D. J.
302
       Random graphs with arbitrary degree distributions and their applications
303
       Phys. Rev. E, 64, 026118 (2001)
304

305
    Examples
306
    --------
307
    One can modify the in- and out-degree sequences from an existing
308
    directed graph in order to create a new directed graph. For example,
309
    here we modify the directed path graph:
310

311
    >>> D = nx.DiGraph([(0, 1), (1, 2), (2, 3)])
312
    >>> din = list(d for n, d in D.in_degree())
313
    >>> dout = list(d for n, d in D.out_degree())
314
    >>> din.append(1)
315
    >>> dout[0] = 2
316
    >>> # We now expect an edge from node 0 to a new node, node 3.
317
    ... D = nx.directed_configuration_model(din, dout)
318

319
    The returned graph is a directed multigraph, which may have parallel
320
    edges. To remove any parallel edges from the returned graph:
321

322
    >>> D = nx.DiGraph(D)
323

324
    Similarly, to remove self-loops:
325

326
    >>> D.remove_edges_from(nx.selfloop_edges(D))
327

328
    """
329
    if sum(in_degree_sequence) != sum(out_degree_sequence):
330
        msg = 'Invalid degree sequences: sequences must have equal sums'
331
        raise nx.NetworkXError(msg)
332

    
333
    if create_using is None:
334
        create_using = nx.MultiDiGraph
335

    
336
    G = _configuration_model(out_degree_sequence, create_using, directed=True,
337
                             in_deg_sequence=in_degree_sequence, seed=seed)
338

    
339
    name = "directed configuration_model {} nodes {} edges"
340
    return G
341

    
342

    
343
@py_random_state(1)
344
def expected_degree_graph(w, seed=None, selfloops=True):
345
    r"""Returns a random graph with given expected degrees.
346

347
    Given a sequence of expected degrees $W=(w_0,w_1,\ldots,w_{n-1})$
348
    of length $n$ this algorithm assigns an edge between node $u$ and
349
    node $v$ with probability
350

351
    .. math::
352

353
       p_{uv} = \frac{w_u w_v}{\sum_k w_k} .
354

355
    Parameters
356
    ----------
357
    w : list
358
        The list of expected degrees.
359
    selfloops: bool (default=True)
360
        Set to False to remove the possibility of self-loop edges.
361
    seed : integer, random_state, or None (default)
362
        Indicator of random number generation state.
363
        See :ref:`Randomness<randomness>`.
364

365
    Returns
366
    -------
367
    Graph
368

369
    Examples
370
    --------
371
    >>> z=[10 for i in range(100)]
372
    >>> G=nx.expected_degree_graph(z)
373

374
    Notes
375
    -----
376
    The nodes have integer labels corresponding to index of expected degrees
377
    input sequence.
378

379
    The complexity of this algorithm is $\mathcal{O}(n+m)$ where $n$ is the
380
    number of nodes and $m$ is the expected number of edges.
381

382
    The model in [1]_ includes the possibility of self-loop edges.
383
    Set selfloops=False to produce a graph without self loops.
384

385
    For finite graphs this model doesn't produce exactly the given
386
    expected degree sequence.  Instead the expected degrees are as
387
    follows.
388

389
    For the case without self loops (selfloops=False),
390

391
    .. math::
392

393
       E[deg(u)] = \sum_{v \ne u} p_{uv}
394
                = w_u \left( 1 - \frac{w_u}{\sum_k w_k} \right) .
395

396

397
    NetworkX uses the standard convention that a self-loop edge counts 2
398
    in the degree of a node, so with self loops (selfloops=True),
399

400
    .. math::
401

402
       E[deg(u)] =  \sum_{v \ne u} p_{uv}  + 2 p_{uu}
403
                = w_u \left( 1 + \frac{w_u}{\sum_k w_k} \right) .
404

405
    References
406
    ----------
407
    .. [1] Fan Chung and L. Lu, Connected components in random graphs with
408
       given expected degree sequences, Ann. Combinatorics, 6,
409
       pp. 125-145, 2002.
410
    .. [2] Joel Miller and Aric Hagberg,
411
       Efficient generation of networks with given expected degrees,
412
       in Algorithms and Models for the Web-Graph (WAW 2011),
413
       Alan Frieze, Paul Horn, and Paweł Prałat (Eds), LNCS 6732,
414
       pp. 115-126, 2011.
415
    """
416
    n = len(w)
417
    G = nx.empty_graph(n)
418

    
419
    # If there are no nodes are no edges in the graph, return the empty graph.
420
    if n == 0 or max(w) == 0:
421
        return G
422

    
423
    rho = 1 / sum(w)
424
    # Sort the weights in decreasing order. The original order of the
425
    # weights dictates the order of the (integer) node labels, so we
426
    # need to remember the permutation applied in the sorting.
427
    order = sorted(enumerate(w), key=itemgetter(1), reverse=True)
428
    mapping = {c: u for c, (u, v) in enumerate(order)}
429
    seq = [v for u, v in order]
430
    last = n
431
    if not selfloops:
432
        last -= 1
433
    for u in range(last):
434
        v = u
435
        if not selfloops:
436
            v += 1
437
        factor = seq[u] * rho
438
        p = min(seq[v] * factor, 1)
439
        while v < n and p > 0:
440
            if p != 1:
441
                r = seed.random()
442
                v += int(math.floor(math.log(r, 1 - p)))
443
            if v < n:
444
                q = min(seq[v] * factor, 1)
445
                if seed.random() < q / p:
446
                    G.add_edge(mapping[u], mapping[v])
447
                v += 1
448
                p = q
449
    return G
450

    
451

    
452
def havel_hakimi_graph(deg_sequence, create_using=None):
453
    """Returns a simple graph with given degree sequence constructed
454
    using the Havel-Hakimi algorithm.
455

456
    Parameters
457
    ----------
458
    deg_sequence: list of integers
459
        Each integer corresponds to the degree of a node (need not be sorted).
460
    create_using : NetworkX graph constructor, optional (default=nx.Graph)
461
        Graph type to create. If graph instance, then cleared before populated.
462
        Directed graphs are not allowed.
463

464
    Raises
465
    ------
466
    NetworkXException
467
        For a non-graphical degree sequence (i.e. one
468
        not realizable by some simple graph).
469

470
    Notes
471
    -----
472
    The Havel-Hakimi algorithm constructs a simple graph by
473
    successively connecting the node of highest degree to other nodes
474
    of highest degree, resorting remaining nodes by degree, and
475
    repeating the process. The resulting graph has a high
476
    degree-associativity.  Nodes are labeled 1,.., len(deg_sequence),
477
    corresponding to their position in deg_sequence.
478

479
    The basic algorithm is from Hakimi [1]_ and was generalized by
480
    Kleitman and Wang [2]_.
481

482
    References
483
    ----------
484
    .. [1] Hakimi S., On Realizability of a Set of Integers as
485
       Degrees of the Vertices of a Linear Graph. I,
486
       Journal of SIAM, 10(3), pp. 496-506 (1962)
487
    .. [2] Kleitman D.J. and Wang D.L.
488
       Algorithms for Constructing Graphs and Digraphs with Given Valences
489
       and Factors  Discrete Mathematics, 6(1), pp. 79-88 (1973)
490
    """
491
    if not nx.is_graphical(deg_sequence):
492
        raise nx.NetworkXError('Invalid degree sequence')
493

    
494
    p = len(deg_sequence)
495
    G = nx.empty_graph(p, create_using)
496
    if G.is_directed():
497
        raise nx.NetworkXError("Directed graphs are not supported")
498
    num_degs = [[] for i in range(p)]
499
    dmax, dsum, n = 0, 0, 0
500
    for d in deg_sequence:
501
        # Process only the non-zero integers
502
        if d > 0:
503
            num_degs[d].append(n)
504
            dmax, dsum, n = max(dmax, d), dsum + d, n + 1
505
    # Return graph if no edges
506
    if n == 0:
507
        return G
508

    
509
    modstubs = [(0, 0)] * (dmax + 1)
510
    # Successively reduce degree sequence by removing the maximum degree
511
    while n > 0:
512
        # Retrieve the maximum degree in the sequence
513
        while len(num_degs[dmax]) == 0:
514
            dmax -= 1
515
        # If there are not enough stubs to connect to, then the sequence is
516
        # not graphical
517
        if dmax > n - 1:
518
            raise nx.NetworkXError('Non-graphical integer sequence')
519

    
520
        # Remove largest stub in list
521
        source = num_degs[dmax].pop()
522
        n -= 1
523
        # Reduce the next dmax largest stubs
524
        mslen = 0
525
        k = dmax
526
        for i in range(dmax):
527
            while len(num_degs[k]) == 0:
528
                k -= 1
529
            target = num_degs[k].pop()
530
            G.add_edge(source, target)
531
            n -= 1
532
            if k > 1:
533
                modstubs[mslen] = (k - 1, target)
534
                mslen += 1
535
        # Add back to the list any nonzero stubs that were removed
536
        for i in range(mslen):
537
            (stubval, stubtarget) = modstubs[i]
538
            num_degs[stubval].append(stubtarget)
539
            n += 1
540

    
541
    return G
542

    
543

    
544
def directed_havel_hakimi_graph(in_deg_sequence,
545
                                out_deg_sequence,
546
                                create_using=None):
547
    """Returns a directed graph with the given degree sequences.
548

549
    Parameters
550
    ----------
551
    in_deg_sequence :  list of integers
552
        Each list entry corresponds to the in-degree of a node.
553
    out_deg_sequence : list of integers
554
        Each list entry corresponds to the out-degree of a node.
555
    create_using : NetworkX graph constructor, optional (default DiGraph)
556
        Graph type to create. If graph instance, then cleared before populated.
557

558
    Returns
559
    -------
560
    G : DiGraph
561
        A graph with the specified degree sequences.
562
        Nodes are labeled starting at 0 with an index
563
        corresponding to the position in deg_sequence
564

565
    Raises
566
    ------
567
    NetworkXError
568
        If the degree sequences are not digraphical.
569

570
    See Also
571
    --------
572
    configuration_model
573

574
    Notes
575
    -----
576
    Algorithm as described by Kleitman and Wang [1]_.
577

578
    References
579
    ----------
580
    .. [1] D.J. Kleitman and D.L. Wang
581
       Algorithms for Constructing Graphs and Digraphs with Given Valences
582
       and Factors Discrete Mathematics, 6(1), pp. 79-88 (1973)
583
    """
584
    assert(nx.utils.is_list_of_ints(in_deg_sequence))
585
    assert(nx.utils.is_list_of_ints(out_deg_sequence))
586

    
587
    # Process the sequences and form two heaps to store degree pairs with
588
    # either zero or nonzero out degrees
589
    sumin, sumout = 0, 0
590
    nin, nout = len(in_deg_sequence), len(out_deg_sequence)
591
    maxn = max(nin, nout)
592
    G = nx.empty_graph(maxn, create_using, default=nx.DiGraph)
593
    if maxn == 0:
594
        return G
595
    maxin = 0
596
    stubheap, zeroheap = [], []
597
    for n in range(maxn):
598
        in_deg, out_deg = 0, 0
599
        if n < nout:
600
            out_deg = out_deg_sequence[n]
601
        if n < nin:
602
            in_deg = in_deg_sequence[n]
603
        if in_deg < 0 or out_deg < 0:
604
            raise nx.NetworkXError(
605
                'Invalid degree sequences. Sequence values must be positive.')
606
        sumin, sumout, maxin = sumin + in_deg, sumout + out_deg, max(maxin, in_deg)
607
        if in_deg > 0:
608
            stubheap.append((-1 * out_deg, -1 * in_deg, n))
609
        elif out_deg > 0:
610
            zeroheap.append((-1 * out_deg, n))
611
    if sumin != sumout:
612
        raise nx.NetworkXError(
613
            'Invalid degree sequences. Sequences must have equal sums.')
614
    heapq.heapify(stubheap)
615
    heapq.heapify(zeroheap)
616

    
617
    modstubs = [(0, 0, 0)] * (maxin + 1)
618
    # Successively reduce degree sequence by removing the maximum
619
    while stubheap:
620
        # Remove first value in the sequence with a non-zero in degree
621
        (freeout, freein, target) = heapq.heappop(stubheap)
622
        freein *= -1
623
        if freein > len(stubheap) + len(zeroheap):
624
            raise nx.NetworkXError('Non-digraphical integer sequence')
625

    
626
        # Attach arcs from the nodes with the most stubs
627
        mslen = 0
628
        for i in range(freein):
629
            if zeroheap and (not stubheap or stubheap[0][0] > zeroheap[0][0]):
630
                (stubout, stubsource) = heapq.heappop(zeroheap)
631
                stubin = 0
632
            else:
633
                (stubout, stubin, stubsource) = heapq.heappop(stubheap)
634
            if stubout == 0:
635
                raise nx.NetworkXError('Non-digraphical integer sequence')
636
            G.add_edge(stubsource, target)
637
            # Check if source is now totally connected
638
            if stubout + 1 < 0 or stubin < 0:
639
                modstubs[mslen] = (stubout + 1, stubin, stubsource)
640
                mslen += 1
641

    
642
        # Add the nodes back to the heaps that still have available stubs
643
        for i in range(mslen):
644
            stub = modstubs[i]
645
            if stub[1] < 0:
646
                heapq.heappush(stubheap, stub)
647
            else:
648
                heapq.heappush(zeroheap, (stub[0], stub[2]))
649
        if freeout < 0:
650
            heapq.heappush(zeroheap, (freeout, target))
651

    
652
    return G
653

    
654

    
655
def degree_sequence_tree(deg_sequence, create_using=None):
656
    """Make a tree for the given degree sequence.
657

658
    A tree has #nodes-#edges=1 so
659
    the degree sequence must have
660
    len(deg_sequence)-sum(deg_sequence)/2=1
661
    """
662
    # The sum of the degree sequence must be even (for any undirected graph).
663
    degree_sum = sum(deg_sequence)
664
    if degree_sum % 2 != 0:
665
        msg = 'Invalid degree sequence: sum of degrees must be even, not odd'
666
        raise nx.NetworkXError(msg)
667
    if len(deg_sequence) - degree_sum // 2 != 1:
668
        msg = ('Invalid degree sequence: tree must have number of nodes equal'
669
               ' to one less than the number of edges')
670
        raise nx.NetworkXError(msg)
671
    G = nx.empty_graph(0, create_using)
672
    if G.is_directed():
673
        raise nx.NetworkXError("Directed Graph not supported")
674

    
675
    # Sort all degrees greater than 1 in decreasing order.
676
    #
677
    # TODO Does this need to be sorted in reverse order?
678
    deg = sorted((s for s in deg_sequence if s > 1), reverse=True)
679

    
680
    # make path graph as backbone
681
    n = len(deg) + 2
682
    nx.add_path(G, range(n))
683
    last = n
684

    
685
    # add the leaves
686
    for source in range(1, n - 1):
687
        nedges = deg.pop() - 2
688
        for target in range(last, last + nedges):
689
            G.add_edge(source, target)
690
        last += nedges
691

    
692
    # in case we added one too many
693
    if len(G) > len(deg_sequence):
694
        G.remove_node(0)
695
    return G
696

    
697

    
698
@py_random_state(1)
699
def random_degree_sequence_graph(sequence, seed=None, tries=10):
700
    r"""Returns a simple random graph with the given degree sequence.
701

702
    If the maximum degree $d_m$ in the sequence is $O(m^{1/4})$ then the
703
    algorithm produces almost uniform random graphs in $O(m d_m)$ time
704
    where $m$ is the number of edges.
705

706
    Parameters
707
    ----------
708
    sequence :  list of integers
709
        Sequence of degrees
710
    seed : integer, random_state, or None (default)
711
        Indicator of random number generation state.
712
        See :ref:`Randomness<randomness>`.
713
    tries : int, optional
714
        Maximum number of tries to create a graph
715

716
    Returns
717
    -------
718
    G : Graph
719
        A graph with the specified degree sequence.
720
        Nodes are labeled starting at 0 with an index
721
        corresponding to the position in the sequence.
722

723
    Raises
724
    ------
725
    NetworkXUnfeasible
726
        If the degree sequence is not graphical.
727
    NetworkXError
728
        If a graph is not produced in specified number of tries
729

730
    See Also
731
    --------
732
    is_graphical, configuration_model
733

734
    Notes
735
    -----
736
    The generator algorithm [1]_ is not guaranteed to produce a graph.
737

738
    References
739
    ----------
740
    .. [1] Moshen Bayati, Jeong Han Kim, and Amin Saberi,
741
       A sequential algorithm for generating random graphs.
742
       Algorithmica, Volume 58, Number 4, 860-910,
743
       DOI: 10.1007/s00453-009-9340-1
744

745
    Examples
746
    --------
747
    >>> sequence = [1, 2, 2, 3]
748
    >>> G = nx.random_degree_sequence_graph(sequence, seed=42)
749
    >>> sorted(d for n, d in G.degree())
750
    [1, 2, 2, 3]
751
    """
752
    DSRG = DegreeSequenceRandomGraph(sequence, seed)
753
    for try_n in range(tries):
754
        try:
755
            return DSRG.generate()
756
        except nx.NetworkXUnfeasible:
757
            pass
758
    raise nx.NetworkXError('failed to generate graph in %d tries' % tries)
759

    
760

    
761
class DegreeSequenceRandomGraph(object):
762
    # class to generate random graphs with a given degree sequence
763
    # use random_degree_sequence_graph()
764
    def __init__(self, degree, rng):
765
        if not nx.is_graphical(degree):
766
            raise nx.NetworkXUnfeasible('degree sequence is not graphical')
767
        self.rng = rng
768
        self.degree = list(degree)
769
        # node labels are integers 0,...,n-1
770
        self.m = sum(self.degree) / 2.0  # number of edges
771
        try:
772
            self.dmax = max(self.degree)  # maximum degree
773
        except ValueError:
774
            self.dmax = 0
775

    
776
    def generate(self):
777
        # remaining_degree is mapping from int->remaining degree
778
        self.remaining_degree = dict(enumerate(self.degree))
779
        # add all nodes to make sure we get isolated nodes
780
        self.graph = nx.Graph()
781
        self.graph.add_nodes_from(self.remaining_degree)
782
        # remove zero degree nodes
783
        for n, d in list(self.remaining_degree.items()):
784
            if d == 0:
785
                del self.remaining_degree[n]
786
        if len(self.remaining_degree) > 0:
787
            # build graph in three phases according to how many unmatched edges
788
            self.phase1()
789
            self.phase2()
790
            self.phase3()
791
        return self.graph
792

    
793
    def update_remaining(self, u, v, aux_graph=None):
794
        # decrement remaining nodes, modify auxiliary graph if in phase3
795
        if aux_graph is not None:
796
            # remove edges from auxiliary graph
797
            aux_graph.remove_edge(u, v)
798
        if self.remaining_degree[u] == 1:
799
            del self.remaining_degree[u]
800
            if aux_graph is not None:
801
                aux_graph.remove_node(u)
802
        else:
803
            self.remaining_degree[u] -= 1
804
        if self.remaining_degree[v] == 1:
805
            del self.remaining_degree[v]
806
            if aux_graph is not None:
807
                aux_graph.remove_node(v)
808
        else:
809
            self.remaining_degree[v] -= 1
810

    
811
    def p(self, u, v):
812
        # degree probability
813
        return 1 - self.degree[u] * self.degree[v] / (4.0 * self.m)
814

    
815
    def q(self, u, v):
816
        # remaining degree probability
817
        norm = float(max(self.remaining_degree.values()))**2
818
        return self.remaining_degree[u] * self.remaining_degree[v] / norm
819

    
820
    def suitable_edge(self):
821
        """Returns True if and only if an arbitrary remaining node can
822
        potentially be joined with some other remaining node.
823

824
        """
825
        nodes = iter(self.remaining_degree)
826
        u = next(nodes)
827
        return any(v not in self.graph[u] for v in nodes)
828

    
829
    def phase1(self):
830
        # choose node pairs from (degree) weighted distribution
831
        rem_deg = self.remaining_degree
832
        while sum(rem_deg.values()) >= 2 * self.dmax**2:
833
            u, v = sorted(random_weighted_sample(rem_deg, 2, self.rng))
834
            if self.graph.has_edge(u, v):
835
                continue
836
            if self.rng.random() < self.p(u, v):  # accept edge
837
                self.graph.add_edge(u, v)
838
                self.update_remaining(u, v)
839

    
840
    def phase2(self):
841
        # choose remaining nodes uniformly at random and use rejection sampling
842
        remaining_deg = self.remaining_degree
843
        rng = self.rng
844
        while len(remaining_deg) >= 2 * self.dmax:
845
            while True:
846
                u, v = sorted(rng.sample(remaining_deg.keys(), 2))
847
                if self.graph.has_edge(u, v):
848
                    continue
849
                if rng.random() < self.q(u, v):
850
                    break
851
            if rng.random() < self.p(u, v):  # accept edge
852
                self.graph.add_edge(u, v)
853
                self.update_remaining(u, v)
854

    
855
    def phase3(self):
856
        # build potential remaining edges and choose with rejection sampling
857
        potential_edges = combinations(self.remaining_degree, 2)
858
        # build auxiliary graph of potential edges not already in graph
859
        H = nx.Graph([(u, v) for (u, v) in potential_edges
860
                      if not self.graph.has_edge(u, v)])
861
        rng = self.rng
862
        while self.remaining_degree:
863
            if not self.suitable_edge():
864
                raise nx.NetworkXUnfeasible('no suitable edges left')
865
            while True:
866
                u, v = sorted(rng.choice(list(H.edges())))
867
                if rng.random() < self.q(u, v):
868
                    break
869
            if rng.random() < self.p(u, v):  # accept edge
870
                self.graph.add_edge(u, v)
871
                self.update_remaining(u, v, aux_graph=H)