diff options
Diffstat (limited to '.venv/lib/python3.12/site-packages/networkx/drawing/layout.py')
| -rw-r--r-- | .venv/lib/python3.12/site-packages/networkx/drawing/layout.py | 1630 |
1 files changed, 1630 insertions, 0 deletions
diff --git a/.venv/lib/python3.12/site-packages/networkx/drawing/layout.py b/.venv/lib/python3.12/site-packages/networkx/drawing/layout.py new file mode 100644 index 00000000..20d34a18 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/drawing/layout.py @@ -0,0 +1,1630 @@ +""" +****** +Layout +****** + +Node positioning algorithms for graph drawing. + +For `random_layout()` the possible resulting shape +is a square of side [0, scale] (default: [0, 1]) +Changing `center` shifts the layout by that amount. + +For the other layout routines, the extent is +[center - scale, center + scale] (default: [-1, 1]). + +Warning: Most layout routines have only been tested in 2-dimensions. + +""" + +import networkx as nx +from networkx.utils import np_random_state + +__all__ = [ + "bipartite_layout", + "circular_layout", + "forceatlas2_layout", + "kamada_kawai_layout", + "random_layout", + "rescale_layout", + "rescale_layout_dict", + "shell_layout", + "spring_layout", + "spectral_layout", + "planar_layout", + "fruchterman_reingold_layout", + "spiral_layout", + "multipartite_layout", + "bfs_layout", + "arf_layout", +] + + +def _process_params(G, center, dim): + # Some boilerplate code. + import numpy as np + + if not isinstance(G, nx.Graph): + empty_graph = nx.Graph() + empty_graph.add_nodes_from(G) + G = empty_graph + + if center is None: + center = np.zeros(dim) + else: + center = np.asarray(center) + + if len(center) != dim: + msg = "length of center coordinates must match dimension of layout" + raise ValueError(msg) + + return G, center + + +@np_random_state(3) +def random_layout(G, center=None, dim=2, seed=None): + """Position nodes uniformly at random in the unit square. + + For every node, a position is generated by choosing each of dim + coordinates uniformly at random on the interval [0.0, 1.0). + + NumPy (http://scipy.org) is required for this function. + + Parameters + ---------- + G : NetworkX graph or list of nodes + A position will be assigned to every node in G. + + center : array-like or None + Coordinate pair around which to center the layout. + + dim : int + Dimension of layout. + + seed : int, RandomState instance or None optional (default=None) + Set the random state for deterministic node layouts. + If int, `seed` is the seed used by the random number generator, + if numpy.random.RandomState instance, `seed` is the random + number generator, + if None, the random number generator is the RandomState instance used + by numpy.random. + + Returns + ------- + pos : dict + A dictionary of positions keyed by node + + Examples + -------- + >>> G = nx.lollipop_graph(4, 3) + >>> pos = nx.random_layout(G) + + """ + import numpy as np + + G, center = _process_params(G, center, dim) + pos = seed.rand(len(G), dim) + center + pos = pos.astype(np.float32) + pos = dict(zip(G, pos)) + + return pos + + +def circular_layout(G, scale=1, center=None, dim=2): + # dim=2 only + """Position nodes on a circle. + + Parameters + ---------- + G : NetworkX graph or list of nodes + A position will be assigned to every node in G. + + scale : number (default: 1) + Scale factor for positions. + + center : array-like or None + Coordinate pair around which to center the layout. + + dim : int + Dimension of layout. + If dim>2, the remaining dimensions are set to zero + in the returned positions. + If dim<2, a ValueError is raised. + + Returns + ------- + pos : dict + A dictionary of positions keyed by node + + Raises + ------ + ValueError + If dim < 2 + + Examples + -------- + >>> G = nx.path_graph(4) + >>> pos = nx.circular_layout(G) + + Notes + ----- + This algorithm currently only works in two dimensions and does not + try to minimize edge crossings. + + """ + import numpy as np + + if dim < 2: + raise ValueError("cannot handle dimensions < 2") + + G, center = _process_params(G, center, dim) + + paddims = max(0, (dim - 2)) + + if len(G) == 0: + pos = {} + elif len(G) == 1: + pos = {nx.utils.arbitrary_element(G): center} + else: + # Discard the extra angle since it matches 0 radians. + theta = np.linspace(0, 1, len(G) + 1)[:-1] * 2 * np.pi + theta = theta.astype(np.float32) + pos = np.column_stack( + [np.cos(theta), np.sin(theta), np.zeros((len(G), paddims))] + ) + pos = rescale_layout(pos, scale=scale) + center + pos = dict(zip(G, pos)) + + return pos + + +def shell_layout(G, nlist=None, rotate=None, scale=1, center=None, dim=2): + """Position nodes in concentric circles. + + Parameters + ---------- + G : NetworkX graph or list of nodes + A position will be assigned to every node in G. + + nlist : list of lists + List of node lists for each shell. + + rotate : angle in radians (default=pi/len(nlist)) + Angle by which to rotate the starting position of each shell + relative to the starting position of the previous shell. + To recreate behavior before v2.5 use rotate=0. + + scale : number (default: 1) + Scale factor for positions. + + center : array-like or None + Coordinate pair around which to center the layout. + + dim : int + Dimension of layout, currently only dim=2 is supported. + Other dimension values result in a ValueError. + + Returns + ------- + pos : dict + A dictionary of positions keyed by node + + Raises + ------ + ValueError + If dim != 2 + + Examples + -------- + >>> G = nx.path_graph(4) + >>> shells = [[0], [1, 2, 3]] + >>> pos = nx.shell_layout(G, shells) + + Notes + ----- + This algorithm currently only works in two dimensions and does not + try to minimize edge crossings. + + """ + import numpy as np + + if dim != 2: + raise ValueError("can only handle 2 dimensions") + + G, center = _process_params(G, center, dim) + + if len(G) == 0: + return {} + if len(G) == 1: + return {nx.utils.arbitrary_element(G): center} + + if nlist is None: + # draw the whole graph in one shell + nlist = [list(G)] + + radius_bump = scale / len(nlist) + + if len(nlist[0]) == 1: + # single node at center + radius = 0.0 + else: + # else start at r=1 + radius = radius_bump + + if rotate is None: + rotate = np.pi / len(nlist) + first_theta = rotate + npos = {} + for nodes in nlist: + # Discard the last angle (endpoint=False) since 2*pi matches 0 radians + theta = ( + np.linspace(0, 2 * np.pi, len(nodes), endpoint=False, dtype=np.float32) + + first_theta + ) + pos = radius * np.column_stack([np.cos(theta), np.sin(theta)]) + center + npos.update(zip(nodes, pos)) + radius += radius_bump + first_theta += rotate + + return npos + + +def bipartite_layout( + G, nodes, align="vertical", scale=1, center=None, aspect_ratio=4 / 3 +): + """Position nodes in two straight lines. + + Parameters + ---------- + G : NetworkX graph or list of nodes + A position will be assigned to every node in G. + + nodes : list or container + Nodes in one node set of the bipartite graph. + This set will be placed on left or top. + + align : string (default='vertical') + The alignment of nodes. Vertical or horizontal. + + scale : number (default: 1) + Scale factor for positions. + + center : array-like or None + Coordinate pair around which to center the layout. + + aspect_ratio : number (default=4/3): + The ratio of the width to the height of the layout. + + Returns + ------- + pos : dict + A dictionary of positions keyed by node. + + Examples + -------- + >>> G = nx.bipartite.gnmk_random_graph(3, 5, 10, seed=123) + >>> top = nx.bipartite.sets(G)[0] + >>> pos = nx.bipartite_layout(G, top) + + Notes + ----- + This algorithm currently only works in two dimensions and does not + try to minimize edge crossings. + + """ + + import numpy as np + + if align not in ("vertical", "horizontal"): + msg = "align must be either vertical or horizontal." + raise ValueError(msg) + + G, center = _process_params(G, center=center, dim=2) + if len(G) == 0: + return {} + + height = 1 + width = aspect_ratio * height + offset = (width / 2, height / 2) + + top = dict.fromkeys(nodes) + bottom = [v for v in G if v not in top] + nodes = list(top) + bottom + + left_xs = np.repeat(0, len(top)) + right_xs = np.repeat(width, len(bottom)) + left_ys = np.linspace(0, height, len(top)) + right_ys = np.linspace(0, height, len(bottom)) + + top_pos = np.column_stack([left_xs, left_ys]) - offset + bottom_pos = np.column_stack([right_xs, right_ys]) - offset + + pos = np.concatenate([top_pos, bottom_pos]) + pos = rescale_layout(pos, scale=scale) + center + if align == "horizontal": + pos = pos[:, ::-1] # swap x and y coords + pos = dict(zip(nodes, pos)) + return pos + + +@np_random_state(10) +def spring_layout( + G, + k=None, + pos=None, + fixed=None, + iterations=50, + threshold=1e-4, + weight="weight", + scale=1, + center=None, + dim=2, + seed=None, +): + """Position nodes using Fruchterman-Reingold force-directed algorithm. + + The algorithm simulates a force-directed representation of the network + treating edges as springs holding nodes close, while treating nodes + as repelling objects, sometimes called an anti-gravity force. + Simulation continues until the positions are close to an equilibrium. + + There are some hard-coded values: minimal distance between + nodes (0.01) and "temperature" of 0.1 to ensure nodes don't fly away. + During the simulation, `k` helps determine the distance between nodes, + though `scale` and `center` determine the size and place after + rescaling occurs at the end of the simulation. + + Fixing some nodes doesn't allow them to move in the simulation. + It also turns off the rescaling feature at the simulation's end. + In addition, setting `scale` to `None` turns off rescaling. + + Parameters + ---------- + G : NetworkX graph or list of nodes + A position will be assigned to every node in G. + + k : float (default=None) + Optimal distance between nodes. If None the distance is set to + 1/sqrt(n) where n is the number of nodes. Increase this value + to move nodes farther apart. + + pos : dict or None optional (default=None) + Initial positions for nodes as a dictionary with node as keys + and values as a coordinate list or tuple. If None, then use + random initial positions. + + fixed : list or None optional (default=None) + Nodes to keep fixed at initial position. + Nodes not in ``G.nodes`` are ignored. + ValueError raised if `fixed` specified and `pos` not. + + iterations : int optional (default=50) + Maximum number of iterations taken + + threshold: float optional (default = 1e-4) + Threshold for relative error in node position changes. + The iteration stops if the error is below this threshold. + + weight : string or None optional (default='weight') + The edge attribute that holds the numerical value used for + the edge weight. Larger means a stronger attractive force. + If None, then all edge weights are 1. + + scale : number or None (default: 1) + Scale factor for positions. Not used unless `fixed is None`. + If scale is None, no rescaling is performed. + + center : array-like or None + Coordinate pair around which to center the layout. + Not used unless `fixed is None`. + + dim : int + Dimension of layout. + + seed : int, RandomState instance or None optional (default=None) + Used only for the initial positions in the algorithm. + Set the random state for deterministic node layouts. + If int, `seed` is the seed used by the random number generator, + if numpy.random.RandomState instance, `seed` is the random + number generator, + if None, the random number generator is the RandomState instance used + by numpy.random. + + Returns + ------- + pos : dict + A dictionary of positions keyed by node + + Examples + -------- + >>> G = nx.path_graph(4) + >>> pos = nx.spring_layout(G) + + # The same using longer but equivalent function name + >>> pos = nx.fruchterman_reingold_layout(G) + """ + import numpy as np + + G, center = _process_params(G, center, dim) + + if fixed is not None: + if pos is None: + raise ValueError("nodes are fixed without positions given") + for node in fixed: + if node not in pos: + raise ValueError("nodes are fixed without positions given") + nfixed = {node: i for i, node in enumerate(G)} + fixed = np.asarray([nfixed[node] for node in fixed if node in nfixed]) + + if pos is not None: + # Determine size of existing domain to adjust initial positions + dom_size = max(coord for pos_tup in pos.values() for coord in pos_tup) + if dom_size == 0: + dom_size = 1 + pos_arr = seed.rand(len(G), dim) * dom_size + center + + for i, n in enumerate(G): + if n in pos: + pos_arr[i] = np.asarray(pos[n]) + else: + pos_arr = None + dom_size = 1 + + if len(G) == 0: + return {} + if len(G) == 1: + return {nx.utils.arbitrary_element(G.nodes()): center} + + try: + # Sparse matrix + if len(G) < 500: # sparse solver for large graphs + raise ValueError + A = nx.to_scipy_sparse_array(G, weight=weight, dtype="f") + if k is None and fixed is not None: + # We must adjust k by domain size for layouts not near 1x1 + nnodes, _ = A.shape + k = dom_size / np.sqrt(nnodes) + pos = _sparse_fruchterman_reingold( + A, k, pos_arr, fixed, iterations, threshold, dim, seed + ) + except ValueError: + A = nx.to_numpy_array(G, weight=weight) + if k is None and fixed is not None: + # We must adjust k by domain size for layouts not near 1x1 + nnodes, _ = A.shape + k = dom_size / np.sqrt(nnodes) + pos = _fruchterman_reingold( + A, k, pos_arr, fixed, iterations, threshold, dim, seed + ) + if fixed is None and scale is not None: + pos = rescale_layout(pos, scale=scale) + center + pos = dict(zip(G, pos)) + return pos + + +fruchterman_reingold_layout = spring_layout + + +@np_random_state(7) +def _fruchterman_reingold( + A, k=None, pos=None, fixed=None, iterations=50, threshold=1e-4, dim=2, seed=None +): + # Position nodes in adjacency matrix A using Fruchterman-Reingold + # Entry point for NetworkX graph is fruchterman_reingold_layout() + import numpy as np + + try: + nnodes, _ = A.shape + except AttributeError as err: + msg = "fruchterman_reingold() takes an adjacency matrix as input" + raise nx.NetworkXError(msg) from err + + if pos is None: + # random initial positions + pos = np.asarray(seed.rand(nnodes, dim), dtype=A.dtype) + else: + # make sure positions are of same type as matrix + pos = pos.astype(A.dtype) + + # optimal distance between nodes + if k is None: + k = np.sqrt(1.0 / nnodes) + # the initial "temperature" is about .1 of domain area (=1x1) + # this is the largest step allowed in the dynamics. + # We need to calculate this in case our fixed positions force our domain + # to be much bigger than 1x1 + t = max(max(pos.T[0]) - min(pos.T[0]), max(pos.T[1]) - min(pos.T[1])) * 0.1 + # simple cooling scheme. + # linearly step down by dt on each iteration so last iteration is size dt. + dt = t / (iterations + 1) + delta = np.zeros((pos.shape[0], pos.shape[0], pos.shape[1]), dtype=A.dtype) + # the inscrutable (but fast) version + # this is still O(V^2) + # could use multilevel methods to speed this up significantly + for iteration in range(iterations): + # matrix of difference between points + delta = pos[:, np.newaxis, :] - pos[np.newaxis, :, :] + # distance between points + distance = np.linalg.norm(delta, axis=-1) + # enforce minimum distance of 0.01 + np.clip(distance, 0.01, None, out=distance) + # displacement "force" + displacement = np.einsum( + "ijk,ij->ik", delta, (k * k / distance**2 - A * distance / k) + ) + # update positions + length = np.linalg.norm(displacement, axis=-1) + length = np.where(length < 0.01, 0.1, length) + delta_pos = np.einsum("ij,i->ij", displacement, t / length) + if fixed is not None: + # don't change positions of fixed nodes + delta_pos[fixed] = 0.0 + pos += delta_pos + # cool temperature + t -= dt + if (np.linalg.norm(delta_pos) / nnodes) < threshold: + break + return pos + + +@np_random_state(7) +def _sparse_fruchterman_reingold( + A, k=None, pos=None, fixed=None, iterations=50, threshold=1e-4, dim=2, seed=None +): + # Position nodes in adjacency matrix A using Fruchterman-Reingold + # Entry point for NetworkX graph is fruchterman_reingold_layout() + # Sparse version + import numpy as np + import scipy as sp + + try: + nnodes, _ = A.shape + except AttributeError as err: + msg = "fruchterman_reingold() takes an adjacency matrix as input" + raise nx.NetworkXError(msg) from err + # make sure we have a LIst of Lists representation + try: + A = A.tolil() + except AttributeError: + A = (sp.sparse.coo_array(A)).tolil() + + if pos is None: + # random initial positions + pos = np.asarray(seed.rand(nnodes, dim), dtype=A.dtype) + else: + # make sure positions are of same type as matrix + pos = pos.astype(A.dtype) + + # no fixed nodes + if fixed is None: + fixed = [] + + # optimal distance between nodes + if k is None: + k = np.sqrt(1.0 / nnodes) + # the initial "temperature" is about .1 of domain area (=1x1) + # this is the largest step allowed in the dynamics. + t = max(max(pos.T[0]) - min(pos.T[0]), max(pos.T[1]) - min(pos.T[1])) * 0.1 + # simple cooling scheme. + # linearly step down by dt on each iteration so last iteration is size dt. + dt = t / (iterations + 1) + + displacement = np.zeros((dim, nnodes)) + for iteration in range(iterations): + displacement *= 0 + # loop over rows + for i in range(A.shape[0]): + if i in fixed: + continue + # difference between this row's node position and all others + delta = (pos[i] - pos).T + # distance between points + distance = np.sqrt((delta**2).sum(axis=0)) + # enforce minimum distance of 0.01 + distance = np.where(distance < 0.01, 0.01, distance) + # the adjacency matrix row + Ai = A.getrowview(i).toarray() # TODO: revisit w/ sparse 1D container + # displacement "force" + displacement[:, i] += ( + delta * (k * k / distance**2 - Ai * distance / k) + ).sum(axis=1) + # update positions + length = np.sqrt((displacement**2).sum(axis=0)) + length = np.where(length < 0.01, 0.1, length) + delta_pos = (displacement * t / length).T + pos += delta_pos + # cool temperature + t -= dt + if (np.linalg.norm(delta_pos) / nnodes) < threshold: + break + return pos + + +def kamada_kawai_layout( + G, dist=None, pos=None, weight="weight", scale=1, center=None, dim=2 +): + """Position nodes using Kamada-Kawai path-length cost-function. + + Parameters + ---------- + G : NetworkX graph or list of nodes + A position will be assigned to every node in G. + + dist : dict (default=None) + A two-level dictionary of optimal distances between nodes, + indexed by source and destination node. + If None, the distance is computed using shortest_path_length(). + + pos : dict or None optional (default=None) + Initial positions for nodes as a dictionary with node as keys + and values as a coordinate list or tuple. If None, then use + circular_layout() for dim >= 2 and a linear layout for dim == 1. + + weight : string or None optional (default='weight') + The edge attribute that holds the numerical value used for + the edge weight. If None, then all edge weights are 1. + + scale : number (default: 1) + Scale factor for positions. + + center : array-like or None + Coordinate pair around which to center the layout. + + dim : int + Dimension of layout. + + Returns + ------- + pos : dict + A dictionary of positions keyed by node + + Examples + -------- + >>> G = nx.path_graph(4) + >>> pos = nx.kamada_kawai_layout(G) + """ + import numpy as np + + G, center = _process_params(G, center, dim) + nNodes = len(G) + if nNodes == 0: + return {} + + if dist is None: + dist = dict(nx.shortest_path_length(G, weight=weight)) + dist_mtx = 1e6 * np.ones((nNodes, nNodes)) + for row, nr in enumerate(G): + if nr not in dist: + continue + rdist = dist[nr] + for col, nc in enumerate(G): + if nc not in rdist: + continue + dist_mtx[row][col] = rdist[nc] + + if pos is None: + if dim >= 3: + pos = random_layout(G, dim=dim) + elif dim == 2: + pos = circular_layout(G, dim=dim) + else: + pos = dict(zip(G, np.linspace(0, 1, len(G)))) + pos_arr = np.array([pos[n] for n in G]) + + pos = _kamada_kawai_solve(dist_mtx, pos_arr, dim) + + pos = rescale_layout(pos, scale=scale) + center + return dict(zip(G, pos)) + + +def _kamada_kawai_solve(dist_mtx, pos_arr, dim): + # Anneal node locations based on the Kamada-Kawai cost-function, + # using the supplied matrix of preferred inter-node distances, + # and starting locations. + + import numpy as np + import scipy as sp + + meanwt = 1e-3 + costargs = (np, 1 / (dist_mtx + np.eye(dist_mtx.shape[0]) * 1e-3), meanwt, dim) + + optresult = sp.optimize.minimize( + _kamada_kawai_costfn, + pos_arr.ravel(), + method="L-BFGS-B", + args=costargs, + jac=True, + ) + + return optresult.x.reshape((-1, dim)) + + +def _kamada_kawai_costfn(pos_vec, np, invdist, meanweight, dim): + # Cost-function and gradient for Kamada-Kawai layout algorithm + nNodes = invdist.shape[0] + pos_arr = pos_vec.reshape((nNodes, dim)) + + delta = pos_arr[:, np.newaxis, :] - pos_arr[np.newaxis, :, :] + nodesep = np.linalg.norm(delta, axis=-1) + direction = np.einsum("ijk,ij->ijk", delta, 1 / (nodesep + np.eye(nNodes) * 1e-3)) + + offset = nodesep * invdist - 1.0 + offset[np.diag_indices(nNodes)] = 0 + + cost = 0.5 * np.sum(offset**2) + grad = np.einsum("ij,ij,ijk->ik", invdist, offset, direction) - np.einsum( + "ij,ij,ijk->jk", invdist, offset, direction + ) + + # Additional parabolic term to encourage mean position to be near origin: + sumpos = np.sum(pos_arr, axis=0) + cost += 0.5 * meanweight * np.sum(sumpos**2) + grad += meanweight * sumpos + + return (cost, grad.ravel()) + + +def spectral_layout(G, weight="weight", scale=1, center=None, dim=2): + """Position nodes using the eigenvectors of the graph Laplacian. + + Using the unnormalized Laplacian, the layout shows possible clusters of + nodes which are an approximation of the ratio cut. If dim is the number of + dimensions then the positions are the entries of the dim eigenvectors + corresponding to the ascending eigenvalues starting from the second one. + + Parameters + ---------- + G : NetworkX graph or list of nodes + A position will be assigned to every node in G. + + weight : string or None optional (default='weight') + The edge attribute that holds the numerical value used for + the edge weight. If None, then all edge weights are 1. + + scale : number (default: 1) + Scale factor for positions. + + center : array-like or None + Coordinate pair around which to center the layout. + + dim : int + Dimension of layout. + + Returns + ------- + pos : dict + A dictionary of positions keyed by node + + Examples + -------- + >>> G = nx.path_graph(4) + >>> pos = nx.spectral_layout(G) + + Notes + ----- + Directed graphs will be considered as undirected graphs when + positioning the nodes. + + For larger graphs (>500 nodes) this will use the SciPy sparse + eigenvalue solver (ARPACK). + """ + # handle some special cases that break the eigensolvers + import numpy as np + + G, center = _process_params(G, center, dim) + + if len(G) <= 2: + if len(G) == 0: + pos = np.array([]) + elif len(G) == 1: + pos = np.array([center]) + else: + pos = np.array([np.zeros(dim), np.array(center) * 2.0]) + return dict(zip(G, pos)) + try: + # Sparse matrix + if len(G) < 500: # dense solver is faster for small graphs + raise ValueError + A = nx.to_scipy_sparse_array(G, weight=weight, dtype="d") + # Symmetrize directed graphs + if G.is_directed(): + A = A + np.transpose(A) + pos = _sparse_spectral(A, dim) + except (ImportError, ValueError): + # Dense matrix + A = nx.to_numpy_array(G, weight=weight) + # Symmetrize directed graphs + if G.is_directed(): + A += A.T + pos = _spectral(A, dim) + + pos = rescale_layout(pos, scale=scale) + center + pos = dict(zip(G, pos)) + return pos + + +def _spectral(A, dim=2): + # Input adjacency matrix A + # Uses dense eigenvalue solver from numpy + import numpy as np + + try: + nnodes, _ = A.shape + except AttributeError as err: + msg = "spectral() takes an adjacency matrix as input" + raise nx.NetworkXError(msg) from err + + # form Laplacian matrix where D is diagonal of degrees + D = np.identity(nnodes, dtype=A.dtype) * np.sum(A, axis=1) + L = D - A + + eigenvalues, eigenvectors = np.linalg.eig(L) + # sort and keep smallest nonzero + index = np.argsort(eigenvalues)[1 : dim + 1] # 0 index is zero eigenvalue + return np.real(eigenvectors[:, index]) + + +def _sparse_spectral(A, dim=2): + # Input adjacency matrix A + # Uses sparse eigenvalue solver from scipy + # Could use multilevel methods here, see Koren "On spectral graph drawing" + import numpy as np + import scipy as sp + + try: + nnodes, _ = A.shape + except AttributeError as err: + msg = "sparse_spectral() takes an adjacency matrix as input" + raise nx.NetworkXError(msg) from err + + # form Laplacian matrix + # TODO: Rm csr_array wrapper in favor of spdiags array constructor when available + D = sp.sparse.csr_array(sp.sparse.spdiags(A.sum(axis=1), 0, nnodes, nnodes)) + L = D - A + + k = dim + 1 + # number of Lanczos vectors for ARPACK solver.What is the right scaling? + ncv = max(2 * k + 1, int(np.sqrt(nnodes))) + # return smallest k eigenvalues and eigenvectors + eigenvalues, eigenvectors = sp.sparse.linalg.eigsh(L, k, which="SM", ncv=ncv) + index = np.argsort(eigenvalues)[1:k] # 0 index is zero eigenvalue + return np.real(eigenvectors[:, index]) + + +def planar_layout(G, scale=1, center=None, dim=2): + """Position nodes without edge intersections. + + Parameters + ---------- + G : NetworkX graph or list of nodes + A position will be assigned to every node in G. If G is of type + nx.PlanarEmbedding, the positions are selected accordingly. + + scale : number (default: 1) + Scale factor for positions. + + center : array-like or None + Coordinate pair around which to center the layout. + + dim : int + Dimension of layout. + + Returns + ------- + pos : dict + A dictionary of positions keyed by node + + Raises + ------ + NetworkXException + If G is not planar + + Examples + -------- + >>> G = nx.path_graph(4) + >>> pos = nx.planar_layout(G) + """ + import numpy as np + + if dim != 2: + raise ValueError("can only handle 2 dimensions") + + G, center = _process_params(G, center, dim) + + if len(G) == 0: + return {} + + if isinstance(G, nx.PlanarEmbedding): + embedding = G + else: + is_planar, embedding = nx.check_planarity(G) + if not is_planar: + raise nx.NetworkXException("G is not planar.") + pos = nx.combinatorial_embedding_to_pos(embedding) + node_list = list(embedding) + pos = np.vstack([pos[x] for x in node_list]) + pos = pos.astype(np.float64) + pos = rescale_layout(pos, scale=scale) + center + return dict(zip(node_list, pos)) + + +def spiral_layout(G, scale=1, center=None, dim=2, resolution=0.35, equidistant=False): + """Position nodes in a spiral layout. + + Parameters + ---------- + G : NetworkX graph or list of nodes + A position will be assigned to every node in G. + scale : number (default: 1) + Scale factor for positions. + center : array-like or None + Coordinate pair around which to center the layout. + dim : int, default=2 + Dimension of layout, currently only dim=2 is supported. + Other dimension values result in a ValueError. + resolution : float, default=0.35 + The compactness of the spiral layout returned. + Lower values result in more compressed spiral layouts. + equidistant : bool, default=False + If True, nodes will be positioned equidistant from each other + by decreasing angle further from center. + If False, nodes will be positioned at equal angles + from each other by increasing separation further from center. + + Returns + ------- + pos : dict + A dictionary of positions keyed by node + + Raises + ------ + ValueError + If dim != 2 + + Examples + -------- + >>> G = nx.path_graph(4) + >>> pos = nx.spiral_layout(G) + >>> nx.draw(G, pos=pos) + + Notes + ----- + This algorithm currently only works in two dimensions. + + """ + import numpy as np + + if dim != 2: + raise ValueError("can only handle 2 dimensions") + + G, center = _process_params(G, center, dim) + + if len(G) == 0: + return {} + if len(G) == 1: + return {nx.utils.arbitrary_element(G): center} + + pos = [] + if equidistant: + chord = 1 + step = 0.5 + theta = resolution + theta += chord / (step * theta) + for _ in range(len(G)): + r = step * theta + theta += chord / r + pos.append([np.cos(theta) * r, np.sin(theta) * r]) + + else: + dist = np.arange(len(G), dtype=float) + angle = resolution * dist + pos = np.transpose(dist * np.array([np.cos(angle), np.sin(angle)])) + + pos = rescale_layout(np.array(pos), scale=scale) + center + + pos = dict(zip(G, pos)) + + return pos + + +def multipartite_layout(G, subset_key="subset", align="vertical", scale=1, center=None): + """Position nodes in layers of straight lines. + + Parameters + ---------- + G : NetworkX graph or list of nodes + A position will be assigned to every node in G. + + subset_key : string or dict (default='subset') + If a string, the key of node data in G that holds the node subset. + If a dict, keyed by layer number to the nodes in that layer/subset. + + align : string (default='vertical') + The alignment of nodes. Vertical or horizontal. + + scale : number (default: 1) + Scale factor for positions. + + center : array-like or None + Coordinate pair around which to center the layout. + + Returns + ------- + pos : dict + A dictionary of positions keyed by node. + + Examples + -------- + >>> G = nx.complete_multipartite_graph(28, 16, 10) + >>> pos = nx.multipartite_layout(G) + + or use a dict to provide the layers of the layout + + >>> G = nx.Graph([(0, 1), (1, 2), (1, 3), (3, 4)]) + >>> layers = {"a": [0], "b": [1], "c": [2, 3], "d": [4]} + >>> pos = nx.multipartite_layout(G, subset_key=layers) + + Notes + ----- + This algorithm currently only works in two dimensions and does not + try to minimize edge crossings. + + Network does not need to be a complete multipartite graph. As long as nodes + have subset_key data, they will be placed in the corresponding layers. + + """ + import numpy as np + + if align not in ("vertical", "horizontal"): + msg = "align must be either vertical or horizontal." + raise ValueError(msg) + + G, center = _process_params(G, center=center, dim=2) + if len(G) == 0: + return {} + + try: + # check if subset_key is dict-like + if len(G) != sum(len(nodes) for nodes in subset_key.values()): + raise nx.NetworkXError( + "all nodes must be in one subset of `subset_key` dict" + ) + except AttributeError: + # subset_key is not a dict, hence a string + node_to_subset = nx.get_node_attributes(G, subset_key) + if len(node_to_subset) != len(G): + raise nx.NetworkXError( + f"all nodes need a subset_key attribute: {subset_key}" + ) + subset_key = nx.utils.groups(node_to_subset) + + # Sort by layer, if possible + try: + layers = dict(sorted(subset_key.items())) + except TypeError: + layers = subset_key + + pos = None + nodes = [] + width = len(layers) + for i, layer in enumerate(layers.values()): + height = len(layer) + xs = np.repeat(i, height) + ys = np.arange(0, height, dtype=float) + offset = ((width - 1) / 2, (height - 1) / 2) + layer_pos = np.column_stack([xs, ys]) - offset + if pos is None: + pos = layer_pos + else: + pos = np.concatenate([pos, layer_pos]) + nodes.extend(layer) + pos = rescale_layout(pos, scale=scale) + center + if align == "horizontal": + pos = pos[:, ::-1] # swap x and y coords + pos = dict(zip(nodes, pos)) + return pos + + +@np_random_state("seed") +def arf_layout( + G, + pos=None, + scaling=1, + a=1.1, + etol=1e-6, + dt=1e-3, + max_iter=1000, + *, + seed=None, +): + """Arf layout for networkx + + The attractive and repulsive forces (arf) layout [1] + improves the spring layout in three ways. First, it + prevents congestion of highly connected nodes due to + strong forcing between nodes. Second, it utilizes the + layout space more effectively by preventing large gaps + that spring layout tends to create. Lastly, the arf + layout represents symmetries in the layout better than + the default spring layout. + + Parameters + ---------- + G : nx.Graph or nx.DiGraph + Networkx graph. + pos : dict + Initial position of the nodes. If set to None a + random layout will be used. + scaling : float + Scales the radius of the circular layout space. + a : float + Strength of springs between connected nodes. Should be larger than 1. The greater a, the clearer the separation ofunconnected sub clusters. + etol : float + Gradient sum of spring forces must be larger than `etol` before successful termination. + dt : float + Time step for force differential equation simulations. + max_iter : int + Max iterations before termination of the algorithm. + seed : int, RandomState instance or None optional (default=None) + Set the random state for deterministic node layouts. + If int, `seed` is the seed used by the random number generator, + if numpy.random.RandomState instance, `seed` is the random + number generator, + if None, the random number generator is the RandomState instance used + by numpy.random. + + References + .. [1] "Self-Organization Applied to Dynamic Network Layout", M. Geipel, + International Journal of Modern Physics C, 2007, Vol 18, No 10, pp. 1537-1549. + https://doi.org/10.1142/S0129183107011558 https://arxiv.org/abs/0704.1748 + + Returns + ------- + pos : dict + A dictionary of positions keyed by node. + + Examples + -------- + >>> G = nx.grid_graph((5, 5)) + >>> pos = nx.arf_layout(G) + + """ + import warnings + + import numpy as np + + if a <= 1: + msg = "The parameter a should be larger than 1" + raise ValueError(msg) + + pos_tmp = nx.random_layout(G, seed=seed) + if pos is None: + pos = pos_tmp + else: + for node in G.nodes(): + if node not in pos: + pos[node] = pos_tmp[node].copy() + + # Initialize spring constant matrix + N = len(G) + # No nodes no computation + if N == 0: + return pos + + # init force of springs + K = np.ones((N, N)) - np.eye(N) + node_order = {node: i for i, node in enumerate(G)} + for x, y in G.edges(): + if x != y: + idx, jdx = (node_order[i] for i in (x, y)) + K[idx, jdx] = a + + # vectorize values + p = np.asarray(list(pos.values())) + + # equation 10 in [1] + rho = scaling * np.sqrt(N) + + # looping variables + error = etol + 1 + n_iter = 0 + while error > etol: + diff = p[:, np.newaxis] - p[np.newaxis] + A = np.linalg.norm(diff, axis=-1)[..., np.newaxis] + # attraction_force - repulsions force + # suppress nans due to division; caused by diagonal set to zero. + # Does not affect the computation due to nansum + with warnings.catch_warnings(): + warnings.simplefilter("ignore") + change = K[..., np.newaxis] * diff - rho / A * diff + change = np.nansum(change, axis=0) + p += change * dt + + error = np.linalg.norm(change, axis=-1).sum() + if n_iter > max_iter: + break + n_iter += 1 + return dict(zip(G.nodes(), p)) + + +@np_random_state("seed") +def forceatlas2_layout( + G, + pos=None, + *, + max_iter=100, + jitter_tolerance=1.0, + scaling_ratio=2.0, + gravity=1.0, + distributed_action=False, + strong_gravity=False, + node_mass=None, + node_size=None, + weight=None, + dissuade_hubs=False, + linlog=False, + seed=None, + dim=2, +): + """Position nodes using the ForceAtlas2 force-directed layout algorithm. + + This function applies the ForceAtlas2 layout algorithm [1]_ to a NetworkX graph, + positioning the nodes in a way that visually represents the structure of the graph. + The algorithm uses physical simulation to minimize the energy of the system, + resulting in a more readable layout. + + Parameters + ---------- + G : nx.Graph + A NetworkX graph to be laid out. + pos : dict or None, optional + Initial positions of the nodes. If None, random initial positions are used. + max_iter : int (default: 100) + Number of iterations for the layout optimization. + jitter_tolerance : float (default: 1.0) + Controls the tolerance for adjusting the speed of layout generation. + scaling_ratio : float (default: 2.0) + Determines the scaling of attraction and repulsion forces. + distributed_attraction : bool (default: False) + Distributes the attraction force evenly among nodes. + strong_gravity : bool (default: False) + Applies a strong gravitational pull towards the center. + node_mass : dict or None, optional + Maps nodes to their masses, influencing the attraction to other nodes. + node_size : dict or None, optional + Maps nodes to their sizes, preventing crowding by creating a halo effect. + dissuade_hubs : bool (default: False) + Prevents the clustering of hub nodes. + linlog : bool (default: False) + Uses logarithmic attraction instead of linear. + seed : int, RandomState instance or None optional (default=None) + Used only for the initial positions in the algorithm. + Set the random state for deterministic node layouts. + If int, `seed` is the seed used by the random number generator, + if numpy.random.RandomState instance, `seed` is the random + number generator, + if None, the random number generator is the RandomState instance used + by numpy.random. + dim : int (default: 2) + Sets the dimensions for the layout. Ignored if `pos` is provided. + + Examples + -------- + >>> import networkx as nx + >>> G = nx.florentine_families_graph() + >>> pos = nx.forceatlas2_layout(G) + >>> nx.draw(G, pos=pos) + + References + ---------- + .. [1] Jacomy, M., Venturini, T., Heymann, S., & Bastian, M. (2014). + ForceAtlas2, a continuous graph layout algorithm for handy network + visualization designed for the Gephi software. PloS one, 9(6), e98679. + https://doi.org/10.1371/journal.pone.0098679 + """ + import numpy as np + + if len(G) == 0: + return {} + # parse optional pos positions + if pos is None: + pos = nx.random_layout(G, dim=dim, seed=seed) + pos_arr = np.array(list(pos.values())) + else: + # set default node interval within the initial pos values + pos_init = np.array(list(pos.values())) + max_pos = pos_init.max(axis=0) + min_pos = pos_init.min(axis=0) + dim = max_pos.size + pos_arr = min_pos + seed.rand(len(G), dim) * (max_pos - min_pos) + for idx, node in enumerate(G): + if node in pos: + pos_arr[idx] = pos[node].copy() + + mass = np.zeros(len(G)) + size = np.zeros(len(G)) + + # Only adjust for size when the users specifies size other than default (1) + adjust_sizes = False + if node_size is None: + node_size = {} + else: + adjust_sizes = True + + if node_mass is None: + node_mass = {} + + for idx, node in enumerate(G): + mass[idx] = node_mass.get(node, G.degree(node) + 1) + size[idx] = node_size.get(node, 1) + + n = len(G) + gravities = np.zeros((n, dim)) + attraction = np.zeros((n, dim)) + repulsion = np.zeros((n, dim)) + A = nx.to_numpy_array(G, weight=weight) + + def estimate_factor(n, swing, traction, speed, speed_efficiency, jitter_tolerance): + """Computes the scaling factor for the force in the ForceAtlas2 layout algorithm. + + This helper function adjusts the speed and + efficiency of the layout generation based on the + current state of the system, such as the number of + nodes, current swing, and traction forces. + + Parameters + ---------- + n : int + Number of nodes in the graph. + swing : float + The current swing, representing the oscillation of the nodes. + traction : float + The current traction force, representing the attraction between nodes. + speed : float + The current speed of the layout generation. + speed_efficiency : float + The efficiency of the current speed, influencing how fast the layout converges. + jitter_tolerance : float + The tolerance for jitter, affecting how much speed adjustment is allowed. + + Returns + ------- + tuple + A tuple containing the updated speed and speed efficiency. + + Notes + ----- + This function is a part of the ForceAtlas2 layout algorithm and is used to dynamically adjust the + layout parameters to achieve an optimal and stable visualization. + + """ + import numpy as np + + # estimate jitter + opt_jitter = 0.05 * np.sqrt(n) + min_jitter = np.sqrt(opt_jitter) + max_jitter = 10 + min_speed_efficiency = 0.05 + + other = min(max_jitter, opt_jitter * traction / n**2) + jitter = jitter_tolerance * max(min_jitter, other) + + if swing / traction > 2.0: + if speed_efficiency > min_speed_efficiency: + speed_efficiency *= 0.5 + jitter = max(jitter, jitter_tolerance) + if swing == 0: + target_speed = np.inf + else: + target_speed = jitter * speed_efficiency * traction / swing + + if swing > jitter * traction: + if speed_efficiency > min_speed_efficiency: + speed_efficiency *= 0.7 + elif speed < 1000: + speed_efficiency *= 1.3 + + max_rise = 0.5 + speed = speed + min(target_speed - speed, max_rise * speed) + return speed, speed_efficiency + + speed = 1 + speed_efficiency = 1 + swing = 1 + traction = 1 + for _ in range(max_iter): + # compute pairwise difference + diff = pos_arr[:, None] - pos_arr[None] + # compute pairwise distance + distance = np.linalg.norm(diff, axis=-1) + + # linear attraction + if linlog: + attraction = -np.log(1 + distance) / distance + np.fill_diagonal(attraction, 0) + attraction = np.einsum("ij, ij -> ij", attraction, A) + attraction = np.einsum("ijk, ij -> ik", diff, attraction) + + else: + attraction = -np.einsum("ijk, ij -> ik", diff, A) + + if distributed_action: + attraction /= mass[:, None] + + # repulsion + tmp = mass[:, None] @ mass[None] + if adjust_sizes: + distance += -size[:, None] - size[None] + + d2 = distance**2 + # remove self-interaction + np.fill_diagonal(tmp, 0) + np.fill_diagonal(d2, 1) + factor = (tmp / d2) * scaling_ratio + repulsion = np.einsum("ijk, ij -> ik", diff, factor) + + # gravity + gravities = ( + -gravity + * mass[:, None] + * pos_arr + / np.linalg.norm(pos_arr, axis=-1)[:, None] + ) + + if strong_gravity: + gravities *= np.linalg.norm(pos_arr, axis=-1)[:, None] + # total forces + update = attraction + repulsion + gravities + + # compute total swing and traction + swing += (mass * np.linalg.norm(pos_arr - update, axis=-1)).sum() + traction += (0.5 * mass * np.linalg.norm(pos_arr + update, axis=-1)).sum() + + speed, speed_efficiency = estimate_factor( + n, + swing, + traction, + speed, + speed_efficiency, + jitter_tolerance, + ) + + # update pos + if adjust_sizes: + swinging = mass * np.linalg.norm(update, axis=-1) + factor = 0.1 * speed / (1 + np.sqrt(speed * swinging)) + df = np.linalg.norm(update, axis=-1) + factor = np.minimum(factor * df, 10.0 * np.ones(df.shape)) / df + else: + swinging = mass * np.linalg.norm(update, axis=-1) + factor = speed / (1 + np.sqrt(speed * swinging)) + + pos_arr += update * factor[:, None] + if abs((update * factor[:, None]).sum()) < 1e-10: + break + + return dict(zip(G, pos_arr)) + + +def rescale_layout(pos, scale=1): + """Returns scaled position array to (-scale, scale) in all axes. + + The function acts on NumPy arrays which hold position information. + Each position is one row of the array. The dimension of the space + equals the number of columns. Each coordinate in one column. + + To rescale, the mean (center) is subtracted from each axis separately. + Then all values are scaled so that the largest magnitude value + from all axes equals `scale` (thus, the aspect ratio is preserved). + The resulting NumPy Array is returned (order of rows unchanged). + + Parameters + ---------- + pos : numpy array + positions to be scaled. Each row is a position. + + scale : number (default: 1) + The size of the resulting extent in all directions. + + Returns + ------- + pos : numpy array + scaled positions. Each row is a position. + + See Also + -------- + rescale_layout_dict + """ + import numpy as np + + # Find max length over all dimensions + pos -= pos.mean(axis=0) + lim = np.abs(pos).max() # max coordinate for all axes + # rescale to (-scale, scale) in all directions, preserves aspect + if lim > 0: + pos *= scale / lim + return pos + + +def rescale_layout_dict(pos, scale=1): + """Return a dictionary of scaled positions keyed by node + + Parameters + ---------- + pos : A dictionary of positions keyed by node + + scale : number (default: 1) + The size of the resulting extent in all directions. + + Returns + ------- + pos : A dictionary of positions keyed by node + + Examples + -------- + >>> import numpy as np + >>> pos = {0: np.array((0, 0)), 1: np.array((1, 1)), 2: np.array((0.5, 0.5))} + >>> nx.rescale_layout_dict(pos) + {0: array([-1., -1.]), 1: array([1., 1.]), 2: array([0., 0.])} + + >>> pos = {0: np.array((0, 0)), 1: np.array((-1, 1)), 2: np.array((-0.5, 0.5))} + >>> nx.rescale_layout_dict(pos, scale=2) + {0: array([ 2., -2.]), 1: array([-2., 2.]), 2: array([0., 0.])} + + See Also + -------- + rescale_layout + """ + import numpy as np + + if not pos: # empty_graph + return {} + pos_v = np.array(list(pos.values())) + pos_v = rescale_layout(pos_v, scale=scale) + return dict(zip(pos, pos_v)) + + +def bfs_layout(G, start, *, align="vertical", scale=1, center=None): + """Position nodes according to breadth-first search algorithm. + + Parameters + ---------- + G : NetworkX graph + A position will be assigned to every node in G. + + start : node in `G` + Starting node for bfs + + center : array-like or None + Coordinate pair around which to center the layout. + + Returns + ------- + pos : dict + A dictionary of positions keyed by node. + + Examples + -------- + >>> G = nx.path_graph(4) + >>> pos = nx.bfs_layout(G, 0) + + Notes + ----- + This algorithm currently only works in two dimensions and does not + try to minimize edge crossings. + + """ + G, center = _process_params(G, center, 2) + + # Compute layers with BFS + layers = dict(enumerate(nx.bfs_layers(G, start))) + + if len(G) != sum(len(nodes) for nodes in layers.values()): + raise nx.NetworkXError( + "bfs_layout didn't include all nodes. Perhaps use input graph:\n" + " G.subgraph(nx.node_connected_component(G, start))" + ) + + # Compute node positions with multipartite_layout + return multipartite_layout( + G, subset_key=layers, align=align, scale=scale, center=center + ) |