Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/networkx/drawing/layout.py @ 2:6af9afd405e9 draft

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