Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (23.1 KB)

1
#    Copyright (C) 2004-2019 by
2
#    Aric Hagberg <hagberg@lanl.gov>
3
#    Dan Schult <dschult@colgate.edu>
4
#    Pieter Swart <swart@lanl.gov>
5
#    All rights reserved.
6
#    BSD license.
7
#
8
# Authors: Aric Hagberg (hagberg@lanl.gov)
9
#          Pieter Swart (swart@lanl.gov)
10
"""Generators for some classic graphs.
11

12
The typical graph generator is called as follows:
13

14
>>> G = nx.complete_graph(100)
15

16
returning the complete graph on n nodes labeled 0, .., 99
17
as a simple graph. Except for empty_graph, all the generators
18
in this module return a Graph class (i.e. a simple, undirected graph).
19

20
"""
21
from __future__ import division
22

    
23
import itertools
24

    
25
import networkx as nx
26
from networkx.classes import Graph
27
from networkx.exception import NetworkXError
28
from networkx.utils import accumulate
29
from networkx.utils import nodes_or_number
30
from networkx.utils import pairwise
31

    
32
__all__ = ['balanced_tree',
33
           'barbell_graph',
34
           'binomial_tree',
35
           'complete_graph',
36
           'complete_multipartite_graph',
37
           'circular_ladder_graph',
38
           'circulant_graph',
39
           'cycle_graph',
40
           'dorogovtsev_goltsev_mendes_graph',
41
           'empty_graph',
42
           'full_rary_tree',
43
           'ladder_graph',
44
           'lollipop_graph',
45
           'null_graph',
46
           'path_graph',
47
           'star_graph',
48
           'trivial_graph',
49
           'turan_graph',
50
           'wheel_graph']
51

    
52

    
53
# -------------------------------------------------------------------
54
#   Some Classic Graphs
55
# -------------------------------------------------------------------
56

    
57
def _tree_edges(n, r):
58
    if n == 0:
59
        return
60
    # helper function for trees
61
    # yields edges in rooted tree at 0 with n nodes and branching ratio r
62
    nodes = iter(range(n))
63
    parents = [next(nodes)]  # stack of max length r
64
    while parents:
65
        source = parents.pop(0)
66
        for i in range(r):
67
            try:
68
                target = next(nodes)
69
                parents.append(target)
70
                yield source, target
71
            except StopIteration:
72
                break
73

    
74

    
75
def full_rary_tree(r, n, create_using=None):
76
    """Creates a full r-ary tree of n vertices.
77

78
    Sometimes called a k-ary, n-ary, or m-ary tree.
79
    "... all non-leaf vertices have exactly r children and all levels
80
    are full except for some rightmost position of the bottom level
81
    (if a leaf at the bottom level is missing, then so are all of the
82
    leaves to its right." [1]_
83

84
    Parameters
85
    ----------
86
    r : int
87
        branching factor of the tree
88
    n : int
89
        Number of nodes in the tree
90
    create_using : NetworkX graph constructor, optional (default=nx.Graph)
91
       Graph type to create. If graph instance, then cleared before populated.
92

93
    Returns
94
    -------
95
    G : networkx Graph
96
        An r-ary tree with n nodes
97

98
    References
99
    ----------
100
    .. [1] An introduction to data structures and algorithms,
101
           James Andrew Storer,  Birkhauser Boston 2001, (page 225).
102
    """
103
    G = empty_graph(n, create_using)
104
    G.add_edges_from(_tree_edges(n, r))
105
    return G
106

    
107

    
108
def balanced_tree(r, h, create_using=None):
109
    """Returns the perfectly balanced `r`-ary tree of height `h`.
110

111
    Parameters
112
    ----------
113
    r : int
114
        Branching factor of the tree; each node will have `r`
115
        children.
116

117
    h : int
118
        Height of the tree.
119

120
    create_using : NetworkX graph constructor, optional (default=nx.Graph)
121
       Graph type to create. If graph instance, then cleared before populated.
122

123
    Returns
124
    -------
125
    G : NetworkX graph
126
        A balanced `r`-ary tree of height `h`.
127

128
    Notes
129
    -----
130
    This is the rooted tree where all leaves are at distance `h` from
131
    the root. The root has degree `r` and all other internal nodes
132
    have degree `r + 1`.
133

134
    Node labels are integers, starting from zero.
135

136
    A balanced tree is also known as a *complete r-ary tree*.
137

138
    """
