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