Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2******
3Layout
4******
6Node positioning algorithms for graph drawing.
8For `random_layout()` the possible resulting shape
9is a square of side [0, scale] (default: [0, 1])
10Changing `center` shifts the layout by that amount.
12For the other layout routines, the extent is
13[center - scale, center + scale] (default: [-1, 1]).
15Warning: Most layout routines have only been tested in 2-dimensions.
17"""
19import networkx as nx
20from networkx.utils import np_random_state
22__all__ = [
23 "bipartite_layout",
24 "circular_layout",
25 "forceatlas2_layout",
26 "kamada_kawai_layout",
27 "random_layout",
28 "rescale_layout",
29 "rescale_layout_dict",
30 "shell_layout",
31 "spring_layout",
32 "spectral_layout",
33 "planar_layout",
34 "fruchterman_reingold_layout",
35 "spiral_layout",
36 "multipartite_layout",
37 "bfs_layout",
38 "arf_layout",
39]
42def _process_params(G, center, dim):
43 # Some boilerplate code.
44 import numpy as np
46 if not isinstance(G, nx.Graph):
47 empty_graph = nx.Graph()
48 empty_graph.add_nodes_from(G)
49 G = empty_graph
51 if center is None:
52 center = np.zeros(dim)
53 else:
54 center = np.asarray(center)
56 if len(center) != dim:
57 msg = "length of center coordinates must match dimension of layout"
58 raise ValueError(msg)
60 return G, center
63@np_random_state(3)
64def random_layout(G, center=None, dim=2, seed=None, store_pos_as=None):
65 """Position nodes uniformly at random in the unit square.
67 For every node, a position is generated by choosing each of dim
68 coordinates uniformly at random on the interval [0.0, 1.0).
70 NumPy (http://scipy.org) is required for this function.
72 Parameters
73 ----------
74 G : NetworkX graph or list of nodes
75 A position will be assigned to every node in G.
77 center : array-like or None
78 Coordinate pair around which to center the layout.
80 dim : int
81 Dimension of layout.
83 seed : int, RandomState instance or None optional (default=None)
84 Set the random state for deterministic node layouts.
85 If int, `seed` is the seed used by the random number generator,
86 if numpy.random.RandomState instance, `seed` is the random
87 number generator,
88 if None, the random number generator is the RandomState instance used
89 by numpy.random.
91 store_pos_as : str, default None
92 If non-None, the position of each node will be stored on the graph as
93 an attribute with this string as its name, which can be accessed with
94 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
96 Returns
97 -------
98 pos : dict
99 A dictionary of positions keyed by node
101 Examples
102 --------
103 >>> from pprint import pprint
104 >>> G = nx.lollipop_graph(4, 3)
105 >>> pos = nx.random_layout(G)
106 >>> # suppress the returned dict and store on the graph directly
107 >>> _ = nx.random_layout(G, seed=42, store_pos_as="pos")
108 >>> pprint(nx.get_node_attributes(G, "pos"))
109 {0: array([0.37454012, 0.9507143 ], dtype=float32),
110 1: array([0.7319939, 0.5986585], dtype=float32),
111 2: array([0.15601864, 0.15599452], dtype=float32),
112 3: array([0.05808361, 0.8661761 ], dtype=float32),
113 4: array([0.601115 , 0.7080726], dtype=float32),
114 5: array([0.02058449, 0.96990985], dtype=float32),
115 6: array([0.83244264, 0.21233912], dtype=float32)}
116 """
117 import numpy as np
119 G, center = _process_params(G, center, dim)
120 pos = seed.rand(len(G), dim) + center
121 pos = pos.astype(np.float32)
122 pos = dict(zip(G, pos))
124 if store_pos_as is not None:
125 nx.set_node_attributes(G, pos, store_pos_as)
126 return pos
129def circular_layout(G, scale=1, center=None, dim=2, store_pos_as=None):
130 # dim=2 only
131 """Position nodes on a circle.
133 Parameters
134 ----------
135 G : NetworkX graph or list of nodes
136 A position will be assigned to every node in G.
138 scale : number (default: 1)
139 Scale factor for positions.
141 center : array-like or None
142 Coordinate pair around which to center the layout.
144 dim : int
145 Dimension of layout.
146 If dim>2, the remaining dimensions are set to zero
147 in the returned positions.
148 If dim<2, a ValueError is raised.
150 store_pos_as : str, default None
151 If non-None, the position of each node will be stored on the graph as
152 an attribute with this string as its name, which can be accessed with
153 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
155 Returns
156 -------
157 pos : dict
158 A dictionary of positions keyed by node
160 Raises
161 ------
162 ValueError
163 If dim < 2
165 Examples
166 --------
167 >>> from pprint import pprint
168 >>> G = nx.path_graph(4)
169 >>> pos = nx.circular_layout(G)
170 >>> # suppress the returned dict and store on the graph directly
171 >>> _ = nx.circular_layout(G, store_pos_as="pos")
172 >>> pprint(nx.get_node_attributes(G, "pos"))
173 {0: array([9.99999986e-01, 2.18556937e-08]),
174 1: array([-3.57647606e-08, 1.00000000e+00]),
175 2: array([-9.9999997e-01, -6.5567081e-08]),
176 3: array([ 1.98715071e-08, -9.99999956e-01])}
179 Notes
180 -----
181 This algorithm currently only works in two dimensions and does not
182 try to minimize edge crossings.
184 """
185 import numpy as np
187 if dim < 2:
188 raise ValueError("cannot handle dimensions < 2")
190 G, center = _process_params(G, center, dim)
192 paddims = max(0, (dim - 2))
194 if len(G) == 0:
195 pos = {}
196 elif len(G) == 1:
197 pos = {nx.utils.arbitrary_element(G): center}
198 else:
199 # Discard the extra angle since it matches 0 radians.
200 theta = np.linspace(0, 1, len(G) + 1)[:-1] * 2 * np.pi
201 theta = theta.astype(np.float32)
202 pos = np.column_stack(
203 [np.cos(theta), np.sin(theta), np.zeros((len(G), paddims))]
204 )
205 pos = rescale_layout(pos, scale=scale) + center
206 pos = dict(zip(G, pos))
208 if store_pos_as is not None:
209 nx.set_node_attributes(G, pos, store_pos_as)
211 return pos
214def shell_layout(
215 G, nlist=None, rotate=None, scale=1, center=None, dim=2, store_pos_as=None
216):
217 """Position nodes in concentric circles.
219 Parameters
220 ----------
221 G : NetworkX graph or list of nodes
222 A position will be assigned to every node in G.
224 nlist : list of lists
225 List of node lists for each shell.
227 rotate : angle in radians (default=pi/len(nlist))
228 Angle by which to rotate the starting position of each shell
229 relative to the starting position of the previous shell.
230 To recreate behavior before v2.5 use rotate=0.
232 scale : number (default: 1)
233 Scale factor for positions.
235 center : array-like or None
236 Coordinate pair around which to center the layout.
238 dim : int
239 Dimension of layout, currently only dim=2 is supported.
240 Other dimension values result in a ValueError.
242 store_pos_as : str, default None
243 If non-None, the position of each node will be stored on the graph as
244 an attribute with this string as its name, which can be accessed with
245 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
247 Returns
248 -------
249 pos : dict
250 A dictionary of positions keyed by node
252 Raises
253 ------
254 ValueError
255 If dim != 2
257 Examples
258 --------
259 >>> from pprint import pprint
260 >>> G = nx.path_graph(4)
261 >>> shells = [[0], [1, 2, 3]]
262 >>> pos = nx.shell_layout(G, shells)
263 >>> # suppress the returned dict and store on the graph directly
264 >>> _ = nx.shell_layout(G, shells, store_pos_as="pos")
265 >>> pprint(nx.get_node_attributes(G, "pos"))
266 {0: array([0., 0.]),
267 1: array([-5.00000000e-01, -4.37113883e-08]),
268 2: array([ 0.24999996, -0.43301272]),
269 3: array([0.24999981, 0.43301281])}
271 Notes
272 -----
273 This algorithm currently only works in two dimensions and does not
274 try to minimize edge crossings.
276 """
277 import numpy as np
279 if dim != 2:
280 raise ValueError("can only handle 2 dimensions")
282 G, center = _process_params(G, center, dim)
284 if len(G) == 0:
285 return {}
286 if len(G) == 1:
287 return {nx.utils.arbitrary_element(G): center}
289 if nlist is None:
290 # draw the whole graph in one shell
291 nlist = [list(G)]
293 radius_bump = scale / len(nlist)
295 if len(nlist[0]) == 1:
296 # single node at center
297 radius = 0.0
298 else:
299 # else start at r=1
300 radius = radius_bump
302 if rotate is None:
303 rotate = np.pi / len(nlist)
304 first_theta = rotate
305 npos = {}
306 for nodes in nlist:
307 # Discard the last angle (endpoint=False) since 2*pi matches 0 radians
308 theta = (
309 np.linspace(0, 2 * np.pi, len(nodes), endpoint=False, dtype=np.float32)
310 + first_theta
311 )
312 pos = radius * np.column_stack([np.cos(theta), np.sin(theta)]) + center
313 npos.update(zip(nodes, pos))
314 radius += radius_bump
315 first_theta += rotate
317 if store_pos_as is not None:
318 nx.set_node_attributes(G, npos, store_pos_as)
319 return npos
322def bipartite_layout(
323 G,
324 nodes=None,
325 align="vertical",
326 scale=1,
327 center=None,
328 aspect_ratio=4 / 3,
329 store_pos_as=None,
330):
331 """Position nodes in two straight lines.
333 Parameters
334 ----------
335 G : NetworkX graph or list of nodes
336 A position will be assigned to every node in G.
338 nodes : collection of nodes
339 Nodes in one node set of the graph. This set will be placed on
340 left or top. If `None` (the default), a node set is chosen arbitrarily
341 if the graph if bipartite.
343 align : string (default='vertical')
344 The alignment of nodes. Vertical or horizontal.
346 scale : number (default: 1)
347 Scale factor for positions.
349 center : array-like or None
350 Coordinate pair around which to center the layout.
352 aspect_ratio : number (default=4/3):
353 The ratio of the width to the height of the layout.
355 store_pos_as : str, default None
356 If non-None, the position of each node will be stored on the graph as
357 an attribute with this string as its name, which can be accessed with
358 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
360 Returns
361 -------
362 pos : dict
363 A dictionary of positions keyed by node.
365 Raises
366 ------
367 NetworkXError
368 If ``nodes=None`` and `G` is not bipartite.
370 Examples
371 --------
372 >>> G = nx.complete_bipartite_graph(3, 3)
373 >>> pos = nx.bipartite_layout(G)
375 The ordering of the layout (i.e. which nodes appear on the left/top) can
376 be specified with the `nodes` parameter:
378 >>> top, bottom = nx.bipartite.sets(G)
379 >>> pos = nx.bipartite_layout(G, nodes=bottom) # "bottom" set appears on the left
381 `store_pos_as` can be used to store the node positions for the computed layout
382 directly on the nodes:
384 >>> _ = nx.bipartite_layout(G, nodes=bottom, store_pos_as="pos")
385 >>> from pprint import pprint
386 >>> pprint(nx.get_node_attributes(G, "pos"))
387 {0: array([ 1. , -0.75]),
388 1: array([1., 0.]),
389 2: array([1. , 0.75]),
390 3: array([-1. , -0.75]),
391 4: array([-1., 0.]),
392 5: array([-1. , 0.75])}
395 The ``bipartite_layout`` function can be used with non-bipartite graphs
396 by explicitly specifying how the layout should be partitioned with `nodes`:
398 >>> G = nx.complete_graph(5) # Non-bipartite
399 >>> pos = nx.bipartite_layout(G, nodes={0, 1, 2})
401 Notes
402 -----
403 This algorithm currently only works in two dimensions and does not
404 try to minimize edge crossings.
406 """
408 import numpy as np
410 if align not in ("vertical", "horizontal"):
411 msg = "align must be either vertical or horizontal."
412 raise ValueError(msg)
414 G, center = _process_params(G, center=center, dim=2)
415 if len(G) == 0:
416 return {}
418 height = 1
419 width = aspect_ratio * height
420 offset = (width / 2, height / 2)
422 if nodes is None:
423 top, bottom = nx.bipartite.sets(G)
424 nodes = list(G)
425 else:
426 top = set(nodes)
427 bottom = set(G) - top
428 # Preserves backward-compatible node ordering in returned pos dict
429 nodes = list(top) + list(bottom)
431 left_xs = np.repeat(0, len(top))
432 right_xs = np.repeat(width, len(bottom))
433 left_ys = np.linspace(0, height, len(top))
434 right_ys = np.linspace(0, height, len(bottom))
436 top_pos = np.column_stack([left_xs, left_ys]) - offset
437 bottom_pos = np.column_stack([right_xs, right_ys]) - offset
439 pos = np.concatenate([top_pos, bottom_pos])
440 pos = rescale_layout(pos, scale=scale) + center
441 if align == "horizontal":
442 pos = pos[:, ::-1] # swap x and y coords
443 pos = dict(zip(nodes, pos))
445 if store_pos_as is not None:
446 nx.set_node_attributes(G, pos, store_pos_as)
448 return pos
451@np_random_state("seed")
452def spring_layout(
453 G,
454 k=None,
455 pos=None,
456 fixed=None,
457 iterations=50,
458 threshold=1e-4,
459 weight="weight",
460 scale=1,
461 center=None,
462 dim=2,
463 seed=None,
464 store_pos_as=None,
465 *,
466 method="auto",
467 gravity=1.0,
468):
469 """Position nodes using Fruchterman-Reingold force-directed algorithm.
471 The algorithm simulates a force-directed representation of the network
472 treating edges as springs holding nodes close, while treating nodes
473 as repelling objects, sometimes called an anti-gravity force.
474 Simulation continues until the positions are close to an equilibrium.
476 There are some hard-coded values: minimal distance between
477 nodes (0.01) and "temperature" of 0.1 to ensure nodes don't fly away.
478 During the simulation, `k` helps determine the distance between nodes,
479 though `scale` and `center` determine the size and place after
480 rescaling occurs at the end of the simulation.
482 Fixing some nodes doesn't allow them to move in the simulation.
483 It also turns off the rescaling feature at the simulation's end.
484 In addition, setting `scale` to `None` turns off rescaling.
486 Parameters
487 ----------
488 G : NetworkX graph or list of nodes
489 A position will be assigned to every node in G.
491 k : float (default=None)
492 Optimal distance between nodes. If None the distance is set to
493 1/sqrt(n) where n is the number of nodes. Increase this value
494 to move nodes farther apart.
496 pos : dict or None optional (default=None)
497 Initial positions for nodes as a dictionary with node as keys
498 and values as a coordinate list or tuple. If None, then use
499 random initial positions.
501 fixed : list or None optional (default=None)
502 Nodes to keep fixed at initial position.
503 Nodes not in ``G.nodes`` are ignored.
504 ValueError raised if `fixed` specified and `pos` not.
506 iterations : int optional (default=50)
507 Maximum number of iterations taken
509 threshold: float optional (default = 1e-4)
510 Threshold for relative error in node position changes.
511 The iteration stops if the error is below this threshold.
513 weight : string or None optional (default='weight')
514 The edge attribute that holds the numerical value used for
515 the edge weight. Larger means a stronger attractive force.
516 If None, then all edge weights are 1.
518 scale : number or None (default: 1)
519 Scale factor for positions. Not used unless `fixed is None`.
520 If scale is None, no rescaling is performed.
522 center : array-like or None
523 Coordinate pair around which to center the layout.
524 Not used unless `fixed is None`.
526 dim : int
527 Dimension of layout.
529 seed : int, RandomState instance or None optional (default=None)
530 Used only for the initial positions in the algorithm.
531 Set the random state for deterministic node layouts.
532 If int, `seed` is the seed used by the random number generator,
533 if numpy.random.RandomState instance, `seed` is the random
534 number generator,
535 if None, the random number generator is the RandomState instance used
536 by numpy.random.
538 store_pos_as : str, default None
539 If non-None, the position of each node will be stored on the graph as
540 an attribute with this string as its name, which can be accessed with
541 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
543 method : str optional (default='auto')
544 The method to compute the layout.
545 If 'force', the force-directed Fruchterman-Reingold algorithm [1]_ is used.
546 If 'energy', the energy-based optimization algorithm [2]_ is used with absolute
547 values of edge weights and gravitational forces acting on each connected component.
548 If 'auto', we use 'force' if ``len(G) < 500`` and 'energy' otherwise.
550 gravity: float optional (default=1.0)
551 Used only for the method='energy'.
552 The positive coefficient of gravitational forces per connected component.
554 Returns
555 -------
556 pos : dict
557 A dictionary of positions keyed by node
559 Examples
560 --------
561 >>> from pprint import pprint
562 >>> G = nx.path_graph(4)
563 >>> pos = nx.spring_layout(G)
564 >>> # suppress the returned dict and store on the graph directly
565 >>> _ = nx.spring_layout(G, seed=123, store_pos_as="pos")
566 >>> pprint(nx.get_node_attributes(G, "pos"))
567 {0: array([-0.61495802, -1. ]),
568 1: array([-0.21789544, -0.35432583]),
569 2: array([0.21847843, 0.35527369]),
570 3: array([0.61437502, 0.99905215])}
573 # The same using longer but equivalent function name
574 >>> pos = nx.fruchterman_reingold_layout(G)
576 References
577 ----------
578 .. [1] Fruchterman, Thomas MJ, and Edward M. Reingold.
579 "Graph drawing by force-directed placement."
580 Software: Practice and experience 21, no. 11 (1991): 1129-1164.
581 http://dx.doi.org/10.1002/spe.4380211102
582 .. [2] Hamaguchi, Hiroki, Naoki Marumo, and Akiko Takeda.
583 "Initial Placement for Fruchterman--Reingold Force Model With Coordinate Newton Direction."
584 arXiv preprint arXiv:2412.20317 (2024).
585 https://arxiv.org/abs/2412.20317
586 """
587 import numpy as np
589 if method not in ("auto", "force", "energy"):
590 raise ValueError("the method must be either auto, force, or energy.")
591 if method == "auto":
592 method = "force" if len(G) < 500 else "energy"
594 G, center = _process_params(G, center, dim)
596 if fixed is not None:
597 if pos is None:
598 raise ValueError("nodes are fixed without positions given")
599 for node in fixed:
600 if node not in pos:
601 raise ValueError("nodes are fixed without positions given")
602 nfixed = {node: i for i, node in enumerate(G)}
603 fixed = np.asarray([nfixed[node] for node in fixed if node in nfixed])
605 if pos is not None:
606 # Determine size of existing domain to adjust initial positions
607 dom_size = max(coord for pos_tup in pos.values() for coord in pos_tup)
608 if dom_size == 0:
609 dom_size = 1
610 pos_arr = seed.rand(len(G), dim) * dom_size + center
612 for i, n in enumerate(G):
613 if n in pos:
614 pos_arr[i] = np.asarray(pos[n])
615 else:
616 pos_arr = None
617 dom_size = 1
619 if len(G) == 0:
620 return {}
621 if len(G) == 1:
622 pos = {nx.utils.arbitrary_element(G.nodes()): center}
623 if store_pos_as is not None:
624 nx.set_node_attributes(G, pos, store_pos_as)
625 return pos
627 # Sparse matrix
628 if len(G) >= 500 or method == "energy":
629 A = nx.to_scipy_sparse_array(G, weight=weight, dtype="f")
630 if k is None and fixed is not None:
631 # We must adjust k by domain size for layouts not near 1x1
632 nnodes, _ = A.shape
633 k = dom_size / np.sqrt(nnodes)
634 pos = _sparse_fruchterman_reingold(
635 A, k, pos_arr, fixed, iterations, threshold, dim, seed, method, gravity
636 )
637 else:
638 A = nx.to_numpy_array(G, weight=weight)
639 if k is None and fixed is not None:
640 # We must adjust k by domain size for layouts not near 1x1
641 nnodes, _ = A.shape
642 k = dom_size / np.sqrt(nnodes)
643 pos = _fruchterman_reingold(
644 A, k, pos_arr, fixed, iterations, threshold, dim, seed
645 )
646 if fixed is None and scale is not None:
647 pos = rescale_layout(pos, scale=scale) + center
648 pos = dict(zip(G, pos))
650 if store_pos_as is not None:
651 nx.set_node_attributes(G, pos, store_pos_as)
653 return pos
656fruchterman_reingold_layout = spring_layout
659@np_random_state(7)
660def _fruchterman_reingold(
661 A, k=None, pos=None, fixed=None, iterations=50, threshold=1e-4, dim=2, seed=None
662):
663 # Position nodes in adjacency matrix A using Fruchterman-Reingold
664 # Entry point for NetworkX graph is fruchterman_reingold_layout()
665 import numpy as np
667 try:
668 nnodes, _ = A.shape
669 except AttributeError as err:
670 msg = "fruchterman_reingold() takes an adjacency matrix as input"
671 raise nx.NetworkXError(msg) from err
673 if pos is None:
674 # random initial positions
675 pos = np.asarray(seed.rand(nnodes, dim), dtype=A.dtype)
676 else:
677 # make sure positions are of same type as matrix
678 pos = pos.astype(A.dtype)
680 # optimal distance between nodes
681 if k is None:
682 k = np.sqrt(1.0 / nnodes)
683 # the initial "temperature" is about .1 of domain area (=1x1)
684 # this is the largest step allowed in the dynamics.
685 # We need to calculate this in case our fixed positions force our domain
686 # to be much bigger than 1x1
687 t = max(max(pos.T[0]) - min(pos.T[0]), max(pos.T[1]) - min(pos.T[1])) * 0.1
688 # simple cooling scheme.
689 # linearly step down by dt on each iteration so last iteration is size dt.
690 dt = t / (iterations + 1)
691 delta = np.zeros((pos.shape[0], pos.shape[0], pos.shape[1]), dtype=A.dtype)
692 # the inscrutable (but fast) version
693 # this is still O(V^2)
694 # could use multilevel methods to speed this up significantly
695 for iteration in range(iterations):
696 # matrix of difference between points
697 delta = pos[:, np.newaxis, :] - pos[np.newaxis, :, :]
698 # distance between points
699 distance = np.linalg.norm(delta, axis=-1)
700 # enforce minimum distance of 0.01
701 np.clip(distance, 0.01, None, out=distance)
702 # displacement "force"
703 displacement = np.einsum(
704 "ijk,ij->ik", delta, (k * k / distance**2 - A * distance / k)
705 )
706 # update positions
707 length = np.linalg.norm(displacement, axis=-1)
708 # Threshold the minimum length prior to position scaling
709 # See gh-8113 for detailed discussion of the threshold
710 length = np.clip(length, a_min=0.01, a_max=None)
711 delta_pos = np.einsum("ij,i->ij", displacement, t / length)
712 if fixed is not None:
713 # don't change positions of fixed nodes
714 delta_pos[fixed] = 0.0
715 pos += delta_pos
716 # cool temperature
717 t -= dt
718 if (np.linalg.norm(delta_pos) / nnodes) < threshold:
719 break
720 return pos
723@np_random_state(7)
724def _sparse_fruchterman_reingold(
725 A,
726 k=None,
727 pos=None,
728 fixed=None,
729 iterations=50,
730 threshold=1e-4,
731 dim=2,
732 seed=None,
733 method="energy",
734 gravity=1.0,
735):
736 # Position nodes in adjacency matrix A using Fruchterman-Reingold
737 # Entry point for NetworkX graph is fruchterman_reingold_layout()
738 # Sparse version
739 import numpy as np
740 import scipy as sp
742 try:
743 nnodes, _ = A.shape
744 except AttributeError as err:
745 msg = "fruchterman_reingold() takes an adjacency matrix as input"
746 raise nx.NetworkXError(msg) from err
748 if pos is None:
749 # random initial positions
750 pos = np.asarray(seed.rand(nnodes, dim), dtype=A.dtype)
751 else:
752 # make sure positions are of same type as matrix
753 pos = pos.astype(A.dtype)
755 # no fixed nodes
756 if fixed is None:
757 fixed = []
759 # optimal distance between nodes
760 if k is None:
761 k = np.sqrt(1.0 / nnodes)
763 if method == "energy":
764 return _energy_fruchterman_reingold(
765 A, nnodes, k, pos, fixed, iterations, threshold, dim, gravity
766 )
768 # make sure we have a LIst of Lists representation
769 try:
770 A = A.tolil()
771 except AttributeError:
772 A = (sp.sparse.coo_array(A)).tolil()
774 # the initial "temperature" is about .1 of domain area (=1x1)
775 # this is the largest step allowed in the dynamics.
776 t = max(max(pos.T[0]) - min(pos.T[0]), max(pos.T[1]) - min(pos.T[1])) * 0.1
777 # simple cooling scheme.
778 # linearly step down by dt on each iteration so last iteration is size dt.
779 dt = t / (iterations + 1)
781 displacement = np.zeros((dim, nnodes))
782 for iteration in range(iterations):
783 displacement *= 0
784 # loop over rows
785 for i in range(A.shape[0]):
786 if i in fixed:
787 continue
788 # difference between this row's node position and all others
789 delta = (pos[i] - pos).T
790 # distance between points
791 distance = np.sqrt((delta**2).sum(axis=0))
792 # enforce minimum distance of 0.01
793 distance = np.clip(distance, a_min=0.01, a_max=None)
794 # the adjacency matrix row
795 Ai = A.getrowview(i).toarray() # TODO: revisit w/ sparse 1D container
796 # displacement "force"
797 displacement[:, i] += (
798 delta * (k * k / distance**2 - Ai * distance / k)
799 ).sum(axis=1)
800 # update positions
801 length = np.sqrt((displacement**2).sum(axis=0))
802 # Threshold the minimum length prior to position scaling
803 # See gh-8113 for detailed discussion of the threshold
804 length = np.clip(length, a_min=0.01, a_max=None)
805 delta_pos = (displacement * t / length).T
806 pos += delta_pos
807 # cool temperature
808 t -= dt
809 if (np.linalg.norm(delta_pos) / nnodes) < threshold:
810 break
811 return pos
814def _energy_fruchterman_reingold(
815 A, nnodes, k, pos, fixed, iterations, threshold, dim, gravity
816):
817 # Entry point for NetworkX graph is fruchterman_reingold_layout()
818 # energy-based version
819 import numpy as np
820 import scipy as sp
822 if gravity <= 0:
823 raise ValueError(f"the gravity must be positive.")
825 # make sure we have a Compressed Sparse Row format
826 try:
827 A = A.tocsr()
828 except AttributeError:
829 A = sp.sparse.csr_array(A)
831 # Take absolute values of edge weights and symmetrize it
832 A = np.abs(A)
833 A = (A + A.T) / 2
835 n_components, labels = sp.sparse.csgraph.connected_components(A, directed=False)
836 bincount = np.bincount(labels)
837 batchsize = 500
839 def _cost_FR(x):
840 pos = x.reshape((nnodes, dim))
841 grad = np.zeros((nnodes, dim))
842 cost = 0.0
843 for l in range(0, nnodes, batchsize):
844 r = min(l + batchsize, nnodes)
845 # difference between selected node positions and all others
846 delta = pos[l:r, np.newaxis, :] - pos[np.newaxis, :, :]
847 # distance between points with a minimum distance of 1e-5
848 distance2 = np.sum(delta * delta, axis=2)
849 distance2 = np.maximum(distance2, 1e-10)
850 distance = np.sqrt(distance2)
851 # temporary variable for calculation
852 Ad = A[l:r] * distance
853 # attractive forces and repulsive forces
854 grad[l:r] = 2 * np.einsum("ij,ijk->ik", Ad / k - k**2 / distance2, delta)
855 # integrated attractive forces
856 cost += np.sum(Ad * distance2) / (3 * k)
857 # integrated repulsive forces
858 cost -= k**2 * np.sum(np.log(distance))
859 # gravitational force from the centroids of connected components to (0.5, ..., 0.5)^T
860 centers = np.zeros((n_components, dim))
861 np.add.at(centers, labels, pos)
862 delta0 = centers / bincount[:, np.newaxis] - 0.5
863 grad += gravity * delta0[labels]
864 cost += gravity * 0.5 * np.sum(bincount * np.linalg.norm(delta0, axis=1) ** 2)
865 # fix positions of fixed nodes
866 grad[fixed] = 0.0
867 return cost, grad.ravel()
869 # Optimization of the energy function by L-BFGS algorithm
870 options = {"maxiter": iterations, "gtol": threshold}
871 return sp.optimize.minimize(
872 _cost_FR, pos.ravel(), method="L-BFGS-B", jac=True, options=options
873 ).x.reshape((nnodes, dim))
876def kamada_kawai_layout(
877 G,
878 dist=None,
879 pos=None,
880 weight="weight",
881 scale=1,
882 center=None,
883 dim=2,
884 store_pos_as=None,
885):
886 """Position nodes using Kamada-Kawai path-length cost-function.
888 Parameters
889 ----------
890 G : NetworkX graph or list of nodes
891 A position will be assigned to every node in G.
893 dist : dict (default=None)
894 A two-level dictionary of optimal distances between nodes,
895 indexed by source and destination node.
896 If None, the distance is computed using shortest_path_length().
898 pos : dict or None optional (default=None)
899 Initial positions for nodes as a dictionary with node as keys
900 and values as a coordinate list or tuple. If None, then use
901 circular_layout() for dim >= 2 and a linear layout for dim == 1.
903 weight : string or None optional (default='weight')
904 The edge attribute that holds the numerical value used for
905 the edge weight. If None, then all edge weights are 1.
907 scale : number (default: 1)
908 Scale factor for positions.
910 center : array-like or None
911 Coordinate pair around which to center the layout.
913 dim : int
914 Dimension of layout.
916 store_pos_as : str, default None
917 If non-None, the position of each node will be stored on the graph as
918 an attribute with this string as its name, which can be accessed with
919 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
921 Returns
922 -------
923 pos : dict
924 A dictionary of positions keyed by node
926 Examples
927 --------
928 >>> from pprint import pprint
929 >>> G = nx.path_graph(4)
930 >>> pos = nx.kamada_kawai_layout(G)
931 >>> # suppress the returned dict and store on the graph directly
932 >>> _ = nx.kamada_kawai_layout(G, store_pos_as="pos")
933 >>> pprint(nx.get_node_attributes(G, "pos"))
934 {0: array([0.99996577, 0.99366857]),
935 1: array([0.32913544, 0.33543827]),
936 2: array([-0.33544334, -0.32910684]),
937 3: array([-0.99365787, -1. ])}
938 """
939 import numpy as np
941 G, center = _process_params(G, center, dim)
942 nNodes = len(G)
943 if nNodes == 0:
944 return {}
946 if dist is None:
947 dist = dict(nx.shortest_path_length(G, weight=weight))
948 dist_mtx = 1e6 * np.ones((nNodes, nNodes))
949 for row, nr in enumerate(G):
950 if nr not in dist:
951 continue
952 rdist = dist[nr]
953 for col, nc in enumerate(G):
954 if nc not in rdist:
955 continue
956 dist_mtx[row][col] = rdist[nc]
958 if pos is None:
959 if dim >= 3:
960 pos = random_layout(G, dim=dim)
961 elif dim == 2:
962 pos = circular_layout(G, dim=dim)
963 else:
964 pos = dict(zip(G, np.linspace(0, 1, len(G))))
965 pos_arr = np.array([pos[n] for n in G])
967 pos = _kamada_kawai_solve(dist_mtx, pos_arr, dim)
969 pos = rescale_layout(pos, scale=scale) + center
970 pos = dict(zip(G, pos))
972 if store_pos_as is not None:
973 nx.set_node_attributes(G, pos, store_pos_as)
975 return pos
978def _kamada_kawai_solve(dist_mtx, pos_arr, dim):
979 # Anneal node locations based on the Kamada-Kawai cost-function,
980 # using the supplied matrix of preferred inter-node distances,
981 # and starting locations.
983 import numpy as np
984 import scipy as sp
986 meanwt = 1e-3
987 costargs = (np, 1 / (dist_mtx + np.eye(dist_mtx.shape[0]) * 1e-3), meanwt, dim)
989 optresult = sp.optimize.minimize(
990 _kamada_kawai_costfn,
991 pos_arr.ravel(),
992 method="L-BFGS-B",
993 args=costargs,
994 jac=True,
995 )
997 return optresult.x.reshape((-1, dim))
1000def _kamada_kawai_costfn(pos_vec, np, invdist, meanweight, dim):
1001 # Cost-function and gradient for Kamada-Kawai layout algorithm
1002 nNodes = invdist.shape[0]
1003 pos_arr = pos_vec.reshape((nNodes, dim))
1005 delta = pos_arr[:, np.newaxis, :] - pos_arr[np.newaxis, :, :]
1006 nodesep = np.linalg.norm(delta, axis=-1)
1007 direction = np.einsum("ijk,ij->ijk", delta, 1 / (nodesep + np.eye(nNodes) * 1e-3))
1009 offset = nodesep * invdist - 1.0
1010 offset[np.diag_indices(nNodes)] = 0
1012 cost = 0.5 * np.sum(offset**2)
1013 grad = np.einsum("ij,ij,ijk->ik", invdist, offset, direction) - np.einsum(
1014 "ij,ij,ijk->jk", invdist, offset, direction
1015 )
1017 # Additional parabolic term to encourage mean position to be near origin:
1018 sumpos = np.sum(pos_arr, axis=0)
1019 cost += 0.5 * meanweight * np.sum(sumpos**2)
1020 grad += meanweight * sumpos
1022 return (cost, grad.ravel())
1025def spectral_layout(G, weight="weight", scale=1, center=None, dim=2, store_pos_as=None):
1026 """Position nodes using the eigenvectors of the graph Laplacian.
1028 Using the unnormalized Laplacian, the layout shows possible clusters of
1029 nodes which are an approximation of the ratio cut. If dim is the number of
1030 dimensions then the positions are the entries of the dim eigenvectors
1031 corresponding to the ascending eigenvalues starting from the second one.
1033 Parameters
1034 ----------
1035 G : NetworkX graph or list of nodes
1036 A position will be assigned to every node in G.
1038 weight : string or None optional (default='weight')
1039 The edge attribute that holds the numerical value used for
1040 the edge weight. If None, then all edge weights are 1.
1042 scale : number (default: 1)
1043 Scale factor for positions.
1045 center : array-like or None
1046 Coordinate pair around which to center the layout.
1048 dim : int
1049 Dimension of layout.
1051 store_pos_as : str, default None
1052 If non-None, the position of each node will be stored on the graph as
1053 an attribute with this string as its name, which can be accessed with
1054 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
1056 Returns
1057 -------
1058 pos : dict
1059 A dictionary of positions keyed by node
1061 Examples
1062 --------
1063 >>> from pprint import pprint
1064 >>> G = nx.path_graph(4)
1065 >>> pos = nx.spectral_layout(G)
1066 >>> # suppress the returned dict and store on the graph directly
1067 >>> _ = nx.spectral_layout(G, store_pos_as="pos")
1068 >>> pprint(nx.get_node_attributes(G, "pos"))
1069 {0: array([-1. , 0.76536686]),
1070 1: array([-0.41421356, -0.76536686]),
1071 2: array([ 0.41421356, -0.76536686]),
1072 3: array([1. , 0.76536686])}
1075 Notes
1076 -----
1077 Directed graphs will be considered as undirected graphs when
1078 positioning the nodes.
1080 For larger graphs (>500 nodes) this will use the SciPy sparse
1081 eigenvalue solver (ARPACK).
1082 """
1083 # handle some special cases that break the eigensolvers
1084 import numpy as np
1086 G, center = _process_params(G, center, dim)
1088 if len(G) <= 2:
1089 if len(G) == 0:
1090 pos = np.array([])
1091 elif len(G) == 1:
1092 pos = np.array([center])
1093 else:
1094 pos = np.array([np.zeros(dim), np.array(center) * 2.0])
1095 return dict(zip(G, pos))
1096 try:
1097 # Sparse matrix
1098 if len(G) < 500: # dense solver is faster for small graphs
1099 raise ValueError
1100 A = nx.to_scipy_sparse_array(G, weight=weight, dtype="d")
1101 # Symmetrize directed graphs
1102 if G.is_directed():
1103 A = A + np.transpose(A)
1104 pos = _sparse_spectral(A, dim)
1105 except (ImportError, ValueError):
1106 # Dense matrix
1107 A = nx.to_numpy_array(G, weight=weight)
1108 # Symmetrize directed graphs
1109 if G.is_directed():
1110 A += A.T
1111 pos = _spectral(A, dim)
1113 pos = rescale_layout(pos, scale=scale) + center
1114 pos = dict(zip(G, pos))
1116 if store_pos_as is not None:
1117 nx.set_node_attributes(G, pos, store_pos_as)
1119 return pos
1122def _spectral(A, dim=2):
1123 # Input adjacency matrix A
1124 # Uses dense eigenvalue solver from numpy
1125 import numpy as np
1127 try:
1128 nnodes, _ = A.shape
1129 except AttributeError as err:
1130 msg = "spectral() takes an adjacency matrix as input"
1131 raise nx.NetworkXError(msg) from err
1133 # form Laplacian matrix where D is diagonal of degrees
1134 D = np.identity(nnodes, dtype=A.dtype) * np.sum(A, axis=1)
1135 L = D - A
1137 eigenvalues, eigenvectors = np.linalg.eig(L)
1138 # sort and keep smallest nonzero
1139 index = np.argsort(eigenvalues)[1 : dim + 1] # 0 index is zero eigenvalue
1140 return np.real(eigenvectors[:, index])
1143def _sparse_spectral(A, dim=2):
1144 # Input adjacency matrix A
1145 # Uses sparse eigenvalue solver from scipy
1146 # Could use multilevel methods here, see Koren "On spectral graph drawing"
1147 import numpy as np
1148 import scipy as sp
1150 try:
1151 nnodes, _ = A.shape
1152 except AttributeError as err:
1153 msg = "sparse_spectral() takes an adjacency matrix as input"
1154 raise nx.NetworkXError(msg) from err
1156 # form Laplacian matrix
1157 D = sp.sparse.dia_array((A.sum(axis=1), 0), shape=(nnodes, nnodes)).tocsr()
1158 L = D - A
1160 k = dim + 1
1161 # number of Lanczos vectors for ARPACK solver.What is the right scaling?
1162 ncv = max(2 * k + 1, int(np.sqrt(nnodes)))
1163 # return smallest k eigenvalues and eigenvectors
1164 eigenvalues, eigenvectors = sp.sparse.linalg.eigsh(L, k, which="SM", ncv=ncv)
1165 index = np.argsort(eigenvalues)[1:k] # 0 index is zero eigenvalue
1166 return np.real(eigenvectors[:, index])
1169def planar_layout(G, scale=1, center=None, dim=2, store_pos_as=None):
1170 """Position nodes without edge intersections.
1172 Parameters
1173 ----------
1174 G : NetworkX graph or list of nodes
1175 A position will be assigned to every node in G. If G is of type
1176 nx.PlanarEmbedding, the positions are selected accordingly.
1178 scale : number (default: 1)
1179 Scale factor for positions.
1181 center : array-like or None
1182 Coordinate pair around which to center the layout.
1184 dim : int
1185 Dimension of layout.
1187 store_pos_as : str, default None
1188 If non-None, the position of each node will be stored on the graph as
1189 an attribute with this string as its name, which can be accessed with
1190 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
1192 Returns
1193 -------
1194 pos : dict
1195 A dictionary of positions keyed by node
1197 Raises
1198 ------
1199 NetworkXException
1200 If G is not planar
1202 Examples
1203 --------
1204 >>> from pprint import pprint
1205 >>> G = nx.path_graph(4)
1206 >>> pos = nx.planar_layout(G)
1207 >>> # suppress the returned dict and store on the graph directly
1208 >>> _ = nx.planar_layout(G, store_pos_as="pos")
1209 >>> pprint(nx.get_node_attributes(G, "pos"))
1210 {0: array([-0.77777778, -0.33333333]),
1211 1: array([ 1. , -0.33333333]),
1212 2: array([0.11111111, 0.55555556]),
1213 3: array([-0.33333333, 0.11111111])}
1214 """
1215 import numpy as np
1217 if dim != 2:
1218 raise ValueError("can only handle 2 dimensions")
1220 G, center = _process_params(G, center, dim)
1222 if len(G) == 0:
1223 return {}
1225 if isinstance(G, nx.PlanarEmbedding):
1226 embedding = G
1227 else:
1228 is_planar, embedding = nx.check_planarity(G)
1229 if not is_planar:
1230 raise nx.NetworkXException("G is not planar.")
1231 pos = nx.combinatorial_embedding_to_pos(embedding)
1232 node_list = list(embedding)
1233 pos = np.vstack([pos[x] for x in node_list])
1234 pos = pos.astype(np.float64)
1235 pos = rescale_layout(pos, scale=scale) + center
1236 pos = dict(zip(node_list, pos))
1237 if store_pos_as is not None:
1238 nx.set_node_attributes(G, pos, store_pos_as)
1239 return pos
1242def spiral_layout(
1243 G,
1244 scale=1,
1245 center=None,
1246 dim=2,
1247 resolution=0.35,
1248 equidistant=False,
1249 store_pos_as=None,
1250):
1251 """Position nodes in a spiral layout.
1253 Parameters
1254 ----------
1255 G : NetworkX graph or list of nodes
1256 A position will be assigned to every node in G.
1258 scale : number (default: 1)
1259 Scale factor for positions.
1261 center : array-like or None
1262 Coordinate pair around which to center the layout.
1264 dim : int, default=2
1265 Dimension of layout, currently only dim=2 is supported.
1266 Other dimension values result in a ValueError.
1268 resolution : float, default=0.35
1269 The compactness of the spiral layout returned.
1270 Lower values result in more compressed spiral layouts.
1272 equidistant : bool, default=False
1273 If True, nodes will be positioned equidistant from each other
1274 by decreasing angle further from center.
1275 If False, nodes will be positioned at equal angles
1276 from each other by increasing separation further from center.
1278 store_pos_as : str, default None
1279 If non-None, the position of each node will be stored on the graph as
1280 an attribute with this string as its name, which can be accessed with
1281 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
1283 Returns
1284 -------
1285 pos : dict
1286 A dictionary of positions keyed by node
1288 Raises
1289 ------
1290 ValueError
1291 If dim != 2
1293 Examples
1294 --------
1295 >>> from pprint import pprint
1296 >>> G = nx.path_graph(4)
1297 >>> pos = nx.spiral_layout(G)
1298 >>> nx.draw(G, pos=pos)
1299 >>> # suppress the returned dict and store on the graph directly
1300 >>> _ = nx.spiral_layout(G, store_pos_as="pos")
1301 >>> pprint(nx.get_node_attributes(G, "pos"))
1302 {0: array([-0.64153279, -0.68555087]),
1303 1: array([-0.03307913, -0.46344795]),
1304 2: array([0.34927952, 0.14899882]),
1305 3: array([0.32533239, 1. ])}
1307 Notes
1308 -----
1309 This algorithm currently only works in two dimensions.
1311 """
1312 import numpy as np
1314 if dim != 2:
1315 raise ValueError("can only handle 2 dimensions")
1317 G, center = _process_params(G, center, dim)
1319 if len(G) == 0:
1320 return {}
1321 if len(G) == 1:
1322 pos = {nx.utils.arbitrary_element(G): center}
1323 if store_pos_as is not None:
1324 nx.set_node_attributes(G, pos, store_pos_as)
1325 return pos
1327 pos = []
1328 if equidistant:
1329 chord = 1
1330 step = 0.5
1331 theta = resolution
1332 theta += chord / (step * theta)
1333 for _ in range(len(G)):
1334 r = step * theta
1335 theta += chord / r
1336 pos.append([np.cos(theta) * r, np.sin(theta) * r])
1338 else:
1339 dist = np.arange(len(G), dtype=float)
1340 angle = resolution * dist
1341 pos = np.transpose(dist * np.array([np.cos(angle), np.sin(angle)]))
1343 pos = rescale_layout(np.array(pos), scale=scale) + center
1345 pos = dict(zip(G, pos))
1347 if store_pos_as is not None:
1348 nx.set_node_attributes(G, pos, store_pos_as)
1350 return pos
1353def multipartite_layout(
1354 G, subset_key="subset", align="vertical", scale=1, center=None, store_pos_as=None
1355):
1356 """Position nodes in layers of straight lines.
1358 Parameters
1359 ----------
1360 G : NetworkX graph or list of nodes
1361 A position will be assigned to every node in G.
1363 subset_key : string or dict (default='subset')
1364 If a string, the key of node data in G that holds the node subset.
1365 If a dict, keyed by layer number to the nodes in that layer/subset.
1367 align : string (default='vertical')
1368 The alignment of nodes. Vertical or horizontal.
1370 scale : number (default: 1)
1371 Scale factor for positions.
1373 center : array-like or None
1374 Coordinate pair around which to center the layout.
1376 store_pos_as : str, default None
1377 If non-None, the position of each node will be stored on the graph as
1378 an attribute with this string as its name, which can be accessed with
1379 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
1381 Returns
1382 -------
1383 pos : dict
1384 A dictionary of positions keyed by node.
1386 Examples
1387 --------
1388 >>> G = nx.complete_multipartite_graph(28, 16, 10)
1389 >>> pos = nx.multipartite_layout(G)
1390 >>> # suppress the returned dict and store on the graph directly
1391 >>> G = nx.complete_multipartite_graph(28, 16, 10)
1392 >>> _ = nx.multipartite_layout(G, store_pos_as="pos")
1394 or use a dict to provide the layers of the layout
1396 >>> G = nx.Graph([(0, 1), (1, 2), (1, 3), (3, 4)])
1397 >>> layers = {"a": [0], "b": [1], "c": [2, 3], "d": [4]}
1398 >>> pos = nx.multipartite_layout(G, subset_key=layers)
1400 Notes
1401 -----
1402 This algorithm currently only works in two dimensions and does not
1403 try to minimize edge crossings.
1405 Network does not need to be a complete multipartite graph. As long as nodes
1406 have subset_key data, they will be placed in the corresponding layers.
1408 """
1409 import numpy as np
1411 if align not in ("vertical", "horizontal"):
1412 msg = "align must be either vertical or horizontal."
1413 raise ValueError(msg)
1415 G, center = _process_params(G, center=center, dim=2)
1416 if len(G) == 0:
1417 return {}
1419 try:
1420 # check if subset_key is dict-like
1421 if len(G) != sum(len(nodes) for nodes in subset_key.values()):
1422 raise nx.NetworkXError(
1423 "all nodes must be in one subset of `subset_key` dict"
1424 )
1425 except AttributeError:
1426 # subset_key is not a dict, hence a string
1427 node_to_subset = nx.get_node_attributes(G, subset_key)
1428 if len(node_to_subset) != len(G):
1429 raise nx.NetworkXError(
1430 f"all nodes need a subset_key attribute: {subset_key}"
1431 )
1432 subset_key = nx.utils.groups(node_to_subset)
1434 # Sort by layer, if possible
1435 try:
1436 layers = dict(sorted(subset_key.items()))
1437 except TypeError:
1438 layers = subset_key
1440 pos = None
1441 nodes = []
1442 width = len(layers)
1443 for i, layer in enumerate(layers.values()):
1444 height = len(layer)
1445 xs = np.repeat(i, height)
1446 ys = np.arange(0, height, dtype=float)
1447 offset = ((width - 1) / 2, (height - 1) / 2)
1448 layer_pos = np.column_stack([xs, ys]) - offset
1449 if pos is None:
1450 pos = layer_pos
1451 else:
1452 pos = np.concatenate([pos, layer_pos])
1453 nodes.extend(layer)
1454 pos = rescale_layout(pos, scale=scale) + center
1455 if align == "horizontal":
1456 pos = pos[:, ::-1] # swap x and y coords
1457 pos = dict(zip(nodes, pos))
1459 if store_pos_as is not None:
1460 nx.set_node_attributes(G, pos, store_pos_as)
1462 return pos
1465@np_random_state("seed")
1466def arf_layout(
1467 G,
1468 pos=None,
1469 scaling=1,
1470 a=1.1,
1471 etol=1e-6,
1472 dt=1e-3,
1473 max_iter=1000,
1474 *,
1475 seed=None,
1476 store_pos_as=None,
1477):
1478 """Arf layout for networkx
1480 The attractive and repulsive forces (arf) layout [1] improves the spring
1481 layout in three ways. First, it prevents congestion of highly connected nodes
1482 due to strong forcing between nodes. Second, it utilizes the layout space
1483 more effectively by preventing large gaps that spring layout tends to create.
1484 Lastly, the arf layout represents symmetries in the layout better than the
1485 default spring layout.
1487 Parameters
1488 ----------
1489 G : nx.Graph or nx.DiGraph
1490 Networkx graph.
1491 pos : dict
1492 Initial position of the nodes. If set to None a
1493 random layout will be used.
1494 scaling : float
1495 Scales the radius of the circular layout space.
1496 a : float
1497 Strength of springs between connected nodes. Should be larger than 1.
1498 The greater a, the clearer the separation of unconnected sub clusters.
1499 etol : float
1500 Gradient sum of spring forces must be larger than `etol` before successful
1501 termination.
1502 dt : float
1503 Time step for force differential equation simulations.
1504 max_iter : int
1505 Max iterations before termination of the algorithm.
1506 seed : int, RandomState instance or None optional (default=None)
1507 Set the random state for deterministic node layouts.
1508 If int, `seed` is the seed used by the random number generator,
1509 if numpy.random.RandomState instance, `seed` is the random
1510 number generator,
1511 if None, the random number generator is the RandomState instance used
1512 by numpy.random.
1513 store_pos_as : str, default None
1514 If non-None, the position of each node will be stored on the graph as
1515 an attribute with this string as its name, which can be accessed with
1516 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
1518 Returns
1519 -------
1520 pos : dict
1521 A dictionary of positions keyed by node.
1523 Examples
1524 --------
1525 >>> G = nx.grid_graph((5, 5))
1526 >>> pos = nx.arf_layout(G)
1527 >>> # suppress the returned dict and store on the graph directly
1528 >>> G = nx.grid_graph((5, 5))
1529 >>> _ = nx.arf_layout(G, store_pos_as="pos")
1531 References
1532 ----------
1533 .. [1] "Self-Organization Applied to Dynamic Network Layout", M. Geipel,
1534 International Journal of Modern Physics C, 2007, Vol 18, No 10,
1535 pp. 1537-1549.
1536 https://doi.org/10.1142/S0129183107011558 https://arxiv.org/abs/0704.1748
1537 """
1538 import warnings
1540 import numpy as np
1542 if a <= 1:
1543 msg = "The parameter a should be larger than 1"
1544 raise ValueError(msg)
1546 pos_tmp = nx.random_layout(G, seed=seed)
1547 if pos is None:
1548 pos = pos_tmp
1549 else:
1550 for node in G.nodes():
1551 if node not in pos:
1552 pos[node] = pos_tmp[node].copy()
1554 # Initialize spring constant matrix
1555 N = len(G)
1556 # No nodes no computation
1557 if N == 0:
1558 return pos
1560 # init force of springs
1561 K = np.ones((N, N)) - np.eye(N)
1562 node_order = {node: i for i, node in enumerate(G)}
1563 for x, y in G.edges():
1564 if x != y:
1565 idx, jdx = (node_order[i] for i in (x, y))
1566 K[idx, jdx] = a
1568 # vectorize values
1569 p = np.asarray(list(pos.values()))
1571 # equation 10 in [1]
1572 rho = scaling * np.sqrt(N)
1574 # looping variables
1575 error = etol + 1
1576 n_iter = 0
1577 while error > etol:
1578 diff = p[:, np.newaxis] - p[np.newaxis]
1579 A = np.linalg.norm(diff, axis=-1)[..., np.newaxis]
1580 # attraction_force - repulsions force
1581 # suppress nans due to division; caused by diagonal set to zero.
1582 # Does not affect the computation due to nansum
1583 with warnings.catch_warnings():
1584 warnings.simplefilter("ignore")
1585 change = K[..., np.newaxis] * diff - rho / A * diff
1586 change = np.nansum(change, axis=0)
1587 p += change * dt
1589 error = np.linalg.norm(change, axis=-1).sum()
1590 if n_iter > max_iter:
1591 break
1592 n_iter += 1
1594 pos = dict(zip(G.nodes(), p))
1596 if store_pos_as is not None:
1597 nx.set_node_attributes(G, pos, store_pos_as)
1599 return pos
1602@np_random_state("seed")
1603@nx._dispatchable(edge_attrs="weight", mutates_input={"store_pos_as": 15})
1604def forceatlas2_layout(
1605 G,
1606 pos=None,
1607 *,
1608 max_iter=100,
1609 jitter_tolerance=1.0,
1610 scaling_ratio=2.0,
1611 gravity=1.0,
1612 distributed_action=False,
1613 strong_gravity=False,
1614 node_mass=None,
1615 node_size=None,
1616 weight=None,
1617 linlog=False,
1618 seed=None,
1619 dim=2,
1620 store_pos_as=None,
1621):
1622 """Position nodes using the ForceAtlas2 force-directed layout algorithm.
1624 This function applies the ForceAtlas2 layout algorithm [1]_ to a NetworkX graph,
1625 positioning the nodes in a way that visually represents the structure of the graph.
1626 The algorithm uses physical simulation to minimize the energy of the system,
1627 resulting in a more readable layout.
1629 Parameters
1630 ----------
1631 G : nx.Graph
1632 A NetworkX graph to be laid out.
1633 pos : dict or None, optional
1634 Initial positions of the nodes. If None, random initial positions are used.
1635 max_iter : int (default: 100)
1636 Number of iterations for the layout optimization.
1637 jitter_tolerance : float (default: 1.0)
1638 Controls the tolerance for adjusting the speed of layout generation.
1639 scaling_ratio : float (default: 2.0)
1640 Determines the scaling of attraction and repulsion forces.
1641 gravity : float (default: 1.0)
1642 Determines the amount of attraction on nodes to the center. Prevents islands
1643 (i.e. weakly connected or disconnected parts of the graph)
1644 from drifting away.
1645 distributed_action : bool (default: False)
1646 Distributes the attraction force evenly among nodes.
1647 strong_gravity : bool (default: False)
1648 Applies a strong gravitational pull towards the center.
1649 node_mass : dict or None, optional
1650 Maps nodes to their masses, influencing the attraction to other nodes.
1651 node_size : dict or None, optional
1652 Maps nodes to their sizes, preventing crowding by creating a halo effect.
1653 weight : string or None, optional (default: None)
1654 The edge attribute that holds the numerical value used for
1655 the edge weight. If None, then all edge weights are 1.
1656 linlog : bool (default: False)
1657 Uses logarithmic attraction instead of linear.
1658 seed : int, RandomState instance or None optional (default=None)
1659 Used only for the initial positions in the algorithm.
1660 Set the random state for deterministic node layouts.
1661 If int, `seed` is the seed used by the random number generator,
1662 if numpy.random.RandomState instance, `seed` is the random
1663 number generator,
1664 if None, the random number generator is the RandomState instance used
1665 by numpy.random.
1666 dim : int (default: 2)
1667 Sets the dimensions for the layout. Ignored if `pos` is provided.
1668 store_pos_as : str, default None
1669 If non-None, the position of each node will be stored on the graph as
1670 an attribute with this string as its name, which can be accessed with
1671 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
1673 Examples
1674 --------
1675 >>> import networkx as nx
1676 >>> G = nx.florentine_families_graph()
1677 >>> pos = nx.forceatlas2_layout(G)
1678 >>> nx.draw(G, pos=pos)
1679 >>> # suppress the returned dict and store on the graph directly
1680 >>> pos = nx.forceatlas2_layout(G, store_pos_as="pos")
1681 >>> _ = nx.forceatlas2_layout(G, store_pos_as="pos")
1683 References
1684 ----------
1685 .. [1] Jacomy, M., Venturini, T., Heymann, S., & Bastian, M. (2014).
1686 ForceAtlas2, a continuous graph layout algorithm for handy network
1687 visualization designed for the Gephi software. PloS one, 9(6), e98679.
1688 https://doi.org/10.1371/journal.pone.0098679
1689 """
1690 import numpy as np
1692 if len(G) == 0:
1693 return {}
1694 # parse optional pos positions
1695 if pos is None:
1696 pos = nx.random_layout(G, dim=dim, seed=seed)
1697 pos_arr = np.array(list(pos.values()))
1698 elif len(pos) == len(G):
1699 pos_arr = np.array([pos[node].copy() for node in G])
1700 else:
1701 # set random node pos within the initial pos values
1702 pos_init = np.array(list(pos.values()))
1703 max_pos = pos_init.max(axis=0)
1704 min_pos = pos_init.min(axis=0)
1705 dim = max_pos.size
1706 pos_arr = min_pos + seed.rand(len(G), dim) * (max_pos - min_pos)
1707 for idx, node in enumerate(G):
1708 if node in pos:
1709 pos_arr[idx] = pos[node].copy()
1711 mass = np.zeros(len(G))
1712 size = np.zeros(len(G))
1714 # Only adjust for size when the users specifies size other than default (1)
1715 adjust_sizes = False
1716 if node_size is None:
1717 node_size = {}
1718 else:
1719 adjust_sizes = True
1721 if node_mass is None:
1722 node_mass = {}
1724 for idx, node in enumerate(G):
1725 mass[idx] = node_mass.get(node, G.degree(node) + 1)
1726 size[idx] = node_size.get(node, 1)
1728 n = len(G)
1729 gravities = np.zeros((n, dim))
1730 attraction = np.zeros((n, dim))
1731 repulsion = np.zeros((n, dim))
1732 A = nx.to_numpy_array(G, weight=weight)
1734 def estimate_factor(n, swing, traction, speed, speed_efficiency, jitter_tolerance):
1735 """Computes the scaling factor for the force in the ForceAtlas2 layout algorithm.
1737 This helper function adjusts the speed and
1738 efficiency of the layout generation based on the
1739 current state of the system, such as the number of
1740 nodes, current swing, and traction forces.
1742 Parameters
1743 ----------
1744 n : int
1745 Number of nodes in the graph.
1746 swing : float
1747 The current swing, representing the oscillation of the nodes.
1748 traction : float
1749 The current traction force, representing the attraction between nodes.
1750 speed : float
1751 The current speed of the layout generation.
1752 speed_efficiency : float
1753 The efficiency of the current speed, influencing how fast the layout converges.
1754 jitter_tolerance : float
1755 The tolerance for jitter, affecting how much speed adjustment is allowed.
1757 Returns
1758 -------
1759 tuple
1760 A tuple containing the updated speed and speed efficiency.
1762 Notes
1763 -----
1764 This function is a part of the ForceAtlas2 layout algorithm and is used to dynamically adjust the
1765 layout parameters to achieve an optimal and stable visualization.
1767 """
1768 import numpy as np
1770 # estimate jitter
1771 opt_jitter = 0.05 * np.sqrt(n)
1772 min_jitter = np.sqrt(opt_jitter)
1773 max_jitter = 10
1774 min_speed_efficiency = 0.05
1776 other = min(max_jitter, opt_jitter * traction / n**2)
1777 jitter = jitter_tolerance * max(min_jitter, other)
1779 if swing / traction > 2.0:
1780 if speed_efficiency > min_speed_efficiency:
1781 speed_efficiency *= 0.5
1782 jitter = max(jitter, jitter_tolerance)
1783 if swing == 0:
1784 target_speed = np.inf
1785 else:
1786 target_speed = jitter * speed_efficiency * traction / swing
1788 if swing > jitter * traction:
1789 if speed_efficiency > min_speed_efficiency:
1790 speed_efficiency *= 0.7
1791 elif speed < 1000:
1792 speed_efficiency *= 1.3
1794 max_rise = 0.5
1795 speed = speed + min(target_speed - speed, max_rise * speed)
1796 return speed, speed_efficiency
1798 speed = 1
1799 speed_efficiency = 1
1800 swing = 1
1801 traction = 1
1802 for _ in range(max_iter):
1803 # compute pairwise difference
1804 diff = pos_arr[:, None] - pos_arr[None]
1805 # compute pairwise distance
1806 distance = np.linalg.norm(diff, axis=-1)
1808 # linear attraction
1809 if linlog:
1810 attraction = -np.log(1 + distance) / distance
1811 np.fill_diagonal(attraction, 0)
1812 attraction = np.einsum("ij, ij -> ij", attraction, A)
1813 attraction = np.einsum("ijk, ij -> ik", diff, attraction)
1815 else:
1816 attraction = -np.einsum("ijk, ij -> ik", diff, A)
1818 if distributed_action:
1819 attraction /= mass[:, None]
1821 # repulsion
1822 tmp = mass[:, None] @ mass[None]
1823 if adjust_sizes:
1824 distance += -size[:, None] - size[None]
1826 d2 = distance**2
1827 # remove self-interaction
1828 np.fill_diagonal(tmp, 0)
1829 np.fill_diagonal(d2, 1)
1830 factor = (tmp / d2) * scaling_ratio
1831 repulsion = np.einsum("ijk, ij -> ik", diff, factor)
1833 # gravity
1834 pos_centered = pos_arr - np.mean(pos_arr, axis=0)
1835 if strong_gravity:
1836 gravities = -gravity * mass[:, None] * pos_centered
1837 else:
1838 # hide warnings for divide by zero. Then change nan to 0
1839 with np.errstate(divide="ignore", invalid="ignore"):
1840 unit_vec = pos_centered / np.linalg.norm(pos_centered, axis=-1)[:, None]
1841 unit_vec = np.nan_to_num(unit_vec, nan=0)
1842 gravities = -gravity * mass[:, None] * unit_vec
1844 # total forces
1845 update = attraction + repulsion + gravities
1847 # compute total swing and traction
1848 swing += (mass * np.linalg.norm(pos_arr - update, axis=-1)).sum()
1849 traction += (0.5 * mass * np.linalg.norm(pos_arr + update, axis=-1)).sum()
1851 speed, speed_efficiency = estimate_factor(
1852 n,
1853 swing,
1854 traction,
1855 speed,
1856 speed_efficiency,
1857 jitter_tolerance,
1858 )
1860 # update pos
1861 if adjust_sizes:
1862 df = np.linalg.norm(update, axis=-1)
1863 swinging = mass * df
1864 factor = 0.1 * speed / (1 + np.sqrt(speed * swinging))
1865 factor = np.minimum(factor * df, 10.0 * np.ones(df.shape)) / df
1866 else:
1867 swinging = mass * np.linalg.norm(update, axis=-1)
1868 factor = speed / (1 + np.sqrt(speed * swinging))
1870 factored_update = update * factor[:, None]
1871 pos_arr += factored_update
1872 if abs(factored_update).sum() < 1e-10:
1873 break
1875 pos = dict(zip(G, pos_arr))
1876 if store_pos_as is not None:
1877 nx.set_node_attributes(G, pos, store_pos_as)
1879 return pos
1882def rescale_layout(pos, scale=1):
1883 """Returns scaled position array to (-scale, scale) in all axes.
1885 The function acts on NumPy arrays which hold position information.
1886 Each position is one row of the array. The dimension of the space
1887 equals the number of columns. Each coordinate in one column.
1889 To rescale, the mean (center) is subtracted from each axis separately.
1890 Then all values are scaled so that the largest magnitude value
1891 from all axes equals `scale` (thus, the aspect ratio is preserved).
1892 The resulting NumPy Array is returned (order of rows unchanged).
1894 Parameters
1895 ----------
1896 pos : numpy array
1897 positions to be scaled. Each row is a position.
1899 scale : number (default: 1)
1900 The size of the resulting extent in all directions.
1902 attribute : str, default None
1903 If non-None, the position of each node will be stored on the graph as
1904 an attribute named `attribute` which can be accessed with
1905 `G.nodes[...][attribute]`. The function still returns the dictionary.
1907 Returns
1908 -------
1909 pos : numpy array
1910 scaled positions. Each row is a position.
1912 See Also
1913 --------
1914 rescale_layout_dict
1915 """
1916 import numpy as np
1918 # Find max length over all dimensions
1919 pos -= pos.mean(axis=0)
1920 lim = np.abs(pos).max() # max coordinate for all axes
1921 # rescale to (-scale, scale) in all directions, preserves aspect
1922 if lim > 0:
1923 pos *= scale / lim
1924 return pos
1927def rescale_layout_dict(pos, scale=1):
1928 """Return a dictionary of scaled positions keyed by node
1930 Parameters
1931 ----------
1932 pos : A dictionary of positions keyed by node
1934 scale : number (default: 1)
1935 The size of the resulting extent in all directions.
1937 Returns
1938 -------
1939 pos : A dictionary of positions keyed by node
1941 Examples
1942 --------
1943 >>> import numpy as np
1944 >>> pos = {0: np.array((0, 0)), 1: np.array((1, 1)), 2: np.array((0.5, 0.5))}
1945 >>> nx.rescale_layout_dict(pos)
1946 {0: array([-1., -1.]), 1: array([1., 1.]), 2: array([0., 0.])}
1948 >>> pos = {0: np.array((0, 0)), 1: np.array((-1, 1)), 2: np.array((-0.5, 0.5))}
1949 >>> nx.rescale_layout_dict(pos, scale=2)
1950 {0: array([ 2., -2.]), 1: array([-2., 2.]), 2: array([0., 0.])}
1952 See Also
1953 --------
1954 rescale_layout
1955 """
1956 import numpy as np
1958 if not pos: # empty_graph
1959 return {}
1960 pos_v = np.array(list(pos.values()))
1961 pos_v = rescale_layout(pos_v, scale=scale)
1962 return dict(zip(pos, pos_v))
1965def bfs_layout(G, start, *, align="vertical", scale=1, center=None, store_pos_as=None):
1966 """Position nodes according to breadth-first search algorithm.
1968 Parameters
1969 ----------
1970 G : NetworkX graph
1971 A position will be assigned to every node in G.
1973 start : node in `G`
1974 Starting node for bfs
1976 align : string (default='vertical')
1977 The alignment of nodes within a layer, either `"vertical"` or
1978 `"horizontal"`.
1980 scale : number (default: 1)
1981 Scale factor for positions.
1983 center : array-like or None
1984 Coordinate pair around which to center the layout.
1986 store_pos_as : str, default None
1987 If non-None, the position of each node will be stored on the graph as
1988 an attribute with this string as its name, which can be accessed with
1989 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
1991 Returns
1992 -------
1993 pos : dict
1994 A dictionary of positions keyed by node.
1996 Examples
1997 --------
1998 >>> from pprint import pprint
1999 >>> G = nx.path_graph(4)
2000 >>> pos = nx.bfs_layout(G, 0)
2001 >>> # suppress the returned dict and store on the graph directly
2002 >>> _ = nx.bfs_layout(G, 0, store_pos_as="pos")
2003 >>> pprint(nx.get_node_attributes(G, "pos"))
2004 {0: array([-1., 0.]),
2005 1: array([-0.33333333, 0. ]),
2006 2: array([0.33333333, 0. ]),
2007 3: array([1., 0.])}
2011 Notes
2012 -----
2013 This algorithm currently only works in two dimensions and does not
2014 try to minimize edge crossings.
2016 """
2017 G, center = _process_params(G, center, 2)
2019 # Compute layers with BFS
2020 layers = dict(enumerate(nx.bfs_layers(G, start)))
2022 if len(G) != sum(len(nodes) for nodes in layers.values()):
2023 raise nx.NetworkXError(
2024 "bfs_layout didn't include all nodes. Perhaps use input graph:\n"
2025 " G.subgraph(nx.node_connected_component(G, start))"
2026 )
2028 # Compute node positions with multipartite_layout
2029 pos = multipartite_layout(
2030 G, subset_key=layers, align=align, scale=scale, center=center
2031 )
2033 if store_pos_as is not None:
2034 nx.set_node_attributes(G, pos, store_pos_as)
2036 return pos