139
    # The number of nodes in the balanced tree is `1 + r + ... + r^h`,
140
    # which is computed by using the closed-form formula for a geometric
141
    # sum with ratio `r`. In the special case that `r` is 1, the number
142
    # of nodes is simply `h + 1` (since the tree is actually a path
143
    # graph).
144
    if r == 1:
145
        n = h + 1
146
    else:
147
        # This must be an integer if both `r` and `h` are integers. If
148
        # they are not, we force integer division anyway.
149
        n = (1 - r ** (h + 1)) // (1 - r)
150
    return full_rary_tree(r, n, create_using=create_using)
151

    
152

    
153
def barbell_graph(m1, m2, create_using=None):
154
    """Returns the Barbell Graph: two complete graphs connected by a path.
155

156
    For $m1 > 1$ and $m2 >= 0$.
157

158
    Two identical complete graphs $K_{m1}$ form the left and right bells,
159
    and are connected by a path $P_{m2}$.
160

161
    The `2*m1+m2`  nodes are numbered
162
        `0, ..., m1-1` for the left barbell,
163
        `m1, ..., m1+m2-1` for the path,
164
        and `m1+m2, ..., 2*m1+m2-1` for the right barbell.
165

166
    The 3 subgraphs are joined via the edges `(m1-1, m1)` and
167
    `(m1+m2-1, m1+m2)`. If `m2=0`, this is merely two complete
168
    graphs joined together.
169

170
    This graph is an extremal example in David Aldous
171
    and Jim Fill's e-text on Random Walks on Graphs.
172

173
    """
174
    if m1 < 2:
175
        raise NetworkXError(
176
            "Invalid graph description, m1 should be >=2")
177
    if m2 < 0:
178
        raise NetworkXError(
179
            "Invalid graph description, m2 should be >=0")
180

    
181
    # left barbell
182
    G = complete_graph(m1, create_using)
183
    if G.is_directed():
184
        raise NetworkXError("Directed Graph not supported")
185

    
186
    # connecting path
187
    G.add_nodes_from(range(m1, m1 + m2 - 1))
188
    if m2 > 1:
189
        G.add_edges_from(pairwise(range(m1, m1 + m2)))
190
    # right barbell
191
    G.add_edges_from((u, v) for u in range(m1 + m2, 2 * m1 + m2)
192
                     for v in range(u + 1, 2 * m1 + m2))
193
    # connect it up
194
    G.add_edge(m1 - 1, m1)
195
    if m2 > 0:
196
        G.add_edge(m1 + m2 - 1, m1 + m2)
197
    return G
198

    
199
def binomial_tree(n):
200
    """Returns the Binomial Tree of order n.
201
    
202
    The binomial tree of order 0 consists of a single vertex. A binomial tree of order k 
203
    is defined recursively by linking two binomial trees of order k-1: the root of one is 
204
    the leftmost child of the root of the other.
205

206
    Parameters
207
    ----------
208
    n : int
209
        Order of the binomial tree.
210

211
    Returns
212
    -------
213
    G : NetworkX graph
214
        A binomial tree of $2^n$ vertices and $2^n - 1$ edges.
215

216
    """
217
    G = nx.empty_graph(1)
218
    N = 1
219
    for i in range(n):
220
        edges = [(u + N, v + N)  for (u, v) in G.edges]
221
        G.add_edges_from(edges)
222
        G.add_edge(0,N)
223
        N *= 2
224
    return G
