### comparison env/lib/python3.9/site-packages/networkx/drawing/layout.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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",
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()
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:
165 theta = np.linspace(0, 1, len(G) + 1)[:-1] * 2 * np.pi
166 theta = theta.astype(np.float32)
167 pos = np.column_stack(
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 = [, [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) == 1:
243 # single node at center
245 else:
246 # else start at r=1
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))
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)
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) - min(pos.T), max(pos.T) - min(pos.T)) * 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, pos.shape, pos.shape), 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) - min(pos.T), max(pos.T) - min(pos.T)) * 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):
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
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)
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
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) * 1e-3), meanwt, dim)
740
741 optresult = minimize(
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):
754 nNodes = invdist.shape
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
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
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
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):
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):
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