Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/generators/classic.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 # 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
22 import itertools
23
24 import networkx as nx
25 from networkx.classes import Graph
26 from networkx.exception import NetworkXError
27 from networkx.utils import accumulate
28 from networkx.utils import nodes_or_number
29 from networkx.utils import pairwise
30
31 __all__ = ['balanced_tree',
32 'barbell_graph',
33 'binomial_tree',
34 'complete_graph',
35 'complete_multipartite_graph',
36 'circular_ladder_graph',
37 'circulant_graph',
38 'cycle_graph',
39 'dorogovtsev_goltsev_mendes_graph',
40 'empty_graph',
41 'full_rary_tree',
42 'ladder_graph',
43 'lollipop_graph',
44 'null_graph',
45 'path_graph',
46 'star_graph',
47 'trivial_graph',
48 'turan_graph',
49 'wheel_graph']
50
51
52 # -------------------------------------------------------------------
53 # Some Classic Graphs
54 # -------------------------------------------------------------------
55
56 def _tree_edges(n, r):
57 if n == 0:
58 return
59 # helper function for trees
60 # yields edges in rooted tree at 0 with n nodes and branching ratio r
61 nodes = iter(range(n))
62 parents = [next(nodes)] # stack of max length r
63 while parents:
64 source = parents.pop(0)
65 for i in range(r):
66 try:
67 target = next(nodes)
68 parents.append(target)
69 yield source, target
70 except StopIteration:
71 break
72
73
74 def full_rary_tree(r, n, create_using=None):
75 """Creates a full r-ary tree of n vertices.
76
77 Sometimes called a k-ary, n-ary, or m-ary tree.
78 "... all non-leaf vertices have exactly r children and all levels
79 are full except for some rightmost position of the bottom level
80 (if a leaf at the bottom level is missing, then so are all of the
81 leaves to its right." [1]_
82
83 Parameters
84 ----------
85 r : int
86 branching factor of the tree
87 n : int
88 Number of nodes in the tree
89 create_using : NetworkX graph constructor, optional (default=nx.Graph)
90 Graph type to create. If graph instance, then cleared before populated.
91
92 Returns
93 -------
94 G : networkx Graph
95 An r-ary tree with n nodes
96
97 References
98 ----------
99 .. [1] An introduction to data structures and algorithms,
100 James Andrew Storer, Birkhauser Boston 2001, (page 225).
101 """
102 G = empty_graph(n, create_using)
103 G.add_edges_from(_tree_edges(n, r))
104 return G
105
106
107 def balanced_tree(r, h, create_using=None):
108 """Returns the perfectly balanced `r`-ary tree of height `h`.
109
110 Parameters
111 ----------
112 r : int
113 Branching factor of the tree; each node will have `r`
114 children.
115
116 h : int
117 Height of the tree.
118
119 create_using : NetworkX graph constructor, optional (default=nx.Graph)
120 Graph type to create. If graph instance, then cleared before populated.
121
122 Returns
123 -------
124 G : NetworkX graph
125 A balanced `r`-ary tree of height `h`.
126
127 Notes
128 -----
129 This is the rooted tree where all leaves are at distance `h` from
130 the root. The root has degree `r` and all other internal nodes
131 have degree `r + 1`.
132
133 Node labels are integers, starting from zero.
134
135 A balanced tree is also known as a *complete r-ary tree*.
136
137 """
138 # The number of nodes in the balanced tree is `1 + r + ... + r^h`,
139 # which is computed by using the closed-form formula for a geometric
140 # sum with ratio `r`. In the special case that `r` is 1, the number
141 # of nodes is simply `h + 1` (since the tree is actually a path
142 # graph).
143 if r == 1:
144 n = h + 1
145 else:
146 # This must be an integer if both `r` and `h` are integers. If
147 # they are not, we force integer division anyway.
148 n = (1 - r ** (h + 1)) // (1 - r)
149 return full_rary_tree(r, n, create_using=create_using)
150
151
152 def barbell_graph(m1, m2, create_using=None):
153 """Returns the Barbell Graph: two complete graphs connected by a path.
154
155 For $m1 > 1$ and $m2 >= 0$.
156
157 Two identical complete graphs $K_{m1}$ form the left and right bells,
158 and are connected by a path $P_{m2}$.
159
160 The `2*m1+m2` nodes are numbered
161 `0, ..., m1-1` for the left barbell,
162 `m1, ..., m1+m2-1` for the path,
163 and `m1+m2, ..., 2*m1+m2-1` for the right barbell.
164
165 The 3 subgraphs are joined via the edges `(m1-1, m1)` and
166 `(m1+m2-1, m1+m2)`. If `m2=0`, this is merely two complete
167 graphs joined together.
168
169 This graph is an extremal example in David Aldous
170 and Jim Fill's e-text on Random Walks on Graphs.
171
172 """
173 if m1 < 2:
174 raise NetworkXError(
175 "Invalid graph description, m1 should be >=2")
176 if m2 < 0:
177 raise NetworkXError(
178 "Invalid graph description, m2 should be >=0")
179
180 # left barbell
181 G = complete_graph(m1, create_using)
182 if G.is_directed():
183 raise NetworkXError("Directed Graph not supported")
184
185 # connecting path
186 G.add_nodes_from(range(m1, m1 + m2 - 1))
187 if m2 > 1:
188 G.add_edges_from(pairwise(range(m1, m1 + m2)))
189 # right barbell
190 G.add_edges_from((u, v) for u in range(m1 + m2, 2 * m1 + m2)
191 for v in range(u + 1, 2 * m1 + m2))
192 # connect it up
193 G.add_edge(m1 - 1, m1)
194 if m2 > 0:
195 G.add_edge(m1 + m2 - 1, m1 + m2)
196 return G
197
198 def binomial_tree(n):
199 """Returns the Binomial Tree of order n.
200
201 The binomial tree of order 0 consists of a single vertex. A binomial tree of order k
202 is defined recursively by linking two binomial trees of order k-1: the root of one is
203 the leftmost child of the root of the other.
204
205 Parameters
206 ----------
207 n : int
208 Order of the binomial tree.
209
210 Returns
211 -------
212 G : NetworkX graph
213 A binomial tree of $2^n$ vertices and $2^n - 1$ edges.
214
215 """
216 G = nx.empty_graph(1)
217 N = 1
218 for i in range(n):
219 edges = [(u + N, v + N) for (u, v) in G.edges]
220 G.add_edges_from(edges)
221 G.add_edge(0,N)
222 N *= 2
223 return G
224
225 @nodes_or_number(0)
226 def complete_graph(n, create_using=None):
227 """ Return the complete graph `K_n` with n nodes.
228
229 Parameters
230 ----------
231 n : int or iterable container of nodes
232 If n is an integer, nodes are from range(n).
233 If n is a container of nodes, those nodes appear in the graph.
234 create_using : NetworkX graph constructor, optional (default=nx.Graph)
235 Graph type to create. If graph instance, then cleared before populated.
236
237 Examples
238 --------
239 >>> G = nx.complete_graph(9)
240 >>> len(G)
241 9
242 >>> G.size()
243 36
244 >>> G = nx.complete_graph(range(11, 14))
245 >>> list(G.nodes())
246 [11, 12, 13]
247 >>> G = nx.complete_graph(4, nx.DiGraph())
248 >>> G.is_directed()
249 True
250
251 """
252 n_name, nodes = n
253 G = empty_graph(n_name, create_using)
254 if len(nodes) > 1:
255 if G.is_directed():
256 edges = itertools.permutations(nodes, 2)
257 else:
258 edges = itertools.combinations(nodes, 2)
259 G.add_edges_from(edges)
260 return G
261
262
263 def circular_ladder_graph(n, create_using=None):
264 """Returns the circular ladder graph $CL_n$ of length n.
265
266 $CL_n$ consists of two concentric n-cycles in which
267 each of the n pairs of concentric nodes are joined by an edge.
268
269 Node labels are the integers 0 to n-1
270
271 """
272 G = ladder_graph(n, create_using)
273 G.add_edge(0, n - 1)
274 G.add_edge(n, 2 * n - 1)
275 return G
276
277
278 def circulant_graph(n, offsets, create_using=None):
279 """Generates the circulant graph $Ci_n(x_1, x_2, ..., x_m)$ with $n$ vertices.
280
281 Returns
282 -------
283 The graph $Ci_n(x_1, ..., x_m)$ consisting of $n$ vertices $0, ..., n-1$ such
284 that the vertex with label $i$ is connected to the vertices labelled $(i + x)$
285 and $(i - x)$, for all $x$ in $x_1$ up to $x_m$, with the indices taken modulo $n$.
286
287 Parameters
288 ----------
289 n : integer
290 The number of vertices the generated graph is to contain.
291 offsets : list of integers
292 A list of vertex offsets, $x_1$ up to $x_m$, as described above.
293 create_using : NetworkX graph constructor, optional (default=nx.Graph)
294 Graph type to create. If graph instance, then cleared before populated.
295
296 Examples
297 --------
298 Many well-known graph families are subfamilies of the circulant graphs;
299 for example, to generate the cycle graph on n points, we connect every
300 vertex to every other at offset plus or minus one. For n = 10,
301
302 >>> import networkx
303 >>> G = networkx.generators.classic.circulant_graph(10, [1])
304 >>> edges = [
305 ... (0, 9), (0, 1), (1, 2), (2, 3), (3, 4),
306 ... (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]
307 ...
308 >>> sorted(edges) == sorted(G.edges())
309 True
310
311 Similarly, we can generate the complete graph on 5 points with the set of
312 offsets [1, 2]:
313
314 >>> G = networkx.generators.classic.circulant_graph(5, [1, 2])
315 >>> edges = [
316 ... (0, 1), (0, 2), (0, 3), (0, 4), (1, 2),
317 ... (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
318 ...
319 >>> sorted(edges) == sorted(G.edges())
320 True
321
322 """
323 G = empty_graph(n, create_using)
324 for i in range(n):
325 for j in offsets:
326 G.add_edge(i, (i - j) % n)
327 G.add_edge(i, (i + j) % n)
328 return G
329
330
331 @nodes_or_number(0)
332 def cycle_graph(n, create_using=None):
333 """Returns the cycle graph $C_n$ of cyclically connected nodes.
334
335 $C_n$ is a path with its two end-nodes connected.
336
337 Parameters
338 ----------
339 n : int or iterable container of nodes
340 If n is an integer, nodes are from `range(n)`.
341 If n is a container of nodes, those nodes appear in the graph.
342 create_using : NetworkX graph constructor, optional (default=nx.Graph)
343 Graph type to create. If graph instance, then cleared before populated.
344
345 Notes
346 -----
347 If create_using is directed, the direction is in increasing order.
348
349 """
350 n_orig, nodes = n
351 G = empty_graph(nodes, create_using)
352 G.add_edges_from(pairwise(nodes))
353 G.add_edge(nodes[-1], nodes[0])
354 return G
355
356
357 def dorogovtsev_goltsev_mendes_graph(n, create_using=None):
358 """Returns the hierarchically constructed Dorogovtsev-Goltsev-Mendes graph.
359
360 n is the generation.
361 See: arXiv:/cond-mat/0112143 by Dorogovtsev, Goltsev and Mendes.
362
363 """
364 G = empty_graph(0, create_using)
365 if G.is_directed():
366 raise NetworkXError("Directed Graph not supported")
367 if G.is_multigraph():
368 raise NetworkXError("Multigraph not supported")
369
370 G.add_edge(0, 1)
371 if n == 0:
372 return G
373 new_node = 2 # next node to be added
374 for i in range(1, n + 1): # iterate over number of generations.
375 last_generation_edges = list(G.edges())
376 number_of_edges_in_last_generation = len(last_generation_edges)
377 for j in range(0, number_of_edges_in_last_generation):
378 G.add_edge(new_node, last_generation_edges[j][0])
379 G.add_edge(new_node, last_generation_edges[j][1])
380 new_node += 1
381 return G
382
383
384 @nodes_or_number(0)
385 def empty_graph(n=0, create_using=None, default=nx.Graph):
386 """Returns the empty graph with n nodes and zero edges.
387
388 Parameters
389 ----------
390 n : int or iterable container of nodes (default = 0)
391 If n is an integer, nodes are from `range(n)`.
392 If n is a container of nodes, those nodes appear in the graph.
393 create_using : Graph Instance, Constructor or None
394 Indicator of type of graph to return.
395 If a Graph-type instance, then clear and use it.
396 If None, use the `default` constructor.
397 If a constructor, call it to create an empty graph.
398 default : Graph constructor (optional, default = nx.Graph)
399 The constructor to use if create_using is None.
400 If None, then nx.Graph is used.
401 This is used when passing an unknown `create_using` value
402 through your home-grown function to `empty_graph` and
403 you want a default constructor other than nx.Graph.
404
405 Examples
406 --------
407 >>> G = nx.empty_graph(10)
408 >>> G.number_of_nodes()
409 10
410 >>> G.number_of_edges()
411 0
412 >>> G = nx.empty_graph("ABC")
413 >>> G.number_of_nodes()
414 3
415 >>> sorted(G)
416 ['A', 'B', 'C']
417
418 Notes
419 -----
420 The variable create_using should be a Graph Constructor or a
421 "graph"-like object. Constructors, e.g. `nx.Graph` or `nx.MultiGraph`
422 will be used to create the returned graph. "graph"-like objects
423 will be cleared (nodes and edges will be removed) and refitted as
424 an empty "graph" with nodes specified in n. This capability
425 is useful for specifying the class-nature of the resulting empty
426 "graph" (i.e. Graph, DiGraph, MyWeirdGraphClass, etc.).
427
428 The variable create_using has three main uses:
429 Firstly, the variable create_using can be used to create an
430 empty digraph, multigraph, etc. For example,
431
432 >>> n = 10
433 >>> G = nx.empty_graph(n, create_using=nx.DiGraph)
434
435 will create an empty digraph on n nodes.
436
437 Secondly, one can pass an existing graph (digraph, multigraph,
438 etc.) via create_using. For example, if G is an existing graph
439 (resp. digraph, multigraph, etc.), then empty_graph(n, create_using=G)
440 will empty G (i.e. delete all nodes and edges using G.clear())
441 and then add n nodes and zero edges, and return the modified graph.
442
443 Thirdly, when constructing your home-grown graph creation function
444 you can use empty_graph to construct the graph by passing a user
445 defined create_using to empty_graph. In this case, if you want the
446 default constructor to be other than nx.Graph, specify `default`.
447
448 >>> def mygraph(n, create_using=None):
449 ... G = nx.empty_graph(n, create_using, nx.MultiGraph)
450 ... G.add_edges_from([(0, 1), (0, 1)])
451 ... return G
452 >>> G = mygraph(3)
453 >>> G.is_multigraph()
454 True
455 >>> G = mygraph(3, nx.Graph)
456 >>> G.is_multigraph()
457 False
458
459 See also create_empty_copy(G).
460
461 """
462 if create_using is None:
463 G = default()
464 elif hasattr(create_using, '_adj'):
465 # create_using is a NetworkX style Graph
466 create_using.clear()
467 G = create_using
468 else:
469 # try create_using as constructor
470 G = create_using()
471
472 n_name, nodes = n
473 G.add_nodes_from(nodes)
474 return G
475
476
477 def ladder_graph(n, create_using=None):
478 """Returns the Ladder graph of length n.
479
480 This is two paths of n nodes, with
481 each pair connected by a single edge.
482
483 Node labels are the integers 0 to 2*n - 1.
484
485 """
486 G = empty_graph(2 * n, create_using)
487 if G.is_directed():
488 raise NetworkXError("Directed Graph not supported")
489 G.add_edges_from(pairwise(range(n)))
490 G.add_edges_from(pairwise(range(n, 2 * n)))
491 G.add_edges_from((v, v + n) for v in range(n))
492 return G
493
494
495 @nodes_or_number([0, 1])
496 def lollipop_graph(m, n, create_using=None):
497 """Returns the Lollipop Graph; `K_m` connected to `P_n`.
498
499 This is the Barbell Graph without the right barbell.
500
501 Parameters
502 ----------
503 m, n : int or iterable container of nodes (default = 0)
504 If an integer, nodes are from `range(m)` and `range(m,m+n)`.
505 If a container, the entries are the coordinate of the node.
506
507 The nodes for m appear in the complete graph $K_m$ and the nodes
508 for n appear in the path $P_n$
509 create_using : NetworkX graph constructor, optional (default=nx.Graph)
510 Graph type to create. If graph instance, then cleared before populated.
511
512 Notes
513 -----
514 The 2 subgraphs are joined via an edge (m-1, m).
515 If n=0, this is merely a complete graph.
516
517 (This graph is an extremal example in David Aldous and Jim
518 Fill's etext on Random Walks on Graphs.)
519
520 """
521 m, m_nodes = m
522 n, n_nodes = n
523 M = len(m_nodes)
524 N = len(n_nodes)
525 if isinstance(m, int):
526 n_nodes = [len(m_nodes) + i for i in n_nodes]
527 if M < 2:
528 raise NetworkXError(
529 "Invalid graph description, m should be >=2")
530 if N < 0:
531 raise NetworkXError(
532 "Invalid graph description, n should be >=0")
533
534 # the ball
535 G = complete_graph(m_nodes, create_using)
536 if G.is_directed():
537 raise NetworkXError("Directed Graph not supported")
538 # the stick
539 G.add_nodes_from(n_nodes)
540 if N > 1:
541 G.add_edges_from(pairwise(n_nodes))
542 # connect ball to stick
543 if M > 0 and N > 0:
544 G.add_edge(m_nodes[-1], n_nodes[0])
545 return G
546
547
548 def null_graph(create_using=None):
549 """Returns the Null graph with no nodes or edges.
550
551 See empty_graph for the use of create_using.
552
553 """
554 G = empty_graph(0, create_using)
555 return G
556
557
558 @nodes_or_number(0)
559 def path_graph(n, create_using=None):
560 """Returns the Path graph `P_n` of linearly connected nodes.
561
562 Parameters
563 ----------
564 n : int or iterable
565 If an integer, node labels are 0 to n with center 0.
566 If an iterable of nodes, the center is the first.
567 create_using : NetworkX graph constructor, optional (default=nx.Graph)
568 Graph type to create. If graph instance, then cleared before populated.
569
570 """
571 n_name, nodes = n
572 G = empty_graph(nodes, create_using)
573 G.add_edges_from(pairwise(nodes))
574 return G
575
576
577 @nodes_or_number(0)
578 def star_graph(n, create_using=None):
579 """ Return the star graph
580
581 The star graph consists of one center node connected to n outer nodes.
582
583 Parameters
584 ----------
585 n : int or iterable
586 If an integer, node labels are 0 to n with center 0.
587 If an iterable of nodes, the center is the first.
588 create_using : NetworkX graph constructor, optional (default=nx.Graph)
589 Graph type to create. If graph instance, then cleared before populated.
590
591 Notes
592 -----
593 The graph has n+1 nodes for integer n.
594 So star_graph(3) is the same as star_graph(range(4)).
595 """
596 n_name, nodes = n
597 if isinstance(n_name, int):
598 nodes = nodes + [n_name] # there should be n+1 nodes
599 first = nodes[0]
600 G = empty_graph(nodes, create_using)
601 if G.is_directed():
602 raise NetworkXError("Directed Graph not supported")
603 G.add_edges_from((first, v) for v in nodes[1:])
604 return G
605
606
607 def trivial_graph(create_using=None):
608 """ Return the Trivial graph with one node (with label 0) and no edges.
609
610 """
611 G = empty_graph(1, create_using)
612 return G
613
614
615 def turan_graph(n, r):
616 r""" Return the Turan Graph
617
618 The Turan Graph is a complete multipartite graph on $n$ vertices
619 with $r$ disjoint subsets. It is the graph with the edges for any graph with
620 $n$ vertices and $r$ disjoint subsets.
621
622 Given $n$ and $r$, we generate a complete multipartite graph with
623 $r-(n \mod r)$ partitions of size $n/r$, rounded down, and
624 $n \mod r$ partitions of size $n/r+1$, rounded down.
625
626 Parameters
627 ----------
628 n : int
629 The number of vertices.
630 r : int
631 The number of partitions.
632 Must be less than or equal to n.
633
634 Notes
635 -----
636 Must satisfy $1 <= r <= n$.
637 The graph has $(r-1)(n^2)/(2r)$ edges, rounded down.
638 """
639
640 if not 1 <= r <= n:
641 raise NetworkXError("Must satisfy 1 <= r <= n")
642
643 partitions = [n // r] * (r - (n % r)) + [n // r + 1] * (n % r)
644 G = complete_multipartite_graph(*partitions)
645 return G
646
647
648 @nodes_or_number(0)
649 def wheel_graph(n, create_using=None):
650 """ Return the wheel graph
651
652 The wheel graph consists of a hub node connected to a cycle of (n-1) nodes.
653
654 Parameters
655 ----------
656 n : int or iterable
657 If an integer, node labels are 0 to n with center 0.
658 If an iterable of nodes, the center is the first.
659 create_using : NetworkX graph constructor, optional (default=nx.Graph)
660 Graph type to create. If graph instance, then cleared before populated.
661
662 Node labels are the integers 0 to n - 1.
663 """
664 n_name, nodes = n
665 if n_name == 0:
666 G = empty_graph(0, create_using)
667 return G
668 G = star_graph(nodes, create_using)
669 if len(G) > 2:
670 G.add_edges_from(pairwise(nodes[1:]))
671 G.add_edge(nodes[-1], nodes[1])
672 return G
673
674
675 def complete_multipartite_graph(*subset_sizes):
676 """Returns the complete multipartite graph with the specified subset sizes.
677
678 Parameters
679 ----------
680 subset_sizes : tuple of integers or tuple of node iterables
681 The arguments can either all be integer number of nodes or they
682 can all be iterables of nodes. If integers, they represent the
683 number of vertices in each subset of the multipartite graph.
684 If iterables, each is used to create the nodes for that subset.
685 The length of subset_sizes is the number of subsets.
686
687 Returns
688 -------
689 G : NetworkX Graph
690 Returns the complete multipartite graph with the specified subsets.
691
692 For each node, the node attribute 'subset' is an integer
693 indicating which subset contains the node.
694
695 Examples
696 --------
697 Creating a complete tripartite graph, with subsets of one, two, and three
698 vertices, respectively.
699
700 >>> import networkx as nx
701 >>> G = nx.complete_multipartite_graph(1, 2, 3)
702 >>> [G.nodes[u]['subset'] for u in G]
703 [0, 1, 1, 2, 2, 2]
704 >>> list(G.edges(0))
705 [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]
706 >>> list(G.edges(2))
707 [(2, 0), (2, 3), (2, 4), (2, 5)]
708 >>> list(G.edges(4))
709 [(4, 0), (4, 1), (4, 2)]
710
711 >>> G = nx.complete_multipartite_graph('a', 'bc', 'def')
712 >>> [G.nodes[u]['subset'] for u in sorted(G)]
713 [0, 1, 1, 2, 2, 2]
714
715 Notes
716 -----
717 This function generalizes several other graph generator functions.
718
719 - If no subset sizes are given, this returns the null graph.
720 - If a single subset size `n` is given, this returns the empty graph on
721 `n` nodes.
722 - If two subset sizes `m` and `n` are given, this returns the complete
723 bipartite graph on `m + n` nodes.
724 - If subset sizes `1` and `n` are given, this returns the star graph on
725 `n + 1` nodes.
726
727 See also
728 --------
729 complete_bipartite_graph
730 """
731 # The complete multipartite graph is an undirected simple graph.
732 G = Graph()
733
734 if len(subset_sizes) == 0:
735 return G
736
737 # set up subsets of nodes
738 try:
739 extents = pairwise(accumulate((0,) + subset_sizes))
740 subsets = [range(start, end) for start, end in extents]
741 except TypeError:
742 subsets = subset_sizes
743
744 # add nodes with subset attribute
745 # while checking that ints are not mixed with iterables
746 try:
747 for (i, subset) in enumerate(subsets):
748 G.add_nodes_from(subset, subset=i)
749 except TypeError:
750 raise NetworkXError("Arguments must be all ints or all iterables")
751
752 # Across subsets, all vertices should be adjacent.
753 # We can use itertools.combinations() because undirected.
754 for subset1, subset2 in itertools.combinations(subsets, 2):
755 G.add_edges_from(itertools.product(subset1, subset2))
756 return G