225

    
226
@nodes_or_number(0)
227
def complete_graph(n, create_using=None):
228
    """ Return the complete graph `K_n` with n nodes.
229

230
    Parameters
231
    ----------
232
    n : int or iterable container of nodes
233
        If n is an integer, nodes are from range(n).
234
        If n is a container of nodes, those nodes appear in the graph.
235
    create_using : NetworkX graph constructor, optional (default=nx.Graph)
236
       Graph type to create. If graph instance, then cleared before populated.
237

238
    Examples
239
    --------
240
    >>> G = nx.complete_graph(9)
241
    >>> len(G)
242
    9
243
    >>> G.size()
244
    36
245
    >>> G = nx.complete_graph(range(11, 14))
246
    >>> list(G.nodes())
247
    [11, 12, 13]
248
    >>> G = nx.complete_graph(4, nx.DiGraph())
249
    >>> G.is_directed()
250
    True
251

252
    """
253
    n_name, nodes = n
254
    G = empty_graph(n_name, create_using)
255
    if len(nodes) > 1:
256
        if G.is_directed():
257
            edges = itertools.permutations(nodes, 2)
258
        else:
259
            edges = itertools.combinations(nodes, 2)
260
        G.add_edges_from(edges)
261
    return G
262

    
263

    
264
def circular_ladder_graph(n, create_using=None):
265
    """Returns the circular ladder graph $CL_n$ of length n.
266

267
    $CL_n$ consists of two concentric n-cycles in which
268
    each of the n pairs of concentric nodes are joined by an edge.
269

270
    Node labels are the integers 0 to n-1
271

272
    """
273
    G = ladder_graph(n, create_using)
274
    G.add_edge(0, n - 1)
275
    G.add_edge(n, 2 * n - 1)
276
    return G
277

    
278

    
279
def circulant_graph(n, offsets, create_using=None):
280
    """Generates the circulant graph $Ci_n(x_1, x_2, ..., x_m)$ with $n$ vertices.
281

282
    Returns
283
    -------
284
    The graph $Ci_n(x_1, ..., x_m)$ consisting of $n$ vertices $0, ..., n-1$ such
285
    that the vertex with label $i$ is connected to the vertices labelled $(i + x)$
286
    and $(i - x)$, for all $x$ in $x_1$ up to $x_m$, with the indices taken modulo $n$.
287

288
    Parameters
289
    ----------
290
    n : integer
291
        The number of vertices the generated graph is to contain.
292
    offsets : list of integers
293
        A list of vertex offsets, $x_1$ up to $x_m$, as described above.
294
    create_using : NetworkX graph constructor, optional (default=nx.Graph)
295
       Graph type to create. If graph instance, then cleared before populated.
296

297
    Examples
298
    --------
299
    Many well-known graph families are subfamilies of the circulant graphs;
300
    for example, to generate the cycle graph on n points, we connect every
301
    vertex to every other at offset plus or minus one. For n = 10,
302

303
    >>> import networkx
304
    >>> G = networkx.generators.classic.circulant_graph(10, [1])
305
    >>> edges = [
306
    ...     (0, 9), (0, 1), (1, 2), (2, 3), (3, 4),
307
    ...     (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]
308
    ...
309
    >>> sorted(edges) == sorted(G.edges())
310
    True
311

312
    Similarly, we can generate the complete graph on 5 points with the set of
313
    offsets [1, 2]:
314

315
    >>> G = networkx.generators.classic.circulant_graph(5, [1, 2])
316
    >>> edges = [
317
    ...     (0, 1), (0, 2), (0, 3), (0, 4), (1, 2),
318
    ...     (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
319
    ...
320
    >>> sorted(edges) == sorted(G.edges())
321
    True
322

323
    """
324
    G = empty_graph(n, create_using)
325
    for i in range(n):
326
        for j in offsets:
327
            G.add_edge(i, (i - j) % n)
328
            G.add_edge(i, (i + j) % n)
329
    return G
