two version of R2R are hereHEADmaster

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
+    )