Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/drawing/layout.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 """ | |
2 ****** | |
3 Layout | |
4 ****** | |
5 | |
6 Node positioning algorithms for graph drawing. | |
7 | |
8 For `random_layout()` the possible resulting shape | |
9 is a square of side [0, scale] (default: [0, 1]) | |
10 Changing `center` shifts the layout by that amount. | |
11 | |
12 For the other layout routines, the extent is | |
13 [center - scale, center + scale] (default: [-1, 1]). | |
14 | |
15 Warning: Most layout routines have only been tested in 2-dimensions. | |
16 | |
17 """ | |
18 import networkx as nx | |
19 from networkx.utils import random_state | |
20 | |
21 __all__ = [ | |
22 "bipartite_layout", | |
23 "circular_layout", | |
24 "kamada_kawai_layout", | |
25 "random_layout", | |
26 "rescale_layout", | |
27 "rescale_layout_dict", | |
28 "shell_layout", | |
29 "spring_layout", | |
30 "spectral_layout", | |
31 "planar_layout", | |
32 "fruchterman_reingold_layout", | |
33 "spiral_layout", | |
34 "multipartite_layout", | |
35 ] | |
36 | |
37 | |
38 def _process_params(G, center, dim): | |
39 # Some boilerplate code. | |
40 import numpy as np | |
41 | |
42 if not isinstance(G, nx.Graph): | |
43 empty_graph = nx.Graph() | |
44 empty_graph.add_nodes_from(G) | |
45 G = empty_graph | |
46 | |
47 if center is None: | |
48 center = np.zeros(dim) | |
49 else: | |
50 center = np.asarray(center) | |
51 | |
52 if len(center) != dim: | |
53 msg = "length of center coordinates must match dimension of layout" | |
54 raise ValueError(msg) | |
55 | |
56 return G, center | |
57 | |
58 | |
59 @random_state(3) | |
60 def random_layout(G, center=None, dim=2, seed=None): | |
61 """Position nodes uniformly at random in the unit square. | |
62 | |
63 For every node, a position is generated by choosing each of dim | |
64 coordinates uniformly at random on the interval [0.0, 1.0). | |
65 | |
66 NumPy (http://scipy.org) is required for this function. | |
67 | |
68 Parameters | |
69 ---------- | |
70 G : NetworkX graph or list of nodes | |
71 A position will be assigned to every node in G. | |
72 | |
73 center : array-like or None | |
74 Coordinate pair around which to center the layout. | |
75 | |
76 dim : int | |
77 Dimension of layout. | |
78 | |
79 seed : int, RandomState instance or None optional (default=None) | |
80 Set the random state for deterministic node layouts. | |
81 If int, `seed` is the seed used by the random number generator, | |
82 if numpy.random.RandomState instance, `seed` is the random | |
83 number generator, | |
84 if None, the random number generator is the RandomState instance used | |
85 by numpy.random. | |
86 | |
87 Returns | |
88 ------- | |
89 pos : dict | |
90 A dictionary of positions keyed by node | |
91 | |
92 Examples | |
93 -------- | |
94 >>> G = nx.lollipop_graph(4, 3) | |
95 >>> pos = nx.random_layout(G) | |
96 | |
97 """ | |
98 import numpy as np | |
99 | |
100 G, center = _process_params(G, center, dim) | |
101 pos = seed.rand(len(G), dim) + center | |
102 pos = pos.astype(np.float32) | |
103 pos = dict(zip(G, pos)) | |
104 | |
105 return pos | |
106 | |
107 | |
108 def circular_layout(G, scale=1, center=None, dim=2): | |
109 # dim=2 only | |
110 """Position nodes on a circle. | |
111 | |
112 Parameters | |
113 ---------- | |
114 G : NetworkX graph or list of nodes | |
115 A position will be assigned to every node in G. | |
116 | |
117 scale : number (default: 1) | |
118 Scale factor for positions. | |
119 | |
120 center : array-like or None | |
121 Coordinate pair around which to center the layout. | |
122 | |
123 dim : int | |
124 Dimension of layout. | |
125 If dim>2, the remaining dimensions are set to zero | |
126 in the returned positions. | |
127 If dim<2, a ValueError is raised. | |
128 | |
129 Returns | |
130 ------- | |
131 pos : dict | |
132 A dictionary of positions keyed by node | |
133 | |
134 Raises | |
135 ------- | |
136 ValueError | |
137 If dim < 2 | |
138 | |
139 Examples | |
140 -------- | |
141 >>> G = nx.path_graph(4) | |
142 >>> pos = nx.circular_layout(G) | |
143 | |
144 Notes | |
145 ----- | |
146 This algorithm currently only works in two dimensions and does not | |
147 try to minimize edge crossings. | |
148 | |
149 """ | |
150 import numpy as np | |
151 | |
152 if dim < 2: | |
153 raise ValueError("cannot handle dimensions < 2") | |
154 | |
155 G, center = _process_params(G, center, dim) | |
156 | |
157 paddims = max(0, (dim - 2)) | |
158 | |
159 if len(G) == 0: | |
160 pos = {} | |
161 elif len(G) == 1: | |
162 pos = {nx.utils.arbitrary_element(G): center} | |
163 else: | |
164 # Discard the extra angle since it matches 0 radians. | |
165 theta = np.linspace(0, 1, len(G) + 1)[:-1] * 2 * np.pi | |
166 theta = theta.astype(np.float32) | |
167 pos = np.column_stack( | |
168 [np.cos(theta), np.sin(theta), np.zeros((len(G), paddims))] | |
169 ) | |
170 pos = rescale_layout(pos, scale=scale) + center | |
171 pos = dict(zip(G, pos)) | |
172 | |
173 return pos | |
174 | |
175 | |
176 def shell_layout(G, nlist=None, rotate=None, scale=1, center=None, dim=2): | |
177 """Position nodes in concentric circles. | |
178 | |
179 Parameters | |
180 ---------- | |
181 G : NetworkX graph or list of nodes | |
182 A position will be assigned to every node in G. | |
183 | |
184 nlist : list of lists | |
185 List of node lists for each shell. | |
186 | |
187 rotate : angle in radians (default=pi/len(nlist)) | |
188 Angle by which to rotate the starting position of each shell | |
189 relative to the starting position of the previous shell. | |
190 To recreate behavior before v2.5 use rotate=0. | |
191 | |
192 scale : number (default: 1) | |
193 Scale factor for positions. | |
194 | |
195 center : array-like or None | |
196 Coordinate pair around which to center the layout. | |
197 | |
198 dim : int | |
199 Dimension of layout, currently only dim=2 is supported. | |
200 Other dimension values result in a ValueError. | |
201 | |
202 Returns | |
203 ------- | |
204 pos : dict | |
205 A dictionary of positions keyed by node | |
206 | |
207 Raises | |
208 ------- | |
209 ValueError | |
210 If dim != 2 | |
211 | |
212 Examples | |
213 -------- | |
214 >>> G = nx.path_graph(4) | |
215 >>> shells = [[0], [1, 2, 3]] | |
216 >>> pos = nx.shell_layout(G, shells) | |
217 | |
218 Notes | |
219 ----- | |
220 This algorithm currently only works in two dimensions and does not | |
221 try to minimize edge crossings. | |
222 | |
223 """ | |
224 import numpy as np | |
225 | |
226 if dim != 2: | |
227 raise ValueError("can only handle 2 dimensions") | |
228 | |
229 G, center = _process_params(G, center, dim) | |
230 | |
231 if len(G) == 0: | |
232 return {} | |
233 if len(G) == 1: | |
234 return {nx.utils.arbitrary_element(G): center} | |
235 | |
236 if nlist is None: | |
237 # draw the whole graph in one shell | |
238 nlist = [list(G)] | |
239 | |
240 radius_bump = scale / len(nlist) | |
241 | |
242 if len(nlist[0]) == 1: | |
243 # single node at center | |
244 radius = 0.0 | |
245 else: | |
246 # else start at r=1 | |
247 radius = radius_bump | |
248 | |
249 if rotate is None: | |
250 rotate = np.pi / len(nlist) | |
251 first_theta = rotate | |
252 npos = {} | |
253 for nodes in nlist: | |
254 # Discard the last angle (endpoint=False) since 2*pi matches 0 radians | |
255 theta = ( | |
256 np.linspace(0, 2 * np.pi, len(nodes), endpoint=False, dtype=np.float32) | |
257 + first_theta | |
258 ) | |
259 pos = radius * np.column_stack([np.cos(theta), np.sin(theta)]) + center | |
260 npos.update(zip(nodes, pos)) | |
261 radius += radius_bump | |
262 first_theta += rotate | |
263 | |
264 return npos | |
265 | |
266 | |
267 def bipartite_layout( | |
268 G, nodes, align="vertical", scale=1, center=None, aspect_ratio=4 / 3 | |
269 ): | |
270 """Position nodes in two straight lines. | |
271 | |
272 Parameters | |
273 ---------- | |
274 G : NetworkX graph or list of nodes | |
275 A position will be assigned to every node in G. | |
276 | |
277 nodes : list or container | |
278 Nodes in one node set of the bipartite graph. | |
279 This set will be placed on left or top. | |
280 | |
281 align : string (default='vertical') | |
282 The alignment of nodes. Vertical or horizontal. | |
283 | |
284 scale : number (default: 1) | |
285 Scale factor for positions. | |
286 | |
287 center : array-like or None | |
288 Coordinate pair around which to center the layout. | |
289 | |
290 aspect_ratio : number (default=4/3): | |
291 The ratio of the width to the height of the layout. | |
292 | |
293 Returns | |
294 ------- | |
295 pos : dict | |
296 A dictionary of positions keyed by node. | |
297 | |
298 Examples | |
299 -------- | |
300 >>> G = nx.bipartite.gnmk_random_graph(3, 5, 10, seed=123) | |
301 >>> top = nx.bipartite.sets(G)[0] | |
302 >>> pos = nx.bipartite_layout(G, top) | |
303 | |
304 Notes | |
305 ----- | |
306 This algorithm currently only works in two dimensions and does not | |
307 try to minimize edge crossings. | |
308 | |
309 """ | |
310 | |
311 import numpy as np | |
312 | |
313 G, center = _process_params(G, center=center, dim=2) | |
314 if len(G) == 0: | |
315 return {} | |
316 | |
317 height = 1 | |
318 width = aspect_ratio * height | |
319 offset = (width / 2, height / 2) | |
320 | |
321 top = set(nodes) | |
322 bottom = set(G) - top | |
323 nodes = list(top) + list(bottom) | |
324 | |
325 if align == "vertical": | |
326 left_xs = np.repeat(0, len(top)) | |
327 right_xs = np.repeat(width, len(bottom)) | |
328 left_ys = np.linspace(0, height, len(top)) | |
329 right_ys = np.linspace(0, height, len(bottom)) | |
330 | |
331 top_pos = np.column_stack([left_xs, left_ys]) - offset | |
332 bottom_pos = np.column_stack([right_xs, right_ys]) - offset | |
333 | |
334 pos = np.concatenate([top_pos, bottom_pos]) | |
335 pos = rescale_layout(pos, scale=scale) + center | |
336 pos = dict(zip(nodes, pos)) | |
337 return pos | |
338 | |
339 if align == "horizontal": | |
340 top_ys = np.repeat(height, len(top)) | |
341 bottom_ys = np.repeat(0, len(bottom)) | |
342 top_xs = np.linspace(0, width, len(top)) | |
343 bottom_xs = np.linspace(0, width, len(bottom)) | |
344 | |
345 top_pos = np.column_stack([top_xs, top_ys]) - offset | |
346 bottom_pos = np.column_stack([bottom_xs, bottom_ys]) - offset | |
347 | |
348 pos = np.concatenate([top_pos, bottom_pos]) | |
349 pos = rescale_layout(pos, scale=scale) + center | |
350 pos = dict(zip(nodes, pos)) | |
351 return pos | |
352 | |
353 msg = "align must be either vertical or horizontal." | |
354 raise ValueError(msg) | |
355 | |
356 | |
357 @random_state(10) | |
358 def fruchterman_reingold_layout( | |
359 G, | |
360 k=None, | |
361 pos=None, | |
362 fixed=None, | |
363 iterations=50, | |
364 threshold=1e-4, | |
365 weight="weight", | |
366 scale=1, | |
367 center=None, | |
368 dim=2, | |
369 seed=None, | |
370 ): | |
371 """Position nodes using Fruchterman-Reingold force-directed algorithm. | |
372 | |
373 The algorithm simulates a force-directed representation of the network | |
374 treating edges as springs holding nodes close, while treating nodes | |
375 as repelling objects, sometimes called an anti-gravity force. | |
376 Simulation continues until the positions are close to an equilibrium. | |
377 | |
378 There are some hard-coded values: minimal distance between | |
379 nodes (0.01) and "temperature" of 0.1 to ensure nodes don't fly away. | |
380 During the simulation, `k` helps determine the distance between nodes, | |
381 though `scale` and `center` determine the size and place after | |
382 rescaling occurs at the end of the simulation. | |
383 | |
384 Fixing some nodes doesn't allow them to move in the simulation. | |
385 It also turns off the rescaling feature at the simulation's end. | |
386 In addition, setting `scale` to `None` turns off rescaling. | |
387 | |
388 Parameters | |
389 ---------- | |
390 G : NetworkX graph or list of nodes | |
391 A position will be assigned to every node in G. | |
392 | |
393 k : float (default=None) | |
394 Optimal distance between nodes. If None the distance is set to | |
395 1/sqrt(n) where n is the number of nodes. Increase this value | |
396 to move nodes farther apart. | |
397 | |
398 pos : dict or None optional (default=None) | |
399 Initial positions for nodes as a dictionary with node as keys | |
400 and values as a coordinate list or tuple. If None, then use | |
401 random initial positions. | |
402 | |
403 fixed : list or None optional (default=None) | |
404 Nodes to keep fixed at initial position. | |
405 ValueError raised if `fixed` specified and `pos` not. | |
406 | |
407 iterations : int optional (default=50) | |
408 Maximum number of iterations taken | |
409 | |
410 threshold: float optional (default = 1e-4) | |
411 Threshold for relative error in node position changes. | |
412 The iteration stops if the error is below this threshold. | |
413 | |
414 weight : string or None optional (default='weight') | |
415 The edge attribute that holds the numerical value used for | |
416 the edge weight. If None, then all edge weights are 1. | |
417 | |
418 scale : number or None (default: 1) | |
419 Scale factor for positions. Not used unless `fixed is None`. | |
420 If scale is None, no rescaling is performed. | |
421 | |
422 center : array-like or None | |
423 Coordinate pair around which to center the layout. | |
424 Not used unless `fixed is None`. | |
425 | |
426 dim : int | |
427 Dimension of layout. | |
428 | |
429 seed : int, RandomState instance or None optional (default=None) | |
430 Set the random state for deterministic node layouts. | |
431 If int, `seed` is the seed used by the random number generator, | |
432 if numpy.random.RandomState instance, `seed` is the random | |
433 number generator, | |
434 if None, the random number generator is the RandomState instance used | |
435 by numpy.random. | |
436 | |
437 Returns | |
438 ------- | |
439 pos : dict | |
440 A dictionary of positions keyed by node | |
441 | |
442 Examples | |
443 -------- | |
444 >>> G = nx.path_graph(4) | |
445 >>> pos = nx.spring_layout(G) | |
446 | |
447 # The same using longer but equivalent function name | |
448 >>> pos = nx.fruchterman_reingold_layout(G) | |
449 """ | |
450 import numpy as np | |
451 | |
452 G, center = _process_params(G, center, dim) | |
453 | |
454 if fixed is not None: | |
455 if pos is None: | |
456 raise ValueError("nodes are fixed without positions given") | |
457 for node in fixed: | |
458 if node not in pos: | |
459 raise ValueError("nodes are fixed without positions given") | |
460 nfixed = {node: i for i, node in enumerate(G)} | |
461 fixed = np.asarray([nfixed[node] for node in fixed]) | |
462 | |
463 if pos is not None: | |
464 # Determine size of existing domain to adjust initial positions | |
465 dom_size = max(coord for pos_tup in pos.values() for coord in pos_tup) | |
466 if dom_size == 0: | |
467 dom_size = 1 | |
468 pos_arr = seed.rand(len(G), dim) * dom_size + center | |
469 | |
470 for i, n in enumerate(G): | |
471 if n in pos: | |
472 pos_arr[i] = np.asarray(pos[n]) | |
473 else: | |
474 pos_arr = None | |
475 dom_size = 1 | |
476 | |
477 if len(G) == 0: | |
478 return {} | |
479 if len(G) == 1: | |
480 return {nx.utils.arbitrary_element(G.nodes()): center} | |
481 | |
482 try: | |
483 # Sparse matrix | |
484 if len(G) < 500: # sparse solver for large graphs | |
485 raise ValueError | |
486 A = nx.to_scipy_sparse_matrix(G, weight=weight, dtype="f") | |
487 if k is None and fixed is not None: | |
488 # We must adjust k by domain size for layouts not near 1x1 | |
489 nnodes, _ = A.shape | |
490 k = dom_size / np.sqrt(nnodes) | |
491 pos = _sparse_fruchterman_reingold( | |
492 A, k, pos_arr, fixed, iterations, threshold, dim, seed | |
493 ) | |
494 except ValueError: | |
495 A = nx.to_numpy_array(G, weight=weight) | |
496 if k is None and fixed is not None: | |
497 # We must adjust k by domain size for layouts not near 1x1 | |
498 nnodes, _ = A.shape | |
499 k = dom_size / np.sqrt(nnodes) | |
500 pos = _fruchterman_reingold( | |
501 A, k, pos_arr, fixed, iterations, threshold, dim, seed | |
502 ) | |
503 if fixed is None and scale is not None: | |
504 pos = rescale_layout(pos, scale=scale) + center | |
505 pos = dict(zip(G, pos)) | |
506 return pos | |
507 | |
508 | |
509 spring_layout = fruchterman_reingold_layout | |
510 | |
511 | |
512 @random_state(7) | |
513 def _fruchterman_reingold( | |
514 A, k=None, pos=None, fixed=None, iterations=50, threshold=1e-4, dim=2, seed=None | |
515 ): | |
516 # Position nodes in adjacency matrix A using Fruchterman-Reingold | |
517 # Entry point for NetworkX graph is fruchterman_reingold_layout() | |
518 import numpy as np | |
519 | |
520 try: | |
521 nnodes, _ = A.shape | |
522 except AttributeError as e: | |
523 msg = "fruchterman_reingold() takes an adjacency matrix as input" | |
524 raise nx.NetworkXError(msg) from e | |
525 | |
526 if pos is None: | |
527 # random initial positions | |
528 pos = np.asarray(seed.rand(nnodes, dim), dtype=A.dtype) | |
529 else: | |
530 # make sure positions are of same type as matrix | |
531 pos = pos.astype(A.dtype) | |
532 | |
533 # optimal distance between nodes | |
534 if k is None: | |
535 k = np.sqrt(1.0 / nnodes) | |
536 # the initial "temperature" is about .1 of domain area (=1x1) | |
537 # this is the largest step allowed in the dynamics. | |
538 # We need to calculate this in case our fixed positions force our domain | |
539 # to be much bigger than 1x1 | |
540 t = max(max(pos.T[0]) - min(pos.T[0]), max(pos.T[1]) - min(pos.T[1])) * 0.1 | |
541 # simple cooling scheme. | |
542 # linearly step down by dt on each iteration so last iteration is size dt. | |
543 dt = t / float(iterations + 1) | |
544 delta = np.zeros((pos.shape[0], pos.shape[0], pos.shape[1]), dtype=A.dtype) | |
545 # the inscrutable (but fast) version | |
546 # this is still O(V^2) | |
547 # could use multilevel methods to speed this up significantly | |
548 for iteration in range(iterations): | |
549 # matrix of difference between points | |
550 delta = pos[:, np.newaxis, :] - pos[np.newaxis, :, :] | |
551 # distance between points | |
552 distance = np.linalg.norm(delta, axis=-1) | |
553 # enforce minimum distance of 0.01 | |
554 np.clip(distance, 0.01, None, out=distance) | |
555 # displacement "force" | |
556 displacement = np.einsum( | |
557 "ijk,ij->ik", delta, (k * k / distance ** 2 - A * distance / k) | |
558 ) | |
559 # update positions | |
560 length = np.linalg.norm(displacement, axis=-1) | |
561 length = np.where(length < 0.01, 0.1, length) | |
562 delta_pos = np.einsum("ij,i->ij", displacement, t / length) | |
563 if fixed is not None: | |
564 # don't change positions of fixed nodes | |
565 delta_pos[fixed] = 0.0 | |
566 pos += delta_pos | |
567 # cool temperature | |
568 t -= dt | |
569 err = np.linalg.norm(delta_pos) / nnodes | |
570 if err < threshold: | |
571 break | |
572 return pos | |
573 | |
574 | |
575 @random_state(7) | |
576 def _sparse_fruchterman_reingold( | |
577 A, k=None, pos=None, fixed=None, iterations=50, threshold=1e-4, dim=2, seed=None | |
578 ): | |
579 # Position nodes in adjacency matrix A using Fruchterman-Reingold | |
580 # Entry point for NetworkX graph is fruchterman_reingold_layout() | |
581 # Sparse version | |
582 import numpy as np | |
583 | |
584 try: | |
585 nnodes, _ = A.shape | |
586 except AttributeError as e: | |
587 msg = "fruchterman_reingold() takes an adjacency matrix as input" | |
588 raise nx.NetworkXError(msg) from e | |
589 try: | |
590 from scipy.sparse import coo_matrix | |
591 except ImportError as e: | |
592 msg = "_sparse_fruchterman_reingold() scipy numpy: http://scipy.org/ " | |
593 raise ImportError(msg) from e | |
594 # make sure we have a LIst of Lists representation | |
595 try: | |
596 A = A.tolil() | |
597 except AttributeError: | |
598 A = (coo_matrix(A)).tolil() | |
599 | |
600 if pos is None: | |
601 # random initial positions | |
602 pos = np.asarray(seed.rand(nnodes, dim), dtype=A.dtype) | |
603 else: | |
604 # make sure positions are of same type as matrix | |
605 pos = pos.astype(A.dtype) | |
606 | |
607 # no fixed nodes | |
608 if fixed is None: | |
609 fixed = [] | |
610 | |
611 # optimal distance between nodes | |
612 if k is None: | |
613 k = np.sqrt(1.0 / nnodes) | |
614 # the initial "temperature" is about .1 of domain area (=1x1) | |
615 # this is the largest step allowed in the dynamics. | |
616 t = max(max(pos.T[0]) - min(pos.T[0]), max(pos.T[1]) - min(pos.T[1])) * 0.1 | |
617 # simple cooling scheme. | |
618 # linearly step down by dt on each iteration so last iteration is size dt. | |
619 dt = t / float(iterations + 1) | |
620 | |
621 displacement = np.zeros((dim, nnodes)) | |
622 for iteration in range(iterations): | |
623 displacement *= 0 | |
624 # loop over rows | |
625 for i in range(A.shape[0]): | |
626 if i in fixed: | |
627 continue | |
628 # difference between this row's node position and all others | |
629 delta = (pos[i] - pos).T | |
630 # distance between points | |
631 distance = np.sqrt((delta ** 2).sum(axis=0)) | |
632 # enforce minimum distance of 0.01 | |
633 distance = np.where(distance < 0.01, 0.01, distance) | |
634 # the adjacency matrix row | |
635 Ai = np.asarray(A.getrowview(i).toarray()) | |
636 # displacement "force" | |
637 displacement[:, i] += ( | |
638 delta * (k * k / distance ** 2 - Ai * distance / k) | |
639 ).sum(axis=1) | |
640 # update positions | |
641 length = np.sqrt((displacement ** 2).sum(axis=0)) | |
642 length = np.where(length < 0.01, 0.1, length) | |
643 delta_pos = (displacement * t / length).T | |
644 pos += delta_pos | |
645 # cool temperature | |
646 t -= dt | |
647 err = np.linalg.norm(delta_pos) / nnodes | |
648 if err < threshold: | |
649 break | |
650 return pos | |
651 | |
652 | |
653 def kamada_kawai_layout( | |
654 G, dist=None, pos=None, weight="weight", scale=1, center=None, dim=2 | |
655 ): | |
656 """Position nodes using Kamada-Kawai path-length cost-function. | |
657 | |
658 Parameters | |
659 ---------- | |
660 G : NetworkX graph or list of nodes | |
661 A position will be assigned to every node in G. | |
662 | |
663 dist : dict (default=None) | |
664 A two-level dictionary of optimal distances between nodes, | |
665 indexed by source and destination node. | |
666 If None, the distance is computed using shortest_path_length(). | |
667 | |
668 pos : dict or None optional (default=None) | |
669 Initial positions for nodes as a dictionary with node as keys | |
670 and values as a coordinate list or tuple. If None, then use | |
671 circular_layout() for dim >= 2 and a linear layout for dim == 1. | |
672 | |
673 weight : string or None optional (default='weight') | |
674 The edge attribute that holds the numerical value used for | |
675 the edge weight. If None, then all edge weights are 1. | |
676 | |
677 scale : number (default: 1) | |
678 Scale factor for positions. | |
679 | |
680 center : array-like or None | |
681 Coordinate pair around which to center the layout. | |
682 | |
683 dim : int | |
684 Dimension of layout. | |
685 | |
686 Returns | |
687 ------- | |
688 pos : dict | |
689 A dictionary of positions keyed by node | |
690 | |
691 Examples | |
692 -------- | |
693 >>> G = nx.path_graph(4) | |
694 >>> pos = nx.kamada_kawai_layout(G) | |
695 """ | |
696 import numpy as np | |
697 | |
698 G, center = _process_params(G, center, dim) | |
699 nNodes = len(G) | |
700 if nNodes == 0: | |
701 return {} | |
702 | |
703 if dist is None: | |
704 dist = dict(nx.shortest_path_length(G, weight=weight)) | |
705 dist_mtx = 1e6 * np.ones((nNodes, nNodes)) | |
706 for row, nr in enumerate(G): | |
707 if nr not in dist: | |
708 continue | |
709 rdist = dist[nr] | |
710 for col, nc in enumerate(G): | |
711 if nc not in rdist: | |
712 continue | |
713 dist_mtx[row][col] = rdist[nc] | |
714 | |
715 if pos is None: | |
716 if dim >= 3: | |
717 pos = random_layout(G, dim=dim) | |
718 elif dim == 2: | |
719 pos = circular_layout(G, dim=dim) | |
720 else: | |
721 pos = {n: pt for n, pt in zip(G, np.linspace(0, 1, len(G)))} | |
722 pos_arr = np.array([pos[n] for n in G]) | |
723 | |
724 pos = _kamada_kawai_solve(dist_mtx, pos_arr, dim) | |
725 | |
726 pos = rescale_layout(pos, scale=scale) + center | |
727 return dict(zip(G, pos)) | |
728 | |
729 | |
730 def _kamada_kawai_solve(dist_mtx, pos_arr, dim): | |
731 # Anneal node locations based on the Kamada-Kawai cost-function, | |
732 # using the supplied matrix of preferred inter-node distances, | |
733 # and starting locations. | |
734 | |
735 import numpy as np | |
736 from scipy.optimize import minimize | |
737 | |
738 meanwt = 1e-3 | |
739 costargs = (np, 1 / (dist_mtx + np.eye(dist_mtx.shape[0]) * 1e-3), meanwt, dim) | |
740 | |
741 optresult = minimize( | |
742 _kamada_kawai_costfn, | |
743 pos_arr.ravel(), | |
744 method="L-BFGS-B", | |
745 args=costargs, | |
746 jac=True, | |
747 ) | |
748 | |
749 return optresult.x.reshape((-1, dim)) | |
750 | |
751 | |
752 def _kamada_kawai_costfn(pos_vec, np, invdist, meanweight, dim): | |
753 # Cost-function and gradient for Kamada-Kawai layout algorithm | |
754 nNodes = invdist.shape[0] | |
755 pos_arr = pos_vec.reshape((nNodes, dim)) | |
756 | |
757 delta = pos_arr[:, np.newaxis, :] - pos_arr[np.newaxis, :, :] | |
758 nodesep = np.linalg.norm(delta, axis=-1) | |
759 direction = np.einsum("ijk,ij->ijk", delta, 1 / (nodesep + np.eye(nNodes) * 1e-3)) | |
760 | |
761 offset = nodesep * invdist - 1.0 | |
762 offset[np.diag_indices(nNodes)] = 0 | |
763 | |
764 cost = 0.5 * np.sum(offset ** 2) | |
765 grad = np.einsum("ij,ij,ijk->ik", invdist, offset, direction) - np.einsum( | |
766 "ij,ij,ijk->jk", invdist, offset, direction | |
767 ) | |
768 | |
769 # Additional parabolic term to encourage mean position to be near origin: | |
770 sumpos = np.sum(pos_arr, axis=0) | |
771 cost += 0.5 * meanweight * np.sum(sumpos ** 2) | |
772 grad += meanweight * sumpos | |
773 | |
774 return (cost, grad.ravel()) | |
775 | |
776 | |
777 def spectral_layout(G, weight="weight", scale=1, center=None, dim=2): | |
778 """Position nodes using the eigenvectors of the graph Laplacian. | |
779 | |
780 Using the unnormalized Laplacian, the layout shows possible clusters of | |
781 nodes which are an approximation of the ratio cut. If dim is the number of | |
782 dimensions then the positions are the entries of the dim eigenvectors | |
783 corresponding to the ascending eigenvalues starting from the second one. | |
784 | |
785 Parameters | |
786 ---------- | |
787 G : NetworkX graph or list of nodes | |
788 A position will be assigned to every node in G. | |
789 | |
790 weight : string or None optional (default='weight') | |
791 The edge attribute that holds the numerical value used for | |
792 the edge weight. If None, then all edge weights are 1. | |
793 | |
794 scale : number (default: 1) | |
795 Scale factor for positions. | |
796 | |
797 center : array-like or None | |
798 Coordinate pair around which to center the layout. | |
799 | |
800 dim : int | |
801 Dimension of layout. | |
802 | |
803 Returns | |
804 ------- | |
805 pos : dict | |
806 A dictionary of positions keyed by node | |
807 | |
808 Examples | |
809 -------- | |
810 >>> G = nx.path_graph(4) | |
811 >>> pos = nx.spectral_layout(G) | |
812 | |
813 Notes | |
814 ----- | |
815 Directed graphs will be considered as undirected graphs when | |
816 positioning the nodes. | |
817 | |
818 For larger graphs (>500 nodes) this will use the SciPy sparse | |
819 eigenvalue solver (ARPACK). | |
820 """ | |
821 # handle some special cases that break the eigensolvers | |
822 import numpy as np | |
823 | |
824 G, center = _process_params(G, center, dim) | |
825 | |
826 if len(G) <= 2: | |
827 if len(G) == 0: | |
828 pos = np.array([]) | |
829 elif len(G) == 1: | |
830 pos = np.array([center]) | |
831 else: | |
832 pos = np.array([np.zeros(dim), np.array(center) * 2.0]) | |
833 return dict(zip(G, pos)) | |
834 try: | |
835 # Sparse matrix | |
836 if len(G) < 500: # dense solver is faster for small graphs | |
837 raise ValueError | |
838 A = nx.to_scipy_sparse_matrix(G, weight=weight, dtype="d") | |
839 # Symmetrize directed graphs | |
840 if G.is_directed(): | |
841 A = A + np.transpose(A) | |
842 pos = _sparse_spectral(A, dim) | |
843 except (ImportError, ValueError): | |
844 # Dense matrix | |
845 A = nx.to_numpy_array(G, weight=weight) | |
846 # Symmetrize directed graphs | |
847 if G.is_directed(): | |
848 A += A.T | |
849 pos = _spectral(A, dim) | |
850 | |
851 pos = rescale_layout(pos, scale=scale) + center | |
852 pos = dict(zip(G, pos)) | |
853 return pos | |
854 | |
855 | |
856 def _spectral(A, dim=2): | |
857 # Input adjacency matrix A | |
858 # Uses dense eigenvalue solver from numpy | |
859 import numpy as np | |
860 | |
861 try: | |
862 nnodes, _ = A.shape | |
863 except AttributeError as e: | |
864 msg = "spectral() takes an adjacency matrix as input" | |
865 raise nx.NetworkXError(msg) from e | |
866 | |
867 # form Laplacian matrix where D is diagonal of degrees | |
868 D = np.identity(nnodes, dtype=A.dtype) * np.sum(A, axis=1) | |
869 L = D - A | |
870 | |
871 eigenvalues, eigenvectors = np.linalg.eig(L) | |
872 # sort and keep smallest nonzero | |
873 index = np.argsort(eigenvalues)[1 : dim + 1] # 0 index is zero eigenvalue | |
874 return np.real(eigenvectors[:, index]) | |
875 | |
876 | |
877 def _sparse_spectral(A, dim=2): | |
878 # Input adjacency matrix A | |
879 # Uses sparse eigenvalue solver from scipy | |
880 # Could use multilevel methods here, see Koren "On spectral graph drawing" | |
881 import numpy as np | |
882 from scipy.sparse import spdiags | |
883 from scipy.sparse.linalg.eigen import eigsh | |
884 | |
885 try: | |
886 nnodes, _ = A.shape | |
887 except AttributeError as e: | |
888 msg = "sparse_spectral() takes an adjacency matrix as input" | |
889 raise nx.NetworkXError(msg) from e | |
890 | |
891 # form Laplacian matrix | |
892 data = np.asarray(A.sum(axis=1).T) | |
893 D = spdiags(data, 0, nnodes, nnodes) | |
894 L = D - A | |
895 | |
896 k = dim + 1 | |
897 # number of Lanczos vectors for ARPACK solver.What is the right scaling? | |
898 ncv = max(2 * k + 1, int(np.sqrt(nnodes))) | |
899 # return smallest k eigenvalues and eigenvectors | |
900 eigenvalues, eigenvectors = eigsh(L, k, which="SM", ncv=ncv) | |
901 index = np.argsort(eigenvalues)[1:k] # 0 index is zero eigenvalue | |
902 return np.real(eigenvectors[:, index]) | |
903 | |
904 | |
905 def planar_layout(G, scale=1, center=None, dim=2): | |
906 """Position nodes without edge intersections. | |
907 | |
908 Parameters | |
909 ---------- | |
910 G : NetworkX graph or list of nodes | |
911 A position will be assigned to every node in G. If G is of type | |
912 nx.PlanarEmbedding, the positions are selected accordingly. | |
913 | |
914 scale : number (default: 1) | |
915 Scale factor for positions. | |
916 | |
917 center : array-like or None | |
918 Coordinate pair around which to center the layout. | |
919 | |
920 dim : int | |
921 Dimension of layout. | |
922 | |
923 Returns | |
924 ------- | |
925 pos : dict | |
926 A dictionary of positions keyed by node | |
927 | |
928 Raises | |
929 ------ | |
930 NetworkXException | |
931 If G is not planar | |
932 | |
933 Examples | |
934 -------- | |
935 >>> G = nx.path_graph(4) | |
936 >>> pos = nx.planar_layout(G) | |
937 """ | |
938 import numpy as np | |
939 | |
940 if dim != 2: | |
941 raise ValueError("can only handle 2 dimensions") | |
942 | |
943 G, center = _process_params(G, center, dim) | |
944 | |
945 if len(G) == 0: | |
946 return {} | |
947 | |
948 if isinstance(G, nx.PlanarEmbedding): | |
949 embedding = G | |
950 else: | |
951 is_planar, embedding = nx.check_planarity(G) | |
952 if not is_planar: | |
953 raise nx.NetworkXException("G is not planar.") | |
954 pos = nx.combinatorial_embedding_to_pos(embedding) | |
955 node_list = list(embedding) | |
956 pos = np.row_stack([pos[x] for x in node_list]) | |
957 pos = pos.astype(np.float64) | |
958 pos = rescale_layout(pos, scale=scale) + center | |
959 return dict(zip(node_list, pos)) | |
960 | |
961 | |
962 def spiral_layout(G, scale=1, center=None, dim=2, resolution=0.35, equidistant=False): | |
963 """Position nodes in a spiral layout. | |
964 | |
965 Parameters | |
966 ---------- | |
967 G : NetworkX graph or list of nodes | |
968 A position will be assigned to every node in G. | |
969 scale : number (default: 1) | |
970 Scale factor for positions. | |
971 center : array-like or None | |
972 Coordinate pair around which to center the layout. | |
973 dim : int | |
974 Dimension of layout, currently only dim=2 is supported. | |
975 Other dimension values result in a ValueError. | |
976 resolution : float | |
977 The compactness of the spiral layout returned. | |
978 Lower values result in more compressed spiral layouts. | |
979 equidistant : bool | |
980 If True, nodes will be plotted equidistant from each other. | |
981 Returns | |
982 ------- | |
983 pos : dict | |
984 A dictionary of positions keyed by node | |
985 Raises | |
986 ------- | |
987 ValueError | |
988 If dim != 2 | |
989 | |
990 Examples | |
991 -------- | |
992 >>> G = nx.path_graph(4) | |
993 >>> pos = nx.spiral_layout(G) | |
994 | |
995 Notes | |
996 ----- | |
997 This algorithm currently only works in two dimensions. | |
998 | |
999 """ | |
1000 import numpy as np | |
1001 | |
1002 if dim != 2: | |
1003 raise ValueError("can only handle 2 dimensions") | |
1004 | |
1005 G, center = _process_params(G, center, dim) | |
1006 | |
1007 if len(G) == 0: | |
1008 return {} | |
1009 if len(G) == 1: | |
1010 return {nx.utils.arbitrary_element(G): center} | |
1011 | |
1012 pos = [] | |
1013 if equidistant: | |
1014 chord = 1 | |
1015 step = 0.5 | |
1016 theta = resolution | |
1017 for _ in range(len(G)): | |
1018 r = step * theta | |
1019 theta += chord / r | |
1020 pos.append([np.cos(theta) * r, np.sin(theta) * r]) | |
1021 | |
1022 else: | |
1023 # set the starting angle and step | |
1024 step = 1 | |
1025 angle = 0.0 | |
1026 dist = 0.0 | |
1027 # set the radius for the spiral to the number of nodes in the graph | |
1028 radius = len(G) | |
1029 | |
1030 while dist * np.hypot(np.cos(angle), np.sin(angle)) < radius: | |
1031 pos.append([dist * np.cos(angle), dist * np.sin(angle)]) | |
1032 dist += step | |
1033 angle += resolution | |
1034 | |
1035 pos = rescale_layout(np.array(pos), scale=scale) + center | |
1036 | |
1037 pos = dict(zip(G, pos)) | |
1038 | |
1039 return pos | |
1040 | |
1041 | |
1042 def multipartite_layout(G, subset_key="subset", align="vertical", scale=1, center=None): | |
1043 """Position nodes in layers of straight lines. | |
1044 | |
1045 Parameters | |
1046 ---------- | |
1047 G : NetworkX graph or list of nodes | |
1048 A position will be assigned to every node in G. | |
1049 | |
1050 subset_key : string (default='subset') | |
1051 Key of node data to be used as layer subset. | |
1052 | |
1053 align : string (default='vertical') | |
1054 The alignment of nodes. Vertical or horizontal. | |
1055 | |
1056 scale : number (default: 1) | |
1057 Scale factor for positions. | |
1058 | |
1059 center : array-like or None | |
1060 Coordinate pair around which to center the layout. | |
1061 | |
1062 Returns | |
1063 ------- | |
1064 pos : dict | |
1065 A dictionary of positions keyed by node. | |
1066 | |
1067 Examples | |
1068 -------- | |
1069 >>> G = nx.complete_multipartite_graph(28, 16, 10) | |
1070 >>> pos = nx.multipartite_layout(G) | |
1071 | |
1072 Notes | |
1073 ----- | |
1074 This algorithm currently only works in two dimensions and does not | |
1075 try to minimize edge crossings. | |
1076 | |
1077 Network does not need to be a complete multipartite graph. As long as nodes | |
1078 have subset_key data, they will be placed in the corresponding layers. | |
1079 | |
1080 """ | |
1081 import numpy as np | |
1082 | |
1083 G, center = _process_params(G, center=center, dim=2) | |
1084 if len(G) == 0: | |
1085 return {} | |
1086 | |
1087 layers = {} | |
1088 for v, data in G.nodes(data=True): | |
1089 try: | |
1090 layer = data[subset_key] | |
1091 except KeyError: | |
1092 msg = "all nodes must have subset_key (default='subset') as data" | |
1093 raise ValueError(msg) | |
1094 layers[layer] = [v] + layers.get(layer, []) | |
1095 | |
1096 pos = None | |
1097 nodes = [] | |
1098 if align == "vertical": | |
1099 width = len(layers) | |
1100 for i, layer in layers.items(): | |
1101 height = len(layer) | |
1102 xs = np.repeat(i, height) | |
1103 ys = np.arange(0, height, dtype=float) | |
1104 offset = ((width - 1) / 2, (height - 1) / 2) | |
1105 layer_pos = np.column_stack([xs, ys]) - offset | |
1106 if pos is None: | |
1107 pos = layer_pos | |
1108 else: | |
1109 pos = np.concatenate([pos, layer_pos]) | |
1110 nodes.extend(layer) | |
1111 pos = rescale_layout(pos, scale=scale) + center | |
1112 pos = dict(zip(nodes, pos)) | |
1113 return pos | |
1114 | |
1115 if align == "horizontal": | |
1116 height = len(layers) | |
1117 for i, layer in layers.items(): | |
1118 width = len(layer) | |
1119 xs = np.arange(0, width, dtype=float) | |
1120 ys = np.repeat(i, width) | |
1121 offset = ((width - 1) / 2, (height - 1) / 2) | |
1122 layer_pos = np.column_stack([xs, ys]) - offset | |
1123 if pos is None: | |
1124 pos = layer_pos | |
1125 else: | |
1126 pos = np.concatenate([pos, layer_pos]) | |
1127 nodes.extend(layer) | |
1128 pos = rescale_layout(pos, scale=scale) + center | |
1129 pos = dict(zip(nodes, pos)) | |
1130 return pos | |
1131 | |
1132 msg = "align must be either vertical or horizontal." | |
1133 raise ValueError(msg) | |
1134 | |
1135 | |
1136 def rescale_layout(pos, scale=1): | |
1137 """Returns scaled position array to (-scale, scale) in all axes. | |
1138 | |
1139 The function acts on NumPy arrays which hold position information. | |
1140 Each position is one row of the array. The dimension of the space | |
1141 equals the number of columns. Each coordinate in one column. | |
1142 | |
1143 To rescale, the mean (center) is subtracted from each axis separately. | |
1144 Then all values are scaled so that the largest magnitude value | |
1145 from all axes equals `scale` (thus, the aspect ratio is preserved). | |
1146 The resulting NumPy Array is returned (order of rows unchanged). | |
1147 | |
1148 Parameters | |
1149 ---------- | |
1150 pos : numpy array | |
1151 positions to be scaled. Each row is a position. | |
1152 | |
1153 scale : number (default: 1) | |
1154 The size of the resulting extent in all directions. | |
1155 | |
1156 Returns | |
1157 ------- | |
1158 pos : numpy array | |
1159 scaled positions. Each row is a position. | |
1160 | |
1161 See Also | |
1162 -------- | |
1163 rescale_layout_dict | |
1164 """ | |
1165 # Find max length over all dimensions | |
1166 lim = 0 # max coordinate for all axes | |
1167 for i in range(pos.shape[1]): | |
1168 pos[:, i] -= pos[:, i].mean() | |
1169 lim = max(abs(pos[:, i]).max(), lim) | |
1170 # rescale to (-scale, scale) in all directions, preserves aspect | |
1171 if lim > 0: | |
1172 for i in range(pos.shape[1]): | |
1173 pos[:, i] *= scale / lim | |
1174 return pos | |
1175 | |
1176 | |
1177 def rescale_layout_dict(pos, scale=1): | |
1178 """Return a dictionary of scaled positions keyed by node | |
1179 | |
1180 Parameters | |
1181 ---------- | |
1182 pos : A dictionary of positions keyed by node | |
1183 | |
1184 scale : number (default: 1) | |
1185 The size of the resulting extent in all directions. | |
1186 | |
1187 Returns | |
1188 ------- | |
1189 pos : A dictionary of positions keyed by node | |
1190 | |
1191 Examples | |
1192 -------- | |
1193 >>> pos = {0: (0, 0), 1: (1, 1), 2: (0.5, 0.5)} | |
1194 >>> nx.rescale_layout_dict(pos) | |
1195 {0: (-1.0, -1.0), 1: (1.0, 1.0), 2: (0.0, 0.0)} | |
1196 | |
1197 >>> pos = {0: (0, 0), 1: (-1, 1), 2: (-0.5, 0.5)} | |
1198 >>> nx.rescale_layout_dict(pos, scale=2) | |
1199 {0: (2.0, -2.0), 1: (-2.0, 2.0), 2: (0.0, 0.0)} | |
1200 | |
1201 See Also | |
1202 -------- | |
1203 rescale_layout | |
1204 """ | |
1205 import numpy as np | |
1206 | |
1207 if not pos: # empty_graph | |
1208 return {} | |
1209 pos_v = np.array(list(pos.values())) | |
1210 pos_v = rescale_layout(pos_v, scale=scale) | |
1211 return {k: tuple(v) for k, v in zip(pos.keys(), pos_v)} |