330

    
331

    
332
@nodes_or_number(0)
333
def cycle_graph(n, create_using=None):
334
    """Returns the cycle graph $C_n$ of cyclically connected nodes.
335

336
    $C_n$ is a path with its two end-nodes connected.
337

338
    Parameters
339
    ----------
340
    n : int or iterable container of nodes
341
        If n is an integer, nodes are from `range(n)`.
342
        If n is a container of nodes, those nodes appear in the graph.
343
    create_using : NetworkX graph constructor, optional (default=nx.Graph)
344
       Graph type to create. If graph instance, then cleared before populated.
345

346
    Notes
347
    -----
348
    If create_using is directed, the direction is in increasing order.
349

350
    """
351
    n_orig, nodes = n
352
    G = empty_graph(nodes, create_using)
353
    G.add_edges_from(pairwise(nodes))
354
    G.add_edge(nodes[-1], nodes[0])
355
    return G
356

    
357

    
358
def dorogovtsev_goltsev_mendes_graph(n, create_using=None):
359
    """Returns the hierarchically constructed Dorogovtsev-Goltsev-Mendes graph.
360

361
    n is the generation.
362
    See: arXiv:/cond-mat/0112143 by Dorogovtsev, Goltsev and Mendes.
363

364
    """
365
    G = empty_graph(0, create_using)
366
    if G.is_directed():
367
        raise NetworkXError("Directed Graph not supported")
368
    if G.is_multigraph():
369
        raise NetworkXError("Multigraph not supported")
370

    
371
    G.add_edge(0, 1)
372
    if n == 0:
373
        return G
374
    new_node = 2         # next node to be added
375
    for i in range(1, n + 1):  # iterate over number of generations.
376
        last_generation_edges = list(G.edges())
377
        number_of_edges_in_last_generation = len(last_generation_edges)
378
        for j in range(0, number_of_edges_in_last_generation):
379
            G.add_edge(new_node, last_generation_edges[j][0])
380
            G.add_edge(new_node, last_generation_edges[j][1])
381
            new_node += 1
382
    return G
383

    
384

    
385
@nodes_or_number(0)
386
def empty_graph(n=0, create_using=None, default=nx.Graph):
387
    """Returns the empty graph with n nodes and zero edges.
388

389
    Parameters
390
    ----------
391
    n : int or iterable container of nodes (default = 0)
392
        If n is an integer, nodes are from `range(n)`.
393
        If n is a container of nodes, those nodes appear in the graph.
394
    create_using : Graph Instance, Constructor or None
395
        Indicator of type of graph to return.
396
        If a Graph-type instance, then clear and use it.
397
        If None, use the `default` constructor.
398
        If a constructor, call it to create an empty graph.
399
    default : Graph constructor (optional, default = nx.Graph)
400
        The constructor to use if create_using is None.
401
        If None, then nx.Graph is used.
402
        This is used when passing an unknown `create_using` value
403
        through your home-grown function to `empty_graph` and
404
        you want a default constructor other than nx.Graph.
405

406
    Examples
407
    --------
408
    >>> G = nx.empty_graph(10)
409
    >>> G.number_of_nodes()
410
    10
411
    >>> G.number_of_edges()
412
    0
413
    >>> G = nx.empty_graph("ABC")
414
    >>> G.number_of_nodes()
415
    3
416
    >>> sorted(G)
417
    ['A', 'B', 'C']
418

419
    Notes
420
    -----
421
    The variable create_using should be a Graph Constructor or a
422
    "graph"-like object. Constructors, e.g. `nx.Graph` or `nx.MultiGraph`
423
    will be used to create the returned graph. "graph"-like objects
424
    will be cleared (nodes and edges will be removed) and refitted as
425
    an empty "graph" with nodes specified in n. This capability
426
    is useful for specifying the class-nature of the resulting empty
427
    "graph" (i.e. Graph, DiGraph, MyWeirdGraphClass, etc.).
428

429
    The variable create_using has three main uses:
430
    Firstly, the variable create_using can be used to create an
431
    empty digraph, multigraph, etc.  For example,
432

433
    >>> n = 10
434
    >>> G = nx.empty_graph(n, create_using=nx.DiGraph)
435

436
    will create an empty digraph on n nodes.
437

438
    Secondly, one can pass an existing graph (digraph, multigraph,
439
    etc.) via create_using. For example, if G is an existing graph
440
    (resp. digraph, multigraph, etc.), then empty_graph(n, create_using=G)
441
    will empty G (i.e. delete all nodes and edges using G.clear())
442
    and then add n nodes and zero edges, and return the modified graph.
443

444
    Thirdly, when constructing your home-grown graph creation function
445
    you can use empty_graph to construct the graph by passing a user
446
    defined create_using to empty_graph. In this case, if you want the
447
    default constructor to be other than nx.Graph, specify `default`.
448

449
    >>> def mygraph(n, create_using=None):
450
    ...     G = nx.empty_graph(n, create_using, nx.MultiGraph)
451
    ...     G.add_edges_from([(0, 1), (0, 1)])
452
    ...     return G
453
    >>> G = mygraph(3)
454
    >>> G.is_multigraph()
455
    True
456
    >>> G = mygraph(3, nx.Graph)
457
    >>> G.is_multigraph()
458
    False
459

460
    See also create_empty_copy(G).
461

462
    """
