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(
604 [nfixed[node] for node in fixed if node in nfixed], dtype=int
605 )
607 if pos is not None:
608 # Determine size of existing domain to adjust initial positions
609 dom_size = max(coord for pos_tup in pos.values() for coord in pos_tup)
610 if dom_size == 0:
611 dom_size = 1
612 pos_arr = seed.rand(len(G), dim) * dom_size + center
614 for i, n in enumerate(G):
615 if n in pos:
616 pos_arr[i] = np.asarray(pos[n])
617 else:
618 pos_arr = None
619 dom_size = 1
621 if len(G) == 0:
622 return {}
623 if len(G) == 1:
624 pos = {nx.utils.arbitrary_element(G.nodes()): center}
625 if store_pos_as is not None:
626 nx.set_node_attributes(G, pos, store_pos_as)
627 return pos
629 # Sparse matrix
630 if len(G) >= 500 or method == "energy":
631 A = nx.to_scipy_sparse_array(G, weight=weight, dtype="f")
632 if k is None and fixed is not None:
633 # We must adjust k by domain size for layouts not near 1x1
634 nnodes, _ = A.shape
635 k = dom_size / np.sqrt(nnodes)
636 pos = _sparse_fruchterman_reingold(
637 A, k, pos_arr, fixed, iterations, threshold, dim, seed, method, gravity
638 )
639 else:
640 A = nx.to_numpy_array(G, weight=weight)
641 if k is None and fixed is not None:
642 # We must adjust k by domain size for layouts not near 1x1
643 nnodes, _ = A.shape
644 k = dom_size / np.sqrt(nnodes)
645 pos = _fruchterman_reingold(
646 A, k, pos_arr, fixed, iterations, threshold, dim, seed
647 )
648 if fixed is None and scale is not None:
649 pos = rescale_layout(pos, scale=scale) + center
650 pos = dict(zip(G, pos))
652 if store_pos_as is not None:
653 nx.set_node_attributes(G, pos, store_pos_as)
655 return pos
658fruchterman_reingold_layout = spring_layout
661@np_random_state(7)
662def _fruchterman_reingold(
663 A, k=None, pos=None, fixed=None, iterations=50, threshold=1e-4, dim=2, seed=None
664):
665 # Position nodes in adjacency matrix A using Fruchterman-Reingold
666 # Entry point for NetworkX graph is fruchterman_reingold_layout()
667 import numpy as np
669 try:
670 nnodes, _ = A.shape
671 except AttributeError as err:
672 msg = "fruchterman_reingold() takes an adjacency matrix as input"
673 raise nx.NetworkXError(msg) from err
675 if pos is None:
676 # random initial positions
677 pos = np.asarray(seed.rand(nnodes, dim), dtype=A.dtype)
678 else:
679 # make sure positions are of same type as matrix
680 pos = pos.astype(A.dtype)
682 # optimal distance between nodes
683 if k is None:
684 k = np.sqrt(1.0 / nnodes)
685 # the initial "temperature" is about .1 of domain area (=1x1)
686 # this is the largest step allowed in the dynamics.
687 # We need to calculate this in case our fixed positions force our domain
688 # to be much bigger than 1x1
689 t = max(max(pos.T[0]) - min(pos.T[0]), max(pos.T[1]) - min(pos.T[1])) * 0.1
690 # simple cooling scheme.
691 # linearly step down by dt on each iteration so last iteration is size dt.
692 dt = t / (iterations + 1)
693 delta = np.zeros((pos.shape[0], pos.shape[0], pos.shape[1]), dtype=A.dtype)
694 # the inscrutable (but fast) version
695 # this is still O(V^2)
696 # could use multilevel methods to speed this up significantly
697 for iteration in range(iterations):
698 # matrix of difference between points
699 delta = pos[:, np.newaxis, :] - pos[np.newaxis, :, :]
700 # distance between points
701 distance = np.linalg.norm(delta, axis=-1)
702 # enforce minimum distance of 0.01
703 np.clip(distance, 0.01, None, out=distance)
704 # displacement "force"
705 displacement = np.einsum(
706 "ijk,ij->ik", delta, (k * k / distance**2 - A * distance / k)
707 )
708 # update positions
709 length = np.linalg.norm(displacement, axis=-1)
710 # Threshold the minimum length prior to position scaling
711 # See gh-8113 for detailed discussion of the threshold
712 length = np.clip(length, a_min=0.01, a_max=None)
713 delta_pos = np.einsum("ij,i->ij", displacement, t / length)
714 if fixed is not None:
715 # don't change positions of fixed nodes
716 delta_pos[fixed] = 0.0
717 pos += delta_pos
718 # cool temperature
719 t -= dt
720 if (np.linalg.norm(delta_pos) / nnodes) < threshold:
721 break
722 return pos
725@np_random_state(7)
726def _sparse_fruchterman_reingold(
727 A,
728 k=None,
729 pos=None,
730 fixed=None,
731 iterations=50,
732 threshold=1e-4,
733 dim=2,
734 seed=None,
735 method="energy",
736 gravity=1.0,
737):
738 # Position nodes in adjacency matrix A using Fruchterman-Reingold
739 # Entry point for NetworkX graph is fruchterman_reingold_layout()
740 # Sparse version
741 import numpy as np
742 import scipy as sp
744 try:
745 nnodes, _ = A.shape
746 except AttributeError as err:
747 msg = "fruchterman_reingold() takes an adjacency matrix as input"
748 raise nx.NetworkXError(msg) from err
750 if pos is None:
751 # random initial positions
752 pos = np.asarray(seed.rand(nnodes, dim), dtype=A.dtype)
753 else:
754 # make sure positions are of same type as matrix
755 pos = pos.astype(A.dtype)
757 # no fixed nodes
758 if fixed is None:
759 fixed = []
761 # optimal distance between nodes
762 if k is None:
763 k = np.sqrt(1.0 / nnodes)
765 if method == "energy":
766 return _energy_fruchterman_reingold(
767 A, nnodes, k, pos, fixed, iterations, threshold, dim, gravity
768 )
770 # make sure we have a LIst of Lists representation
771 try:
772 A = A.tolil()
773 except AttributeError:
774 A = (sp.sparse.coo_array(A)).tolil()
776 # the initial "temperature" is about .1 of domain area (=1x1)
777 # this is the largest step allowed in the dynamics.
778 t = max(max(pos.T[0]) - min(pos.T[0]), max(pos.T[1]) - min(pos.T[1])) * 0.1
779 # simple cooling scheme.
780 # linearly step down by dt on each iteration so last iteration is size dt.
781 dt = t / (iterations + 1)
783 displacement = np.zeros((dim, nnodes))
784 for iteration in range(iterations):
785 displacement *= 0
786 # loop over rows
787 for i in range(A.shape[0]):
788 if i in fixed:
789 continue
790 # difference between this row's node position and all others
791 delta = (pos[i] - pos).T
792 # distance between points
793 distance = np.sqrt((delta**2).sum(axis=0))
794 # enforce minimum distance of 0.01
795 distance = np.clip(distance, a_min=0.01, a_max=None)
796 # the adjacency matrix row
797 Ai = A.getrowview(i).toarray() # TODO: revisit w/ sparse 1D container
798 # displacement "force"
799 displacement[:, i] += (
800 delta * (k * k / distance**2 - Ai * distance / k)
801 ).sum(axis=1)
802 # update positions
803 length = np.sqrt((displacement**2).sum(axis=0))
804 # Threshold the minimum length prior to position scaling
805 # See gh-8113 for detailed discussion of the threshold
806 length = np.clip(length, a_min=0.01, a_max=None)
807 delta_pos = (displacement * t / length).T
808 pos += delta_pos
809 # cool temperature
810 t -= dt
811 if (np.linalg.norm(delta_pos) / nnodes) < threshold:
812 break
813 return pos
816def _energy_fruchterman_reingold(
817 A, nnodes, k, pos, fixed, iterations, threshold, dim, gravity
818):
819 # Entry point for NetworkX graph is fruchterman_reingold_layout()
820 # energy-based version
821 import numpy as np
822 import scipy as sp
824 if gravity <= 0:
825 raise ValueError(f"the gravity must be positive.")
827 # make sure we have a Compressed Sparse Row format
828 try:
829 A = A.tocsr()
830 except AttributeError:
831 A = sp.sparse.csr_array(A)
833 # Take absolute values of edge weights and symmetrize it
834 A = np.abs(A)
835 A = (A + A.T) / 2
837 n_components, labels = sp.sparse.csgraph.connected_components(A, directed=False)
838 bincount = np.bincount(labels)
839 batchsize = 500
841 def _cost_FR(x):
842 pos = x.reshape((nnodes, dim))
843 grad = np.zeros((nnodes, dim))
844 cost = 0.0
845 for l in range(0, nnodes, batchsize):
846 r = min(l + batchsize, nnodes)
847 # difference between selected node positions and all others
848 delta = pos[l:r, np.newaxis, :] - pos[np.newaxis, :, :]
849 # distance between points with a minimum distance of 1e-5
850 distance2 = np.sum(delta * delta, axis=2)
851 distance2 = np.maximum(distance2, 1e-10)
852 distance = np.sqrt(distance2)
853 # temporary variable for calculation
854 Ad = A[l:r] * distance
855 # attractive forces and repulsive forces
856 grad[l:r] = 2 * np.einsum("ij,ijk->ik", Ad / k - k**2 / distance2, delta)
857 # integrated attractive forces
858 cost += np.sum(Ad * distance2) / (3 * k)
859 # integrated repulsive forces
860 cost -= k**2 * np.sum(np.log(distance))
861 # gravitational force from the centroids of connected components to (0.5, ..., 0.5)^T
862 centers = np.zeros((n_components, dim))
863 np.add.at(centers, labels, pos)
864 delta0 = centers / bincount[:, np.newaxis] - 0.5
865 grad += gravity * delta0[labels]
866 cost += gravity * 0.5 * np.sum(bincount * np.linalg.norm(delta0, axis=1) ** 2)
867 # fix positions of fixed nodes
868 grad[fixed] = 0.0
869 return cost, grad.ravel()
871 # Optimization of the energy function by L-BFGS algorithm
872 options = {"maxiter": iterations, "gtol": threshold}
873 return sp.optimize.minimize(
874 _cost_FR, pos.ravel(), method="L-BFGS-B", jac=True, options=options
875 ).x.reshape((nnodes, dim))
878def kamada_kawai_layout(
879 G,
880 dist=None,
881 pos=None,
882 weight="weight",
883 scale=1,
884 center=None,
885 dim=2,
886 store_pos_as=None,
887):
888 """Position nodes using Kamada-Kawai path-length cost-function.
890 Parameters
891 ----------
892 G : NetworkX graph or list of nodes
893 A position will be assigned to every node in G.
895 dist : dict (default=None)
896 A two-level dictionary of optimal distances between nodes,
897 indexed by source and destination node.
898 If None, the distance is computed using shortest_path_length().
900 pos : dict or None optional (default=None)
901 Initial positions for nodes as a dictionary with node as keys
902 and values as a coordinate list or tuple. If None, then use
903 circular_layout() for dim >= 2 and a linear layout for dim == 1.
905 weight : string or None optional (default='weight')
906 The edge attribute that holds the numerical value used for
907 the edge weight. If None, then all edge weights are 1.
909 scale : number (default: 1)
910 Scale factor for positions.
912 center : array-like or None
913 Coordinate pair around which to center the layout.
915 dim : int
916 Dimension of layout.
918 store_pos_as : str, default None
919 If non-None, the position of each node will be stored on the graph as
920 an attribute with this string as its name, which can be accessed with
921 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
923 Returns
924 -------
925 pos : dict
926 A dictionary of positions keyed by node
928 Examples
929 --------
930 >>> from pprint import pprint
931 >>> G = nx.path_graph(4)
932 >>> pos = nx.kamada_kawai_layout(G)
933 >>> # suppress the returned dict and store on the graph directly
934 >>> _ = nx.kamada_kawai_layout(G, store_pos_as="pos")
935 >>> pprint(nx.get_node_attributes(G, "pos"))
936 {0: array([0.99996577, 0.99366857]),
937 1: array([0.32913544, 0.33543827]),
938 2: array([-0.33544334, -0.32910684]),
939 3: array([-0.99365787, -1. ])}
940 """
941 import numpy as np
943 G, center = _process_params(G, center, dim)
944 nNodes = len(G)
945 if nNodes == 0:
946 return {}
948 if dist is None:
949 dist = dict(nx.shortest_path_length(G, weight=weight))
950 dist_mtx = 1e6 * np.ones((nNodes, nNodes))
951 for row, nr in enumerate(G):
952 if nr not in dist:
953 continue
954 rdist = dist[nr]
955 for col, nc in enumerate(G):
956 if nc not in rdist:
957 continue
958 dist_mtx[row][col] = rdist[nc]
960 if pos is None:
961 if dim >= 3:
962 pos = random_layout(G, dim=dim)
963 elif dim == 2:
964 pos = circular_layout(G, dim=dim)
965 else:
966 pos = dict(zip(G, np.linspace(0, 1, len(G))))
967 pos_arr = np.array([pos[n] for n in G])
969 pos = _kamada_kawai_solve(dist_mtx, pos_arr, dim)
971 pos = rescale_layout(pos, scale=scale) + center
972 pos = dict(zip(G, pos))
974 if store_pos_as is not None:
975 nx.set_node_attributes(G, pos, store_pos_as)
977 return pos
980def _kamada_kawai_solve(dist_mtx, pos_arr, dim):
981 # Anneal node locations based on the Kamada-Kawai cost-function,
982 # using the supplied matrix of preferred inter-node distances,
983 # and starting locations.
985 import numpy as np
986 import scipy as sp
988 meanwt = 1e-3
989 costargs = (np, 1 / (dist_mtx + np.eye(dist_mtx.shape[0]) * 1e-3), meanwt, dim)
991 optresult = sp.optimize.minimize(
992 _kamada_kawai_costfn,
993 pos_arr.ravel(),
994 method="L-BFGS-B",
995 args=costargs,
996 jac=True,
997 )
999 return optresult.x.reshape((-1, dim))
1002def _kamada_kawai_costfn(pos_vec, np, invdist, meanweight, dim):
1003 # Cost-function and gradient for Kamada-Kawai layout algorithm
1004 nNodes = invdist.shape[0]
1005 pos_arr = pos_vec.reshape((nNodes, dim))
1007 delta = pos_arr[:, np.newaxis, :] - pos_arr[np.newaxis, :, :]
1008 nodesep = np.linalg.norm(delta, axis=-1)
1009 direction = np.einsum("ijk,ij->ijk", delta, 1 / (nodesep + np.eye(nNodes) * 1e-3))
1011 offset = nodesep * invdist - 1.0
1012 offset[np.diag_indices(nNodes)] = 0
1014 cost = 0.5 * np.sum(offset**2)
1015 grad = np.einsum("ij,ij,ijk->ik", invdist, offset, direction) - np.einsum(
1016 "ij,ij,ijk->jk", invdist, offset, direction
1017 )
1019 # Additional parabolic term to encourage mean position to be near origin:
1020 sumpos = np.sum(pos_arr, axis=0)
1021 cost += 0.5 * meanweight * np.sum(sumpos**2)
1022 grad += meanweight * sumpos
1024 return (cost, grad.ravel())
1027def spectral_layout(G, weight="weight", scale=1, center=None, dim=2, store_pos_as=None):
1028 """Position nodes using the eigenvectors of the graph Laplacian.
1030 Using the unnormalized Laplacian, the layout shows possible clusters of
1031 nodes which are an approximation of the ratio cut. If dim is the number of
1032 dimensions then the positions are the entries of the dim eigenvectors
1033 corresponding to the ascending eigenvalues starting from the second one.
1035 Parameters
1036 ----------
1037 G : NetworkX graph or list of nodes
1038 A position will be assigned to every node in G.
1040 weight : string or None optional (default='weight')
1041 The edge attribute that holds the numerical value used for
1042 the edge weight. If None, then all edge weights are 1.
1044 scale : number (default: 1)
1045 Scale factor for positions.
1047 center : array-like or None
1048 Coordinate pair around which to center the layout.
1050 dim : int
1051 Dimension of layout.
1053 store_pos_as : str, default None
1054 If non-None, the position of each node will be stored on the graph as
1055 an attribute with this string as its name, which can be accessed with
1056 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
1058 Returns
1059 -------
1060 pos : dict
1061 A dictionary of positions keyed by node
1063 Examples
1064 --------
1065 >>> from pprint import pprint
1066 >>> G = nx.path_graph(4)
1067 >>> pos = nx.spectral_layout(G)
1068 >>> # suppress the returned dict and store on the graph directly
1069 >>> _ = nx.spectral_layout(G, store_pos_as="pos")
1070 >>> pprint(nx.get_node_attributes(G, "pos"))
1071 {0: array([-1. , 0.76536686]),
1072 1: array([-0.41421356, -0.76536686]),
1073 2: array([ 0.41421356, -0.76536686]),
1074 3: array([1. , 0.76536686])}
1077 Notes
1078 -----
1079 Directed graphs will be considered as undirected graphs when
1080 positioning the nodes.
1082 For larger graphs (>500 nodes) this will use the SciPy sparse
1083 eigenvalue solver (ARPACK).
1084 """
1085 # handle some special cases that break the eigensolvers
1086 import numpy as np
1088 G, center = _process_params(G, center, dim)
1090 if len(G) <= 2:
1091 if len(G) == 0:
1092 pos = np.array([])
1093 elif len(G) == 1:
1094 pos = np.array([center])
1095 else:
1096 pos = np.array([np.zeros(dim), np.array(center) * 2.0])
1097 return dict(zip(G, pos))
1098 try:
1099 # Sparse matrix
1100 if len(G) < 500: # dense solver is faster for small graphs
1101 raise ValueError
1102 A = nx.to_scipy_sparse_array(G, weight=weight, dtype="d")
1103 # Symmetrize directed graphs
1104 if G.is_directed():
1105 A = A + np.transpose(A)
1106 pos = _sparse_spectral(A, dim)
1107 except (ImportError, ValueError):
1108 # Dense matrix
1109 A = nx.to_numpy_array(G, weight=weight)
1110 # Symmetrize directed graphs
1111 if G.is_directed():
1112 A += A.T
1113 pos = _spectral(A, dim)
1115 pos = rescale_layout(pos, scale=scale) + center
1116 pos = dict(zip(G, pos))
1118 if store_pos_as is not None:
1119 nx.set_node_attributes(G, pos, store_pos_as)
1121 return pos
1124def _spectral(A, dim=2):
1125 # Input adjacency matrix A
1126 # Uses dense eigenvalue solver from numpy
1127 import numpy as np
1129 try:
1130 nnodes, _ = A.shape
1131 except AttributeError as err:
1132 msg = "spectral() takes an adjacency matrix as input"
1133 raise nx.NetworkXError(msg) from err
1135 # form Laplacian matrix where D is diagonal of degrees
1136 D = np.identity(nnodes, dtype=A.dtype) * np.sum(A, axis=1)
1137 L = D - A
1139 eigenvalues, eigenvectors = np.linalg.eig(L)
1140 # sort and keep smallest nonzero
1141 index = np.argsort(eigenvalues)[1 : dim + 1] # 0 index is zero eigenvalue
1142 return np.real(eigenvectors[:, index])
1145def _sparse_spectral(A, dim=2):
1146 # Input adjacency matrix A
1147 # Uses sparse eigenvalue solver from scipy
1148 # Could use multilevel methods here, see Koren "On spectral graph drawing"
1149 import numpy as np
1150 import scipy as sp
1152 try:
1153 nnodes, _ = A.shape
1154 except AttributeError as err:
1155 msg = "sparse_spectral() takes an adjacency matrix as input"
1156 raise nx.NetworkXError(msg) from err
1158 # form Laplacian matrix
1159 D = sp.sparse.dia_array((A.sum(axis=1), 0), shape=(nnodes, nnodes)).tocsr()
1160 L = D - A
1162 k = dim + 1
1163 # number of Lanczos vectors for ARPACK solver.What is the right scaling?
1164 ncv = max(2 * k + 1, int(np.sqrt(nnodes)))
1165 # return smallest k eigenvalues and eigenvectors
1166 eigenvalues, eigenvectors = sp.sparse.linalg.eigsh(L, k, which="SM", ncv=ncv)
1167 index = np.argsort(eigenvalues)[1:k] # 0 index is zero eigenvalue
1168 return np.real(eigenvectors[:, index])
1171def planar_layout(G, scale=1, center=None, dim=2, store_pos_as=None):
1172 """Position nodes without edge intersections.
1174 Parameters
1175 ----------
1176 G : NetworkX graph or list of nodes
1177 A position will be assigned to every node in G. If G is of type
1178 nx.PlanarEmbedding, the positions are selected accordingly.
1180 scale : number (default: 1)
1181 Scale factor for positions.
1183 center : array-like or None
1184 Coordinate pair around which to center the layout.
1186 dim : int
1187 Dimension of layout.
1189 store_pos_as : str, default None
1190 If non-None, the position of each node will be stored on the graph as
1191 an attribute with this string as its name, which can be accessed with
1192 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
1194 Returns
1195 -------
1196 pos : dict
1197 A dictionary of positions keyed by node
1199 Raises
1200 ------
1201 NetworkXException
1202 If G is not planar
1204 Examples
1205 --------
1206 >>> from pprint import pprint
1207 >>> G = nx.path_graph(4)
1208 >>> pos = nx.planar_layout(G)
1209 >>> # suppress the returned dict and store on the graph directly
1210 >>> _ = nx.planar_layout(G, store_pos_as="pos")
1211 >>> pprint(nx.get_node_attributes(G, "pos"))
1212 {0: array([-0.77777778, -0.33333333]),
1213 1: array([ 1. , -0.33333333]),
1214 2: array([0.11111111, 0.55555556]),
1215 3: array([-0.33333333, 0.11111111])}
1216 """
1217 import numpy as np
1219 if dim != 2:
1220 raise ValueError("can only handle 2 dimensions")
1222 G, center = _process_params(G, center, dim)
1224 if len(G) == 0:
1225 return {}
1227 if isinstance(G, nx.PlanarEmbedding):
1228 embedding = G
1229 else:
1230 is_planar, embedding = nx.check_planarity(G)
1231 if not is_planar:
1232 raise nx.NetworkXException("G is not planar.")
1233 pos = nx.combinatorial_embedding_to_pos(embedding)
1234 node_list = list(embedding)
1235 pos = np.vstack([pos[x] for x in node_list])
1236 pos = pos.astype(np.float64)
1237 pos = rescale_layout(pos, scale=scale) + center
1238 pos = dict(zip(node_list, pos))
1239 if store_pos_as is not None:
1240 nx.set_node_attributes(G, pos, store_pos_as)
1241 return pos
1244def spiral_layout(
1245 G,
1246 scale=1,
1247 center=None,
1248 dim=2,
1249 resolution=0.35,
1250 equidistant=False,
1251 store_pos_as=None,
1252):
1253 """Position nodes in a spiral layout.
1255 Parameters
1256 ----------
1257 G : NetworkX graph or list of nodes
1258 A position will be assigned to every node in G.
1260 scale : number (default: 1)
1261 Scale factor for positions.
1263 center : array-like or None
1264 Coordinate pair around which to center the layout.
1266 dim : int, default=2
1267 Dimension of layout, currently only dim=2 is supported.
1268 Other dimension values result in a ValueError.
1270 resolution : float, default=0.35
1271 The compactness of the spiral layout returned.
1272 Lower values result in more compressed spiral layouts.
1274 equidistant : bool, default=False
1275 If True, nodes will be positioned equidistant from each other
1276 by decreasing angle further from center.
1277 If False, nodes will be positioned at equal angles
1278 from each other by increasing separation further from center.
1280 store_pos_as : str, default None
1281 If non-None, the position of each node will be stored on the graph as
1282 an attribute with this string as its name, which can be accessed with
1283 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
1285 Returns
1286 -------
1287 pos : dict
1288 A dictionary of positions keyed by node
1290 Raises
1291 ------
1292 ValueError
1293 If dim != 2
1295 Examples
1296 --------
1297 >>> from pprint import pprint
1298 >>> G = nx.path_graph(4)
1299 >>> pos = nx.spiral_layout(G)
1300 >>> nx.draw(G, pos=pos)
1301 >>> # suppress the returned dict and store on the graph directly
1302 >>> _ = nx.spiral_layout(G, store_pos_as="pos")
1303 >>> pprint(nx.get_node_attributes(G, "pos"))
1304 {0: array([-0.64153279, -0.68555087]),
1305 1: array([-0.03307913, -0.46344795]),
1306 2: array([0.34927952, 0.14899882]),
1307 3: array([0.32533239, 1. ])}
1309 Notes
1310 -----
1311 This algorithm currently only works in two dimensions.
1313 """
1314 import numpy as np
1316 if dim != 2:
1317 raise ValueError("can only handle 2 dimensions")
1319 G, center = _process_params(G, center, dim)
1321 if len(G) == 0:
1322 return {}
1323 if len(G) == 1:
1324 pos = {nx.utils.arbitrary_element(G): center}
1325 if store_pos_as is not None:
1326 nx.set_node_attributes(G, pos, store_pos_as)
1327 return pos
1329 pos = []
1330 if equidistant:
1331 chord = 1
1332 step = 0.5
1333 theta = resolution
1334 theta += chord / (step * theta)
1335 for _ in range(len(G)):
1336 r = step * theta
1337 theta += chord / r
1338 pos.append([np.cos(theta) * r, np.sin(theta) * r])
1340 else:
1341 dist = np.arange(len(G), dtype=float)
1342 angle = resolution * dist
1343 pos = np.transpose(dist * np.array([np.cos(angle), np.sin(angle)]))
1345 pos = rescale_layout(np.array(pos), scale=scale) + center
1347 pos = dict(zip(G, pos))
1349 if store_pos_as is not None:
1350 nx.set_node_attributes(G, pos, store_pos_as)
1352 return pos
1355def multipartite_layout(
1356 G, subset_key="subset", align="vertical", scale=1, center=None, store_pos_as=None
1357):
1358 """Position nodes in layers of straight lines.
1360 Parameters
1361 ----------
1362 G : NetworkX graph or list of nodes
1363 A position will be assigned to every node in G.
1365 subset_key : string or dict (default='subset')
1366 If a string, the key of node data in G that holds the node subset.
1367 If a dict, keyed by layer number to the nodes in that layer/subset.
1369 align : string (default='vertical')
1370 The alignment of nodes. Vertical or horizontal.
1372 scale : number (default: 1)
1373 Scale factor for positions.
1375 center : array-like or None
1376 Coordinate pair around which to center the layout.
1378 store_pos_as : str, default None
1379 If non-None, the position of each node will be stored on the graph as
1380 an attribute with this string as its name, which can be accessed with
1381 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
1383 Returns
1384 -------
1385 pos : dict
1386 A dictionary of positions keyed by node.
1388 Examples
1389 --------
1390 >>> G = nx.complete_multipartite_graph(28, 16, 10)
1391 >>> pos = nx.multipartite_layout(G)
1392 >>> # suppress the returned dict and store on the graph directly
1393 >>> G = nx.complete_multipartite_graph(28, 16, 10)
1394 >>> _ = nx.multipartite_layout(G, store_pos_as="pos")
1396 or use a dict to provide the layers of the layout
1398 >>> G = nx.Graph([(0, 1), (1, 2), (1, 3), (3, 4)])
1399 >>> layers = {"a": [0], "b": [1], "c": [2, 3], "d": [4]}
1400 >>> pos = nx.multipartite_layout(G, subset_key=layers)
1402 Notes
1403 -----
1404 This algorithm currently only works in two dimensions and does not
1405 try to minimize edge crossings.
1407 Network does not need to be a complete multipartite graph. As long as nodes
1408 have subset_key data, they will be placed in the corresponding layers.
1410 """
1411 import numpy as np
1413 if align not in ("vertical", "horizontal"):
1414 msg = "align must be either vertical or horizontal."
1415 raise ValueError(msg)
1417 G, center = _process_params(G, center=center, dim=2)
1418 if len(G) == 0:
1419 return {}
1421 try:
1422 # check if subset_key is dict-like
1423 if len(G) != sum(len(nodes) for nodes in subset_key.values()):
1424 raise nx.NetworkXError(
1425 "all nodes must be in one subset of `subset_key` dict"
1426 )
1427 except AttributeError:
1428 # subset_key is not a dict, hence a string
1429 node_to_subset = nx.get_node_attributes(G, subset_key)
1430 if len(node_to_subset) != len(G):
1431 raise nx.NetworkXError(
1432 f"all nodes need a subset_key attribute: {subset_key}"
1433 )
1434 subset_key = nx.utils.groups(node_to_subset)
1436 # Sort by layer, if possible
1437 try:
1438 layers = dict(sorted(subset_key.items()))
1439 except TypeError:
1440 layers = subset_key
1442 pos = None
1443 nodes = []
1444 width = len(layers)
1445 for i, layer in enumerate(layers.values()):
1446 height = len(layer)
1447 xs = np.repeat(i, height)
1448 ys = np.arange(0, height, dtype=float)
1449 offset = ((width - 1) / 2, (height - 1) / 2)
1450 layer_pos = np.column_stack([xs, ys]) - offset
1451 if pos is None:
1452 pos = layer_pos
1453 else:
1454 pos = np.concatenate([pos, layer_pos])
1455 nodes.extend(layer)
1456 pos = rescale_layout(pos, scale=scale) + center
1457 if align == "horizontal":
1458 pos = pos[:, ::-1] # swap x and y coords
1459 pos = dict(zip(nodes, pos))
1461 if store_pos_as is not None:
1462 nx.set_node_attributes(G, pos, store_pos_as)
1464 return pos
1467@np_random_state("seed")
1468def arf_layout(
1469 G,
1470 pos=None,
1471 scaling=1,
1472 a=1.1,
1473 etol=1e-6,
1474 dt=1e-3,
1475 max_iter=1000,
1476 *,
1477 seed=None,
1478 store_pos_as=None,
1479):
1480 """Arf layout for networkx
1482 The attractive and repulsive forces (arf) layout [1] improves the spring
1483 layout in three ways. First, it prevents congestion of highly connected nodes
1484 due to strong forcing between nodes. Second, it utilizes the layout space
1485 more effectively by preventing large gaps that spring layout tends to create.
1486 Lastly, the arf layout represents symmetries in the layout better than the
1487 default spring layout.
1489 Parameters
1490 ----------
1491 G : nx.Graph or nx.DiGraph
1492 Networkx graph.
1493 pos : dict
1494 Initial position of the nodes. If set to None a
1495 random layout will be used.
1496 scaling : float
1497 Scales the radius of the circular layout space.
1498 a : float
1499 Strength of springs between connected nodes. Should be larger than 1.
1500 The greater a, the clearer the separation of unconnected sub clusters.
1501 etol : float
1502 Gradient sum of spring forces must be larger than `etol` before successful
1503 termination.
1504 dt : float
1505 Time step for force differential equation simulations.
1506 max_iter : int
1507 Max iterations before termination of the algorithm.
1508 seed : int, RandomState instance or None optional (default=None)
1509 Set the random state for deterministic node layouts.
1510 If int, `seed` is the seed used by the random number generator,
1511 if numpy.random.RandomState instance, `seed` is the random
1512 number generator,
1513 if None, the random number generator is the RandomState instance used
1514 by numpy.random.
1515 store_pos_as : str, default None
1516 If non-None, the position of each node will be stored on the graph as
1517 an attribute with this string as its name, which can be accessed with
1518 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
1520 Returns
1521 -------
1522 pos : dict
1523 A dictionary of positions keyed by node.
1525 Examples
1526 --------
1527 >>> G = nx.grid_graph((5, 5))
1528 >>> pos = nx.arf_layout(G)
1529 >>> # suppress the returned dict and store on the graph directly
1530 >>> G = nx.grid_graph((5, 5))
1531 >>> _ = nx.arf_layout(G, store_pos_as="pos")
1533 References
1534 ----------
1535 .. [1] "Self-Organization Applied to Dynamic Network Layout", M. Geipel,
1536 International Journal of Modern Physics C, 2007, Vol 18, No 10,
1537 pp. 1537-1549.
1538 https://doi.org/10.1142/S0129183107011558 https://arxiv.org/abs/0704.1748
1539 """
1540 import warnings
1542 import numpy as np
1544 if a <= 1:
1545 msg = "The parameter a should be larger than 1"
1546 raise ValueError(msg)
1548 pos_tmp = nx.random_layout(G, seed=seed)
1549 if pos is None:
1550 pos = pos_tmp
1551 else:
1552 for node in G.nodes():
1553 if node not in pos:
1554 pos[node] = pos_tmp[node].copy()
1556 # Initialize spring constant matrix
1557 N = len(G)
1558 # No nodes no computation
1559 if N == 0:
1560 return pos
1562 # init force of springs
1563 K = np.ones((N, N)) - np.eye(N)
1564 node_order = {node: i for i, node in enumerate(G)}
1565 for x, y in G.edges():
1566 if x != y:
1567 idx, jdx = (node_order[i] for i in (x, y))
1568 K[idx, jdx] = a
1570 # vectorize values
1571 p = np.asarray(list(pos.values()))
1573 # equation 10 in [1]
1574 rho = scaling * np.sqrt(N)
1576 # looping variables
1577 error = etol + 1
1578 n_iter = 0
1579 while error > etol:
1580 diff = p[:, np.newaxis] - p[np.newaxis]
1581 A = np.linalg.norm(diff, axis=-1)[..., np.newaxis]
1582 # attraction_force - repulsions force
1583 # suppress nans due to division; caused by diagonal set to zero.
1584 # Does not affect the computation due to nansum
1585 with warnings.catch_warnings():
1586 warnings.simplefilter("ignore")
1587 change = K[..., np.newaxis] * diff - rho / A * diff
1588 change = np.nansum(change, axis=0)
1589 p += change * dt
1591 error = np.linalg.norm(change, axis=-1).sum()
1592 if n_iter > max_iter:
1593 break
1594 n_iter += 1
1596 pos = dict(zip(G.nodes(), p))
1598 if store_pos_as is not None:
1599 nx.set_node_attributes(G, pos, store_pos_as)
1601 return pos
1604@np_random_state("seed")
1605@nx._dispatchable(edge_attrs="weight", mutates_input={"store_pos_as": 15})
1606def forceatlas2_layout(
1607 G,
1608 pos=None,
1609 *,
1610 max_iter=100,
1611 jitter_tolerance=1.0,
1612 scaling_ratio=2.0,
1613 gravity=1.0,
1614 distributed_action=False,
1615 strong_gravity=False,
1616 node_mass=None,
1617 node_size=None,
1618 weight=None,
1619 linlog=False,
1620 seed=None,
1621 dim=2,
1622 store_pos_as=None,
1623):
1624 """Position nodes using the ForceAtlas2 force-directed layout algorithm.
1626 This function applies the ForceAtlas2 layout algorithm [1]_ to a NetworkX graph,
1627 positioning the nodes in a way that visually represents the structure of the graph.
1628 The algorithm uses physical simulation to minimize the energy of the system,
1629 resulting in a more readable layout.
1631 Parameters
1632 ----------
1633 G : nx.Graph
1634 A NetworkX graph to be laid out.
1635 pos : dict or None, optional
1636 Initial positions of the nodes. If None, random initial positions are used.
1637 max_iter : int (default: 100)
1638 Number of iterations for the layout optimization.
1639 jitter_tolerance : float (default: 1.0)
1640 Controls the tolerance for adjusting the speed of layout generation.
1641 scaling_ratio : float (default: 2.0)
1642 Determines the scaling of attraction and repulsion forces.
1643 gravity : float (default: 1.0)
1644 Determines the amount of attraction on nodes to the center. Prevents islands
1645 (i.e. weakly connected or disconnected parts of the graph)
1646 from drifting away.
1647 distributed_action : bool (default: False)
1648 Distributes the attraction force evenly among nodes.
1649 strong_gravity : bool (default: False)
1650 Applies a strong gravitational pull towards the center.
1651 node_mass : dict or None, optional
1652 Maps nodes to their masses, influencing the attraction to other nodes.
1653 node_size : dict or None, optional
1654 Maps nodes to their sizes, preventing crowding by creating a halo effect.
1655 weight : string or None, optional (default: None)
1656 The edge attribute that holds the numerical value used for
1657 the edge weight. If None, then all edge weights are 1.
1658 linlog : bool (default: False)
1659 Uses logarithmic attraction instead of linear.
1660 seed : int, RandomState instance or None optional (default=None)
1661 Used only for the initial positions in the algorithm.
1662 Set the random state for deterministic node layouts.
1663 If int, `seed` is the seed used by the random number generator,
1664 if numpy.random.RandomState instance, `seed` is the random
1665 number generator,
1666 if None, the random number generator is the RandomState instance used
1667 by numpy.random.
1668 dim : int (default: 2)
1669 Sets the dimensions for the layout. Ignored if `pos` is provided.
1670 store_pos_as : str, default None
1671 If non-None, the position of each node will be stored on the graph as
1672 an attribute with this string as its name, which can be accessed with
1673 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
1675 Examples
1676 --------
1677 >>> import networkx as nx
1678 >>> G = nx.florentine_families_graph()
1679 >>> pos = nx.forceatlas2_layout(G)
1680 >>> nx.draw(G, pos=pos)
1681 >>> # suppress the returned dict and store on the graph directly
1682 >>> pos = nx.forceatlas2_layout(G, store_pos_as="pos")
1683 >>> _ = nx.forceatlas2_layout(G, store_pos_as="pos")
1685 References
1686 ----------
1687 .. [1] Jacomy, M., Venturini, T., Heymann, S., & Bastian, M. (2014).
1688 ForceAtlas2, a continuous graph layout algorithm for handy network
1689 visualization designed for the Gephi software. PloS one, 9(6), e98679.
1690 https://doi.org/10.1371/journal.pone.0098679
1691 """
1692 import numpy as np
1694 if len(G) == 0:
1695 return {}
1696 # parse optional pos positions
1697 if pos is None:
1698 pos = nx.random_layout(G, dim=dim, seed=seed)
1699 pos_arr = np.array(list(pos.values()))
1700 elif len(pos) == len(G):
1701 pos_arr = np.array([pos[node] for node in G])
1702 else:
1703 # set random node pos within the initial pos values
1704 pos_init = np.array(list(pos.values()))
1705 max_pos = pos_init.max(axis=0)
1706 min_pos = pos_init.min(axis=0)
1707 dim = max_pos.size
1708 pos_arr = min_pos + seed.rand(len(G), dim) * (max_pos - min_pos)
1709 for idx, node in enumerate(G):
1710 if node in pos:
1711 pos_arr[idx] = pos[node].copy()
1713 mass = np.zeros(len(G))
1714 size = np.zeros(len(G))
1716 # Only adjust for size when the users specifies size other than default (1)
1717 adjust_sizes = False
1718 if node_size is None:
1719 node_size = {}
1720 else:
1721 adjust_sizes = True
1723 if node_mass is None:
1724 node_mass = {}
1726 for idx, node in enumerate(G):
1727 mass[idx] = node_mass.get(node, G.degree(node) + 1)
1728 size[idx] = node_size.get(node, 1)
1730 n = len(G)
1731 gravities = np.zeros((n, dim))
1732 attraction = np.zeros((n, dim))
1733 repulsion = np.zeros((n, dim))
1734 A = nx.to_numpy_array(G, weight=weight)
1736 def estimate_factor(n, swing, traction, speed, speed_efficiency, jitter_tolerance):
1737 """Computes the scaling factor for the force in the ForceAtlas2 layout algorithm.
1739 This helper function adjusts the speed and
1740 efficiency of the layout generation based on the
1741 current state of the system, such as the number of
1742 nodes, current swing, and traction forces.
1744 Parameters
1745 ----------
1746 n : int
1747 Number of nodes in the graph.
1748 swing : float
1749 The current swing, representing the oscillation of the nodes.
1750 traction : float
1751 The current traction force, representing the attraction between nodes.
1752 speed : float
1753 The current speed of the layout generation.
1754 speed_efficiency : float
1755 The efficiency of the current speed, influencing how fast the layout converges.
1756 jitter_tolerance : float
1757 The tolerance for jitter, affecting how much speed adjustment is allowed.
1759 Returns
1760 -------
1761 tuple
1762 A tuple containing the updated speed and speed efficiency.
1764 Notes
1765 -----
1766 This function is a part of the ForceAtlas2 layout algorithm and is used to dynamically adjust the
1767 layout parameters to achieve an optimal and stable visualization.
1769 """
1770 import numpy as np
1772 # estimate jitter
1773 opt_jitter = 0.05 * np.sqrt(n)
1774 min_jitter = np.sqrt(opt_jitter)
1775 max_jitter = 10
1776 min_speed_efficiency = 0.05
1778 other = min(max_jitter, opt_jitter * traction / n**2)
1779 jitter = jitter_tolerance * max(min_jitter, other)
1781 if swing / traction > 2.0:
1782 if speed_efficiency > min_speed_efficiency:
1783 speed_efficiency *= 0.5
1784 jitter = max(jitter, jitter_tolerance)
1785 if swing == 0:
1786 target_speed = np.inf
1787 else:
1788 target_speed = jitter * speed_efficiency * traction / swing
1790 if swing > jitter * traction:
1791 if speed_efficiency > min_speed_efficiency:
1792 speed_efficiency *= 0.7
1793 elif speed < 1000:
1794 speed_efficiency *= 1.3
1796 max_rise = 0.5
1797 speed = speed + min(target_speed - speed, max_rise * speed)
1798 return speed, speed_efficiency
1800 speed = 1
1801 speed_efficiency = 1
1802 swing = 1
1803 traction = 1
1804 for _ in range(max_iter):
1805 # compute pairwise difference
1806 diff = pos_arr[:, None] - pos_arr[None]
1807 # compute pairwise distance
1808 distance = np.linalg.norm(diff, axis=-1)
1810 # linear attraction
1811 if linlog:
1812 attraction = -np.log(1 + distance) / distance
1813 np.fill_diagonal(attraction, 0)
1814 attraction = np.einsum("ij, ij -> ij", attraction, A)
1815 attraction = np.einsum("ijk, ij -> ik", diff, attraction)
1817 else:
1818 attraction = -np.einsum("ijk, ij -> ik", diff, A)
1820 if distributed_action:
1821 attraction /= mass[:, None]
1823 # repulsion
1824 tmp = mass[:, None] @ mass[None]
1825 if adjust_sizes:
1826 distance += -size[:, None] - size[None]
1828 d2 = distance**2
1829 # remove self-interaction
1830 np.fill_diagonal(tmp, 0)
1831 np.fill_diagonal(d2, 1)
1832 factor = (tmp / d2) * scaling_ratio
1833 repulsion = np.einsum("ijk, ij -> ik", diff, factor)
1835 # gravity
1836 pos_centered = pos_arr - np.mean(pos_arr, axis=0)
1837 if strong_gravity:
1838 gravities = -gravity * mass[:, None] * pos_centered
1839 else:
1840 # hide warnings for divide by zero. Then change nan to 0
1841 with np.errstate(divide="ignore", invalid="ignore"):
1842 unit_vec = pos_centered / np.linalg.norm(pos_centered, axis=-1)[:, None]
1843 unit_vec = np.nan_to_num(unit_vec, nan=0)
1844 gravities = -gravity * mass[:, None] * unit_vec
1846 # total forces
1847 update = attraction + repulsion + gravities
1849 # compute total swing and traction
1850 swing += (mass * np.linalg.norm(pos_arr - update, axis=-1)).sum()
1851 traction += (0.5 * mass * np.linalg.norm(pos_arr + update, axis=-1)).sum()
1853 speed, speed_efficiency = estimate_factor(
1854 n,
1855 swing,
1856 traction,
1857 speed,
1858 speed_efficiency,
1859 jitter_tolerance,
1860 )
1862 # update pos
1863 if adjust_sizes:
1864 df = np.linalg.norm(update, axis=-1)
1865 swinging = mass * df
1866 factor = 0.1 * speed / (1 + np.sqrt(speed * swinging))
1867 factor = np.minimum(factor * df, 10.0 * np.ones(df.shape)) / df
1868 else:
1869 swinging = mass * np.linalg.norm(update, axis=-1)
1870 factor = speed / (1 + np.sqrt(speed * swinging))
1872 factored_update = update * factor[:, None]
1873 pos_arr += factored_update
1874 if abs(factored_update).sum() < 1e-10:
1875 break
1877 pos = dict(zip(G, pos_arr))
1878 if store_pos_as is not None:
1879 nx.set_node_attributes(G, pos, store_pos_as)
1881 return pos
1884def rescale_layout(pos, scale=1):
1885 """Returns scaled position array to (-scale, scale) in all axes.
1887 The function acts on NumPy arrays which hold position information.
1888 Each position is one row of the array. The dimension of the space
1889 equals the number of columns. Each coordinate in one column.
1891 To rescale, the mean (center) is subtracted from each axis separately.
1892 Then all values are scaled so that the largest magnitude value
1893 from all axes equals `scale` (thus, the aspect ratio is preserved).
1894 The resulting NumPy Array is returned (order of rows unchanged).
1896 Parameters
1897 ----------
1898 pos : numpy array
1899 positions to be scaled. Each row is a position.
1901 scale : number (default: 1)
1902 The size of the resulting extent in all directions.
1904 attribute : str, default None
1905 If non-None, the position of each node will be stored on the graph as
1906 an attribute named `attribute` which can be accessed with
1907 `G.nodes[...][attribute]`. The function still returns the dictionary.
1909 Returns
1910 -------
1911 pos : numpy array
1912 scaled positions. Each row is a position.
1914 See Also
1915 --------
1916 rescale_layout_dict
1917 """
1918 import numpy as np
1920 # Find max length over all dimensions
1921 pos -= pos.mean(axis=0)
1922 lim = np.abs(pos).max() # max coordinate for all axes
1923 # rescale to (-scale, scale) in all directions, preserves aspect
1924 if lim > 0:
1925 pos *= scale / lim
1926 return pos
1929def rescale_layout_dict(pos, scale=1):
1930 """Return a dictionary of scaled positions keyed by node
1932 Parameters
1933 ----------
1934 pos : A dictionary of positions keyed by node
1936 scale : number (default: 1)
1937 The size of the resulting extent in all directions.
1939 Returns
1940 -------
1941 pos : A dictionary of positions keyed by node
1943 Examples
1944 --------
1945 >>> import numpy as np
1946 >>> pos = {0: np.array((0, 0)), 1: np.array((1, 1)), 2: np.array((0.5, 0.5))}
1947 >>> nx.rescale_layout_dict(pos)
1948 {0: array([-1., -1.]), 1: array([1., 1.]), 2: array([0., 0.])}
1950 >>> pos = {0: np.array((0, 0)), 1: np.array((-1, 1)), 2: np.array((-0.5, 0.5))}
1951 >>> nx.rescale_layout_dict(pos, scale=2)
1952 {0: array([ 2., -2.]), 1: array([-2., 2.]), 2: array([0., 0.])}
1954 See Also
1955 --------
1956 rescale_layout
1957 """
1958 import numpy as np
1960 if not pos: # empty_graph
1961 return {}
1962 pos_v = np.array(list(pos.values()))
1963 pos_v = rescale_layout(pos_v, scale=scale)
1964 return dict(zip(pos, pos_v))
1967def bfs_layout(G, start, *, align="vertical", scale=1, center=None, store_pos_as=None):
1968 """Position nodes according to breadth-first search algorithm.
1970 Parameters
1971 ----------
1972 G : NetworkX graph
1973 A position will be assigned to every node in G.
1975 start : node in `G`
1976 Starting node for bfs
1978 align : string (default='vertical')
1979 The alignment of nodes within a layer, either `"vertical"` or
1980 `"horizontal"`.
1982 scale : number (default: 1)
1983 Scale factor for positions.
1985 center : array-like or None
1986 Coordinate pair around which to center the layout.
1988 store_pos_as : str, default None
1989 If non-None, the position of each node will be stored on the graph as
1990 an attribute with this string as its name, which can be accessed with
1991 ``G.nodes[...][store_pos_as]``. The function still returns the dictionary.
1993 Returns
1994 -------
1995 pos : dict
1996 A dictionary of positions keyed by node.
1998 Examples
1999 --------
2000 >>> from pprint import pprint
2001 >>> G = nx.path_graph(4)
2002 >>> pos = nx.bfs_layout(G, 0)
2003 >>> # suppress the returned dict and store on the graph directly
2004 >>> _ = nx.bfs_layout(G, 0, store_pos_as="pos")
2005 >>> pprint(nx.get_node_attributes(G, "pos"))
2006 {0: array([-1., 0.]),
2007 1: array([-0.33333333, 0. ]),
2008 2: array([0.33333333, 0. ]),
2009 3: array([1., 0.])}
2013 Notes
2014 -----
2015 This algorithm currently only works in two dimensions and does not
2016 try to minimize edge crossings.
2018 """
2019 G, center = _process_params(G, center, 2)
2021 # Compute layers with BFS
2022 layers = dict(enumerate(nx.bfs_layers(G, start)))
2024 if len(G) != sum(len(nodes) for nodes in layers.values()):
2025 raise nx.NetworkXError(
2026 "bfs_layout didn't include all nodes. Perhaps use input graph:\n"
2027 " G.subgraph(nx.node_connected_component(G, start))"
2028 )
2030 # Compute node positions with multipartite_layout
2031 pos = multipartite_layout(
2032 G, subset_key=layers, align=align, scale=scale, center=center
2033 )
2035 if store_pos_as is not None:
2036 nx.set_node_attributes(G, pos, store_pos_as)
2038 return pos