463
    if create_using is None:
464
        G = default()
465
    elif hasattr(create_using, '_adj'):
466
        # create_using is a NetworkX style Graph
467
        create_using.clear()
468
        G = create_using
469
    else:
470
        # try create_using as constructor
471
        G = create_using()
472

    
473
    n_name, nodes = n
474
    G.add_nodes_from(nodes)
475
    return G
476

    
477

    
478
def ladder_graph(n, create_using=None):
479
    """Returns the Ladder graph of length n.
480

481
    This is two paths of n nodes, with
482
    each pair connected by a single edge.
483

484
    Node labels are the integers 0 to 2*n - 1.
485

486
    """
487
    G = empty_graph(2 * n, create_using)
488
    if G.is_directed():
489
        raise NetworkXError("Directed Graph not supported")
490
    G.add_edges_from(pairwise(range(n)))
491
    G.add_edges_from(pairwise(range(n, 2 * n)))
492
    G.add_edges_from((v, v + n) for v in range(n))
493
    return G
494

    
495

    
496
@nodes_or_number([0, 1])
497
def lollipop_graph(m, n, create_using=None):
498
    """Returns the Lollipop Graph; `K_m` connected to `P_n`.
499

500
    This is the Barbell Graph without the right barbell.
501

502
    Parameters
503
    ----------
504
    m, n : int or iterable container of nodes (default = 0)
505
        If an integer, nodes are from `range(m)` and `range(m,m+n)`.
506
        If a container, the entries are the coordinate of the node.
507

508
        The nodes for m appear in the complete graph $K_m$ and the nodes
509
        for n appear in the path $P_n$
510
    create_using : NetworkX graph constructor, optional (default=nx.Graph)
511
       Graph type to create. If graph instance, then cleared before populated.
512

513
    Notes
514
    -----
515
    The 2 subgraphs are joined via an edge (m-1, m).
516
    If n=0, this is merely a complete graph.
517

518
    (This graph is an extremal example in David Aldous and Jim
519
    Fill's etext on Random Walks on Graphs.)
520

521
    """
522
    m, m_nodes = m
523
    n, n_nodes = n
524
    M = len(m_nodes)
525
    N = len(n_nodes)
526
    if isinstance(m, int):
527
        n_nodes = [len(m_nodes) + i for i in n_nodes]
528
    if M < 2:
529
        raise NetworkXError(
530
            "Invalid graph description, m should be >=2")
531
    if N < 0:
532
        raise NetworkXError(
533
            "Invalid graph description, n should be >=0")
534

    
535
    # the ball
536
    G = complete_graph(m_nodes, create_using)
537
    if G.is_directed():
538
        raise NetworkXError("Directed Graph not supported")
539
    # the stick
540
    G.add_nodes_from(n_nodes)
541
    if N > 1:
542
        G.add_edges_from(pairwise(n_nodes))
543
    # connect ball to stick
544
    if M > 0 and N > 0:
545
        G.add_edge(m_nodes[-1], n_nodes[0])
546
    return G
547

    
548

    
549
def null_graph(create_using=None):
550
    """Returns the Null graph with no nodes or edges.
551

552
    See empty_graph for the use of create_using.
553

554
    """
555
    G = empty_graph(0, create_using)
556
    return G
557

    
558

    
559
@nodes_or_number(0)
560
def path_graph(n, create_using=None):
561
    """Returns the Path graph `P_n` of linearly connected nodes.
562

563
    Parameters
564
    ----------
565
    n : int or iterable
566
        If an integer, node labels are 0 to n with center 0.
567
        If an iterable of nodes, the center is the first.
568
    create_using : NetworkX graph constructor, optional (default=nx.Graph)
569
       Graph type to create. If graph instance, then cleared before populated.
570

571
    """
572
    n_name, nodes = n
573
    G = empty_graph(nodes, create_using)
574
    G.add_edges_from(pairwise(nodes))
575
    return G
576

    
577

    
578
@nodes_or_number(0)
579
def star_graph(n, create_using=None):
580
    """ Return the star graph
581

582
    The star graph consists of one center node connected to n outer nodes.
583

584
    Parameters
585
    ----------
586
    n : int or iterable
587
        If an integer, node labels are 0 to n with center 0.
588
        If an iterable of nodes, the center is the first.
589
    create_using : NetworkX graph constructor, optional (default=nx.Graph)
590
       Graph type to create. If graph instance, then cleared before populated.
591

592
    Notes
593
    -----
594
    The graph has n+1 nodes for integer n.
595
    So star_graph(3) is the same as star_graph(range(4)).
596
    """
597
    n_name, nodes = n
598
    if isinstance(n_name, int):
599
        nodes = nodes + [n_name]  # there should be n+1 nodes
600
    first = nodes[0]
601
    G = empty_graph(nodes, create_using)
602
    if G.is_directed():
603
        raise NetworkXError("Directed Graph not supported")
604
    G.add_edges_from((first, v) for v in nodes[1:])
605
    return G
606

    
607

    
608
def trivial_graph(create_using=None):
609
    """ Return the Trivial graph with one node (with label 0) and no edges.
610

611
    """
612
    G = empty_graph(1, create_using)
613
    return G
614

    
615

    
616
def turan_graph(n, r):
617
    r""" Return the Turan Graph
618

619
    The Turan Graph is a complete multipartite graph on $n$ vertices
620
    with $r$ disjoint subsets. It is the graph with the edges for any graph with
621
    $n$ vertices and $r$ disjoint subsets.
622

623
    Given $n$ and $r$, we generate a complete multipartite graph with
624
    $r-(n \mod r)$ partitions of size $n/r$, rounded down, and
625
    $n \mod r$ partitions of size $n/r+1$, rounded down.
626

627
    Parameters
628
    ----------
629
    n : int
630
        The number of vertices.
631
    r : int
632
        The number of partitions.
633
        Must be less than or equal to n.
634

635
    Notes
636
    -----
637
    Must satisfy $1 <= r <= n$.
638
    The graph has $(r-1)(n^2)/(2r)$ edges, rounded down.
639
    """
640

    
641
    if not 1 <= r <= n:
642
        raise NetworkXError("Must satisfy 1 <= r <= n")
643

    
644
    partitions = [n // r] * (r - (n % r)) + [n // r + 1] * (n % r)
645
    G = complete_multipartite_graph(*partitions)
646
    return G
647

    
648

    
649
@nodes_or_number(0)
650
def wheel_graph(n, create_using=None):
651
    """ Return the wheel graph
652

653
    The wheel graph consists of a hub node connected to a cycle of (n-1) nodes.
654

655
    Parameters
656
    ----------
657
    n : int or iterable
658
        If an integer, node labels are 0 to n with center 0.
659
        If an iterable of nodes, the center is the first.
660
    create_using : NetworkX graph constructor, optional (default=nx.Graph)
661
       Graph type to create. If graph instance, then cleared before populated.
662

663
    Node labels are the integers 0 to n - 1.
664
    """
665
    n_name, nodes = n
666
    if n_name == 0:
667
        G = empty_graph(0, create_using)
668
        return G
669
    G = star_graph(nodes, create_using)
670
    if len(G) > 2:
671
        G.add_edges_from(pairwise(nodes[1:]))
672
        G.add_edge(nodes[-1], nodes[1])
673
    return G
674

    
675

    
676
def complete_multipartite_graph(*subset_sizes):
677
    """Returns the complete multipartite graph with the specified subset sizes.
678

679
    Parameters
680
    ----------
681
    subset_sizes : tuple of integers or tuple of node iterables
682
       The arguments can either all be integer number of nodes or they
683
       can all be iterables of nodes. If integers, they represent the
684
       number of vertices in each subset of the multipartite graph.
685
       If iterables, each is used to create the nodes for that subset.
686
       The length of subset_sizes is the number of subsets.
687

688
    Returns
689
    -------
690
    G : NetworkX Graph
691
       Returns the complete multipartite graph with the specified subsets.
692

693
       For each node, the node attribute 'subset' is an integer
694
       indicating which subset contains the node.
695

696
    Examples
697
    --------
698
    Creating a complete tripartite graph, with subsets of one, two, and three
699
    vertices, respectively.
700

701
        >>> import networkx as nx
702
        >>> G = nx.complete_multipartite_graph(1, 2, 3)
703
        >>> [G.nodes[u]['subset'] for u in G]
704
        [0, 1, 1, 2, 2, 2]
705
        >>> list(G.edges(0))
706
        [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]
707
        >>> list(G.edges(2))
708
        [(2, 0), (2, 3), (2, 4), (2, 5)]
709
        >>> list(G.edges(4))
710
        [(4, 0), (4, 1), (4, 2)]
711

712
        >>> G = nx.complete_multipartite_graph('a', 'bc', 'def')
713
        >>> [G.nodes[u]['subset'] for u in sorted(G)]
714
        [0, 1, 1, 2, 2, 2]
715

716
    Notes
717
    -----
718
    This function generalizes several other graph generator functions.
719

720
    - If no subset sizes are given, this returns the null graph.
721
    - If a single subset size `n` is given, this returns the empty graph on
722
      `n` nodes.
723
    - If two subset sizes `m` and `n` are given, this returns the complete
724
      bipartite graph on `m + n` nodes.
725
    - If subset sizes `1` and `n` are given, this returns the star graph on
726
      `n + 1` nodes.
727

728
    See also
729
    --------
730
    complete_bipartite_graph
731
    """
732
    # The complete multipartite graph is an undirected simple graph.
733
    G = Graph()
734

    
735
    if len(subset_sizes) == 0:
736
        return G
737

    
738
    # set up subsets of nodes
739
    try:
740
        extents = pairwise(accumulate((0,) + subset_sizes))
741
        subsets = [range(start, end) for start, end in extents]
742
    except TypeError:
743
        subsets = subset_sizes
744

    
745
    # add nodes with subset attribute
746
    # while checking that ints are not mixed with iterables
747
    try:
748
        for (i, subset) in enumerate(subsets):
749
            G.add_nodes_from(subset, subset=i)
750
    except TypeError:
751
        raise NetworkXError("Arguments must be all ints or all iterables")
752

    
753
    # Across subsets, all vertices should be adjacent.
754
    # We can use itertools.combinations() because undirected.
755
    for subset1, subset2 in itertools.combinations(subsets, 2):
756
        G.add_edges_from(itertools.product(subset1, subset2))
757
    return G